对$\boldsymbol{x} = ({x_1},{x_2}, \cdots ,{x_n}) \in{\mathbb{R}^n}$，及$1 \leqslant {i_1} \leqslant {i_2} \leqslant n$，定义$\operatorname{Parse} (\boldsymbol{x},{i_1},{i_2}) = {\text{(}}{x_{{i_1}}},{x_{{i_1} + 1}}, \cdots ,{x_{{i_2}}}{\text{)}}$。

本文方案用到的参数如表 1所示：$\lambda $为安全参数，群容量${N_{gs}} = {2^l} \in {\text{poly}}(\lambda )$。

本文方案的安全性依赖于SIS和LWE假设。

引理1^[8]    对于实数m，$\beta = {\text{poly}}(n)$，$q \geqslant \beta \cdot $ $\omega (\sqrt {n\log n} )$，${\operatorname{SIS} _{n,m,q,\beta }}$问题描述如下：给定矩阵$\boldsymbol{A}$ ${ \leftarrow _R}\mathbb{Z}_q^{n \times m}$，寻找向量$\boldsymbol{x} \in \mathit{\Lambda } _q^ \bot (\boldsymbol{A})$，使得$0 < \left\| \boldsymbol{x} \right\| \leqslant \beta $。求解${\operatorname{SIS} _{n,m,q,\beta }}$问题的困难性至少等价于求解${\operatorname{SIVP} _\gamma }$问题，其中$\gamma = \beta \cdot \widetilde {\mathcal{O}}(\sqrt n )$。

引理2^{[11, 12]}    给定$n,m \geqslant 1$，$q \geqslant 2$，以及$\mathbb{Z}$上的一个概率分布$\chi $。对于$\boldsymbol{s} \in \mathbb{Z}_q^n$，通过采样向量$\boldsymbol{a}{ \leftarrow _R}\mathbb{Z}_q^n$和误差$e \leftarrow \chi $，获得分布${\boldsymbol{A}_{\boldsymbol{s},\chi }}$，同时输出$(\boldsymbol{a},{\boldsymbol{a}^{\bf{T}}}\boldsymbol{s} + e)$$ \in \mathbb{Z}_q^n \times \mathbb{Z}_q$。区分取自分布${\boldsymbol{A}_{\boldsymbol{s},\chi }}$的$m$个样本和取自${\mathbb{Z}}_q^n \times \mathbb{Z}_q$上的均匀分布的$m$个样本就是${\operatorname{LWE} _{n,q,\chi }}$问题。对于某一$\gamma = \widetilde {\mathcal{O}}(nq/\beta )$和$\beta $界的分布$\chi $，以及素数q，其中$\beta \geqslant \sqrt n \omega (\log q)$，求解${\operatorname{LWE} _{n,q,\chi }}$问题等价于求解${\operatorname{SIVP} _\gamma }$问题。

引理3^[13]    对实数$\delta > 0$，安全参数$n$，奇素数$q = {\text{poly}}(n)$，及整数$m = \mathcal{O}{\text{(}}n\log q{\text{)}}$，存在一个PPT算法TrapGen，输出$(\boldsymbol{A},{\boldsymbol{T}_\boldsymbol{A}})$，其中${\boldsymbol{T}_\boldsymbol{A}} \subset \mathit{\boldsymbol{ \boldsymbol{\varLambda} }} _q^ \bot (\boldsymbol{A})$，使得$\boldsymbol{A} \sim U(\mathbb{Z}_q^{n \times m})$(要求满足统计距离不大于${2^{ - \mathit{\Omega } (n)}}$)，$\left\| {{\boldsymbol{T}_\boldsymbol{A}}} \right\|$$ \leqslant \mathcal{O}(n\log q)$，且$\left\| {{\boldsymbol{{\widetilde T}}_\boldsymbol{A}}} \right\| \leqslant \mathcal{O}(\sqrt {n\log q} ) = $$\mathcal{O}(\sqrt m )$。进一步，对任意$\boldsymbol{u} \in \mathbb{Z}_q^n$和$\sigma = \mathcal{O}(\sqrt {n\log q} )$，存在一个PPT算法SampleD(${\boldsymbol{T}_\boldsymbol{A}},\boldsymbol{A},\boldsymbol{u},\sigma $)，依分布${D_{{\mathbb{Z}^m},\sigma }}$采样一个向量$\boldsymbol{x} \in \mathbb{Z}^m$，满足$\boldsymbol{A} \cdot \boldsymbol{x} = \boldsymbol{u}$mod q。

引理4^[14]    存在一个PPT算法ExtRndBasis，输入$\boldsymbol{A}' = [\boldsymbol{A}{\text{|}}\boldsymbol{B}] \in \mathbb{Z}_q^{n \times (m + k)}$，格$\mathit{\boldsymbol{ \boldsymbol{\varLambda} }} _q^ \bot (\boldsymbol{A})$的基${\boldsymbol{T}_\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m}$，以及实数$\sigma \geqslant \left\| {{\boldsymbol{{\widetilde T}}_\boldsymbol{A}}} \right\| \cdot \omega (\sqrt {\log m} )$，输出格$\mathit{\boldsymbol{ \boldsymbol{\varLambda} }} _q^ \bot (\boldsymbol{A}')$的基${\boldsymbol{T}_{\boldsymbol{A}'}}$，满足$\left\| {{\boldsymbol{T}_{\boldsymbol{A}'}}} \right\| \leqslant s(m + m')$，且$\left\| {{\boldsymbol{{\widetilde T}}_{\boldsymbol{A}'}}} \right\| \leqslant s\sqrt {m + m'} $。

引理5^[15]令$m > n$，$\sigma > \left\| {{\boldsymbol{{\tilde T}}_\boldsymbol{A}}} \right\| \cdot \sqrt m \cdot \omega (\log m)$，$q > 2$，存在PPT算法SampleRight ($\boldsymbol{A},\boldsymbol{B},\boldsymbol{R},{\boldsymbol{T}_\boldsymbol{B}},\boldsymbol{u},\sigma $)，该算法输入矩阵$\boldsymbol{A},\boldsymbol{B} \in \mathbb{Z}_q^{n \times m}$，其中B为列满秩矩阵；随机矩阵$\boldsymbol{R} \in {\{ - 1,1\} ^{m \times m}}$，格$\mathit{\Lambda} _q^ \bot (\boldsymbol{B})$的一个短基${\boldsymbol{T}_\boldsymbol{B}}$以及向量$\boldsymbol{u} \in \mathbb{Z}_q^n$。记$\boldsymbol{F} = (\boldsymbol{A}|\boldsymbol{AR}{\text{ + }}\boldsymbol{B})$，输出向量$\boldsymbol{e} \in \mathbb{Z}^{2m}$，且$\boldsymbol{e}$~${D_{\mathit{\boldsymbol{ \boldsymbol{\varLambda} }} _q^\boldsymbol{u}({\boldsymbol{F}}),\sigma }}$。

首先，定义一些集合：

${\boldsymbol{B}_{2i}}$：${\boldsymbol{B}_{2i}} \in {\{ 0,1\} ^{2i}}$，恰有i个分量为1。

${\boldsymbol{B}_{3i}}$：${\boldsymbol{B}_{3i}} \in {\{ - 1,0,1\} ^{3i}}$，对$j \in \{ - 1,0,1\} $，恰好有i个分量等于j。

${\beta _j}$：${\beta _j} = \left\lfloor {\beta + {2^{j + 1}}/{2^j}} \right\rfloor $，$\forall j \in [1,{\delta _\beta }]$。则$\sum\limits_{j = 1}^{{\delta _\beta }} {{\beta _j}} {\text{ = }}$ $\beta $。$\forall w \in [ - \beta ,\beta ]$，$\exists {w^{(1)}}$, ${w^{(2)}}$, $ \cdots $, ${w^{({\delta _\beta })}}$ $ \in \{ - 1,0,1\} $，使得$\sum\limits_{j = 1}^{{\delta _\beta }} {{\delta _j} \cdot {w^{(j)}}} = w$。

$\mathcal{S}$：所有置换$\pi $的集合。同时，记${T_\pi }$为置换函数。

对于$\boldsymbol{w} \in {\{ 0,1\} ^m}$，有：

引理6^[16]    存在一个PPT算法EleDE，当输入$\boldsymbol{w} \in {\{ 0,1\} ^m}$时，输出为${\boldsymbol{w}^*} \in {\boldsymbol{B}_{2m}}$。对于任意置换$\pi $$ \in $$\mathcal{S}$，有${\boldsymbol{w}^*} \in {\boldsymbol{B}_{2m}} \Leftrightarrow \pi ({\boldsymbol{w}^*}) \in {\boldsymbol{B}_{2m}}$。

对于$\boldsymbol{w} \in {[ - \beta ,\beta ]^m}$，有：

引理7^[16]    存在一个PPT算法VecDE，当输入$\boldsymbol{w} \in {[ - \beta ,\beta ]^m}$时，输出${\boldsymbol{w}^*} \in {\boldsymbol{B}_{3m{\delta _\beta }}}$。对任意置换$\pi \in \mathcal{S}$，有${\boldsymbol{w}^*} \in {\boldsymbol{B}_{3m{\delta _\beta }}} \Leftrightarrow \pi ({\boldsymbol{w}^*}) \in {\boldsymbol{B}_{3m{\delta _\beta }}}$。

本文要构造一个协议，使验证者相信：

1) 签名者正确执行了签名算法：签名是用签名者私钥和公开信息正确运算所得。

