0 概述

1991年，CHAUM等人首次提出群签名的概念^[1]，其具有匿名性和追踪性。群签名允许群中合法成员代表群对消息进行签名，任意验证者均可利用群公钥来验证该签名的合法性，但无法确定签名者的真实身份，即匿名性；当发生争议时，群管理员可以通过追踪密钥打开签名找到真实的签名者，即追踪性。群签名的匿名性和追踪性使其被广泛应用于多种场景，如电子投票、电子商务系统和可信计算等。文献[2]指出，基于经典数论难题的传统密码方案^[3-5]在多项式时间内会被量子计算机破解，基于格的新型密码体制将成为后量子密码时代的研究热点。

2010年，GORDON等人在Asiacrypt2010会议上提出格上群签名方案^[6]，但该方案的密钥长度和签名长度都与群成员数量呈线性关系。2013年，LANGUILLAUMIE等人在Asiacrypt2013会议上提出一种密钥长度、签名长度与群成员数量呈对数关系的群签名方案^[7]，虽然缩短了密钥长度和签名长度，但由于两者均依赖于群成员数量，因此该方案并不适用于大群组的群签名系统。2015年，NGUYEN等人提出一种简单高效的群签名方案^[8]，该方案的密钥长度和签名长度与群成员数量无关，适用于大群组的群签名系统，但由于群成员私钥由群管理员产生，因此不能抵抗群管理员对群成员的陷害攻击。考虑到用户加入群的动作在任意时间都有可能发生，并且当发现某些群成员有行为不端的现象时，群管理员应有权撤销不法成员的签名权力，因此，群签名系统应包含支持群成员动态加入、撤销的加入机制和撤销机制^[9-10]。然而，以上群签名方案都不支持群成员的加入和撤销。

2016年，LIBERT等人构造了一个包含加入机制的群签名方案^[11]，但仍缺少群成员的动态撤销机制。2017年，LING等人基于Merkle哈希树构造了一个格基完全动态（同时包含加入和撤销机制）的群签名方案^[12]，但该方案撤销成员时需要更新哈希树，计算较复杂且耗时较长，并且签名长度仍与群成员数量相关。2018年，LING等人又提出了格上本地撤销群签名方案^[13]，但该方案不支持群成员的动态加入。2019年，李雪莲等人提出一种适合大群组的格基完全动态签名方案^[14]，但由于在加入过程中使用变色龙哈希函数和随机采样技术，并且撤销过程中增加了与撤销图灵机的交互代价，因此该方案的开销较大。

为加快群成员的加入和撤销速度，降低完全动态群签名方案加入和撤销机制的复杂性，本文在文献[8]群签名方案的基础上，结合文献[11, 14]提出的动态群签名思想，基于错误学习（Learning with Error，LWE）问题和非齐次小整数解（Inhomogeneous Small Integer Solution，ISIS）问题构造一个高效的格上完全动态群签名方案，对其进行安全性证明，并与现有的格上群签名方案进行效率对比。

1 预备知识 1.1 符号定义

本文方案中的符号定义如表 1所示。

1.2 格

定义1（格）  设$ {\boldsymbol{b}}_{1}, {\boldsymbol{b}}_{2}, \cdots , {\boldsymbol{b}}_{m} $是$ n $维欧式空间$ {\mathbb{R}}^{m} $上$ m $个线性无关的向量，则格$ \boldsymbol{L} $被定义为$ {\boldsymbol{b}}_{1}, {\boldsymbol{b}}_{2}, \cdots , {\boldsymbol{b}}_{m} $上所有整系数线性组合所构成的集合，表示为$ \boldsymbol{L}=\left\{{a}_{1}{\boldsymbol{b}}_{1}+{a}_{2}{\boldsymbol{b}}_{2}+\cdots +{a}_{m}{\boldsymbol{b}}_{m}\right\}\left({a}_{1}, {a}_{2}, \cdots , {a}_{m}\in {\mathbb{Z}}_{q}\right) $，而$ {\boldsymbol{b}}_{1}, {\boldsymbol{b}}_{2}, \cdots , {\boldsymbol{b}}_{m} $称为格$ \boldsymbol{L} $的一组基。

定义2（$ q $元格）  设$ q, m, n\in \mathbb{Z}, \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，向量$ \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $，q元格表示为：

$ {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{A}\right)=\left\{\boldsymbol{e}\in {\mathbb{Z}}_{q}^{m}:\boldsymbol{A}\boldsymbol{e}=0\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right)\right\} $

$ {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\boldsymbol{u}}\left(\boldsymbol{A}\right)=\left\{\boldsymbol{e}\in {\mathbb{Z}}_{q}^{m}:\boldsymbol{A}\boldsymbol{e}=\boldsymbol{u}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right)\right\} $

$ {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left({\boldsymbol{A}}^{\mathrm{{\rm T}}}\right)=\left\{\boldsymbol{y}\in {\mathbb{Z}}_{q}^{m}:\boldsymbol{y}={\boldsymbol{A}}^{\mathrm{{\rm T}}}\boldsymbol{e}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right)，\forall \boldsymbol{e}\in {\mathbb{Z}}_{q}^{n}\right\} $

定义3（离散高斯分布）  给定实向量$ \boldsymbol{c}\in {\mathbb{R}}^{m} $，任意实数$ s>0 $，则格$ \boldsymbol{L} $上以$ \boldsymbol{c} $为中心、以s为参数的离散高斯分布密度函数表示为：

$ \forall \boldsymbol{x}\in \boldsymbol{L}, {\rho }_{s, \boldsymbol{c}}=\mathrm{e}\mathrm{x}\mathrm{p}\left(-\pi {\left(\frac{‖\boldsymbol{x}-\boldsymbol{c}‖}{s}\right)}^{2}\right) $

当$ s=1 $，$ \boldsymbol{c}=0 $时，格$ \boldsymbol{L} $上任意一点$ \boldsymbol{x} $的离散高斯分布表示为：

${D_{\boldsymbol{L},s,\boldsymbol{c}}}\left( \boldsymbol{x} \right) = \frac{{{\rho _{s,\boldsymbol{c}}}\left( \boldsymbol{x} \right)}}{{\sum\limits_{\boldsymbol{y} \in \boldsymbol{L}} {{\rho _{s,\boldsymbol{c}}}\left( \boldsymbol{y} \right)} }} $

1.3 格上困难问题

定义4（SIS问题）  给定模数$ q\in \mathbb{Z} $、实数$ \beta $和矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，找到一个非零向量$ \boldsymbol{e}\in {\mathbb{Z}}^{m} $且$ ‖\boldsymbol{e}‖\le \beta $，满足$ \boldsymbol{A}\boldsymbol{e}={\bf{0}}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right) $。

定义5（ISIS问题）  给定模数$ q\in \mathbb{Z} $、实数$ \beta $、$ \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $和矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，找到一个非零向量$ \boldsymbol{e}\in {\mathbb{Z}}^{m} $且$ ‖\boldsymbol{e}‖\le \beta $，满足$ \boldsymbol{A}\boldsymbol{e}=\boldsymbol{u}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right) $。

定义6（LWE问题）  给定模数$ q\in \mathbb{Z} $、$ \alpha \in {\mathbb{R}}^{+} $、向量$ \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $和矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，$ {\chi }_{\alpha } $表示$ {\mathbb{Z}}_{q} $上的离散高斯分布。随机选择$ \boldsymbol{e}\leftarrow {}_{R}{\chi }_{\alpha }^{m}，\boldsymbol{e}\in {\mathbb{Z}}_{q}^{m} $，则：

1）LWE搜索问题为：求出向量$ \boldsymbol{t}\in {\mathbb{Z}}_{q}^{m} $，使得等式$ \boldsymbol{u}=\boldsymbol{A}\boldsymbol{t}+\boldsymbol{e} $成立。

2）LWE判定问题为：判断向量$ \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $是由$ \boldsymbol{u}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{n} $还是由$ \boldsymbol{u}=\boldsymbol{A}\boldsymbol{t}+\boldsymbol{e} $计算得到。

1.4 抽样函数

引理1^[15]  给定正数$ n $，$ q=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(n\right)，m>5n\mathrm{l}\mathrm{b}q $，则存在一个多项式时间算法$ \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}\left({1}^{n}, {1}^{m}, q\right) $，产生一个矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $和一个陷门基$ {\boldsymbol{T}}_{\boldsymbol{A}}\subset {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{A}\right) $，矩阵$ \boldsymbol{A} $的分布统计接近于$ {\mathbb{Z}}_{q}^{n\times m} $上的均匀分布，并且$ ‖{{\widetilde{\boldsymbol{T}}}_{A}}‖\le O\left(\sqrt{n\mathrm{l}\mathrm{b}q}\right)=O\left(\sqrt{m}\right) $以极大概率成立。

