群签名由Chaum等人[1]在1991年提出，是密码学领域中的一个重要概念.在群签名中，合法群成员能够代表整个群进行签名，但是无法通过签名来确定签名者的身份信息，即群签名有匿名性.此外，当有争议发生时，群管理员能够利用追踪密钥打开签名并得到签名者的真实信息，即群签名有可追溯性.匿名性和可追溯性使得群签名能够在多种场景下得到应用，例如，匿名电子投票、受信计算平台以及电子商务系统等.

近几年，量子计算机的研究不断取得突破，一旦量子计算机得到应用，基于传统数论难题构造的群签名就能够在概率多项式时间(probabilistic poly-nomial time, PPT)内被攻破，因此建立在最坏情况困难性假设上的格密码成为了后量子密码时代的研究热点.2010年，Gordon等人[2]在随机预言模型下提出了第1个格上的群签名方案，并且将该方案的匿名性和可追溯性分别规约到容错学习(learning with errors, LWE)问题和GapSVP(gap shortest vector problem)问题，但其密钥和签名的开销过大.随后，Laguillaumie等人[3]提出了一种更为高效的格上群签名方案，将其方案的可追溯性规约至小整数解(short integer solution, SIS)问题上，同时优化了密钥长度和签名长度，但代价是公共参数开销较大.2015年，Nguyen等人[4]和Ling等人[5]设计了2种不同的格上群签名方案，前者使用了与身份编码技术相结合的非交互零知识证明协议，使得该方案的结构更为简单，而后者基于多项式环以及环上小整数解(ring short integer solution, RSIS)、环上容错学习(ring learning with errors, RLWE)问题，具有更低的存储开销和时间复杂度.张彦华等人[6]利用文献[4]提出的身份编码技术构造了支持验证者本地撤销的群签名.Libert等人[7]基于Merkle Hash树以及Stern非交互式零知识证明协议，提出了第1个不依赖GPV陷门[8]的格上群签名方案.2017年，Ling等人[9]提出了完全动态的群签名方案，允许用户动态地加入和离开群组，李雪莲等人[10]在此基础上构造了新的群成员撤销机制，支持动态地加入和撤销用户.2018年，Ling等人[11]提出了固定签名长度的群签名方案，该方案利用Ducas等人[12]提出的签名算法设计了零知识证明协议，使密钥大小和签名大小都与用户成员数N无关.Pino等人[13]基于小型的零知识证明[14]构造了计算效率更高和存储开销更小的群签名方案.2019年，Katsumata等人[15]提出了标准模型下的格上群签名，该方案没有使用零知识证明系统，提高了运算效率，且满足CCA(chosen ciphertext attack)自身匿名性和完全可追溯性.2020年，Sun等人[16]和Canard等人[17]在文献[15]的基础上进行了改进.但上述的格上群签名方案均基于传统公钥基础设施(public key infrastructure, PKI)进行构造，无法抵抗公钥伪造攻击，且存在PKI体系中复杂的用户证书管理问题.

基于身份的加密体制(identity based encryption, IBE)是另一种密码学原语，由Shamir[18]于1984年提出.在基于身份的密码体制中，密钥生成中心(key generation center, KGC)根据用户的身份信息，例如：姓名、身份证号、电子邮箱等生成用户公钥，并使用用户身份信息和系统私钥计算生成对应的私钥并发放给用户，有效地避免了PKI体系中公钥证书管理的问题.Ibraimi等人[19]、Emura等人[20]分别提出了基于身份的群签名方案，但都基于有限域离散对数的传统数论难题，难以抵抗量子算法的攻击.

本文将格上的群签名与基于身份加密体制相结合，提出了一种格上基于身份的群签名方案.主要贡献有2个方面：

1) 通过环上陷门生成算法[5]生成系统公钥和系统主密钥，再利用格基委派技术[21]和原像采样算法生成用户私钥，采用拒绝采样算法[22]和经过Naor-Yung变换[23]的双重加密算法[24](LPR加密算法)生成签名.在Bellare等人[25]的群签名安全模型下，对所提方案进行严谨的安全证明.证明结果表明，在随机预言模型下，所提方案满足正确性、完全匿名性、不可伪造性以及完全可追溯性.其中，完全匿名性可规约至RLWE困难性假设，不可伪造性和完全可追溯性可规约至RSIS困难性假设.

2) 将本文方案与4个现有的格上群签名方案[7,9,11,26]进行了效率比较，分析比较结果表明，与其他方案相比，本文方案具有更小的密钥和签名尺寸.且由于使用了拒绝采样技术，本文方案在签名时避免零知识证明系统的并行重复，有效地提高了签名和验证过程的计算效率.

1 预备知识

1.1 符号说明

表1对本文出现的符号进行简要的说明.

1.2 格的相关定义