2) 签名者的撤销标签隐藏于LWE函数：验证者可以验证签名者身份未被撤销。

Stern型协议：正整数$D,L,q \geqslant 2$，VALID为${\{ - 1,0,1\} ^L}$的子集。任取置换$\pi \in \mathcal{S}$，对应置换函数${T_\pi }$，满足以下关系：

目标是要构造一个满足下面关系的统计零知识证明：

具体协议如下：

1) Commitment：选取随机数${\rho _1},{\rho _2},{\rho _3}$，置换$\pi { \leftarrow _R}\mathcal{S}$，以及向量${\boldsymbol{r}_1}{ \leftarrow _R}\mathbb{Z}_q^{3(n + 14m){\delta _\beta }}$和${\boldsymbol{r}_2}{ \leftarrow _R}$ ${[ - B,B]^{2m}}$。令${\boldsymbol{r}_{1,0}} = $ $Parse({r_1},9m + 1,11m)$，发送承诺$CMT = ({C_1},{C_2},{C_3})$给验证者：

2) Challenge：验证者发送挑战${\text{Ch}}{ \leftarrow _R}\{ 1,2,3\} $给证明者。

3) Response：根据挑战${\text{Ch}}$，证明者做出以下回应：

${\text{Ch}} = 1$：${\boldsymbol{t}_x} = {T_\pi }(\boldsymbol{x})$，${\boldsymbol{t}_e} = {T_\pi }(\boldsymbol{e})$，${\boldsymbol{t}_{{r_1}}} = {T_\pi }({\boldsymbol{r}_1})$，${\boldsymbol{t}_{{r_2}}} = {T_\pi }({\boldsymbol{r}_2})$，回应为$\operatorname{RSP} = {\text{(}}{\boldsymbol{t}_x},{\boldsymbol{t}_e},{\boldsymbol{t}_{{r_1}}},{\boldsymbol{t}_{{r_2}}};{\rho _2},{\rho _3})$；

${\text{Ch}} = 2$：令${\pi _2} = \pi $，${\boldsymbol{y}_1} = \boldsymbol{x} + {\boldsymbol{r}_1}$，${\boldsymbol{y}_2} = \boldsymbol{e} + {\boldsymbol{r}_2}$，则回应为$\operatorname{RSP} = ({\pi _2},{\boldsymbol{y}_1},{\boldsymbol{y}_1};{\rho _1},{\rho _1})$；

${\text{Ch}} = 3$：令${\pi _3} = \pi $，${\boldsymbol{r}_{3,1}} = {\boldsymbol{r}_1}$，${\boldsymbol{r}_{3,2}} = {\boldsymbol{r}_2}$，则回应为$\operatorname{RSP} = ({\pi _3},{\boldsymbol{r}_{3,1}},{\boldsymbol{r}_{3,2}};{\rho _1},{\rho _2})$。

Verification：收到RSP，令${\boldsymbol{y}_{1,0}} = \operatorname{Parse} ({\boldsymbol{y}_1},$ $9m + 1,11m)$，${\boldsymbol{r}_{3,0}} = \operatorname{Parse} ({\boldsymbol{r}_{3,1}},m + 1,2m)$，验证如下：

${\text{Ch}} = 1$：验证${\boldsymbol{t}_x} \in {\rm{VALID}}$，${C_2} = {\rm{COM}}({\mathit{\boldsymbol{t}}_{{r_1}}},{\mathit{\boldsymbol{t}}_{{r_2}}},{\rho _1},{\rho _2})$，${C_3} = \operatorname{COM} ({\boldsymbol{t}_x} + {\boldsymbol{t}_{{r_1}}},{\boldsymbol{t}_e} + {\boldsymbol{t}_{{r_2}}};{\rho _3})$；

${\text{Ch}} = 2$：验证${C_1} = \operatorname{COM} ({\pi _2},\boldsymbol{P} \cdot {\boldsymbol{y}_1} - \boldsymbol{v},\boldsymbol{G} \cdot {\boldsymbol{A}_1} \cdot $ ${\boldsymbol{y}_{1,0}} + {\boldsymbol{y}_2} - \boldsymbol{b};{\rho _1})$，${C_3} = \operatorname{COM} ({T_{{\pi _2}}}({\boldsymbol{y}_1}),{T_\pi }({\boldsymbol{y}_2});{\rho _3})$;

${\text{Ch}} = 3$：验证${C_1} = \operatorname{COM} ({\pi _3},\boldsymbol{P} \cdot {\boldsymbol{r}_{3,1}},\boldsymbol{G} \cdot {\boldsymbol{A}_1} \cdot {\boldsymbol{r}_{3,0}} + $ ${\boldsymbol{r}_{3,2}};{\rho _1})$，${C_2} = \operatorname{COM} ({T_{{\pi _3}}}({\boldsymbol{r}_{3,1}}),{T_{{\pi _3}}}({\boldsymbol{r}_{3,2}});{\rho _2})$。

如果每种情况下的验证都通过，输出Valid。

该协议调用COM承诺方案^[17]，满足：

引理8^[17]     上述协议是关于$\boldsymbol{P} \cdot \boldsymbol{x} = \boldsymbol{v}\,\bmod \,q$的零知识证明协议，具有完美的完整性，2/3的合理性误差，$\widetilde {\mathcal{O}}(L\log q)$的通信开销。且：

1) 存在一个有效的模拟器，在输入$(\boldsymbol{P},\boldsymbol{v})$时，输出一个可接受的副本，该副本统计上接近于实际证明者所产生的副本。

2) 存在一个有效的知识提取器，在输入承诺CMT和分别对应值$Ch = \{ 1,2,3\} $的有效$({\operatorname{RSP} _1},RS{P_2},{\operatorname{RSP} _3})$时，输出向量$\boldsymbol{x}' \in \operatorname{VALID} $，满足$\boldsymbol{P} \cdot \boldsymbol{x}' = \boldsymbol{v}\,\bmod \,q$。

一个动态群签名方案应该有3个参与方^[18]：群管理员$\mathcal{G}\mathcal{M}$、打开权威$\mathcal{O}\mathcal{A}$以及用户集合$\mathcal{U}$。具体描述如下：