引理2^[7]  给定$ n\in \mathbb{Z} $、$ q\ge 2\mathrm{、}m\ge ⌈6n\mathrm{l}\mathrm{b}q+n⌉ $、矩阵$ \boldsymbol{C}\in {\mathbb{Z}}_{q}^{n\times n}\mathrm{、}\boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，则存在一个多项式时间算法$ \mathrm{S}\mathrm{u}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\left({1}^{n}, {1}^{m}, q, \boldsymbol{A}, \boldsymbol{C}\right) $，产生格基$ {\boldsymbol{T}}_{\boldsymbol{B}}\subset {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{B}\right) $和矩阵$ \boldsymbol{B}\in {\mathbb{Z}}_{q}^{n\times m} $满足$ \boldsymbol{A}{\boldsymbol{B}}^{\mathrm{{\rm T}}}=\boldsymbol{C} $，并且同时满足$ ‖{\boldsymbol{T}}_{\boldsymbol{B}}‖\le {m}^{1.5}\cdot \omega \left(\sqrt{\mathrm{l}\mathrm{b}m}\right) $，$ ‖{{\widetilde{\boldsymbol{T}}}_{B}}‖\le m\cdot \omega \left(\sqrt{\mathrm{l}\mathrm{b}m}\right) $。

引理3^[16]  给定矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times {m}_{1}}\mathrm{、}{\boldsymbol{T}}_{\boldsymbol{A}}\subset {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{A}\right)\mathrm{、}\boldsymbol{B}\in $ $ {\mathbb{Z}}_{q}^{n\times {m}_{2}} $以及一个实数$ s\ge ‖{{\widetilde{\boldsymbol{T}}}_{A}}‖\cdot \omega \left(\sqrt{\mathrm{l}\mathrm{b}m}\right) $，令$ {\boldsymbol{A}}^{'}=\left(\boldsymbol{A}\left|\right|\boldsymbol{B}\right)\in {\mathbb{Z}}_{q}^{n\times \left({m}_{1}+{m}_{2}\right)} $，存在一个概率多项式算法$ \mathrm{E}\mathrm{x}\mathrm{t}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\left({\boldsymbol{A}}^{'}, {\boldsymbol{T}}_{\boldsymbol{A}}, s\right) $输出一个格基$ {\boldsymbol{T}}_{{\boldsymbol{A}}^{'}}\subset {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left({\boldsymbol{A}}^{'}\right) $，且同时满足$ ‖{\boldsymbol{T}}_{{\boldsymbol{A}}^{'}}‖\le s\left({m}_{1}+{m}_{2}\right) $，$ ‖{{\widetilde{\boldsymbol{T}}}_{A}}{'}‖\le s\sqrt{\left({m}_{1}+{m}_{2}\right)} $。

引理4^[17]  给定矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m}\mathrm{、}{\boldsymbol{T}}_{\boldsymbol{A}}\subset {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{A}\right) $、实数$ s\ge ‖{{\widetilde{\boldsymbol{T}}}_{A}}‖\cdot \omega \left(\sqrt{\mathrm{l}\mathrm{b}m}\right) $和向量$ \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $，则存在一个多项式时间算法$ \mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}\left(\boldsymbol{A}, {\boldsymbol{T}}_{\boldsymbol{A}}, s, \boldsymbol{u}\right) $输出一个向量$ \boldsymbol{e}\sim {D}_{{\mathbb{Z}}^{m}, s}，\boldsymbol{e}\in {\mathbb{Z}}^{m} $，满足$ \boldsymbol{A}\boldsymbol{e}=\boldsymbol{u}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right) $。

1.5 非交互零知识证明

2013年，LAGUILLAUMIE等人给出一个关于ISIS问题的零知识证明^[7]：

$ {R}_{\mathrm{I}\mathrm{S}\mathrm{I}\mathrm{S}}=\left\{\left(\boldsymbol{A}, \boldsymbol{y}, \beta ;\boldsymbol{x}\right)\in {\mathbb{Z}}_{q}^{n\times m}\times {\mathbb{Z}}_{q}^{n}\times \mathbb{R}\times {\mathbb{Z}}_{q}^{m}:\\ \;\;\;\;\;\;\;\;\;\;\;\;\boldsymbol{A}\boldsymbol{x}=\boldsymbol{y}, ‖\boldsymbol{x}‖<\beta \right\} $

2015年，NGUYEN等人给出一个关于Split-SIS问题上的零知识证明^[8]：

$ {R}_{\mathrm{S}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}-\mathrm{S}\mathrm{I}\mathrm{S}}=\left\{\begin{array}{l}\left(\boldsymbol{A}, \boldsymbol{y}, \beta , N;{\boldsymbol{x}}_{1}, h\right)\in {\mathbb{Z}}_{q}^{n\times 2m}\times \left({\mathbb{Z}}_{q}^{n}\times {\mathbb{Z}}^{m}\right)\times \\ \mathbb{R}\times \mathbb{Z}\times {\mathbb{Z}}_{q}^{m}\times \mathbb{Z}:{\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}+h{\boldsymbol{A}}_{2}{\boldsymbol{y}}_{2}={\boldsymbol{y}}_{1}, \\ \boldsymbol{y}=\left({\boldsymbol{y}}_{1}, {\boldsymbol{y}}_{2}\right), ‖{\boldsymbol{x}}_{1}‖<\beta \sqrt{m}, h\in \left[N\right]\end{array}\right\} $

由ISIS和LWE的对偶性可得关于LWE的零知识证明^[18]：

$ {R}_{\mathrm{L}\mathrm{W}\mathrm{E}}=\left\{\left(\boldsymbol{A}, \boldsymbol{b}, \alpha ;\boldsymbol{t}\right)\in {\mathbb{Z}}_{q}^{n\times m}\times {\mathbb{Z}}_{q}^{n}\times \mathbb{R}\times {\mathbb{Z}}_{q}^{n}:\\ \;\;\;\;\;\;\;\;\;\;\;\; ‖\boldsymbol{b}-{\boldsymbol{A}}^{\mathrm{{\rm T}}}\boldsymbol{t}‖<\alpha q\sqrt{m}\right\} $

同时，也可构造一个$ \gamma =\mathrm{m}\mathrm{a}\mathrm{x}\left(\alpha q\sqrt{m}, \beta \right) $的eLWE关系的零知识证明^[18]：

$ {R}_{\mathrm{e}\mathrm{L}\mathrm{W}\mathrm{E}}=\left\{\begin{array}{l}\left(\boldsymbol{A}, \boldsymbol{b}, \gamma ;\boldsymbol{t}, \boldsymbol{e}, \boldsymbol{x}\right)\in {\mathbb{Z}}_{q}^{n\times m}\times {\mathbb{Z}}_{q}^{m}\times \mathbb{R}\times {\mathbb{Z}}_{q}^{n}\times {\mathbb{Z}}^{2m}:\\ \boldsymbol{b}=\boldsymbol{A}\boldsymbol{t}+p\boldsymbol{e}+\boldsymbol{x}, ‖\boldsymbol{x}‖<\gamma , ‖\boldsymbol{e}‖<\gamma \end{array}\right\} $

以上零知识证明都可经过Fiat-Shamir变换转换为非交互零知识证明（Non-Interactive Zero-Knowledge Proofs，NIZKP）。

2 格上高效的动态群签名方案 2.1 动态群签名定义和安全模型 2.1.1 群签名定义

一个动态群签名算法^{[8, 13-14, 19-20]}由以下多项式时间算法组成：

1）$ \mathrm{G}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\left({1}^{n}, {1}^{N}\right)\to pp $：输入群签名系统的安全参数$ n $和群成员数量$ N $，算法产生公共参数$ pp $。

2）密钥生成算法：

（1）$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{G}\mathrm{m}}\left(pp\right)\to \left(\left(gmsk, gmpk\right), \left(gtpk, gtsk\right)\right) $：该算法由群管理员执行，输入公共参数$ pp $，生成群管理员的主密钥对$ \left(gmsk, gmpk\right) $和追踪密钥对$ \left(gtpk, gtsk\right) $。

（2）$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}\left(pp\right)\to \left(us{k}_{i}, up{k}_{i}\right) $：该算法由群成员执行，输入公共参数$ pp $，生成群成员的密钥对$ \left(us{k}_{i}, up{k}_{i}\right) $。

3）$ \mathrm{G}\mathrm{U}\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}\left(pp, gpk, gmsk\right)\to \left(cer{t}_{i}, \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\right) $：该算法是由群管理员和用户执行的交互式算法，输入公共参数$ pp $、群管理员的主私钥gmpk和群公钥gpk，$ gpk=\left(gmpk, gtpk, up{k}_{i}\right) $。若算法执行成功，则群管理员颁发成员证书$ cer{t}_{i} $和计算用户的撤销标记$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i} $，用户加入成功。