定义1. 系数映射和环同态映射.给定多项式v=v0+v1x+…+vn-1xn-1∈Rq，令τ(v)=(v0,v1,…,vn-1)T∈令Rot(v)=(τ(v),τ(v·x),…,τ(v·xn-1))∈对于Rot(A)=(Rot(a1),Rot(a2),…,Rot(am))∈

定义2. RSISn,m,q,β问题[11,27-28].给定安全参数n以及1个均匀随机的矩阵寻找1个非零向量u=(u1,u2,…,um)T∈Rm满足Au=a1u1+a2u2+…+amum=0 mod q且‖x‖∞≤β.当参数满足m>log q/log(2β)，γ=16βmn log2n时，RSISn,m,q,β问题至少和Ideal-SVPγ问题一样困难.

定义3. DRLWEn,m,q,χ问题[24].给定n,m≥1，q≥2，R上的一个概率分布χ.对于s∈Rq，随机选取a←Rq和e←χ，定义由(a,b=a·s+e)产生的分布为As,χ.DRLWEn,m,q,χ问题是指判别m个样本是取自分布As,χ还是取自分布U(Rq×Rq).

当q=poly(n)为素数，为整数，χ为R上以B为边界的分布，γ=n2(q/B)·(nm/log(nm)1/4)时，DRLWEn,m,q,χ问题至少和Ideal-SVPγ问题一样困难.

1.3 离散高斯分布和拒绝采样算法

定义4. 离散高斯分布给定格Λ，标准差σ>0和中心向量c∈Rm，对于∀x∈Λ，有其中ρσ,c(x)=exp(-π‖x-c‖2/σ2).

当c=0时，Rm上的高斯分布和格Λ上的高斯分布可以简记为和高斯分布具有以下性质：

引理1[13]. 给定σ>0，正整数m，和任意正整数k>0，则式1)～2)成立：

引理2. 拒绝采样算法[22].令V={v∈为1个概率分布，则存在常数M=O(1),使得2个算法①～②的输出在统计上的距离小于2-ω log m/M：

①以的概率输出(z,v);

②以1/M的概率输出(z,v).其中①输出的概率最小为

1.4 相关算法

给定安全参数n，素数q=poly(n)，m≥2n log q以及有引理3～5：

引理3. 陷门生成算法[5,8].输入参数n,m,q，存在多项式时间算法TrapGenRq(m,q)→(A,TA)，其中为的1组基(满足ATA=0 mod q)，且

引理4. 原像采样算法[5,8].给定基TA，高斯参数σ以及任意多项式u∈Rq，存在PPT算法SamplePreRq(A,TA,u,σ)，通过高斯分布采样1个多项式满足Ax=u mod q.

引理5. 格基委派算法[21].给定随机矩阵A∈的基TA，可逆矩阵R∈m×m以及标准差其中存在格基委派算法BasisDel(A,R,TA,σ)输出1个矩阵B=AR-1∈和的基TB，其中

2 基于身份的群签名定义及安全模型

定义5. 基于身份的群签名.结合Bellare等人[25]和Shamir[18]的定义，1个基于身份的群签名方案有5个多项式时间算法：

1) Keygen(1n,1N).输入安全参数n和群成员的最大可能个数N，输出系统公钥PK，管理员追溯密钥gtk以及系统主密钥gmk.

2) Extract(PK,gmk,IDπ).输入系统公钥PK，系统主密钥gmk以及用户π的身份信息IDπ，输出用户私钥gskπ=(xπ,1,xπ,2).

输入系统公钥PK，用户π的私钥gskπ，待签名消息m∈{0,1}*以及群成员的身份集合输出用户π对消息m的签名Σ.

输入系统公钥PK，待验证消息m∈{0,1}*及其对应的群签名Σ，群成员的身份集合若Σ为m的合法群签名，则验证者返回“Valid”，否则返回“Invalid”.

输入系统公钥PK，验证消息m∈{0,1}*及其对应的群签名Σ，管理员追溯密钥gtk以及群成员的身份集合若Σ为m的合法群签名，则管理员得到签名者的身份信息，否则返回“⊥”.

基于身份的群签名需要满足正确性、匿名性、不可伪造性和完全可追溯性.其中，群签名的正确性包括验证正确性和打开正确性；匿名性是指攻击者无法确定一个群签名具体是由群中哪个用户生成的，而本文方案具有的完全匿名性又称作CCA匿名性[4,15]，是指在允许攻击者A进行签名问询和打开问询后仍然能够保持签名的匿名性，具体见定义6；不可伪造性是指在没有群成员签名密钥的情况下，攻击者无法生成有效的群签名，具体见定义7；完全可追溯性是指任意1个合法的群签名一定能够被群管理员通过追踪密钥打开，具体见定义8.本文通过攻击者A和挑战者C之间进行的一系列游戏来刻画基于身份群签名的安全性定义.在随机预言模型下，攻击者A能够访问随机预言机并且向挑战者C进行3种问询：