定义1(动态群签名)    一个动态群签名方案由下面几个算法组成：

Setup(${1^\lambda },{1^{{N_{gs}}}}$)：该算法由可信第三方完成。输入安全参数$\lambda $和群最大容纳量${N_{gs}} \in \mathbb{N}$，输出公钥$\mathcal{Y}$，$\mathcal{G}\mathcal{M}$的私钥${\mathcal{S}_{\mathcal{G}\mathcal{M}}}$以及$\mathcal{O}\mathcal{A}$的打开钥${\mathcal{S}_{\mathcal{O}\mathcal{A}}}$，同时，初始化数据库状态$\operatorname{St} $。$\operatorname{St} $由三部分组成——当前群成员数据集合${\text{S}}{{\text{t}}_{{\text{users}}}}$、群用户信息数据库${\text{S}}{{\text{t}}_{{\text{trans}}}} = $ $\mathop \cup \limits_i < i,\text{transcript}_i > $，及撤销用户集合${\text{RL}}$。其初始化状态分别为${\text{S}}{{\text{t}}_{{\text{users}}}}{\text{ = }}\emptyset $，${\rm{S}}{{\rm{t}}_{{\rm{trans}}}}{\rm{ = \epsilon}}$，RL=$\emptyset $。

Join($\mathcal{Y},{\text{St}},{\mathcal{S}_{\mathcal{G}\mathcal{M}}}$)：该算法由$\mathcal{G}\mathcal{M}$和${\mathcal{U}_i}$交互完成。它包含两个交互图灵机${\boldsymbol{J}_{{\text{user}}}}$和${\boldsymbol{J}_{\mathcal{G}\mathcal{M}}}$，其输入均为$\mathcal{Y}$。定义该协议为[${\boldsymbol{J}_{{\text{user}}}}(\lambda ,\mathcal{Y})$, ${\boldsymbol{J}_{\mathcal{G}\mathcal{M}}}(\lambda ,St,\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}})$]。正确执行协议后，${\mathcal{U}_i}$将获得私钥${\text{se}}{{\text{c}}_i}$和群身份证书${\text{cer}}{{\text{t}}_i}$，同时，$\mathcal{G}\mathcal{M}$更新数据库$St$:${\text{S}}{{\text{t}}_{{\text{users}}}}: = {\text{S}}{{\text{t}}_{{\text{users}}}} \cup \{ i\} $，${\text{S}}{{\text{t}}_{{\text{trans}}}}: = $${\text{S}}{{\text{t}}_{{\text{trans}}}}\parallel < i,\text{transcript}_i > $。

Revoke($\mathcal{G}\mathcal{M},{\mathcal{U}_i}$)：该算法由群管理员或用户访问执行。如果要更新撤销列表${\text{RL}}$，首先验证其身份，验证通过，更新撤销链表为${\text{RL}} = {\text{RL}} \cup {\text{grt}}[i]$，同时，更新群成员数据库${\bf{St}}_{{\text{users}}}$$ = {\bf{St}}_{{\text{users}}}/i$；验证不通过，输出$ \bot $(其中$ \bot $表示失败，终止协议)。

Sign($\mathcal{Y},{\text{cer}}{{\text{t}}_i},{\text{se}}{{\text{c}}_i},M$)：输入消息M，公钥$\mathcal{Y}$，群成员证书${\text{cer}}{{\text{t}}_i}$，以及群私钥${\text{se}}{{\text{c}}_i}$，输出签名$\mathit{\Sigma } $。

Verify($\mathcal{Y},\mathit{\Sigma } $)：输入群签名$\mathit{\Sigma } $，消息M，和群公钥$\mathcal{Y}$，该算法返回1或0。

Open($\mathcal{Y},{\mathcal{S}_{\mathcal{O}\mathcal{A}}},M,\mathit{\Sigma } $)：打开权威运行该算法。输入消息M，公钥$\mathcal{Y}$，签名$\mathit{\Sigma } $，及打开钥${\text{ }}{\mathcal{S}_{\mathcal{O}\mathcal{A}}}$，输出身份$i \in {\text{S}}{{\text{t}}_{{\text{users}}}} \cup \bot $(其中$ \bot $表示打开失败)。

对群签名方案的最基本要求是：一个由合法群成员通过诚实计算产生的签名一定能通过验证，且打开权威一定能成功进行追踪(正确性)。即，对于任意${\text{(}}\mathcal{Y}{\text{, }}{\mathcal{S}_{\mathcal{O}\mathcal{A}}},{\text{sec}})$，消息M，$i \in [{N_{gs}}]$，如果$\mathit{\Sigma } \leftarrow {\rm{Sign}}$ $(\mathcal{Y},{\text{cer}}{{\text{t}}_i},{\text{se}}{{\text{c}}_i},M)$，那么

${\rm{Verify}}(\mathit{\Sigma } ,M,\mathcal{Y}) = 1$且${\rm{Open}}(\mathcal{Y},M,\mathit{\Sigma } ) = i$。

另外，群签名方案还需要满足两个安全性要求：匿名性和可追踪性。下面用游戏的方式，给出这两个性质的具体说明。

1) 匿名性：在匿名性游戏中，敌手的目标是判定两个用户中的哪一个是真正产生签名的签名者。具体的游戏过程如下：

① Setup：挑战者运行算法${\rm{Setup}}({1^\lambda },{1^{{N_{gs}}}})$以产生$({\rm{St}},\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}},{\mathcal{S}_{\mathcal{O}\mathcal{A}}})$，然后把$\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}}$发送给敌手$\mathcal{A}$。

② 查询：敌手$\mathcal{A}$可以做以下的查询：

签名查询：敌手$\mathcal{A}$可以查询签名预言机，得到任意消息$M \in {\{ 0,1\} ^*}$任意用户的签名。

腐败：$\mathcal{A}$可以查询任意用户的私钥，挑战者将被询问过的用户加入腐败集合${U_a}$。

撤销：$\mathcal{A}$查询任意用户的撤销token，挑战者将被询问过的用户加入集合${U_b}$。

③ 挑战：敌手$\mathcal{A}$选择未查询过的消息${M^*}$，并选择两个用户${d_0}$和${d_1}$，${d_i} \notin {U_a} \cup {U_b}$，其私钥证书对分别为$({\text{sec}}_0^*,{\text{cert}}_0^*)$和$({\text{sec}}_1^*,{\text{cert}}_1^*)$，发送这些给挑战者。挑战者选择$b{ \leftarrow _R}\{ 0,1\} $，并用$({\text{sec}}_b^*,{\text{cert}}_b^*)$计算挑战签名${\mathit{\Sigma } ^{\text{*}}}$，将${\mathit{\Sigma } ^{\text{*}}}$发送给敌手$\mathcal{A}$。

④ 受限查询：这一阶段，敌手$\mathcal{A}$仍能做一些查询，但不允许对用户${d_0}$和${d_1}$做腐败和撤销查询。

⑤ 输出：$\mathcal{A}$输出${b^*}$。如果${b^*} = b$，敌手获胜。

敌手的优势可定义为：

当${\rm{Adv}}_\mathcal{A}^{}$可忽略时，该群签名方案具有匿名性。

2) 可追踪性：在可追踪性游戏中，敌手的目标是伪造一个签名，利用追踪算法不能追踪到腐败集合中的用户。敌手能腐化群管理员和打开权威，也能在查询阶段腐化用户，并可利用加入算法产生一些虚拟成员。

① Setup：挑战者运行${\rm{Setup}}({1^\lambda },{1^{{N_{gs}}}})$算法产生$({\rm{St}},\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}},{\mathcal{S}_{\mathcal{O}\mathcal{A}}})$，然后发送$({\rm{St}},\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}},{\mathcal{S}_{\mathcal{O}\mathcal{A}}})$给敌手$\mathcal{A}$，并设置${U_a} = \emptyset $。