4）$ \mathrm{G}\mathrm{S}\mathrm{i}\mathrm{g}\left(gpk, us{k}_{i}, cer{t}_{i}, m\right)\to \varSigma $：该算法由群成员执行，将$ \left(gpk, us{k}_{i}, cer{t}_{i}, m\right) $作为输入参数，输出一个由用户$ us{k}_{i} $在消息m上的签名。

5）$ \mathrm{G}\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{o}\mathrm{k}\mathrm{e}\to 0/1 $：该算法由群管理员或用户执行，主要是群管理员将撤销标记加入到撤销列表RL中，并更新和发布撤销列表，若算法输出为1则撤销成功，否则输出为0。

6）$ \mathrm{G}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}\left(gpk, m, \varSigma , \mathrm{R}\mathrm{L}\right)\to 0/1 $：该算法为确定性算法，并由验证者执行，将$ \left(gpk, m, \varSigma , \mathrm{R}\mathrm{L}\right) $作为输入参数来判断该签名的签名者是否已被撤销，若未被撤销，则判定该签名是否是消息$ m $上的合法签名，若是，则输出为1，否则输出为0。

7）$ \mathrm{G}\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{n}\left(gpk, gtsk, m, \varSigma \right)\to I{d}_{i} $：该算法为确定性算法，由群管理员执行，输入参数$ \left(gpk, gtsk, m, \varSigma \mathrm{ }\right) $，返回对消息$ m $做签名的用户者身份$ I{d}_{i} $。

2.1.2 群签名安全模型

一个群签名方案必须满足正确性、匿名性和追踪性这3个安全特性^{[6-8, 13-14]}，其中，正确性是群签名中最基本的要求，匿名性和追踪性是对群签名的安全性要求。

1）在正确性方面，要求方案满足签名验证正确性和签名打开正确性^{[6-8, 13-14]}，其中：签名验证正确性是指按算法步骤产生的签名一定能通过验证算法的验证；签名打开正确性是指按算法步骤产生的签名一定能被群管理员打开。

2）匿名性是指任何获得签名的人都不能通过签名判断出真正的签名者身份（除群管理员外）。匿名性又分为弱匿名性（CPA-匿名）和完全匿名性（CCA-匿名）^[6-8]。在CCA-匿名的游戏中，敌手能够进行签名打开查询，而在CPA-匿名的游戏中，敌手不能进行签名打开查询。显然，CCA-匿名游戏中的敌手比CPA-匿名游戏中的敌手具有更强的攻击能力，因此，满足CCA-匿名的群签名方案比满足CPA-匿名的群签名方案更安全。本文的群签名方案是满足CCA-匿名的。

3）追踪性是指群成员产生的合法签名能够被群管理员打开，而伪造的签名，即使是由合谋的群成员共同伪造的签名，也不能够被群管理员打开。追踪性又分为CPA-追踪和CCA-追踪，两者的区别在于游戏中敌手是否能够进行腐败查询。本文方案的追踪性是满足CCA-追踪的。

正确性具体的形式化定义如下：

定义7（正确性）  对于任意$ n\mathrm{、}N $，所有由$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{G}\mathrm{m}}(·) $、$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}(·) $、$ \mathrm{G}\mathrm{U}\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}(·) $产生的$ (gpk, cer{t}_{i}, gmsk, gtsk, $ $ us{k}_{i}) $、消息$ m $、$ i\in \left[N\right] $，若$ \mathrm{G}\mathrm{S}\mathrm{i}\mathrm{g}(gpk, us{k}_{i}, cer{t}_{i}, m)\to \varSigma $，则$ \mathrm{G}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y} $ $ \left(gpk, m, \varSigma \right)=1\iff \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\notin \mathrm{R}\mathrm{L} $且$ \mathrm{G}\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{n}\left(\mathrm{g}\mathrm{p}\mathrm{k}, gtsk, \right. $ $ \left.m, \varSigma \right)=I{d}_{i} $。

关于匿名性，下面给出一个敌手$\mathcal{A} $和挑战者$ \mathcal{B}$之间的游戏：

1）参数建立。输入任意正整数$ n\mathrm{、}N $，挑战者$ \mathcal{B}$执行算法$ \mathrm{G}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}(·) $、$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{G}\mathrm{m}}(·) $、$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}(·) $、$ \mathrm{G}\mathrm{U}\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}(·) $产生$ \left(gpk, cer{t}_{i}, gmsk, gtsk, us{k}_{i}\right) $，并将群公钥$ gpk $发送给敌手$\mathcal{A} $。

2）查询。敌手$\mathcal{A} $可以做签名、撤销、腐败和签名打开查询，查询过程如下：

（1）签名查询：敌手$\mathcal{A} $输入用户身份$ I{d}_{i} $、任意消息$ m, $签名预言机用$ \left(cer{t}_{i}, us{k}_{i}\right) $产生用户$ I{d}_{i} $的签名，并将签名返回给敌手$\mathcal{A} $。

（2）腐败查询：敌手$\mathcal{A} $输入用户身份$ I{d}_{i} $，腐败预言机返回用户$ I{d}_{i} $的私钥给敌手$\mathcal{A} $，挑战者$ \mathcal{B}$将腐败的用户加入到腐败集合$ {U}_{\mathrm{a}} $。

（3）撤销查询：敌手$\mathcal{A} $可以查询任意用户的撤销标记，挑战者$ \mathcal{B}$将被查询过的标记加入到集合$ {U}_{\mathrm{c}} $

（4）签名打开查询：敌手$\mathcal{A} $输入$ \left(m, \varSigma \mathrm{ }\right) $，签名打开预言机返回用户身份$ I{d}_{i} $。

3）挑战。敌手$\mathcal{A} $选择未被查询的消息$ m $，并同时选择2个用户$ {d}_{0}，{d}_{1}\notin {U}_{\mathrm{a}}\bigcup {U}_{\mathrm{c}} $，其中，用户的私钥和证书分别为$ \left(us{k}_{0}^{\mathrm{*}}, cer{t}_{0}^{\mathrm{*}}\mathrm{ }\right) $和$ \left(us{k}_{1}^{\mathrm{*}}, cer{t}_{1}^{\mathrm{*}}\mathrm{ }\right) $，将这些信息发送给挑战者$ \mathcal{B}$。挑战者$ \mathcal{B}$选择$ b\leftarrow {}_{\mathrm{R}}\left\{0, 1\right\} $，用$ \left(us{k}_{b}^{\mathrm{*}}, cer{t}_{b}^{\mathrm{*}}\mathrm{ }\right) $计算挑战签名$ {\varSigma }^{\mathrm{*}} $，将其发送给敌手$\mathcal{A} $。

4）受限查询。敌手仍可做一些查询，但不能对用户$ {d}_{0}\mathrm{、}{d}_{1} $做腐败、撤销和签名打开查询。

5）输出。敌手$\mathcal{A} $输出$ {b}^{\mathrm{*}} $。若$ {b}^{\mathrm{*}}=b $，称敌手获胜。

敌手$\mathcal{A} $在上述游戏中获胜的优势定义为：$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathcal{A}}^{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}}=\left|\mathrm{P}\mathrm{r}\left[{b}^{\mathrm{*}}=b\right]-1/2\right| $。

定义8（匿名性）  对于任意概率多项式时间的敌手$\mathcal{A} $，若$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathcal{A}}^{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}}\le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(n\right) $，则称群签名方案具有CCA-匿名性。

关于追踪性，下面给出一个敌手$\mathcal{A} $与挑战者$ \mathcal{B}$之间的游戏。在游戏中，敌手$\mathcal{A} $的目标是伪造一个签名，管理员利用签名打开算法不能打开伪造的签名。敌手$\mathcal{A} $能够腐化群管理员，在查询阶段也能腐化用户，并可利用加入算法产生一些虚拟成员。游戏过程如下：

1）参数建立。挑战者$ \mathcal{B}$执行算法$ \mathrm{G}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}(·) $、$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{G}\mathrm{m}}(·) $、$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}(·) $，产生$ (gpk, cer{t}_{i}, gmsk, gtsk, $ $ us{k}_{i}) $，将群公钥发送给敌手$\mathcal{A} $，并设置$ {U}_{\mathrm{a}}=\mathrm{\varnothing } $。

2）查询。敌手$\mathcal{A} $可以做签名和腐败用户的查询，查询过程如下：

（1）签名查询：敌手$\mathcal{A} $输入任意消息$ m $和用户身份$ I{d}_{i} $，签名预言机可以返回对应的签名$ \varSigma $，并将查询过的签名加入到集合$ {U}_{\mathrm{s}\mathrm{i}\mathrm{g}} $（$ {U}_{\mathrm{s}\mathrm{i}\mathrm{g}} $是由用户身份$ I{d}_{i} $、消息$ m $和对应消息签名$ \varSigma $组成的集合）。

（2）腐败查询：敌手$\mathcal{A} $询问任意用户的私钥时，挑战者$ \mathcal{B}$将询问过的用户加入到集合$ {U}_{\mathrm{a}} $，并返回对应用户的私钥。