1) 签名问询.攻击者A选择群中成员j∈[N]以及待签消息m∈{0,1}*进行问询，C运行Signature()签名算法使用IDj对应的私钥gskj对m进行签名，并返回对应的Σ给A.

2) 私钥问询.A选择群中成员j∈[N]进行问询，C运行Extract()私钥提取算法返回IDj对应的私钥gskj.

3) 打开问询.A选择消息m∈{0,1}*及其对应的群签名Σ进行问询，C运行Opening()打开算法，如果Σ由群中用户j∈[N]合法产生，则返回用户j的身份信息IDj，否则返回⊥.

定义6. 完全匿名性[4,15].与CPA匿名性不同，完全匿名性(CCA匿名性)是指挑战者C在问询阶段授予攻击者A签名问询和打开问询的权限，攻击者A赢得4个阶段的游戏的优势仍然是忽略的:

1) 系统建立.挑战者C输入安全参数λ和用户数N诚实地运行Keygen(1n,1N)算法，得到系统公钥PK管理员追溯密钥gtk以及系统主密钥gmk，将系统公钥PK和群用户私钥gskj发送给攻击者A.

2) 问询阶段.攻击者A可以访问预言机并进行系统建立阶段的签名问询和打开问询.

3) 挑战阶段.攻击者A选取消息m*∈{0,1}*和2个有效身份发送给挑战者C.C随机选取b*∈{0,1}，并且计算IDb*对应的私钥gskb*，调用Signature()签名算法生成消息m*对应的群签名Σ*，将Σ*返回给A.在此阶段A仍能够继续进行签名问询和打开问询，但是需限制A无法对待猜测的(m*,Σ*)进行打开问询.

4) 猜测阶段.攻击者A对签名者身份进行猜测，得出b*∈{0,1}，若满足条件b*=b，则称A赢得了完全匿名性游戏.

定义A赢得游戏的优势为

定义7. 不可伪造性.群签名的不可伪造性是指攻击者A伪造出1个有效签名的优势是可忽略的，可用攻击者A和挑战者C之间的游戏进行描述：

1) 系统建立.输入安全参数λ和用户数N，挑战者C诚实地运行Keygen(1n,1N)算法，得到系统公钥PK，管理员追溯密钥gtk以及系统主密钥gmk，将系统公钥PK和追溯密钥gtk发送给攻击者A.

2) 问询阶段.攻击者A被允许进行上述的签名问询和私钥问询.

3) 伪造阶段.攻击者A给出关于消息m*的签名Σ*，判断是否满足条件(①～③)：

①

② A未对群成员j∈[N]进行过私钥问询.

③ A未对消息m*以及群成员j∈[N]进行过签名问询.

则返回1；否则返回0.

定义攻击者A赢得不可伪造性游戏的优势为

定义8. 完全可追溯性[15].群签名的完全可追溯性是指，攻击者A生成1个不可打开或者嫁祸群内其他成员的群签名的优势是可忽略的，可以通过如下攻击者A和挑战者C之间的游戏进行描述，其中挑战者C负责维护列表Γ和Ι，并且在游戏开始时设置Γ和Ι为空.

1) 系统建立.挑战者C输入安全参数λ和用户数N诚实地运行Keygen(1n,1N)算法，得到系统公钥PK管理员追溯密钥gtk以及系统主密钥gmk，将系统公钥PK和追溯密钥gtk发送给攻击者A.

2) 问询阶段.攻击者A能够访问预言机并进行上述的签名问询和私钥问询.令Γ用来存储经过私钥问询的j；令Ι用来存储经过签名问询的(j,m).

3) 伪造阶段.攻击者A最终输出一个关于消息m*的签名Σ*，满足如果则返回1；如果其中j*∉Γ且(j*,m*)∉Ι，则返回1.其余情况，返回0.

定义A赢得完全可追溯游戏的优势为

3 方案构造

本文结合引理3～5的算法构造了一个随机预言模型下的格上基于身份的群签名方案，核心思想是使用引理3的陷门生成算法建立，并获得系统公钥和主密钥，然后利用引理5的格基委派技术和引理4的原像采样算法提取用户身份信息并生成用户公私钥.在签名生成阶段使用引理2的拒绝采样技术以一定概率生成签名，并使得签名的概率分布与签名私钥的分布相独立，签名过程中同时使用了LPR双重加密算法，能够将本文方案的完全匿名性规约到RLWE困难假设下.方案的流程图如图1所示.