② 查询：该阶段，敌手$\mathcal{A}$可查询以下预言机。

签名：$\mathcal{A}$输入任意消息和用户，签名预言机返回对应签名。将所有询问过的签名添加到集合Sig中(集合Sig是由$(i,M,\mathit{\Sigma } )$组成的集合，其中i指用户身份，M是消息，$\mathit{\Sigma } $是对应的签名)。

腐败：敌手$\mathcal{A}$询问任意用户的私钥时，挑战者将该用户加入集合${U_a}$中，并返回其私钥。

③ 伪造：敌手$\mathcal{A}$利用其所拥有的信息产生一个消息签名对$({M^{\text{*}}},{\mathit{\Sigma } ^{\text{*}}})$和撤销链表${\text{R}}{{\text{L}}^*}$，使其满足：

Ⅰ Verify$({\text{R}}{{\text{L}}^*},{\mathit{\Sigma } ^*},{M^*},\mathcal{Y}) = 1$；

Ⅱ 打开失败，或$i = {\rm{Open}}({M^*},{\mathit{\Sigma } ^*},{\mathcal{S}_{\mathcal{O}\mathcal{A}}},\mathcal{Y},St')$，且$i \in {U_a}/{\text{R}}{{\text{L}}^{\text{*}}}$；

Ⅲ ${\rm{Sigs}}$表示用户$i$曾产生的签名，${\mathit{\Sigma } ^*} \notin {\rm{Sigs}}$；

则敌手赢得该游戏，返回1；否则，返回0。

当敌手的优势可忽略时，称该群签名方案具有可追踪性。

Setup(${1^\lambda }$, ${1^{{N_{gs}}}}$)：给定群安全参数$\lambda $以及群最大容量${N_{gs}}$，参数$n,q,m,\sigma ,\beta ,B$。$\chi $为$B$界的分布。对于$t = \omega (\log n)$，随机预言机$H$:${\{ 0,1\} ^*} \to {\{ 1,2,3\} ^t}$，${H_0}$:${\{ 0,1\} ^*} \to \mathbb{Z}_q^{n \times 2m}$。依次运行以下步骤：

1) 运行算法获得$({\boldsymbol{A}_1},{\boldsymbol{T}_{{\boldsymbol{A}_1}}}) \leftarrow {\rm{TrapGen}}({1^n},{1^m},q)$，其中${\boldsymbol{A}_1} \in \mathbb{Z}_q^{n \times m}$，${\boldsymbol{T}_{{\boldsymbol{A}_1}}}$为格$\mathit{\Lambda } _q^ \bot ({\boldsymbol{A}_1})$的一个短基；

2) ${\boldsymbol{A}_{2,1}},{\boldsymbol{A}_{2,2}},\boldsymbol{D}{ \leftarrow _R}\mathbb{Z}_q^{n \times m}$，${\boldsymbol{D}_0},{\boldsymbol{D}_1}{ \leftarrow _R}\mathbb{Z}_q^{2n \times 2m}$，$\boldsymbol{u}{ \leftarrow _R}\mathbb{Z}_q^n$；

3) $\boldsymbol{F}{ \leftarrow _R}\mathbb{Z}_q^{4n \times 4m}$，该矩阵将被用来确保能抵抗指定攻击；

4) 生成满足GPV-IBE方案的公私钥对$(\boldsymbol{B},{\boldsymbol{T}_\boldsymbol{B}})$，其中$\boldsymbol{B} \in \mathbb{Z}_q^{n \times m}$，${\boldsymbol{T}_\boldsymbol{B}}$为格$\mathit{\Lambda } _q^ \bot (\boldsymbol{B})$的一个短基；

5) 选取具备强不可伪造性的一次签名方案${\Pi ^{{\rm{OTS}}}} = (\mathcal{G},{\mathcal{S}_{{\rm{sig}}}},{\mathcal{V}_{{\rm{ver}}}})$。

则群公钥为：

群管理员$\mathcal{G}\mathcal{M}$的私钥为${\mathcal{S}_{\mathcal{G}\mathcal{M}}} = {\boldsymbol{T}_{{\boldsymbol{A}_1}}}$；打开权威$\mathcal{O}\mathcal{A}$的密钥为${\mathcal{S}_{\mathcal{O}\mathcal{A}}} = {\boldsymbol{T}_\boldsymbol{B}}$。

设置初始的撤销列表为${\text{RL}} = \emptyset $，群成员集合为${\text{S}}{{\text{t}}_{{\text{users}}}} = \emptyset $，用户信息库为${\rm{S}}{{\rm{t}}_{{\rm{trans}}}}{\rm{ = \epsilon}}$。其中，${\text{S}}{{\text{t}}_{{\text{trans}}}}$仅允许$\mathcal{G}\mathcal{M}$和$\mathcal{O}\mathcal{A}$访问；${\text{S}}{{\text{t}}_{{\text{users}}}}$允许任何人访问，但仅允许$\mathcal{G}\mathcal{M}$做写入操作；任何人都可访问${\text{RL}}$，仅允许撤销图灵机进行写入操作。

Join($\mathcal{Y},{\text{St}},{\mathcal{S}_{\mathcal{G}\mathcal{M}}}$)：

1) ${\mathcal{U}_i}$

选取${\boldsymbol{z}_i}{ \leftarrow _R}{D_{{\mathbb{Z}^{4m}},\sigma }}$，及${\boldsymbol{s}_{i,2}}{ \leftarrow _R}{D_{{\mathbb{Z}^m},\sigma }}$，并计算${\boldsymbol{v}_i} = $ $\boldsymbol{F} \cdot {\boldsymbol{z}_i}\bmod q$$ \in \mathbb{Z}_q^{4n}$；利用PKI系统中常用密钥签名${\text{si}}{{\text{g}}_i} = {\operatorname{Sign} _{{\boldsymbol{usk}}[i]}}({\boldsymbol{v}_i})$。发送${\boldsymbol{v}_i}$, ${{\boldsymbol{s}}_{i,{\text{2}}}}$，及签名${\text{si}}{{\text{g}}_i}$到$\mathcal{G}\mathcal{M}$；

2) $\mathcal{G}\mathcal{M}$

验证${\boldsymbol{v}_i}$被注册与否，并验证签名${\text{si}}{{\text{g}}_i}$的正确性。如果被注册过或签名不正确，终止协议；否则，$\mathcal{G}\mathcal{M}$要做以下工作：

① 选取新身份$i(0 < i \leqslant {N_{gs}})$，定义

计算${\boldsymbol{u}_i} = ({\boldsymbol{A}_{2,1}} + i{\boldsymbol{A}_{2,2}}) \cdot {\boldsymbol{s}_{i,2}}$；

② 运行${\boldsymbol{T}_i} \leftarrow {\rm{ExtRndBasis}}({\boldsymbol{{\overline A}} _i},{\boldsymbol{T}_{{\boldsymbol{A}_1}}})$，${\boldsymbol{T}_i} \in {\mathbb{Z}^{2m \times 2m}}$和${\boldsymbol{s}_{i,1}} \leftarrow {\rm{SampleD}}({\boldsymbol{A}_1},{\boldsymbol{T}_{{A_1}}},\boldsymbol{u} - {\boldsymbol{u}_i},\sigma )$；

③ 定义${\boldsymbol{s}_i} = ({\boldsymbol{s}_{i,1}},{\boldsymbol{s}_{i,2}}) \in \mathbb{Z}_q^{2m}$，计算其变色龙哈希函数${\boldsymbol{c}_s} = {\boldsymbol{D}_0} \cdot {\text{bin}}({v_i}) + {\boldsymbol{D}_1} \cdot {\boldsymbol{s}_i}$；