3）伪造。敌手$\mathcal{A} $利用其所拥有的信息产生一个消息签名对$ ({m}^{\mathrm{*}}, {\varSigma }^{\bf{*}}) $和撤销列表$ \mathrm{R}{\mathrm{L}}^{\mathrm{*}} $，如果$ \mathrm{G}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(gpk, {m}^{\mathrm{*}}, {\varSigma }^{\bf{*}}，\mathrm{R}{\mathrm{L}}^{\mathrm{*}})\to 1 $，对于$ I{d}_{i}\notin {U}_{\mathrm{a}}, (I{d}_{i}, {m}^{\mathrm{*}}, $ $ {\varSigma }^{\mathrm{*}})\notin {U}_{\mathrm{s}\mathrm{i}\mathrm{g}} $，签名打开失败同时$ \mathrm{G}\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{n}\left(\mathrm{g}\mathrm{p}\mathrm{k}, gtsk, \right.{m}^{\mathrm{*}}, $ $ \left.{\varSigma }^{\mathrm{*}}\right)=I{d}_{i} $且$ I{d}_{i}\in {U}_{\mathrm{a}}/\mathrm{R}\mathrm{L} $，则称敌手$\mathcal{A} $获胜。

敌手$\mathcal{A} $在上述游戏中获胜的优势可定义为$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathcal{A}}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}} $。

定义9（追踪性）  若对于任意概率多项式时间的敌手$\mathcal{A} $，$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathcal{A}}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}} $ $ \le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(n\right) $，则称群签名方案具有CCA-追踪性。

2.2 本文方案

本文将文献[11, 14]提出的动态群签名思想引入到文献[8]的群签名方案中，提出一个具有加入和撤销机制的格上完全动态群签名方案。该方案包含2个密钥生成阶段：第1个阶段是群管理员的密钥生成阶段，其中使用文献[8]的GPV陷门生成算法和正交抽样算法产生群管理员的主密钥和追踪密钥；第2个阶段是群成员的密钥生成阶段，其中使用文献[11]的离散高斯采样算法，采取满足一定条件的短向量作为群成员的签名私钥。在加入阶段，使用GPV的格基扩展技术和原像采样算法生成群成员证书；在签名阶段，采用和文献[6-8, 14]类似的对偶LWE算法；撤销阶段分为用户主动撤销和群管理员撤销群成员，两者共同之处是都将撤销标记加入到撤销列表中。

对于方案参数，本文仍按照文献[8]进行选择：$ n $为安全参数；$ \delta $为实数；$ N $为群成员数；$ m=6{n}^{1+\delta } $，q = $ {m}^{2.5}\cdot \mathrm{m}\mathrm{a}\mathrm{x}\left({m}^{6}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{2.5}\right), 4N\right) $且满足$ {n}^{1+\delta }>⌈\left(n+1\right)\mathrm{l}{\mathrm{b}}_{}\;q+n⌉ $，$ \beta ={m}^{1.5}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{1.5}\right) $；$ s=m\cdot \omega \left(\mathrm{l}{\mathrm{b}}_{}m\right) $，$ p={m}^{2.5}\beta ={m}^{4}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{1.5}\right) $，$ \alpha =2\sqrt{m}/q $，$ \eta =\mathrm{m}\mathrm{a}\mathrm{x}\left(\beta , \alpha q\right)\sqrt{m}={m}^{2}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{1.5}\right) $。

1）系统建立

$ \mathrm{G}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\left({1}^{n}, {1}^{N}\right)\to pp $：$ n $为系统安全参数，$ N $为群成员个数，该算法产生的随机预言机为$ H:{\left\{0, 1\right\}}^{\mathrm{*}}\to $ $ {\left\{0, 1\mathrm{ }\right\}}^{t} $，其中，$ t=\omega \left(\mathrm{l}\mathrm{b}\;n\right) $，$ {\boldsymbol{A}}_{0}, {\boldsymbol{A}}_{1}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{n\times m} $，则参数$ pp=\left\{n, N, m, q, s, p, \alpha , \beta , \eta , {\boldsymbol{A}}_{0}, {\boldsymbol{A}}_{1}\right\} $。

2）密钥生成算法

（1）$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{G}\mathrm{m}}\left(pp\right)\to \left(\left(gmsk, gmpk\right), \left(gtpk, gtsk\right)\right) $：群管理员首先计算$ \left(\boldsymbol{A}, {\boldsymbol{T}}_{\boldsymbol{A}}\right)\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}\left({1}^{n}, {1}^{m}, q\right) $，其中，$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m} $，$ {\boldsymbol{T}}_{\boldsymbol{A}} $为格$ {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{A}\right) $的一个短基，然后计算$ \left(\boldsymbol{B}, {\boldsymbol{T}}_{\boldsymbol{B}}\right)\leftarrow \mathrm{S}\mathrm{u}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\left({1}^{n}, {1}^{m}, q, \boldsymbol{A}, 0\right) $，其中，$ \boldsymbol{B}\in {\mathbb{Z}}_{q}^{n\times m} $，$ {\boldsymbol{T}}_{\boldsymbol{B}} $为格$ {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}}_{q}^{\perp }\left(\boldsymbol{B}\right) $的一个短基，则群管理员的主私钥$ gmsk={\boldsymbol{T}}_{\boldsymbol{A}} $，主公钥$ gmpk=\boldsymbol{A} $，追踪私钥$ gtsk={\boldsymbol{T}}_{\boldsymbol{B}} $，追踪公钥$ gtpk=\boldsymbol{B} $。

（2）$ \mathrm{G}\mathrm{K}\mathrm{g}\mathrm{e}{\mathrm{n}}_{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}\left(pp\right)\to \left(usk, upk\right) $：用户在格上利用离散高斯采样算法^[17]，采取一个短向量$ {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{n} $，再随机选取矩阵$ \boldsymbol{F}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m\times n} $，并计算满足$ {\boldsymbol{v}}_{i}=\boldsymbol{F}\cdot {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{m} $，则用户的签名私钥为$ {\boldsymbol{z}}_{i} $，用户公钥为$ {\boldsymbol{v}}_{i} $。

由此可知群公钥$ gpk=\left(\boldsymbol{A}, \boldsymbol{B}, \boldsymbol{F}, pp, {\boldsymbol{v}}_{i}\right) $。

3）$ \mathrm{G}\mathrm{U}\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}\left(pp, gpk, gmsk\right)\to \left(cer{t}_{i}, \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\right) $

用户先利用PKI中注册过的密钥$ \left(\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{k}\left[i\right]\right., \left.pupk\left[i\right]\right) $对$ {\boldsymbol{v}}_{i} $做普通的数字签名：$ si{g}_{i}=\mathrm{S}\mathrm{i}{\mathrm{g}}_{\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{k}\left[i\right]}\left({\boldsymbol{v}}_{i}\right) $，再将$ \left({\boldsymbol{v}}_{i}, si{g}_{i}\right) $发送给群管理员。群管理员验证$ {\boldsymbol{v}}_{i} $是否已被注册，并且用$ pupk\left[i\right] $验证该签名的合法性。若该签名合法或是已被注册过，则终止加入过程；否则群管理员做以下工作：

首先群管理员为用户选取新的身份，令$ I{d}_{i}=i，i\in \left[N\right] $，计算$ {\boldsymbol{A}}_{I{d}_{i}}=\left[\boldsymbol{A}\left|\right|{\boldsymbol{A}}_{0}+I{d}_{i}{\boldsymbol{A}}_{1}\right]\in {\mathbb{Z}}_{q}^{n\times 2m} $，$ {\boldsymbol{T}}_{{\boldsymbol{A}}_{I{d}_{i}}}\leftarrow $ $ \mathrm{E}\mathrm{x}\mathrm{t}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\left({\boldsymbol{A}}_{I{d}_{i}}, {\boldsymbol{T}}_{\boldsymbol{A}}, s\right) $，其中，$ {\boldsymbol{T}}_{{\boldsymbol{A}}_{I{d}_{i}}}\in {\mathbb{Z}}_{q}^{m\times m} $且满足$ ‖{{\widetilde{\boldsymbol{T}}}_{{{\boldsymbol{A}}_{I{{d}_{i}}}}}}‖\le $ $ s\sqrt{2m} $，令$ {\boldsymbol{u}}_{i}=\boldsymbol{A}{\boldsymbol{v}}_{i}\in {\mathbb{Z}}_{q}^{n} $；然后计算$ \left({\boldsymbol{x}}_{0}, {\boldsymbol{x}}_{1}\right)\leftarrow $ $ \mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}\left({\boldsymbol{A}}_{I{d}_{i}}, {\boldsymbol{T}}_{{A}_{I{d}_{i}}}, \beta , {\boldsymbol{u}}_{i}\right) $且$ {\boldsymbol{x}}_{0}, {\boldsymbol{x}}_{1}\in {D}_{{\mathbb{Z}}^{m}, \beta } $；最后计算群用户的撤销标记$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}={\boldsymbol{A}}_{1}{\boldsymbol{v}}_{i}\in {\mathbb{Z}}_{q}^{n} $。由以上步骤产生群成员证书$ cer{t}_{i}=\left(I{d}_{i}, {\boldsymbol{x}}_{0}, {\boldsymbol{x}}_{1}\right) $，群管理员将$ \left({\boldsymbol{v}}_{i}, cer{t}_{i}, \right. $ $ \left.\bf{r}\bf{e}{\boldsymbol{g}}_{i}, si{g}_{i}\right) $存储在注册列表中，并将证书通过安全信道发送给群成员。