1) 系统建立Keygen(1n,1N).由KGC输入安全参数n和群成员的最大可能个数N.高斯参数σ1=poly(n)且为正数，β=poly(n)，素数给定多项式环R=[x]/(xn+1)和Rq=R/qR.选择边界参数并且定义错误分布χ为R上以B为边界的分布，高斯参数σ2>nmω(log2m) log q.定义3个Hash函数H1:{0,1}*→{v:v∈(H2:{0,1}*→{v：v∈{-1,0,1}m,‖v‖≤t}，H3:{0,1}*→{c:c∈q}.建立列表且初始化为空.随后按照如下方式生成系统公钥PK和管理员追溯密钥gtk及系统主密钥gmk：

① 通过多项式环陷门生成算法，得到(A,TA)←ΤrapGenRq(m,q)，其中

② 随机选取并且计算b=(as+e) mod q.

③ 随机选取

④ 输出系统公钥PK=(A,B,u,a,b)，追溯密钥gtk=s，主密钥gmk=TA.

2) 私钥提取Extract(PK,gmk,IDπ).此步骤由KGC运行.输入系统系统公钥PK，系统主密钥gmk以及用户身份IDπ，KGC进行如下操作提取用户私钥：

①

② 令gπ与KGC本地的列表进行对比，如果gπ与已有的某个gi,i∈{1,…,N}值相等时，重新进行步骤①；否则将gπ存入列表中.

③ 计算H1(IDπ)，将H1(IDπ)中的元素按行依次替换等阶单位矩阵中的斜对角元素，得到的对角矩阵为此时Cπ可逆.令运行引理5格基委派算法BasisDel(Rot(A),Rot(Cπ),TA,σ2)，输出Λ⊥(Rot(Dπ))的1组基Tπ∈nm×nm.

④ 计算xπ,2←SamplePreRq(Dπ,Tπ,u-gπ,σ1).

⑤ 输出用户私钥gskπ=(xπ,1,xπ,2).

3) 签名算法输入系统公钥PK，用户π的签名私钥gskπ，待签名消息m∈{0,1}*以及群成员的身份集合进行如下运算：

① 利用LPR双重加密算法[24]，随机选取e1,e2,e3←χl,s1←χ,计算gπ=Bxπ,1 mod q,令为gπ的二进制形式，计算t1=as1+e1，t2=

② 根据每个用户的身份信息IDi计算出对应的Di，随机选取计算令c′∈{0,1}l为c的

二进制形式,并计算t3=bs1+e3+q/2c′.

③

④ 当i≠π时，zi,1=yi,1，zi,2=yi,2；当i=π时，利用拒绝采样算法，以的概率得到zi,1=xi,1v1+yi,1，zi,2=xi,2v1+yi,2.

⑤ 输出用户π对m的群签名Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3).

4) 验证算法输入系统公钥PK，待验证消息m∈{0,1}*及其对应的群签名Σ，群成员的身份集合进行如下操作：

① 根据每个用户的身份信息IDi计算对应的Di，计算判断是否成立.

② 判断是否成立.

③ 如果步骤①和②都成立，则验证者返回“Valid”，即认为群签名Σ为群中某一成员对消息m的有效签名；否则验证者返回“Invalid”.

5) 打开算法输入系统公钥PK，待打开的签名Σ及其对应的消息m，管理员追溯密钥gtk，群成员的身份集合在进行打开算法前首先对签名进行验证，若该签名为有效群签名，则进行如下计算：

① 令对于1≤i≤l，判断如果则令否则，令计算

② 令利用步骤①中同样的方式恢复出c.

③ 根据每个用户的身份信息IDi计算出对应的Di，验证gk是否满足等式

且gk能够被管理员在KGC的列表中找到.

④ 如果步骤③成立，则证明打开成功，并且返回用户身份IDk；否则打开失败，返回“⊥”.

4 安全性证明

此部分对所提方案的正确性、完全匿名性以及完全可追溯性3个重要的安全属性进行详细的证明，并且将完全匿名性和完全可追溯性分别规约到RLWE和RSIS问题上.

定理1. 正确性.本文提出的方案是正确的，即一个真实的签名是能够被成功验证和打开的.

证明.

1) 验证正确性.

假设Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)是群中用户π对消息m按照签名算法产生的签名，则下列等式成立：

当i≠π时，由引理1可以得出所以是压倒性概率成立的.当i=π时，zi,1=xi,1×v1+yi,1,zi,2=xi,2×v1+yi,2通过拒绝采样生成，其中根据引理2可知，zi,1,zi,2与高斯分布在统计上是不可区分的，统计距离为2-ω log n/M.因此是以压倒性概率成立的.

本方案的验证正确性得以满足.

2) 打开正确性.

假设Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)是群中用户π对消息m的有效签名.

注意其中‖e1‖∞,‖e2‖∞,‖e3‖∞,‖s1‖∞≤B，此时有

‖es1+e2-e1s‖∞

因此可得如果则令中的分量否则令重的分量最终可以计算出同理可以恢复出c.如果该签名为合法群成员的有效签名，可以得出且下列等式可以满足：

可得

本方案的打开正确性得以满足.证毕.

定理2. 完全匿名性.在DRLWEn,l,q,χ问题的假设下，本文的方案在随机预言模型中是完全匿名的.

证明. 下面通过证明G0,G1,G2,G3一系列游戏的不可区分来证明本文方案的完全匿名性.