④ 定义${\boldsymbol{u}_s} = \boldsymbol{u} + \boldsymbol{D} \cdot {\text{bin}}({\boldsymbol{c}_s})$，采样获得${\boldsymbol{d}_i} \leftarrow $ ${\rm{SampleD}}({\boldsymbol{T}_i},{\boldsymbol{{\bar A}}_i},{\boldsymbol{u}_s},\sigma )$；

⑤ 发送$(i,{\boldsymbol{d}_i},{\boldsymbol{s}_i})$给用户${\mathcal{U}_i}$；

⑥ 定义用户${\mathcal{U}_i}$的撤销标签

令${\text{S}}{{\text{t}}_{{\text{users}}}}: = {\text{S}}{{\text{t}}_{{\text{users}}}} \cup \{ i\} $，将副本信息${\text{transcrip}}{{\text{t}}_i} = $ $({v_i},{\text{cer}}{{\text{t}}_i},{\text{upk}}[i]$, ${\text{si}}{{\text{g}}_i},{\bf{grt}}[i])$存储到${\text{S}}{{\text{t}}_{{\text{trans}}}}$中。

3) ${\mathcal{U}_i}$

验证接收信息是否满足：${\boldsymbol{{\bar A}}_i} \cdot {\boldsymbol{d}_i} = \boldsymbol{u} + \boldsymbol{D} \cdot $ ${\text{bin}}({\boldsymbol{D}_0} \cdot {\text{bin}}({\boldsymbol{v}_i}) + {\boldsymbol{D}_1} \cdot {\boldsymbol{s}_i})\bmod q$，$\parallel {\boldsymbol{d}_i}{\parallel _\infty } \leqslant \beta $，以及$\parallel {\boldsymbol{s}_i}{\parallel _\infty } \leqslant \beta $。如果不满足，终止协议；满足，则定义其成员身份证书为${\text{cer}}{{\text{t}}_i} = (i,{\boldsymbol{d}_i},{\boldsymbol{s}_i})$，私钥为${\text{se}}{{\text{c}}_i} = {\boldsymbol{z}_i}$。

Revoke($\mathcal{G}\mathcal{M},{\mathcal{U}_i}$)：

撤销算法相当于一个可信第三方$\mathcal{W}$，可根据访问者身份不同分两种情况——群管理员访问算法和群成员访问算法。要撤销群成员${\mathcal{U}_i}$的合法群身份，具体过程如下。

1) $\mathcal{G}\mathcal{M}$访问时

直接发送${\bf{grt}}[i]$到撤销第三方$\mathcal{W}$。假设$\mathcal{W}$能分辨管理员身份(如果不能，$\mathcal{G}\mathcal{M}$与$\mathcal{W}$交互通信来验证$\mathcal{G}\mathcal{M}$身份)，更新撤销列表${\text{RL}}: = {\text{RL}} \cup \{ {\bf{grt}}[i]\} $。

2) ${\mathcal{U}_i}$访问时

发送证书${\text{cer}}{{\text{t}}_i}$和$({\boldsymbol{v}_i},{\text{si}}{{\text{g}}_i})$到撤销第三方$\mathcal{W}$。$\mathcal{W}$接到${\mathcal{U}_i}$的请求后，将收到信息转发给$\mathcal{G}\mathcal{M}$，由$\mathcal{G}\mathcal{M}$验证其信息正确性。验证通过，将${\bf{grt}}[i]$返回给$\mathcal{W}$，$\mathcal{W}$更新撤销列表${\text{RL}}: = {\text{RL}} \cup \{ {\bf{grt}}[i]\} $。

撤销完成后，$\mathcal{G}\mathcal{M}$更新${\text{S}}{{\text{t}}_{{\text{users}}}}: = {\text{S}}{{\text{t}}_{{\text{users}}}}/\{ i\} $。

Sign($\mathcal{Y},{\text{cer}}{{\text{t}}_i},{\text{se}}{{\text{c}}_i},M$)：

对于消息$M \in {\{ 0,1\} ^*}$，群成员${\mathcal{U}_i}$要对其做群签名，具体操作如下。

1) 选取一次签名密钥对$({\text{svk}},{\text{ssk}}) \leftarrow \mathcal{G}(n)$，并记${\mathit{\boldsymbol{d}}_i} = [{\mathit{\boldsymbol{d}}_{i,1}}/{\mathit{\boldsymbol{d}}_{i,2}}] \in {\mathbb{Z}^{2m}}$；

2) 令$\boldsymbol{G} = {H_0}({\text{svk}}) \in \mathbb{Z}_q^{n \times 2m}$，选取$\boldsymbol{e}{ \leftarrow _R}{\chi ^{2m}}$，${\boldsymbol{e}_0}{ \leftarrow _R}{\chi ^n}$，${\boldsymbol{x}_1}{ \leftarrow _R}{\chi ^m}$，${\boldsymbol{x}_2}{ \leftarrow _R}{\chi ^{2m}}$，得：

3) 产生一个零知识证明(简记为ZKAoK)协议(具体见下节)。该协议可以用来证明：①签名者是拥有合法群身份的成员；② $\boldsymbol{b}$是诚实计算所得。并行执行$t = \omega (\log n)$次该协议，使得合理性误差足够小。然后利用Fiat-Shamir启发式将其转化为非交互ZKAoK协议：

4) 定义${\mathit{\Sigma } _1} = (\boldsymbol{b},{\boldsymbol{c}_1},{\boldsymbol{c}_2},\tau )$，计算${\mathit{\Sigma } _2} = {\mathcal{S}_{{\text{sig}}}}({\text{ssk}},{\mathit{\Sigma } _1})$；

5) 输出群签名

Verify($Y,M,\mathit{\Sigma } $)：

按式(12)分解签名$\mathit{\Sigma } $，依次执行下列步骤：

1) 计算$\boldsymbol{G} = {H_0}({\text{svk}})$；

2) 验证${\mathcal{V}_{{\text{ver}}}}(M,{\text{svk}},{\text{RL}},{\boldsymbol{c}_1},{\boldsymbol{c}_2},\boldsymbol{b},\tau ,{{{\Sigma }}_2}) = 1$，如果通过，执行下一步；

3) 验证ZKAoK协议$\tau $是否成立，若成立，则进入下一步；

4) 遍历撤销列表${\text{RL}}$，$\forall {\bf{grt}}[i] \in {\text{RL}}$，计算${\boldsymbol{e}'_i} = \boldsymbol{b} - {\boldsymbol{G}^{\text{T}}} \cdot {\bf{grt}}[i]\bmod q$。验证是否存在$i$，使得$\parallel {e'_i}{\parallel _\infty } \leqslant B$。

如果中间不终止，且最后不存在$i$，则验证通过，返回1；否则，返回0。

Open($\mathcal{Y},{\mathcal{S}_{\mathcal{O}\mathcal{A}}},M,\mathit{\Sigma } $)：

打开权威$\mathcal{O}\mathcal{A}$可利用其私钥${\mathcal{S}_{\mathcal{O}\mathcal{A}}} = {\boldsymbol{T}_\boldsymbol{B}}$打开签名获得真实签名者身份，步骤如下：

1) 计算$\boldsymbol{G} = {H_0}({\text{svk}})$，运行$2m$次SampleD算法获得小范数矩阵$\boldsymbol{{E}_{{\text{svk}}}} \in {\mathbb{Z}^{m \times 2m}}$，使得其满足$\boldsymbol{B} \cdot {\boldsymbol{E}_{{\text{svk}}}} = \boldsymbol{G}\bmod q$；

2) 利用${\boldsymbol{E}_{{\text{svk}}}}$解密部分密文${\boldsymbol{c}_1}$和${\boldsymbol{c}_2}$，解密结果为${\text{bin}}(\boldsymbol{v}) = \left\lfloor {({\boldsymbol{c}_2} - \boldsymbol{E}_{{\text{svk}}}^{\text{T}} \cdot {\boldsymbol{c}_2})/(q/2)} \right\rfloor $；