4）$ \mathrm{G}\mathrm{S}\mathrm{i}\mathrm{g}\left(gpk, usk, cert, m\right)\to \varSigma $

（1）群成员选取$ {\boldsymbol{s}}_{0}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{n}, {\boldsymbol{e}}_{0}\leftarrow {}_{\mathrm{R}}{\chi }_{\alpha }^{m} $，计算$ {\boldsymbol{c}}_{0}={\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{s}}_{0}+ $ $ p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0} $，并产生一个关于$ \left({\boldsymbol{s}}_{0}, {\boldsymbol{e}}_{0}, {\boldsymbol{x}}_{0}\right) $的非交互零知识证明$ {\pi }_{0} $，使得$ \left(\boldsymbol{B}, {\boldsymbol{c}}_{0}, \eta ;{\boldsymbol{s}}_{0}, {\boldsymbol{e}}_{0}, {\boldsymbol{x}}_{0}\right)\in {R}_{\mathrm{e}\mathrm{L}\mathrm{W}\mathrm{E}} $。

（2）令$ \overline{\beta }=⌊\beta ⌋, l=⌈\mathrm{l}\mathrm{o}{{\mathrm{g}}_{\overline{\beta }}}_{}N⌉ $，定义$ {\boldsymbol{u}}_{i}=\boldsymbol{A}{\boldsymbol{v}}_{i}\in {\mathbb{Z}}_{q}^{n} $，$ \boldsymbol{b}={\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}\in {\mathbb{Z}}_{q}^{n}, \boldsymbol{D}=\left(\boldsymbol{b}, \overline{\beta }\boldsymbol{b}, {\overline{\beta }}^{2}\boldsymbol{b}, \cdots , {\overline{\beta }}^{l-1}\boldsymbol{b}\right)\in {\mathbb{Z}}_{q}^{n\times l} $，$ I{d}_{i} $的向量表示$ \boldsymbol{i}{\boldsymbol{d}}_{i}=\left(i{d}_{0}, i{d}_{1}, \cdots , i{d}_{l-1}\right)\in {\mathbb{Z}}_{\overline{\beta }}^{l} $，并产生一个关于$ \left({\boldsymbol{x}}_{0}, {\boldsymbol{e}}_{0}, I{d}_{i}\right) $的非交互零知识证明$ {\pi }_{1} $，满足$ \boldsymbol{A}{\boldsymbol{c}}_{0}+{\boldsymbol{A}}_{0}{\boldsymbol{x}}_{1}-{\boldsymbol{u}}_{i}=\left(p\boldsymbol{A}\right){\boldsymbol{e}}_{0}-\boldsymbol{D}\cdot i{d}_{i} $，$ \boldsymbol{A}{\boldsymbol{c}}_{0}=\left(p\boldsymbol{A}\right){\boldsymbol{e}}_{0}+\boldsymbol{A}{\boldsymbol{x}}_{0} $。

（3）群成员选取$ {\boldsymbol{e}}_{1}\leftarrow {}_{\mathrm{R}}{\chi }_{\alpha }^{m} $，计算$ {\boldsymbol{c}}_{1}={\boldsymbol{B}}^{\mathrm{{\rm T}}}\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}+{\boldsymbol{e}}_{1} $，同时产生一个关于$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i} $满足$ \left(\boldsymbol{A}, {\boldsymbol{c}}_{1}, \alpha ;\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\right)\in {R}_{\mathrm{L}\mathrm{W}\mathrm{E}} $的非交互零知识证明$ {\pi }_{2} $。

（4）群成员产生一个关于$ {\boldsymbol{z}}_{i} $并满足$ \left(\boldsymbol{F}, {\boldsymbol{v}}_{i}, \beta ;{\boldsymbol{z}}_{i}\right)\in $ $ {R}_{\mathrm{I}\mathrm{S}\mathrm{I}\mathrm{S}} $，的非交互零知识证明$ {\pi }_{3} $。

（5）输出签名$ \varSigma =\left({\boldsymbol{c}}_{0}, {\boldsymbol{c}}_{1}, {\boldsymbol{x}}_{1}, {\pi }_{0}, {\pi }_{1}, {\pi }_{2}, {\pi }_{3}\right) $。

5）$ \mathrm{G}\mathrm{R}\mathrm{e}\mathrm{v}\mathrm{o}\mathrm{k}\mathrm{e}\to 0/1 $

（1）若是群管理员执行该算法，则将撤销标记$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i} $加入到撤销列表中，即令$ \mathrm{R}\mathrm{L}=\mathrm{R}\mathrm{L}\bigcup \left\{\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\right\} $，然后发布撤销列表，撤销成功并返回1；否则返回0。

（2）若是用户执行该算法，则将$ \left({\boldsymbol{v}}_{i}, cer{t}_{i}, \right.\left.\bf{r}\bf{e}{\boldsymbol{g}}_{i}, si{g}_{i}\right) $发送给群管理员，向群管理员提交撤销申请，群管理员对用户进行身份验证，若验证成功，则将用户的撤销标记$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i} $加入到撤销列表中，$ \mathrm{R}\mathrm{L}=\mathrm{R}\mathrm{L}\bigcup \left\{\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}\right\} $，然后发布撤销列表，撤销成功返回1，否则，返回0。

6）$ \mathrm{G}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}\left(gpk, m, \varSigma , \mathrm{R}\mathrm{L}\right)\to 0/1 $