1) G0. G0为挑战者C诚实地运行本文方案，输入安全参数λ，最大可能群用户生成追溯密钥gtk，系统主密钥gmk，系统公钥PK以及用户私钥gski，C将PK和群用户gski发送给攻击者A,A能够向C进行以下问询：

① 签名问询.输入任意明文m∈{0,1}*以及用户i，返回对应的签名Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)给A.

② 打开问询.A选择消息m∈{0,1}*及其对应的群签名Σ进行问询，如果Σ由群中用户j∈[N]合法产生，则返回用户j的身份信息，否则返回⊥.

A提供1个消息m∈{0,1}*和2个有效的身份信息并将m和ID0,ID1发送给C.

C随机选取b←{0,1}，并且计算IDb对应的私钥gskb，调用签名算法返回签名Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3).最终，A输出1个猜测值b′，设b=b′的概率为Pr[G0].

2) G1. G1与G0大致相同，只是在调用签名算法时将i=b时的zi,2=xi,2×v1+yi,2改为

3) G2. 在G1的基础上，将i=b时的zi,1=xi,1v1+yi,1改为此时G2游戏中生成的签名已完全不使用用户的私钥gskb，唯一包含用户有效身份信息的只有t2(t2中含有

4) G3. 在G2的基础上将改为随机选取的向量g*.定义攻击者A在G3中的猜测值b′=b的概率为Pr[G3].

引理6. G1与G0在统计上不可区分.

证明. 由引理2可知，当i=b时，zi,2与高斯分布在统计上的距离是可忽略的(统计距离为同样服从高斯分布所以zi,2与在统计上不可区分，因此G1与G0的统计距离是可忽略的.

证毕.

引理7. G1与G2在统计上不可区分.

证明. 与引理6证明同理可得G2与G1的距离在统计上是可忽略的.

证毕.

引理8. G3与G2在计算上不可区分.

证明. 根据LPR双重加密方案[24]可知，改变g′对于攻击者A是不可区分的，即A无法区分和所以A无法区分G3和G2.

证毕.

G3可以看作是经过Naor-Yung变换[23]的LPR加密方案[24]，而该加密方案被证明是IND-CCA安全的.且G3中所得签名均由随机向量构成，所以A已无法从签名中得到任何有关用户IDb的信息.因此，可以计算出Pr[G3]=1/2+negl(n).由引理6～8可得，G0,G1,G2,G3在统计和计算上是不可区分的，因此得出A赢得G0的概率为Pr[G0]=1/2+negl(n)，即A攻破G0的完全匿名性的优势是可忽略的，而G0是挑战者C诚实执行本文方案后进行的交互游戏，因此A攻破本方案的完全匿名性的优势是可忽略的.

证毕.

定理3. 不可伪造性.在RSISn,m,q,β问题的假设下，本文方案在随机预言模型下满足不可伪造性.

证明. 假设攻击者A以不可忽略的概率ε伪造出有效的签名，则挑战者C利用A伪造的结果构造1组RSIS问题的非零解.首先C输入安全参数λ，建立用户群诚实地运行Keygen(1n,1N)算法，生成gtk,gmk,gski,PK，将PK和gtk发送给A.A被允许多项式次访问预言机进行Hash、私钥、签名问询，C进行以下回复：

1) Hash问询.A输入消息m以及t1,t2,t3，C随机选取v∈{-1,0,1}m发送给A，并将(m,(yi,1,yi,2)1≤i≤N,v,t1,t2,t3)加入Hash问询列表.

2) 私钥问询.A输入运行Extract(PK,gmk,IDπ)算法计算k对应的私钥gskk，将其加入至私钥问询列表，并将结果返回给A.

3) 签名问询.A输入和消息m，C将签名算法中的zi,1和zi,2修改为zi,1=yi,1，zi,2=yi,2，并返回签名((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)并将(k,m)加入到签名问询列表.

最终，A伪造出1个关于消息m，群成员的签名满足且私钥问询列表和签名问询列表中不存在和消息m.通过分叉引理[29]可知，A至少能够以ε(-2-n)的概率输出2个伪造签名和且其中h1≥2为Hash函数H2输出的长度.

由于A伪造的签名和满足正确性，对于有以下等式成立：

对于有以下等式成立：

对上式化简可得

(1)

(2)

联立式(1)(2)后，得到

由于因此根据引理6可知,有效签名与签名预言机返回的模拟签名的统计距离是可忽略的，因此得到

由于因此挑战者C利用A的伪造结果构造出了问题的解.

证毕.

定理4. 完全可追溯性.在问题的假设下，本文的方案在随机预言模型下是完全可追溯的.

证明. 假设攻击者A以不可忽略的概率成功伪造不可追溯的签名，则挑战者C利用A伪造的结果构造1组RSIS问题的非零解.首先C将列表Γ，I，L初始化为空，输入安全参数λ和最大用户群随机选定j∈{1,2,…,N}，并诚实地运行本文方案，生成gtk,gmk,gski,PK，将PK和gtk发送给A，对于A的询问，C进行以下回复：

1) 私钥问询.A输入若k=j，C终止游戏；若k≠j，C将k对应的私钥gskk返回给A.令Γ用来存储经过私钥问询的k.