3) 计算$\boldsymbol{v} = {\boldsymbol{H}_{4n \times 2m}} \cdot {\text{bin}}(\boldsymbol{v})\bmod q$，对照数据库${\text{S}}{{\text{t}}_{{\text{trans}}}}$，找出与$v$一致的用户身份$i$，输出$i$。若查找失败，输出$ \bot $。

引理9^[6]    令$B = \sqrt n \omega (\log n)$，$q \geqslant $${(4B + 1)^2}$，$m = 2n\left\lceil {\log q} \right\rceil $，那么，在$\boldsymbol{G} \in \mathbb{Z}_q^{n \times 2m}$的随机性基础上，有：

定理1(正确性)极大概率本文的方案是正确的。

证明：正确性定义见文献[7]。很容易验证，该方案满足定义中所提出条件。在此，本文只需另外证明关于向量$\boldsymbol{b}$的部分。

对每个${\bf{grt}}[j] \in $${\text{RL}}$，计算${\boldsymbol{e}'_j} = \boldsymbol{b} - {\boldsymbol{G}^{\rm{T}}} \cdot {\bf{grt}}[j] = $ ${\boldsymbol{G}^{\rm{T}}} \cdot ({\bf{grt}}[i] - {\bf{grt}}[j])$$ + e\bmod q$。如果存在指标i使得${\bf{grt}}[i] = {\bf{grt}}[j]$，这时有${\left\| {{{\boldsymbol{e}'}_i}} \right\|_\infty } = {\left\| \boldsymbol{e} \right\|_\infty } \leqslant B$，验证不通过，矛盾。如果${\bf{grt}}[i] \notin {\text{RL}}$，那么对任意i，向量$\boldsymbol{g} = {\bf{grt}}[i]$$ - {\bf{grt}}[j]$非零。由引理9知，以很大概率有${\left\| {{\boldsymbol{G}^{\rm{T}}} \cdot \boldsymbol{g}} \right\|_\infty } \leqslant 2B$。另一方面，${\left\| {{\boldsymbol{G}^{\rm{T}}} \cdot \boldsymbol{g}} \right\|_\infty } \leqslant {\left\| {{{\boldsymbol{e}'}_j}} \right\|_\infty } + {\left\| \boldsymbol{e} \right\|_\infty }$ $ \leqslant {\left\| {{{\boldsymbol{e}'}_j}} \right\|_\infty } + B$，故${\left\| {{{\boldsymbol{e}'}_j}} \right\|_\infty } \geqslant 2B - B = B$有很大概率是成立的，验证通过。

定理2(匿名性)随机预言机模型下，基于LWE$_{n,q,\chi }$假设，如果${\mathit{\Pi } ^{{\text{OTS}}}}$为强不可伪造一次签名，那么本文的方案具有匿名性。

证明：利用一系列游戏来证明匿名性。

Game$G_0^{(b)}$：

1) 运行算法${\rm{Setup}}({1^\lambda },{1^{{N_{{\text{gs}}}}}})$产生$({\rm{St}}$, $\mathcal{Y}$, ${\mathcal{S}_{\mathcal{G}\mathcal{M}}}$, ${\mathcal{S}_{\mathcal{O}\mathcal{A}}})$，然后将$\mathcal{Y},{\mathcal{S}_{\mathcal{G}\mathcal{M}}}$发送给$\mathcal{A}$。初始化撤销链表$RL$$ = $$\emptyset $，腐败集合${U_a} = \emptyset $，撤销查询集合${U_b} = \emptyset $；

2) 在查询阶段，$\mathcal{A}$不仅可以查询任意用户对任意消息M的签名，还能更新${U_a}$和${U_b}$；

3) $\mathcal{A}$输出选定消息${M^*}$和两个指标${d_0}$, ${d_1}$$ \notin $ ${U_a} \cup {U_b}$，满足${\bf{grt}}[{d_0}]$，${\bf{grt}}[{d_1}] \notin {\text{RL}}$；

4) 选择$b{ \leftarrow _R}\{ 0,1\} $，产生一个合法签名${\mathit{\Sigma } _0} = ({M^*},$${\text{sv}}{{\text{k}}^*},\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},{\pi ^*},\mathit{\Sigma } _2^*) \leftarrow \operatorname{Sign} (\mathcal{Y},{\text{cert}}_b^*,{\text{sec}}_b^*,$ ${M^*})$，返回给敌手$\mathcal{A}$；

5) $\mathcal{A}$仍能做一些查询，但不允许查询${d_0}$和${d_1}$的私钥和撤销令牌；

6) $\mathcal{A}$返回$b'$。

Game$G_1^{(b)}$：

此游戏通过修改Game${G_0}$获得：在步骤4)中，利用模拟器来模拟产生$\pi $。输出签名${\mathit{\Sigma } _1} = ({M^*},{\text{sv}}{{\text{k}}^*},$ $\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},{\pi ^*},\mathit{\Sigma } _2^*)$。

Game$G_{2,0}^{(b)}$：

此游戏在Game$G_1^{(b)}$上修改获得：选取${\boldsymbol{g}_c}{ \leftarrow _R}\mathbb{Z}_q^n$，计算$\boldsymbol{b} = {\boldsymbol{G}^{\text{T}}} \cdot {\boldsymbol{g}_c} + \boldsymbol{e}\bmod q$。输出签名${\mathit{\Sigma } _{2,0}} = ({M^*},$${\text{sv}}{{\text{k}}^*},\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,\boldsymbol{b},{\pi ^*},\mathit{\Sigma } _2^*)$。

Game$G_{2,1}^{(b)}$：

对Game${G_{2,0}}$作修改：随机选择$\boldsymbol{b}'{ \leftarrow _R}\mathbb{Z}_q^{2m}$，输出签名${\mathit{\Sigma } _{2,1}} = ({M^*}$, ${\text{sv}}{{\text{k}}^*}$, $\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,\boldsymbol{b}',{\pi ^*},\mathit{\Sigma } _2^*)$。

Game$G_{3,0}^{(b)}$：