验证者首先查看RL，对任意的$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j}\in \mathrm{R}\mathrm{L} $，计算$ {\boldsymbol{e}}_{1}^{'}={\boldsymbol{c}}_{1}-{\boldsymbol{B}}^{\mathrm{{\rm T}}}\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j} $，即$ {\boldsymbol{e}}_{1}^{'}={\boldsymbol{B}}^{\mathrm{{\rm T}}}\left(\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}-\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j}\right)+\boldsymbol{e} $，若$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}=\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j} $且$ {\boldsymbol{e}}_{1}^{'}\le \alpha q\sqrt{m} $，则说明该验证者已被撤销，验证者则拒绝接受签名；反之，分析签名，验证$ {\pi }_{0} \sim {\pi }_{3} $有效且满足$ ‖{\boldsymbol{x}}_{1}‖\le \beta \sqrt{m}, {\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}\ne 0 $，则验证成功，若签名为合法签名，输出1；反之，输出0。

7）$ \mathrm{G}\mathrm{O}\mathrm{p}\mathrm{e}\mathrm{n}\left(gpk, gtsk, m, \varSigma \right)\to I{d}_{i} $

群管理员使用追踪密钥$ {\boldsymbol{T}}_{\boldsymbol{B}} $对密文$ {\boldsymbol{c}}_{0} $解密，得到$ {\boldsymbol{x}}_{0} $，计算$ {\boldsymbol{y}}_{0}={\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1} $，$ {\boldsymbol{y}}_{1}=\boldsymbol{A}{\boldsymbol{x}}_{0}+{\boldsymbol{A}}_{0}{\boldsymbol{x}}_{1} $，若$ {\boldsymbol{y}}_{0}\ne 0 $，能够找到一个$ I{d}_{i} $同时满足$ {\boldsymbol{y}}_{1}+I{d}_{i}{\boldsymbol{y}}_{0}={\boldsymbol{u}}_{i} $则该算法输出$ I{d}_{i} $；否则输出$ \perp $。

3 安全性分析 3.1 正确性证明

对本文方案的验证正确性和打开正确性进行证明。

3.1.1 验证正确性证明

对每个$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j}\in \mathrm{R}\mathrm{L} $，计算$ {\boldsymbol{e}}_{1}^{'}={\boldsymbol{c}}_{1}-{\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{reg}}_{j}={\boldsymbol{B}}^{\mathrm{{\rm T}}}(\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}- $ $ {\boldsymbol{reg}}_{j})+{\boldsymbol{e}}_{1}, {\boldsymbol{e}}_{1}^{'}\le \alpha q\sqrt{m} $，若存在用户$ i $使得$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{i}=\boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{j} $且$ {\boldsymbol{e}}_{1}^{'}\le \alpha q\sqrt{m} $，则说明验证不通过，拒绝接受签名；反之，接受签名。又由于$ {\boldsymbol{x}}_{1}\sim {D}_{{\mathbb{Z}}^{m}, \beta } $，则由文献[8]的引理3可知，$ ‖{\boldsymbol{x}}_{1}‖\le \beta \sqrt{m}\mathrm{P}\mathrm{r}\left({\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}=0\right)\le O\left({q}^{-n}\right) $，又由文献[8]可知$ \left({\pi }_{0}, {\pi }_{1}, {\pi }_{2}, {\pi }_{3}\right) $具有完备性，所以，签名能通过$ \mathrm{G}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y} $算法的检验，该签名为合法签名。

3.1.2 打开正确性证明

因为$ {\boldsymbol{c}}_{0}={\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{s}}_{0}+p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0} $，群管理员使用$ {\boldsymbol{T}}_{\boldsymbol{B}}\in {\mathbb{Z}}_{q}^{m\times m} $对$ {\boldsymbol{c}}_{0} $解密，即有$ {\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{c}}_{0}={\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}\left(p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0}\right)\mathrm{m}\mathrm{o}\mathrm{d}\;q $。由文献[8]的引理1和引理2可知$ ‖p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0}‖\le $ $ 3{m}^{6}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{3}\right) $，又由本文引理2可知$ ‖{\boldsymbol{T}}_{\boldsymbol{B}}‖\le {m}^{1.5}\cdot \omega \left(\sqrt{\mathrm{l}{\mathrm{b}}_{}m}\right) $，易得$ {‖{\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}\left(p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0}\right)‖}_{\mathrm{\infty }}\le $ $ 3{m}^{8}\cdot \omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{3.5}\right)\ll q $，因此，当$ {‖{\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}\left(p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0}\right)‖}_{\mathrm{\infty }}<q/2 $时，等式$ {\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{c}}_{0}={\boldsymbol{T}}_{\boldsymbol{B}}^{\mathrm{{\rm T}}}\left(p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0}\right)\mathrm{m}\mathrm{o}\mathrm{d}\;q $成立，又因为$ {\boldsymbol{T}}_{\boldsymbol{B}}\in {\mathbb{Z}}_{q}^{m\times m} $为满秩矩阵，所以可利用高斯消元法得到$ {\boldsymbol{x}}^{'}=p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0} $。此外，由$ \beta ={m}^{1.5}\omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{1.5}\right) $、$ p={m}^{2.5}\beta $的选择，存在$ {‖{\boldsymbol{x}}_{0}‖}_{\mathrm{\infty }}\le ‖{\boldsymbol{x}}_{0}‖<p/2 $，通过计算$ {\boldsymbol{x}}^{'}=p{\boldsymbol{e}}_{0}+{\boldsymbol{x}}_{0} $可求解出$ {\boldsymbol{x}}_{0} $。因此，可利用追踪密钥$ {\boldsymbol{T}}_{\boldsymbol{B}} $解密$ {\boldsymbol{c}}_{0} $得到$ {\boldsymbol{x}}_{0} $，进而计算得到$ I{d}_{i} $，即找到签名者。

3.2 安全性证明

本文方案满足CCA-匿名性和CCA-追踪性，并且能够抵抗陷害攻击。下文将对其匿名性、追踪性、安全性和抗陷害攻击性进行证明。

3.2.1 匿名性证明

定理1  在随机预言机模型下，本文方案在LWE假设下是CCA-匿名的。

证明：通过一系列的游戏$ {\mathrm{G}}_{0}\sim{\mathrm{G}}_{5} $证明。

$ {\mathrm{G}}_{0} $游戏过程如下：

1）挑战者$ \mathcal{B}$按照本文方案获得群公钥$ gpk=\left(\boldsymbol{A}, \boldsymbol{B}, \boldsymbol{F}, pp, {\boldsymbol{v}}_{i}\right) $、成员证书$ cer{t}_{i}=\left(I{d}_{i}, {\boldsymbol{x}}_{0}, {\boldsymbol{x}}_{1}\right) $、群成员的私钥$ us{k}_{i}={\boldsymbol{z}}_{i}, i\in \left[N\right] $和追踪私钥$ gtsk={\boldsymbol{T}}_{\boldsymbol{B}} $，并将群公钥、成员证书和群成员私钥发送给敌手。

2）$ \mathcal{B}$初始化撤销链表$ \mathrm{R}\mathrm{L}=\mathrm{\varnothing } $、腐败用户集合$ {U}_{\mathrm{a}}=\mathrm{\varnothing } $和撤销查询集合$ {U}_{\mathrm{c}}=\mathrm{\varnothing } $。

3）敌手$\mathcal{A} $在查询阶段可以对任意用户的任意消息$ m $的签名进行查询，对对应消息上的签名进行打开查询，还可以更新$ {U}_{\mathrm{a}} $和$ {U}_{\mathrm{c}} $。

4）敌手$\mathcal{A} $输出选择的消息$ {m}^{\mathrm{*}} $和身份标识$ I{d}_{0}, $ $ I{d}_{1}\in \left[N\right] $，满足$ I{d}_{0}，I{d}_{1}\notin {U}_{\mathrm{a}}\bigcup {U}_{\mathrm{c}} $且$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{{d}_{0}}, \bf{r}\bf{e}{\boldsymbol{g}}_{{d}_{1}}\notin \mathrm{ }\mathrm{R}\mathrm{L} $。

5）挑战者选择$ b{\leftarrow }_{\mathrm{R}}\left\{0, 1\right\} $，以$ I{d}_{b} $的身份按照本文方案计算$ {\varSigma }^{\mathrm{*}}=\left({\boldsymbol{c}}_{0}^{\mathrm{*}}, {\boldsymbol{c}}_{1}^{\mathrm{*}}, {\pi }_{0}^{\mathrm{*}}, {\pi }_{1}^{\mathrm{*}}, {\pi }_{2}^{\mathrm{*}}, {\pi }_{3}^{\mathrm{*}}\right) $，然后将该签名发送给敌手$\mathcal{A} $。此后，敌手$\mathcal{A} $还可以做关于$ I{d}_{i}\ne I{d}_{b} $签名、私钥、打开和撤销标记查询。

$ {\mathrm{G}}_{1} $游戏过程与$ {\mathrm{G}}_{0} $类似，除了$ {\mathrm{G}}_{1} $中是利用NIZKP模拟器生成$ {\pi }_{0}^{\mathrm{*}}, {\pi }_{1}^{\mathrm{*}}, {\pi }_{2}^{\mathrm{*}}, {\pi }_{3}^{\mathrm{*}} $（$ {\mathrm{G}}_{0} $利用随机预言机），则由NIZKP的性质可得，$ {\mathrm{G}}_{0} $和$ {\mathrm{G}}_{1} $是计算上不可区分的。

$ {\mathrm{G}}_{2} $游戏过程与$ {\mathrm{G}}_{1} $类似，除了$ {\boldsymbol{x}}_{1}^{\mathrm{*}}\leftarrow {}_{\mathrm{R}}{D}_{{\mathbb{Z}}^{m}, \beta } $，利用$ {\boldsymbol{T}}_{\boldsymbol{A}} $计算$ {\boldsymbol{x}}_{{}_{0}}^{\mathrm{*}} $，满足等式$ \overline{{\boldsymbol{A}}_{{i}_{b}}}\left({\boldsymbol{x}}_{0}^{\mathrm{*}};{\boldsymbol{x}}_{1}^{\mathrm{*}}\right)={\boldsymbol{u}}_{{i}_{b}} $，又由$ \mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}\left(·\right) $函数的性质^[12-13]可知，$ {\mathrm{G}}_{2} $与$ {\mathrm{G}}_{1} $中选择的$ {\boldsymbol{x}}_{{}_{1}}^{\mathrm{*}} $是统计接近的。

$ {\mathrm{G}}_{3} $游戏过程与$ {\mathrm{G}}_{2} $类似，除了$ {\boldsymbol{g}}_{i}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{n} $，计算$ {\boldsymbol{c}}_{1}^{\mathrm{*}}={\boldsymbol{B}}^{\mathrm{{\rm T}}}{\boldsymbol{g}}_{i}+{\boldsymbol{e}}_{1} $，输出签名$ {\varSigma }^{\mathrm{*}}=\left({\boldsymbol{c}}_{0}^{\mathrm{*}}, {\boldsymbol{c}}_{1}^{\mathrm{*}}, {\pi }_{0}^{\mathrm{*}}, {\pi }_{1}^{\mathrm{*}}, {\pi }_{2}^{\mathrm{*}}, {\pi }_{3}^{\mathrm{*}}\right) $，根据LWE的假设，$ {\mathrm{G}}_{2} $和$ {\mathrm{G}}_{3} $是统计不可区分的。