2) 签名问询.A输入和消息m，若k=j，C将签名算法中的zi,1和zi,2修改为zi,1=yi,1，zi,2=yi,2，并返回签名Σ；如果k≠j，C诚实地运行签名算法，并返回签名Σ，令Ι用来存储经过签名问询的(k,m).

3) H2问询.A输入消息m以及t1,t2,t3，C检查列表L，若A进行过相同的询问，则返回相同的询问结果，否则C随机选取v∈{-1,0,1}m发送给A，并将(m,(yi,1,yi,2)1≤i≤N,v,t1,t2,t3)加入列表L.

经过一系列问询过后，A输出1个关于消息m的签名如果该签名Σ*满足定义8，则说明A赢下了完全可追溯游戏.

1) 假设Σ*是一个有效的签名，并且满足由于在随机预言模型中，Hash函数H2出现碰撞的概率可忽略，则会出现以下2种情况：

① 若Σ*中的在签名预言中出现过，假设该签名预言的输出为由于该签名是一个有效的签名，满足

又由于A伪造的签名Σ*能够满足验证正确性，则有

因为H2的碰撞概率可忽略，所以可得此时有

(3)

又因为Σ和Σ*都能够被成功打开并且追溯到j，所以此时有

即

(4)

联立式(3)(4)可得

因为所以是问题的解.

② A通过H2问询得到伪造签名此时L中有存储记录并且满足

由于H2的碰撞概率可忽略，所以可得

由于A伪造的签名具有验证正确性，满足

又因为Σ*能够被打开并追溯到j，所以有

挑战者C进行构造：若k≠j，则zk,1=yk,1,zk,2=yk,2；若k=j，则令此时构造的签名能够满足等式

即Σ通过了验证算法和打开算法.

此时式(3)和(4)成立，联立可得

因为所以是问题的解.

2) 假设Σ*满足此时A伪造的签名满足以下2种情况：

①

②即

由于上述2种情况都能够通过验证算法，所以有

移项可得

因为所以是问题的解.

综上所述，攻击者A若赢得完全可追溯性游戏，则C将求得上述RSIS问题的小整数解，但是在RSIS困难假设下求小整数解是困难的，因此攻击者A无法满足以上2个条件，所以本方案具有完全可追溯性.

证毕.

5 效率分析

选择4个现有的格上群签名方案与本文方案进行对比，分别是Libert等人[7]提出的没有陷门的对数大小的格上群签名、Ling等人[9]提出的基于格的完全动态群签名、Ling等人[11]提出的格上恒定大小的群签名以及Xu[26]提出的前向安全群签名.本文实验针对系统公钥长度、管理员追溯密钥长度、用户私钥长度、签名长度等指标进行对比.

表2为格上群签名在渐进效率方面的对比，其中n为安全参数，N=2为最大群成员个数.由表2可知，文献[7,9,26]的系统公钥、用户私钥以及签名的长度均与最大群成员个数N呈对数关系，而本文方案的和文献[11]方案的公私钥均为固定长度，仅与安全参数n相关.但注意到由于本文要实现的是基于身份的群签名方案，需要采用格基委派技术生成用户的私钥，进而造成所生成签名的长度与N呈线性关系；而其他方案虽然在签名长度方面或与N呈对数关系(文献[7,9,26])，或为固定长度(文献[11])，但它们均不具有基于身份的属性，存在公钥证书管理的负担.为了使比较结果更加直观，本文在保证所提方案满足安全性的前提下，选取了5组特定参数，即和N∈{256,512,1 024,2 048}，对4个方案的系统公钥长度、管理员追溯密钥长度、用户私钥长度及签名长度进行量化对比，比较结果列于表3.

从表3可以看出，当安全参数n=512，最大群成员个数N∈{256,512,1 024,2 048}时，本文方案的公私钥长度在5个方案中最短，平均缩小了79.6%；当N≤1 024时，本文方案的签名长度在5个方案中仍为最短，平均缩小了57.3%；但当N=2 048时，本文方案的签名长度超过文献[7,9,26]的签名长度.综上所述，相较于文献[7,9,11,26]，本文方案的公私钥长度平均缩小了79.6%，签名长度平均缩小了39.9%.

另外，文献[7,9,11,26]的零知识证明系统存在健全性误差，在生成签名时均需要ω(log n)次的并行重复，而本文方案没有使用到零知识证明系统，仅调用1次拒绝采样算法即可实现签名.因此，与同类方案相比，本文方案具有较小的存储开销和计算开销，且更适用于小群组(例如N≤1 024)的场景.

6 结束语