对Game$G_{2,1}^{(b)}$作以下修改：选择${\boldsymbol{y}_1}{ \leftarrow _R}\mathbb{Z}_q^m$, ${\boldsymbol{y}_2}{ \leftarrow _R}\mathbb{Z}_q^{2m}$，计算${\boldsymbol{c}_1} = {\boldsymbol{y}_1}$；${\boldsymbol{c}_2} = {\boldsymbol{y}_2} + $${\text{bin}}(\boldsymbol{v}_{{d_b}}^*)$$ \cdot \left\lfloor {q/2} \right\rfloor \,$ $\bmod \,q$。则${\mathit{\Sigma } _{3,0}} = ({M^*}$, ${\text{sv}}{{\text{k}}^*}$, ${\boldsymbol{c}_1}$, ${\boldsymbol{c}_2}$, $\boldsymbol{b}'$, $\pi $, $\mathit{\Sigma } _2^*)$。

Game${G_{3,1}}$：

这一游戏在Game$G_{3,0}^{(b)}$基础上修改获得：随机选择${\boldsymbol{c}'_1}{ \leftarrow _R}\mathbb{Z}_q^m$，${\boldsymbol{c}'_2}{ \leftarrow _R}\mathbb{Z}_q^{2m}$。输出签名${\mathit{\Sigma } _{3,1}}$$ = ({M^*}$, ${\text{sv}}{{\text{k}}^*}$, ${\boldsymbol{c}'_1},{\boldsymbol{c}'_2}$, $\boldsymbol{b}'$, $\pi $, $\mathit{\Sigma }_2^*)$。

根据引理8和LWE假设，故有：$G_0^{(0)}\mathop \approx \limits^s $ $G_1^{(0)}\mathop \approx \limits^s G_{2,0}^{(0)}\mathop \approx \limits^c G_{2,1}^{(0)}\mathop \approx \limits^c G_{3,0}^{(0)} \approx {G_{3,1}} \approx G_{3,0}^{(1)}\mathop \approx \limits^c G_{2,1}^{(0)}\mathop \approx \limits^c G_{2,0}^{(0)}\mathop \approx \limits^s G_1^{(1)}\mathop \approx \limits^s $$G_0^{(0)}$。($\mathop \approx \limits^s $表示统计上不可区分；$\mathop \approx \limits^c $表示计算上不可区分)

而Game${G_{3,1}}$不依赖于挑战者的选择，所以匿名性得证。

定理3     (可追踪性)随机预言机模型下，在SIS假设下，本文的方案具有可追踪性。

证明：假设存在一个PPT敌手$\mathcal{A}$，能以不可忽略的概率$\varepsilon $来伪造一个签名${\mathit{\Sigma } ^*}$，为攻击方案的可追踪性，构造一个PPT算法$\mathcal{F}$，本文将证明$\mathcal{F}$利用$\mathcal{A}$能攻破SIS假设。具体来说，给算法$\mathcal{F}$一个输入$\boldsymbol{{\hat A}} \in \mathbb{Z}_q^{n \times m}$，找到一个$\boldsymbol{w} \in \mathit{\Lambda } _q^ \bot (\boldsymbol{{\hat A}})$，$0 < \left\| \boldsymbol{w} \right\| \leqslant \beta '$。

1) Setup：$\mathcal{F}$获得$({\boldsymbol{A}_{2,2}},{\boldsymbol{T}_{{\boldsymbol{A}_{2,2}}}}) \leftarrow {\text{TrapGen}}({1^n},{1^m},$ $q)$，选取${i^*} \in [{N_{gs}}]$，${\boldsymbol{s}_{{i^*},1}}{ \leftarrow _R}{D_{{\mathbb{Z}^m},\sigma }}$，${\boldsymbol{s}_{{i^*},2}}{ \leftarrow _R}{D_{{\mathbb{Z}^m},\sigma }}$。令${\boldsymbol{A}_1} = \boldsymbol{{\hat A}}$，$\boldsymbol{{A}_{2,1}} = {\boldsymbol{A}_1}\boldsymbol{R} - {i^*}{\boldsymbol{A}_{2,2}}$，${\boldsymbol{u}^*} = {\boldsymbol{A}_1}{\boldsymbol{s}_{{i^*},1}} + {\boldsymbol{A}_1}\boldsymbol{R}{\boldsymbol{s}_{{i^*},2}}$，令${\boldsymbol{u}^*} = \boldsymbol{u}$。记${\boldsymbol{s}_{{i^*}}} = ({\boldsymbol{s}_{{i^*},1}},{\boldsymbol{s}_{{i^*},2}})$，其他参数不变。设置${\text{RL}} = \emptyset $，腐败集合${U_a} = \emptyset $。

2) Join：对$i \in [{N_{gs}}]$，当$i \ne {i^*}$时，选择${\boldsymbol{z}_i}{ \leftarrow _R}{D_{{\mathbb{Z}^{4m}},\sigma }}$，${\boldsymbol{s}_{i,2}}{ \leftarrow _R}{D_{{\mathbb{Z}^m},\sigma }}$，则${\boldsymbol{v}_i} = \boldsymbol{F} \cdot {\boldsymbol{z}_i} \in \mathbb{Z}_q^{4n}$。发送${\boldsymbol{v}_i}$, ${\boldsymbol{s}_{i,{\text{2}}}}$，${\text{si}}{{\text{g}}_i} = {\text{Sig}}{{\text{n}}_{{\text{usk}}[i]}}({\boldsymbol{v}_i})$到$\mathcal{F}$。$\mathcal{F}$验证获得${{\boldsymbol{u}}_i} = [{\boldsymbol{A}_1}\boldsymbol{R}{\text{ + }}(i - $${i^*}){\boldsymbol{A}_{2,2}}] \cdot {{\boldsymbol{s}}_{i,2}}$，$({{\boldsymbol{s}}_{i,1}},{\boldsymbol{s}}_{i,2}^{'}) \leftarrow {\text{SampleRight}}$ $({\boldsymbol{A}_1},{\boldsymbol{A}_{2,2}},\boldsymbol{R},{\boldsymbol{T}_{{\boldsymbol{A}_{2,2}}}},\boldsymbol{u} - {\boldsymbol{u}_i},\sigma )$。定义${\boldsymbol{s}_i} = ({\boldsymbol{s}_{i,1}},{\boldsymbol{s}_{i,2}} + {\boldsymbol{s}'_{i,2}})$，则${\boldsymbol{{\overline A}} _i} = [\left. {{\boldsymbol{A}_1}} \right|\boldsymbol{AR} + (i - {i^*}){\boldsymbol{A}_{2,2}}]$，${\boldsymbol{{\bar A}}_i} \cdot {\boldsymbol{s}_i} = \boldsymbol{u}$。对$i \in [{N_{gs}}]$，令${\boldsymbol{c}_s} = $ ${\boldsymbol{D}_0} \cdot {\text{bin}}({\boldsymbol{v}_i}) + {\boldsymbol{D}_1} \cdot {\boldsymbol{s}_i}$，${\boldsymbol{u}_s} = \boldsymbol{u}{\text{ + }}\boldsymbol{D} \cdot {\text{bin}}({\boldsymbol{c}_s})$，$\mathcal{F}$获得${\boldsymbol{d}_i} = {\left[ {{\boldsymbol{d}_{i,1}},{\boldsymbol{d}_{i,2}}} \right]^{\text{T}}} \leftarrow {\text{SampleRight}}({\boldsymbol{A}_1},{\boldsymbol{A}_{2,2}},\boldsymbol{R},{\boldsymbol{T}_{{\boldsymbol{A}_{2,2}}}},$ ${\boldsymbol{u}_\boldsymbol{s}},\sigma )$，发送${\text{cer}}{{\text{t}}_i}$${\text{ = }}(i,{\boldsymbol{d}_i},{\boldsymbol{s}_i})$给用户$i$。${\bf{grt}}[i]$产生方式不变。

3) 查询：敌手$\mathcal{A}$做下面的查询：

① 腐败：询问任意用户$i \in \{ 1,2, \cdots ,{N_{gs}}\} $的私钥，$\mathcal{F}$将$i$加入到集合${U_a}$中，返回${{\boldsymbol{z}}_i}$。

② 签名：查询用户$i$关于消息M的签名，$\mathcal{F}$返回$\mathit{\Sigma } $，并将$(i,M,\mathit{\Sigma } )$加入到集合Sigs中。

4) 伪造：假如敌手$\mathcal{A}$能以优势$\varepsilon $成功伪造签名${\mathit{\Sigma } ^*} = ({M^*},$${\text{sv}}{{\text{k}}^*},\mathit{\Sigma } _1^*,\mathit{\Sigma } _2^*)$，则利用打开算法，可追踪到诚实用户或追踪失败。