$ {\mathrm{G}}_{4} $游戏过程与$ {\mathrm{G}}_{3} $类似，除了$ {\boldsymbol{d}}_{0}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m} $，计算$ {\boldsymbol{c}}_{0}^{\mathrm{*}}={\boldsymbol{d}}_{0}+{\boldsymbol{x}}_{0}^{\mathrm{*}} $，由文献[8]可得，$ {\mathrm{G}}_{3} $和$ {\mathrm{G}}_{4} $不能通过计算区分，则LWE判定问题难以求解，因此，$ {\mathrm{G}}_{3} $和$ {\mathrm{G}}_{4} $是统计不可区分的。

$ {\mathrm{G}}_{5} $游戏过程与$ {\mathrm{G}}_{4} $类似，除了$ {\boldsymbol{c}}_{0}^{\mathrm{*}}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m}, {\boldsymbol{c}}_{1}^{\mathrm{*}}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m} $，在$ {\mathrm{G}}_{4} $中，签名与身份的选取无关，$ {b}^{'}=b $的概率接近$ 1/2 $，因此，敌手$\mathcal{A} $获胜的优势可忽略。

综上所述，在随机预言机模型下，本文方案在LWE假设下是CCA-匿名的。

3.2.2 追踪性证明

定理2  在随机预言机模型下，本文方案在ISIS假设下是CCA-追踪的。

证明：假设敌手$\mathcal{A} $多项式时间内攻破本文方案的追踪性，则可构造一格算法$ \mathcal{C}$解决ISIS问题，即给定矩阵$ \boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m}, \boldsymbol{u}\in {\mathbb{Z}}_{q}^{n} $，寻找一个$ \boldsymbol{x}\in {\mathbb{Z}}_{q}^{m} $，满足$ ‖\boldsymbol{x}‖\le \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(m\right), \boldsymbol{A}\boldsymbol{x}=\boldsymbol{u}\mathrm{m}\mathrm{o}\mathrm{d}\;q $。$ \mathcal{C}$下一步工作为：

1）$ \mathrm{G}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\left({1}^{n}, {1}^{N}\right) $。首先计算$ \left(\boldsymbol{A}, {\boldsymbol{T}}_{\boldsymbol{A}}\right)\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n} $ $ \left({1}^{n}, \right. $ $ \left.{1}^{m}, q\right) $，$ \left(\boldsymbol{B}, {\boldsymbol{T}}_{\boldsymbol{B}}\right)\leftarrow \mathrm{S}\mathrm{u}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\left({1}^{n}, {1}^{m}, q, \boldsymbol{A}, 0\right) $，然后选择$ \boldsymbol{F}\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m\times n} $，高斯采样$ {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{n} $，计算$ {\boldsymbol{v}}_{i}=\boldsymbol{F}\cdot {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{m} $，并设置$ \mathrm{R}\mathrm{L}=\mathrm{\varnothing } $，腐败用户集合$ {U}_{\mathrm{a}}=\mathrm{\varnothing } $，最后将$ gpk=\left(\boldsymbol{A}, \boldsymbol{B}, \boldsymbol{F}, pp, {\boldsymbol{v}}_{i}\right) $，追踪密钥$ gtsk={\boldsymbol{T}}_{\boldsymbol{B}} $发送给敌手$\mathcal{A} $。

2）$ \mathrm{G}\mathrm{U}\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}\left(pp, gmpk, gtpk\right) $。对$ i\in \left[N\right] $，当$ i\ne {i}^{\mathrm{*}} $时，首先对$ {\boldsymbol{v}}_{{i}^{\mathrm{*}}}\in {\mathbb{Z}}_{q}^{m} $做签名$ si{g}_{{i}^{\mathrm{*}}}=\mathrm{S}\mathrm{i}{\mathrm{g}}_{pusk\left[i\right]}\left({v}_{{i}^{\mathrm{*}}}\right) $，并将$ \left({\boldsymbol{v}}_{i}, si{g}_{i}\right) $发送到$ \mathcal{C}$，$ \mathcal{C}$随机选择$ \boldsymbol{R}{\leftarrow }_{\mathrm{R}}{\left\{-1, 1\right\}}^{m\times m} $，从$ I{d}_{i}^{\mathrm{*}}\leftarrow \left\{-4{m}^{2.5}N+1, -4{m}^{2.5}N+2, \cdots , 4{m}^{2.5}N-1\right\} $选择新身份，计算$ \left({\boldsymbol{A}}_{1}, {\boldsymbol{T}}_{{\boldsymbol{A}}_{1}}\right)\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}\left({1}^{n}, {1}^{m}, q\right) $，$ {\boldsymbol{A}}_{0}=\boldsymbol{A}\boldsymbol{R}-I{d}_{i}^{\mathrm{*}}{\boldsymbol{A}}_{1} $；然后计算$ {\boldsymbol{A}}_{\mathrm{I}{\mathrm{d}}_{{i}^{\mathrm{*}}}}=\left[\boldsymbol{A}\left|\right|{\boldsymbol{A}}_{0}+I{d}_{i}{\boldsymbol{A}}_{1}\right]\in {\mathbb{Z}}_{q}^{n\times 2m} $，$ {\boldsymbol{T}}_{{\boldsymbol{A}}_{I{d}_{{i}^{\mathrm{*}}}}}\leftarrow $ $ \mathrm{E}\mathrm{x}\mathrm{t}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\left({\boldsymbol{A}}_{I{d}_{i}}, {\boldsymbol{T}}_{\boldsymbol{A}}, s\right) $，其中，$ {\boldsymbol{T}}_{{\boldsymbol{A}}_{I{d}_{{i}^{\mathrm{*}}}}}\in {\mathbb{Z}}_{q}^{m\times m} $且满足$ ‖{\stackrel{~}{\boldsymbol{T}}}_{{\boldsymbol{A}}_{\mathrm{I}{\mathrm{d}}_{{{}^{i}}^{\mathrm{*}}}}}‖\le s\sqrt{2m} $；再令$ {\boldsymbol{u}}_{{i}^{\mathrm{*}}}=\boldsymbol{A}{\boldsymbol{v}}_{{i}^{\mathrm{*}}}\in {\mathbb{Z}}_{q}^{n} $，计算$ \left({\boldsymbol{x}}_{0}^{\mathrm{*}}, {\boldsymbol{x}}_{1}^{\mathrm{*}}\right)\leftarrow $ $ \mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}\left({\boldsymbol{A}}_{I{d}_{{{}^{i}}^{\mathrm{*}}}}, {\boldsymbol{T}}_{{A}_{I{d}_{{{}^{i}}^{\mathrm{*}}}}}, \beta , {\boldsymbol{u}}_{{i}^{\mathrm{*}}}\right) $且$ {\boldsymbol{x}}_{0}^{\mathrm{*}}, {\boldsymbol{x}}_{1}^{\mathrm{*}}\in {D}_{{\mathbb{Z}}^{m}, \beta } $，并计算撤销标记$ \boldsymbol{r}\boldsymbol{e}{\boldsymbol{g}}_{{i}^{\mathrm{*}}}={\boldsymbol{A}}_{1}{\boldsymbol{v}}_{{i}^{\mathrm{*}}} $；最后向用户$ i $发送成员证书$ cer{t}_{{i}^{\mathrm{*}}}=\left(I{d}_{{i}^{\mathrm{*}}}, {\boldsymbol{x}}_{0}^{\mathrm{*}}, {\boldsymbol{x}}_{1}^{\mathrm{*}}\right) $。

3）查询。敌手$\mathcal{A} $先对用户进行腐败，再做签名查询，过程如下：

（1）腐败。向预言机询问任意用户$ i\in \left[N\right] $的私钥，将$ i $加入到集合$ {U}_{a}=\mathrm{\varnothing } $中，并返回$ {\boldsymbol{z}}_{i} $。

（2）签名询问。敌手$\mathcal{A} $向预言机询问用户关于消息$ m $的签名，并将签名发送给$ \mathcal{C}$。若$ I{d}_{i}=i，$ $ i\notin \left[N\right] $，则$ \mathcal{C}$拒绝接受签名；若$ I{d}_{i}=I{d}_{{i}^{\mathrm{*}}} $，$ \mathcal{C}$对消息$ m $进行签名并利用NIZKP模拟器产生$ {\pi }_{0}^{\mathrm{*}}\sim{\pi }_{3}^{\mathrm{*}} $，否则，将在私钥询问阶段中用回答的签名私钥作为$ I{d}_{i} $对消息$ m $签名。