相较于其他群签名，格上的群签名能够抵抗量子算法的攻击，格上基于身份的群签名能够避免复杂的用户公钥证书管理问题，可以有效地应用于匿名电子投票和电子商务系统等领域.本文基于RLWE和RSIS困难假设，在随机预言模型下提出了一个格上基于身份的群签名方案，并给出了详细的安全性证明.与已有的格上群签名方案相比，本文方案没有使用零知识证明，而是通过拒绝采样算法提高签名生成计算效率，密钥尺寸也相较其他方案更具优势，但签名长度与用户数呈线性关系，用户数N≥2 048时签名尺寸相对于其他方案较长.因此，下一步将考虑构造签名长度更短、运行效率更高的格上基于身份的群签名.

作者贡献声明：汤永利指导方案的整体设计、安全性分析以及论文撰写，把握论文整体创新性；李元鸿负责方案拟定、论文撰写以及效率分析；张晓航负责论文图表设计与规划，并参与了实验数据的整理；叶青负责把握论文创新性，并参与数学公式校对和方案效率分析.

参考文献

[1]Chaum D, Heyst V E. Group signatures[G] //LNCS 547: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1991: 257-265

[2]Gordon S D, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions[G] //LNCS 6477: Proc of the 16th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 395-412

[3]Laguillaumie F, Langlois A, Libert B, et al. Lattice-based group signatures with logarithmic signature size[G] //LNCS 8270: Proc of the 19th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2013: 41-61

[4]Nguyen P Q, Zhang Jiang, Zhang Zhenfeng. Simpler efficient group signatures from lattices[G] //LNCS 9020: Proc of the 18th IACR Int Conf on Practice and Theory in Public-Key Cryptography. Berlin: Springer, 2015: 401-426

[5]Ling San, Nguyen K, Wang Huaxiong. Group signatures from lattices: Simpler, tighter, shorter, ring-based[G] //LNCS 9020: Proc of the 18th IACR Int Conf on Practice and Theory in Public-Key Cryptography. Berlin: Springer, 2015: 427-449

[6]Zhang Yanhua, Hu Yupu, Liu Ximeng, et al. Zero-knowledge proofs for attribute-based group signatures with verifier-local revocation over lattices[J]. Journal of Electronics and Information Technology, 2020, 42(2): 315-321 (in Chinese)(张彦华, 胡予濮, 刘西蒙, 等. 格上本地验证者撤销属性基群签名的零知识证明[J]. 电子与信息学报, 2020, 42(2): 315-321)

[7]Libert B, Ling San, Nguyen K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[G] //LNCS 9666: Proc of the 35th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2016: 1-31

[8]Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C] //Proc of the 40th Annual ACM Symp on Theory of Computing. New York: ACM, 2008: 197-206

[9]Ling San, Nguyen K, Wang Huaxiong, et al. Lattice-based group signatures: Achieving full dynamicity with ease[G] //LNCS 10355: Proc of the 15th Int Conf on Applied Cryptography and Network Security. Cham: Springer, 2017: 293-312

[10]Li Xuelian, Lu Xiaolin, Guo Lijuan, et al. A dynamic group signature scheme based on lattice for large groups[J]. Journal of the University of Electronic Science and Technology of China, 2019, 48(1): 80-87 (in Chinese)(李雪莲, 吕晓琳, 郭利娟, 等. 适合大群组的格基动态群签名方案[J].电子科技大学学报, 2019, 48(1): 80-87)

[11]Ling San, Nguyen K, Wang Huaxiong, et al. Constant-size group signatures from lattices[G] //LNCS 10770: Proc of the 21st IACR Int Conf on Practice and Theory of Public-Key Cryptography. Cham: Springer, 2018: 58-88

[12]Ducas L, Micciancio D. Improved short lattice signatures in the standard model[G] //LNCS 8616: Proc of the 34th Annual Cryptology Conf. Berlin: Springer, 2014: 335-352

[13]Pino R D, Lyubashevsky V, Seiler G. Lattice-based group signatures and zero-knowledge proofs of automorphism stability[C] //Proc of ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 574-591

[14]Baum C, Damgard I, Lyubashevsky V, et al. More efficient commitments from structured lattice assumptions[G] //LNCS 11035: Proc of the 11th Int Conf on Security and Cryptography for Networks. Cham: Springer, 2018: 368-385

[15]Katsumata S, Yamada S. Group signatures without NIZK: from lattices in the standard model[G] //LNCS 11478: Proc of the 38th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Cham: Springer, 2019: 312-344

[16]Sun Yiru, Liu Yanyan. A Lattice-based fully dynamic group signature scheme without NIZK[G] //LNCS 12612: Proc of the 16th Int Conf on Information Security and Cryptology. Cham: Springer, 2020: 359-367

[17]Canard S, Georgescu A, Kaim G, et al. Constant-size lattice-based group signature with forward security in the standard model[G] //LNCS 12505: Proc of the 14th Int Conf Provable Security. Cham: Springer, 2020: 24-44