对${\mathit{\Sigma } ^*}$，${\pi ^*} = \{ \{ {\text{CM}}{{\text{T}}^{*(k)}}\} _{k = 1}^t,{\text{C}}{{\text{H}}^*},\{ {\text{RS}}{{\text{P}}^{*(k)}}\} _{k = 1}^t\} $，$\mathcal{A}$必须调用预言机$H$(且输入为$({M^*},{\text{sv}}{{\text{k}}^*},\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},$ $\{ {\text{CM}}{{\text{T}}^{*(k)}}\} _{k = 1}^t)$)，否则，等式$H({M^*},{\text{sv}}{{\text{k}}^*},\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},$ $\{ {\text{CM}}{{\text{T}}^{*(k)}}\} _{k = 1}^t) = {\text{C}}{{\text{H}}^*}$成立的概率至多为${3^{ - t}}$。记${Q_H}$为查询$H$的上限，则$\mathcal{A}$的查询结果与第${\kappa ^*}$次查询重合概率至少为$\varepsilon ' = \varepsilon - {3^{ - t}}$，${\kappa ^*} \leqslant {Q_H}$。$\mathcal{F}$调用$32 \cdot {Q_H}/(\varepsilon $$ - {3^{ - t}})$次$\mathcal{A}$算法。这些查询中，前${\kappa ^*} - 1$查询保持输入和随机预言机不变，则挑战值${\text{C}}{{\text{H}}_1}$, ${\text{C}}{{\text{H}}_2}$, $ \cdots ,{\text{C}}{{\text{H}}_{{\kappa ^*} - 1}}$相同。但从第${\kappa ^*}$次查询开始，挑战值${\text{C}}{{\text{H}}_{{\kappa ^*}}},{\text{C}}{{\text{H}}_{{\kappa ^*} + 1}}, \cdots ,{\text{C}}{{\text{H}}_{{Q_H}}}$开始不同。改进的Forking引理^[16]保证了，对于$({M^*},{\text{sv}}{{\text{k}}^*},\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},$ $\{ {\text{CM}}{{\text{T}}^{*(k)}}\} _{k = 1}^t)$，$\mathcal{F}$能以大于1/2的概率获得${\text{CH}}_{{\kappa ^*}}^{(1)},{\text{CH}}_{{\kappa ^*}}^{(2)},{\text{CH}}_{{\kappa ^*}}^{(3)} \in {\{ 1,2,3\} ^t}$。以$1 - {(7/9)^t}$的概率，存在$j \in $ $\{ 1,2, \cdots ,t\} $，使得${\text{CH}}_{{\kappa ^*}}^{(1)},{\text{CH}}_{{\kappa ^*}}^{(2)},{\text{CH}}_{{\kappa ^*}}^{(3)}$的第$j$位是$({\text{CH}}_{{\kappa ^*}}^{(1)},{\text{CH}}_{{\kappa ^*}}^{(2)},{\text{CH}}_{{\kappa ^*}}^{(3)}) = $$(1,2,3)$。从相对应的回应$({{\text{RSP}}{_{(j)}^{*}}^{(1)}},{{\text{RSP}}{_{(j)}^{*}}^{(2)}},$${{\text{RSP}}{_{(j)}^{*}}^{(3)}})$，$\mathcal{F}$能提取${\boldsymbol{s}^*} = $ $(\boldsymbol{s}_{i,1}^*,\boldsymbol{s}_{i,2}^*) \in {\mathbb{Z}^{2m}}$，$\boldsymbol{v}' \in {\mathbb{Z}^{4m}}$，${\boldsymbol{e}^*} \in {\mathbb{Z}^n}$(引理8)。

考虑以下情况：

1) $i \ne {i^*}$，发生概率至多为$\frac{{{N_{gs}} - 1}}{{{N_{gs}}}}$。此时，$\mathcal{F}$输出“Fail”并终止；

2) $i = {i^*}$时，${\boldsymbol{A}_1}{\boldsymbol{s}_{{i^*},1}} + {\boldsymbol{A}_1}\boldsymbol{R}{\boldsymbol{s}_{{i^*},2}} = {\boldsymbol{A}_1}\boldsymbol{s}_{i,1}^* + {\boldsymbol{A}_1}\boldsymbol{R}\boldsymbol{s}_{i,2}^*$ $\bmod q$，且${\boldsymbol{A}_1}[({\boldsymbol{s}_{{i^*},1}} - \boldsymbol{s}_{_{i,1}}^*) + \boldsymbol{R}({\boldsymbol{s}_{{i^*},1}} - \boldsymbol{s}_{_{i,1}}^*)] = $$0\bmod q$。

下面证明以很大概率有$({\boldsymbol{s}_{{i^*},1}} - \boldsymbol{s}_{_{i,1}}^*){\text{ + }}\boldsymbol{R}({\boldsymbol{s}_{{i^*},1}} - $ $\boldsymbol{s}_{_{i,1}}^*) \ne 0\bmod q$。

1) 如果追踪失败，即$\mathcal{V}({M^*},{\text{svk}},{\text{grt}}[{i^*}]$，$\boldsymbol{c}_1^*,\boldsymbol{c}_2^*,{\boldsymbol{b}^*},\pi ,{\mathit{\Sigma } _2})$$ = 1$。由签名的正确性可知${\boldsymbol{A}_1} \cdot \boldsymbol{v}' = {\boldsymbol{A}_1} \cdot {\boldsymbol{v}_{{i^*}}}\, \ne {\text{grt}}[{i^*}]$，则$\boldsymbol{v}' \ne {\boldsymbol{v}_{{i^*}}}$，进而有$\boldsymbol{z}_i^* \ne {\boldsymbol{z}_{{i^*}}}$。由于$\mathcal{Y}$给定时，${\text{cert}}$与${\text{sec}}$一一对应，可知$\boldsymbol{s}_i^* \ne {s\boldsymbol{}_{{i^*}}}$。

2) 如果追踪到用户$k \notin {U_a}/{\text{RL}}$。考虑以下两种情况：

① 如果$\mathcal{A}$从未查询过${\boldsymbol{z}_{{i^*}}}$，那么${\boldsymbol{v}_{{i^*}}}$对$\mathcal{A}$来说是未知的。这时，很大概率有$\boldsymbol{v}' \ne {\boldsymbol{v}_{{i^*}}}$。

② 如果$\mathcal{A}$查询过${\boldsymbol{z}_{{i^*}}}$，那么${i^*} \in {U_a}$。此时有$k \ne {i^*}$，${\bf{grt}}[k] \ne {\bf{grt}}[{i^*}]$，从而有$\boldsymbol{v}' \ne {\boldsymbol{v}_{{i^*}}}$。

记$\boldsymbol{x} = ({\boldsymbol{s}_{{i^*},1}} - \boldsymbol{s}_{_{i,1}}^*) + \boldsymbol{R}({\boldsymbol{s}_{{i^*},1}} - \boldsymbol{s}_{_{i,1}}^*) \in {\mathbb{Z}^m}$，因此x为${\mathit{\boldsymbol{A}}_1} \bullet \mathit{\boldsymbol{x}} = 0\bmod q$的一个非零解。从而解决了SIS问题。由引理1知，敌手成功伪造签名的优势是可忽略的。

文献[3]是格基群签名的经典方案，文献[7]是第一个实现了群成员动态加入的格基群签名方案，文献[9]是第一个动态格基群签名方案。本文选取文献[3, 7, 9]进行储存空间对比和计算开销对比，结果如表 2所示。其中，$N$表示群成员个数，$S$表示哈希运算的时间，$W$表示零知识证明的运算时间，$V$表示一次签名运算时间，${T_1}$表示一次随机采样算法的时间，${T_2}$表示一次数乘运算的时间，${T_3}$表示运行一次特殊采样算法的时间(不同采样算法的运行时间是不同的，在这里不考虑这点)。

数的加法运算时间忽略不计。从表 2可以看出，与文献[7]相比，本文的方案牺牲了一点计算开销：一个矩阵乘运算和一次随机采样，但实现了群成员的撤销；与方案[9]相比，本文方案的私钥尺寸较小，且撤销方式简单，当群成员加入和撤销时，需要更新的数量较小，更适用于成员变化较频繁的群。

本文给出了一个动态格基群签名方案，并在随机预言机模型下，基于SIS和LWE假设证明了方案的安全性。与已有的方案相比，本文的方案允许群成员在任何时间加入和退出群，而且公钥尺寸较小。另一方面，构造依赖于LWE加密方案，而且在随机预言机模型下是CPA-匿名的。构造一个更加简单高效，且在标准模型下具有CCA-匿名性的格基群签名方案是我们下一步的工作。