4）伪造。设成功伪造有效签名$ \varSigma =({\boldsymbol{c}}_{0}, {\boldsymbol{c}}_{1}, {\boldsymbol{x}}_{1}, {\pi }_{0}, $ $ {\pi }_{1}, {\pi }_{2}, {\pi }_{3}) $的概率为$ \varepsilon $，利用随机预言机对$ {\boldsymbol{z}}_{i} $和$ {\boldsymbol{e}}_{0}, {\boldsymbol{x}}_{0}, I{d}_{i}\le 4\eta {m}^{2} $进行零知识提取，并由文献[21]可得，对于其提取成功的概率为$ \varepsilon \left(\varepsilon /{q}_{h}-{2}^{-t}\right) $，其中，$ {q}_{h} $是敌手$\mathcal{A} $访问hash函数的最大次数，利用$ {\boldsymbol{T}}_{\boldsymbol{B}} $对密文$ {\boldsymbol{c}}_{0} $解密，得到$ {\boldsymbol{e}}_{0}^{'}, {\boldsymbol{x}}_{0}^{'} $。若$ \left({\boldsymbol{e}}_{0}^{'}, {\boldsymbol{x}}_{0}^{'}\right)\ne \left({\boldsymbol{e}}_{0}, {\boldsymbol{x}}_{0}\right) $，则有$ \boldsymbol{A}{\boldsymbol{c}}_{0}=p\boldsymbol{A}{\boldsymbol{e}}_{0}+\boldsymbol{A}{\boldsymbol{x}}_{0}=p\boldsymbol{A}{\boldsymbol{e}}_{0}^{'}+\boldsymbol{A}{\boldsymbol{x}}_{0}^{'} $，因此，$ \boldsymbol{x}=p\left({\boldsymbol{e}}_{0}-{\boldsymbol{e}}_{0}^{'}\right)+\left({\boldsymbol{x}}_{0}-{\boldsymbol{x}}_{0}^{'}\right) $是SIS问题的一个解，且$ ‖\boldsymbol{x}‖\le 8\left(p+1\right)\eta {m}^{2}={m}^{8}\omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{3}\right) $；若$ \left({\boldsymbol{e}}_{0}^{'}, {\boldsymbol{x}}_{0}^{'}\right)=\left({\boldsymbol{e}}_{0}, {\boldsymbol{x}}_{0}\right) $且$ {\boldsymbol{u}}_{i}=\boldsymbol{A}{\boldsymbol{v}}_{i}\in {\mathbb{Z}}_{q}^{n} $，则有$ \boldsymbol{A}{\boldsymbol{x}}_{0}+{\boldsymbol{A}}_{0}{\boldsymbol{x}}_{1}+I{d}_{i}{\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}={\boldsymbol{u}}_{i} $，其中，$ I{d}_{i}=\sum\limits_{i=0}^{l-1}{i{{d}_{i}}{{{\bar{\beta }}}^{i}}} $，$ ‖I{d}_{i}‖<4{m}^{2.5}N<q $。又因为$ {\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}\ne 0 $，$ q $是素数，所以能够求解出$ I{d}_{i} $。若$ I{d}_{i}\ne I{d}_{{i}^{\mathrm{*}}} $，则终止；否则输出$ \boldsymbol{x}={\boldsymbol{x}}_{0}+\boldsymbol{R}{\boldsymbol{x}}_{1} $为所给的ISIS问题的解。因为$ I{d}_{i}\leftarrow \left\{-4{m}^{2.5}N+1, -4{m}^{2.5}N+2, \cdots \right., $ $ \left.4{m}^{2.5}N-1\mathrm{ }\right\} $，所以$ I{d}_{i}=I{d}_{{i}^{\mathrm{*}}} $的概率至少为$ 1/8{m}^{2.5}N $。因为$ I{d}_{i}=I{d}_{{i}^{\mathrm{*}}} $时$ \boldsymbol{A}{\boldsymbol{x}}_{0}+{\boldsymbol{A}}_{0}{\boldsymbol{x}}_{1}+I{d}_{i}{\boldsymbol{A}}_{1}{\boldsymbol{x}}_{1}=\boldsymbol{A}\left({\boldsymbol{x}}_{0}+\boldsymbol{R}{\boldsymbol{x}}_{1}\right)={\boldsymbol{u}}_{i} $，所以ISIS的解$ ‖\boldsymbol{x}‖\le \eta {m}^{2.5}\omega \left(\sqrt{\mathrm{l}{\mathrm{b}}_{}m}\right)={m}^{4.5}\omega \left({\left(\mathrm{l}{\mathrm{b}}_{}m\right)}^{2}\right) $。

由以上所证得，$ \mathcal{C}$解决ISIS问题的概率至少为$ \varepsilon \left(\varepsilon /{q}_{h}-{2}^{-t}\right)/8{m}^{2.5}N $，若$ \varepsilon $是不可忽略的，则$ \varepsilon \left(\varepsilon /{q}_{h}-{2}^{-t}\right)/ $ $ 8{m}^{2.5}N $也是不可忽略的。

综上所述，在随机预言机模型下，本文方案在ISIS假设下是CCA-追踪的。

3.2.3 抗陷害攻击

在本文方案中，用户$ i $的私钥是其通过高斯采样算法采取的短向量$ {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{n} $，进而选取$ F\leftarrow {}_{\mathrm{R}}{\mathbb{Z}}_{q}^{m\times n} $并计算用户$ i $的公钥$ {\boldsymbol{v}}_{i}=\boldsymbol{F}\cdot {\boldsymbol{z}}_{i}\in {\mathbb{Z}}_{q}^{m} $。若群管理员或其他合谋群成员想伪造$ i $的签名，就必须要产生一个非交互零知识$ {\pi }_{3} $，又由于零知识证明$ {\pi }_{3} $具有可靠性，不知道$ {\boldsymbol{z}}_{i} $的群管理员或其他群成员无法产生一个能通过验证的$ {\pi }_{3} $，因此本文方案能够抵抗陷害攻击。

4 效率分析

选取以下4个方案：文献[8]格上高效的群签名方案，文献[11]格上具有高效协议和动态群签名的签名方案，文献[13]格上具有本地撤销机制的群签名方案，文献[14]适合大群组的格基动态群签名方案，从公私钥大小、签名大小、加入代价、撤销代价以及是否为完全动态群签名等方面与本文方案进行比较，如表 2所示。其中，$ n $为安全参数，$ N $为群成员个数，$ q\in \mathbb{Z} $为模数，$ m=6{n}^{1+\delta } $，$ t=\omega \left(\mathrm{l}\mathrm{b}\;n\right) $为零知识证明中证明者和验证者间交互的次数，$ V $为一次签名运算时间，$ {T}_{1} $为一次随机采样算法时间，$ {T}_{2} $为一次数乘运算时间，$ {T}_{3} $为一次特殊采样算法时间（耗时较少的运算如矩阵-矩阵加法、向量-向量加法，运算时间忽略不记）。

由表 2可知：文献[8]方案中公私钥大小均为$ O\left(mn\mathrm{l}{\mathrm{b}}_{}\;q\right) $，签名大小为$ O\left(tmn\mathrm{l}{\mathrm{b}}_{}\;q\right) $（$ t=\omega \left(\mathrm{l}{\mathrm{b}}_{}n\right)>1 $），与群成员数量$ N $无关，但该方案不具有加入和撤销机制，属于静态群签名；文献[11]方案为具有加入机制的部分动态群签名方案，但公钥大小与成员数量相关，不适合大群组的群签名系统，加入过程与本文方案相比虽然减少了1次特殊采样运算，但增加了$ 3nm $次数乘运算和2次随机采样运算；文献[13]方案为具有撤销机制的部分动态群签名方案，但公私钥大小、签名大小均与群成员数量$ N $有关，不适合大群组的群签名系统；文献[14]方案是同时具有加入和撤销机制的全动态群签名方案，其签名大小虽比本文方案的签名短，但在加入过程中与本文方案相比增加了$ 4nm $次数乘运算时间、2次随机采样算法的时间以及1次特殊采样算法时间，在撤销过程中增加了1$ mn $次的数乘运算时间；本文方案是具有加入和撤销机制的完全动态群签名方案，其加入、撤销代价较小，并且签名尺寸为$ O\left(tmn\mathrm{l}{\mathrm{b}}_{}\;q\right) $，公钥尺寸为$ O\left(mn\mathrm{l}{\mathrm{b}}_{}\;q\right) $，签名私钥尺寸为$ O\left(m\right) $，均与群成员的数量$ N $无关，因此，本文方案也是适合大群组的群签名方案。

5 结束语

群签名的加入与撤销机制及其密钥与签名的长度，始终是密码学领域研究者所关注的重点问题。本文将动态群签名思想引入文献[8]群签名方案，提出一个具有加入和撤销机制的格上完全动态群签名方案。在安全性方面，随机预言机模型下该方案基于ISIS和LWE假设是可证明安全的，能够抵抗量子攻击，同时也能避免陷害攻击；在效率方面，该方案不仅能够实现加入和撤销功能，而且复杂度较低。此外，其签名和密钥长度均较短且与群成员的数量无关。本文方案中群成员的加入需要群管理员颁发数字证书，这会增加群成员的加入开销和数字证书的存储开销，下一步将对此进行改进，设计无证书的动态群签名方案。