[18]Shamir A. Identity-based cryptosystems and signature schemes[G] //LNCS 196: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1984: 47-53

[19]Ibraimi L, Nikova S, Hartel P, et al. An identity-based group signature with membership revocation in the standard model, TR-CTIT-10-26[R]. Twente, Netherlands: Centre for Telematics and Information Technology, University of Twente, 2010

[20]Emura K, Miyaji A, Omote K. A revocable group signature scheme with the property of hiding the number of revoked users[G] //LNCS 7259: Proc of the 14th Int Conf on Information Security and Cryptology. Berlin: Springer, 2012: 186-203

[21]Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[G] //LNCS 6223: Proc of the 30th Annual Cryptology Conf. Berlin: Springer, 2010: 98-115

[22]Lyubashevsky V. Lattice signatures without trapdoors[G] //LNCS 7237: Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 738-755

[23]Naor M, Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks[C] //Proc of the 22nd Annual ACM Symp on Theory of Computing. New York: ACM, 1990: 427-437

[24]Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[G] //LNCS 6110: Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 1-23

[25]Bellare M, Shi Haixia, Zhang Chong. Foundations of group signatures: The case of dynamic groups[G] //LNCS 3376: Proc of the Cryptographers’ Track at the RSA Conf 2005. Berlin: Springer, 2005: 136-153

[26]Xu Yanhong. Group signatures with advanced features and lattices[D]. Singapore: Nanyang Technological University, 2018

[27]Lyubashevsky V, Micciancio D. Generalized compact knapsacks are collision resistant[G] //LNCS 4052: Proc of the 33rd Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2006: 144-155

[28]Peikert C, Rosen A. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices[G] //LNCS 3876: Proc of the 3rd Theory of Cryptography Conf. Berlin: Springer, 2006: 145-166

[29]Gama N, Nguyen P Q. Predicting lattice reduction[G] //LNCS 4965: Proc of the 27th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2008: 31-51

Identity-Based Group Signatures Scheme on Lattice

Tang Yongli1, Li Yuanhong1, Zhang Xiaohang2, and Ye Qing1

1(School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454003)2(Henan College of Industry & Information Technology, Jiaozuo, Henan 454003)

Abstract Although the existing group signature schemes on lattice can effectively resist the attacks of quantum computing, it is difficult to avoid the complicated management problem of user’s public key certificate. Based on techniques such as rejection sampling and lattice basis delegation, this paper combines the identity-based encryption with the group signature on lattice to construct an identity-based group signature on lattice in the random oracle model. First of all, the system master key is obtained from the trapdoor generation algorithm; Then, the lattice delegation technology extracts the user’s identity information and obtains the user’s private key. Finally, the signature is generated by using the rejection sampling algorithm instead of the zero-knowledge proof system in the signing stage. Meanwhile, this paper uses the LPR encryption algorithm proposed to ensure that the signature can be opened for group administrator by the traceability key. Security analysis shows that the full anonymity, unforgeability and full traceability of the proposed scheme in this paper can be reduced to the hardness assumptions of RSIS and RLWE. Compared with other group signatures on lattice, the proposed scheme is based on identity-based encryption and has certain advantages in storage overhead. Specifically, the overhead of key and signature are decreased roughly by 79.6%, 39.9%, respectively.

Key words identity-based encryption; lattice; group signature; RSIS; RLWE

中图法分类号 TP309

DOI:10.7544/issn1000-1239.20210930

收稿日期：2021-09-09；修回日期：2022-02-10

基金项目：国家自然科学基金项目(61802117)； 河南省高校科技创新团队支持计划项目(20IRTSTHN013)；河南理工大学青年骨干教师资助计划项目(2018XQG-10)

This work was supported by the National Natural Science Foundation of China (61802117), the Support Plan of Scientific and Technological Innovation Team in Universities of Henan Province (20IRTSTHN013), and the Youth Backbone Teacher Support Program of Henan Polytechnic University (2018XQG-10).

通信作者：张晓航(364210343@qq.com)

Tang Yongli, born in 1972. PhD, professor. Senior member of CCF. His main research interests include information security, computer network and cryptography.

汤永利，1972年生.博士，教授，CCF高级会员.主要研究方向为信息安全、计算机网络和密码学.

Li Yuanhong, born in 1997. Master candidate. His main research interests include information security and cryptography.

李元鸿，1997年生.硕士研究生.主要研究方向为信息安全和密码学.

Zhang Xiaohang, born in 1991. Bachelor, teaching assistant. His main research interest includes computer network.

张晓航，1991年生.学士，助教.主要研究方向为计算机网络.

Ye Qing, born in 1981. PhD, associate professor. Member of CCF. Her main research interests include information security and cryptography.

叶 青，1981年生.博士，副教授，CCF会员.主要研究方向为信息安全和密码学.