Policy-Based Group Signature Scheme from Lattice

Yongli Tang,Yuanhong Li,Qing Ye,＊,Ying Li and Xiaojun Wang

1School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,454000,China

2School of Electronic Engineering,Dublin City University,Dublin 9,Ireland

Abstract: Although the existing group signature schemes from lattice have been optimized for efficiency,the signing abilities of each member in the group are relatively single.It may not be suitable for complex applications.Inspired by the pioneering work of Bellare and Fuchsbauer,we present a primitive called policy-based group signature.In policy-based group signatures,group members can on behalf of the group to sign documents that meet their own policies,and the generated signatures will not leak the identity and policies of the signer.Moreover,the group administrator is allowed to reveal the identity of signer when a controversy occurs.Through the analysis of application scenarios,we concluded that the policy-based group signature needs to meet two essential security properties:simulatability and traceability.And we construct a scheme of policy-based group signature from lattice through techniques such as commitment,zero-knowledge proof,rejection sampling.The security of our scheme is proved to be reduced to the module short integer solution(MSIS)and module learning with errors(MLWE)hard assumptions.Furthermore,we make a performance comparison between our scheme and three lattice-based group signature schemes.The result shows that our scheme has more advantages in storage overhead and the sizes of key and signature are decreased roughly by 83.13%,46.01%,respectively,compared with other schemes.

Keywords: Group signature;policy-based signature;lattice-based cryptography;zero-knowledge proof

1 Introduction

1.1 Policy-Based Signature

Policy-based signature(PBS)is a novel concept of digital signature,which was proposed by Bellare et al.[1]at PKC 2014.PBS requires that signer can only sign documents that satisfy certain policy conditions.The users that do not satisfy the policy conditions cannot possess the ability of legitimate signers,and the signatures will not leak the identity and policy of signers.In [1]introduced two strong security notions:simulatability and extractability.The simulatability means that a legitimate signature is indistinguishable from a simulated signature,which is generated by a signature simulator that does not need signing key or policy;the extractability means that there is an extractor,which is able to extract information of policy and identity from a legitimate signature,but cannot extract from forged signatures generated by an attacker.The simulatability and extractability are strong forms of indistinguishability,and unforgeability respectively according to [1].With the two security notions,PBS will be effectively applied in hierarchical environment.For instance,in an enterprise,the authority expects that the employees in different departments or positions to have different signing abilities.Specifically,the employees in research department can only sign documents related to the research,and employees in finance department can only sign documents related to the finance.In 2016,Cheng et al.[2]constructed a scheme of PBS from lattice assumptions based on a zero-knowledge argument system and Bonsai tree.

1.2 Group Signature

Group signatures (GS) was proposed by Chaum et al.[3],which is an important cryptographic primitive.In GS,legitimate group members can represent the group to sign documents anonymously(anonymity);and the group administrator is allowed to open a signature by the tracking key to obtain the identity of signer(traceability).Due to the two properties of anonymity and traceability,GS can be applied in a variety of scenarios,such as e-commerce systems,trusted computing platforms,electronic voting,and much more.

In recent years,with the breakthroughs in quantum research,GS schemes based on hard assumptions of lattice have attracted the attention of scholars.In 2010,Gordon et al.[4]designed the first GS scheme from lattice in random oracle model(ROM)by the technology of GPV trapdoor,as well as the anonymity and traceability of the scheme can be reduced to the hard assumptions of learning with errors(LWE)and GapSVP respectively.But the storage overhead of keys and signature of their scheme is relatively large,which is linear with the number of group members.In 2013,Laguillaumie et al.[5]constructed a GS scheme with logarithmic size based on the non-interactive zero-knowledge proof of knowledge(NIZKPoK)under the hard assumptions of short integer solution(SIS)and LWE.Since then,a series of GS from lattice based on NIZKPoK have been proposed[6-10],and their storage cost has reached logarithmic size.Later,the constant-size GS are constructed by Ling et al.[11]and Zhang et al.[12].The former is based on the“confined guessing”technique of Ducas et al.signature scheme[13];and the latter uses a compact and scalable identity-encoding technique.Their schemes make the storage cost of keys and signatures independent of the number of group members.However,the NIZKPoK in the above GS schemes needs enough parallel repetition during execution due to its soundness error.This will cause a large cost of parameter and time so that the size of the keys and signature is still large,although it is independent of the number of group members.Therefore,Pino et al.[14]designed a new zero-knowledge proof protocol based on the signature scheme of[15]under the hard assumptions of MSIS and MLWE.Since this protocol limits the size of the message and challenge space,it has a smaller cost of parameter and time compared to other zero-knowledge proof protocols.The GS scheme based on this protocol also has more advantages in the storage overhead of the key and signature.Similarly,Boschini et al.[16]constructed a floppy-sized GS scheme by relaxed zero-knowledge proofs under the hard assumptions of ring short integer solution (RSIS) and ring learning with errors (RLWE).In 2019,a GS scheme without NIZK from lattice was designed by Katsumata et al.[17],but this construction requires a combination of attribute-based encryption and signatures.In 2020,Sun et al.[18]and Canard et al.[19]designed an improved scheme based on[17].In conclusion,with the deepening of research in the field of GS from lattice,the size of GS has been effectively reduced.However,the above GS schemes from lattice are just be applied in the scenarios where the signing capabilities of the group members are relatively consistent.However,the different signing capabilities of each group member are necessary for the GS scheme in actual scenarios,i.e.,enterprises involving multiple departments,electronic voting for multiple regions,and much more.Therefore,GS requires a new primitive to be suitable for more extensive scenarios.

1.3 Our Contributions

In this work,we will define a concept of policy-based group signature(PBGS)based on previous work.Consider the following simple situation:Alice,Bob and Carol are employees of a company.The former two are from the research department and the latter is from the finance department.The authority of the company wants to develop a policy,which Alice,Bob and Carol are only allowed to sign documents that only related to their own department.At the same time,the signatures they generate can represent the company,and the identity of the signer will not be leaked.But if one day a document related to the research department causes a dispute(assuming Bob is the actual signer),the administrator of the company should be allowed to recover the identity of the signer(Bob)by the tracking key.In the above case,Alice,Bob and Carol are required to have different signing capabilities.Thus,the previous GS are not suitable.However,for PBGS,the authority wishes that Alice,Bob and Carol will be distributed signing keys and policies related to the department so that their signing capabilities will differ depending on the policy.The group member will not be able to sign when his policy does not satisfy some relationship with the document to be signed(unforgeability);Alice,Bob,Caro,or other outsiders of the company are unable to know the identity of the signer from a signature(simulatability).Even if given a signature related to the finance department,of which Carol is the only one employee,Carol is still anonymous due to the distribution of policies is a secret.The identity of the signer will be recovered through the PBGS administrator by the tracking key (traceability).In conclusion,the PBGS scheme in the application scenario needs to meet the following security requirements:simulatability,unforgeability and traceability.However,according to the definition of[20],unforgeability is unnecessary for GS because traceability has implied unforgeability.The same is true for the extractability defined in PBS.Therefore,we have extracted two security properties for PBGS:simulatability and traceability.With the above two security properties,PBGS will be applied in a wide range of fields.In addition to the enterprises involving multiple departments,the application of PBGS also includes hierarchical electronic voting for multiple regions,digital copyright management,and much more[21-23].

We show a construction of policy-based group signatures from lattice for the above primitive of PBGS,and it can resist the attacks of existing quantum algorithms.Our scheme satisfies the simulatability and full traceability in ROM under the security model of PBGS defined in Section 3.2.And the simulatability and full traceability are proved to be reduced to MLWE and MSIS assumptions,respectively.In terms of efficiency analysis,our scheme is compared with the three schemes of GS from lattice[11,16,17]in storage overhead.The analysis results show that the storage costs of our scheme are totally independent of the number of group members.The size of the key and signature are of order.Specifically,the size of the signature under a set of practical parameters is decreased roughly by 46.01%on average compared to the schemes of[11,16,17].And the size of keys also decreased roughly by 83.13%.

1.4 Our Techniques

At a high level,our PBGS scheme follows a template similar but not identical to the conventional GS defined by Bellare et al.[20].In conventional GS,the public key,master key and traceability key are generated during the setup phase.But for PBGS,the policy relation also needs to be established to limit the signing ability of group members in the initial phase.After that,the key generation center(KGC)will distribute the policy and the signing key to the group members.During the signature generation process,an efficient NIZKPoK about policy and signing keys is generated by group members.But if the policy of group members cannot satisfy the policy relation with the message to be signed,the signature algorithm will not be executed.Finally,in order to ensure full traceability,a verifiable encryption for identity will be generated by the group members.And then,the group administrator is allowed to decrypt the identity of the signer by the tracking key.

Specifically,we first review the requirements of policy language defined by [2]:(1) the space of messageMshould be large enough,and the space of policypcould be relatively small;(2)a policypmay simultaneously satisfy a lot of messagesM;(3)a messageMcould possibly satisfy a lot of policiesp.An instantiation for the above requirements of policy relation is constructed by Cheng et al.[2].In particular,given a positive integerℓ,n,d,if a signer with the policyp∈{0,1}ℓis allowed to sign a messageM∈Zn2,there is a witnessw∈{0,1}dsatisfyingG1·p+G2·w=M(mod2),wheren-ℓ＜d,G1∈is a uniform random matrix,andG2∈is an approximate identity matrix.We define the relation as:PR({0,1}ℓ×Zn2)×{0,1}d→{0,1}.That is,PR((p,M),w)=1 ⇔G1·p+G2·w=Mmod 2.

It satisfies the above requirements of the policy language,and its hardness is based on the LWE hard assumption.

In the signature generation phase,the signer needs to possess policyp,witnessw,and signing keysin order to sign a messageMthat satisfies the policyp,among which the signing keysis obtained by preimage sampling introduced in [24].Specifically,we first generate a trapdoorRin the setup phase.After that,sis obtained through preimage sampling algorithm,which is executed by KGC through inputting parameters such as the policyp,the identity of signer and the system public key.Then,sandpconstitute a secret pair(p,s).At the moment,the two facts about the secret pair(p,s)and the policy relation have been possessed for the signer.In order to convince the verifier,the signer needs to generate a NIZKPoK about the linear relation for the two facts.The technically challenging question is that policypsatisfies two relations at the same time.Hence it is the key to construct a suitable proof protocol.We will show a new proof protocol based on the linear relation proof from[14]to prove the above facts,and it will be applied to our PBGS scheme after Fiat-Shamir transformation.Furthermore,in order to ensure the full traceability,we will integrate an efficient commitment technology from[25]to generate commitmentCom(i,r)about the signer’s identityiand a randomrduring the signing process.Then the randomrwill be encrypted by the technology of verifiable encryption from [26].And the ciphertext and the transcript of the above NIZKPoK will be formed a signature,which will be verified in the verification algorithm.After that,the group administrator can obtainrthrough using the tracking key to decrypt the ciphertext,and then open the commitmentCom(i,r)to obtain the signer’s identityi.

2 Preliminaries

2.1 Symbol Definition

The symbols that appear in this article are described in Tab.1.

Table 1:Symbol definition

2.2 MSIS and MLWE

Definition 1(MSISl,m,β[27]) Given parametersl,m,βandA∈,the MSISl,m,βis defined as:Findingz∈Rmsuch thatAz=0 and 0＜||z||∞≤β.

Lemma 1[27]For anyβ=poly(d),m≥1,ε＞0,γ≥MSISl,m,βis as difficult as the SIVPγproblem at least.

Definition 2(MLWEm,n,χ[27])Given parametersm,nand error distributionχ={a∈R,||a||∞≤1}.For(s,e)←χn×χmandA←,the MLWEm,n,χis defined as:Distinguishing samples chosen from(A,As+e)and samples chosen from uniform distribution(A,b)

Lemma 2[27]Form,n＞0,α∈(0,1),ε＞0,andq≥2,the MLWEm,n,χis as difficult as the SIVPγproblem at least.

As discussed in [28],the practical hardness of the above assumptions is not affected by the parametermto resist known attacks.Therefore,the assumptions will be simply written MSISl,βand MLWEn,χby omitting them,where thelandnrepresent the module ranks for MSIS and MLWE,respectively.

2.3 Discrete Gaussian Distribution and Rejection Sampling

Given anyσ＞0,vectorc∈ R and functionρσ,c(x)=Then the Gaussian distributionDσ,ccentered incis described as:

Dσ,c(x)=

We will simply writeDσwhenc=0.And if the polynomialx∈R,x←Dσis defined as every coefficient ofxobeying distributionDσ.

Lemma 3[14]For anyσ＞0,positive integernandk＞0,the following formulas holds:

At EUROCRYPT 2012,Lyubasevsky introduced an algorithm of rejection sampling,which can be executed with a certain probability.The description is as follows:

Algorithm 1:Rej(z,b,σ)u ←[0,1)If u＞ 1 3 ·exp(-2〈z,b〉+||b||2 return 0 else return 1 end if 2σ2 )then

Lemma 4 [14,29,30]ForV={v∈Rn:||v||＜t},b∈Rnandσ≥11||b||,a procedure will be run by samplingy←Dnσand outputs Rej(z:=y+b,b,σ).Then the probability of returning 1 in Algorithm 1 is within 1/3+2-100.And the statistical distance between the distribution ofzandDnσis within 2-100when the Algorithm 1 outputs 1.

2.4 Trapdoor from Lattice

Lemma 5[16,24,31]Given positive integern,m,q,i,parameterσ=q1/m·polynomialA∈ 1R1×nandR←χn×m.Set the gadget matrixgT=[1q1/m...q(m-1)/m].LetB=AR∈R1×m,we will get a basisS∈Z(n+m)d×(n+m)forΛ⊥={x∈Rn+m|[A|AR+igT]·x=0(modq)},which fulfills |||| ≤(s1(R)+1)after Gram-Schmidt orthogonalization,whereands1(R)means maximal singular value ofR.And then for any polynomial vectoru∈R,there is an algorithm SampleD(A,B,R,u,σ),which is able to sample from distributionwith a certain probability.

2.5 Commitments

Definition 3(Commitment [25]) Given challenge spaceC={c:c∈R,||c||1=κ,||c||∞=1},public matricesFor the messagem∈Rlqto be committed and the randomr←χk,an effective commitment will be generated as follows:

If the following equation holds:

We call(m,r,c)is a valid opening of commitment.

Lemma 6[25]The above commitments have the following properties:

(1) (Binding) Letκ≥if an attackerAwho has advantageεin outputting a commitment through two valid(m,r,c)and(m′,r′,c′)such thatm≠m′,there is an algorithmA′who has advantageεin solving the MSISn,4κBComwithin the same time.

(2) (Hiding)Form,m′∈Rl q,if an attackerAhas advantageεin distinguishing betweenCom(m,r)andCom(m′,r′),there is an algorithmA′that has advantageε/2 in solving the MLWEk-n-l,χin the same time.

The detailed proof of the above lemma could be found in the work[14,25].

3 Definition of Policy-Based Group Signature and Security Model

3.1 Definition

Definition 4(PBGS) A policy-based group signature composed of five polynomial-time algorithms:

(1) GSetup(1λ):It takes the security parameterλas input,builds the policy relation PR((p,M),w)and outputs group public key gpk,group master private key gmk and administrator tracking key gtk.

(2) KeyGen(gmk,p,i):It takes the group master private key gmk,policypand member identityi∈[N]as inputs,outputs a signing key skp,iof memberiabout the policyp.

(3) Sign(skp,i,M,w):It takes the signing key skp,i,a messageMand a witnesswas inputs,outputs a signature ∑if the policy relation satisfies PR((p,M),w)=1,or ⊥otherwise.

(4) Verify (gpk,∑,M):It takes the group public key gpk,a signature ∑and a messageMas inputs,outputs “Valid” if the signature ∑is a valid signature on messageM,or “Invalid”otherwise.

(5) Open(gtk,∑):It takes the tracking key gtk and a signature ∑as inputs,outputs the identityiof signer if the signature ∑is“Valid”checked by algorithm Verify,or ⊥otherwise.

3.2 Security Model

A PBGS scheme should meet three security properties:correctness,simulatability and traceability.Correctness,is defined in Definition 5 detailedly,includes verification correctness and opening correctness.Simulatability implies that the attacker cannot confirm the identity of the signer through a signature because a valid signature is indistinguishable from a simulated signature.Please refer to Definition 6 for details.Traceability means that a valid signature should be opened through group administrator by the tracking key so that the identity of the signer is restored.Our scheme meets full traceability,which is defined in Definition 7 detailedly.Furthermore,anonymity and unforgeability could be unnecessary for PBGS.We will discuss this issue later in Section 3.3.

Definition 5(Correctness) The correctness of the PBGS contains verification correctness and opening correctness.The verification correctness means that the probability of returning “Invalid”from the algorithm Verify is negligible for a signature generated honestly.That is:

The opening correctness means that the probability of returning ⊥from the algorithm Open is negligible for a signature generated honestly.That is:

Definition 6(Simulatability) The simulatability requires that there is a simulator SimSign(M),which generates signatures without the need for any signing key or policy.Then the simulated signatures generated by SimSign(M)are indistinguishable from the signatures generated honestly.The simulatability game(n)is defined by the following processes between an adversaryAand a challengerC:

Setup:Cruns the algorithm GSetup (1λ) honestly by inputting the security parameterλ,and returns gpk and gmk toA.

Queries:Ais allowed to query adaptively the signing key for policypand memberi∈[N],andCsends skp,igenerated by running algorithm KeyGen(gmk,p,i)toA.

Challenge:Areturnsi∈ [N],M*andw*.If PR((p,M),w)=0,the game will be aborted.Otherwise,Ccomputes←SimSign(M*)and←Sign(skp,i,M*,w*).ThenCselects random bitb∈{0,1}and returnstoA.

Finalization:Areturns a guessb′∈{0,1}.Ifb′=b,the game outputs 1.

The advantage ofAin simulatability game is defined as:

Definition 7(Full Traceability [20]) Full traceability is a strong form of traceability.It asks that a team of group members who concentrate their signing keys is unable to generate a valid signature,which could not be caught by the open algorithm.Even though the colluding group knows the tracking key of group manager,that is true.The full traceability game(n)is defined by the following processes between an adversaryAand a challengerC:

Setup:Cruns honestly the algorithm GSetup(1λ)and initializes two listsΓand I.ThenCsends gpk and gtk toA.

Queries:Ahave access to the following queries:

• Request for the signing key of memberi∈[N]and policyp.Creturns skp,i←KeyGen(gmk,p,i)toAand setsΓ←Γ∪{(p,i)}.

• Request for the signature about any messageMon identityiand policyp.Creturns←SimSign(M)toAand sets I ←I ∪{(M,}.

Finalization:Areturns(M*,∑*).If“Invalid‘‘←Verify(gpk,∑*,M*)or(M*,∑*)∈I,the game outputs 0.Otherwise,Cruns algorithm Open.The game outputs 1 if the algorithm Open returns ⊥or returnsi,where{(p,i)}/∈Γ.While in other cases,the game returns 0.

The advantage ofAin full traceability game is written by:

3.3 Discussion

As described in Section 1.3,the anonymity and unforgeability are unnecessary.First,the normal anonymity does not always provide the privacy for the policy relevant to the key and witness[1].To see this,there is a policy relation such that for every messageM,only one policypsatisfies PR((p,M),w)=1.In this situation,a scheme which is composed of the above policy relation still meets anonymity.But the policy is not hiding in this scheme.Indeed,the simulatability introduced by[1]requires that there is a simulator which is able to produce the simulated signatures does not need any signing key or policy,and the simulated signatures are indistinguishable from the signature generated honestly.Next,Traceability is a basic property for GS.It has implied the unforgeability of ordinary digital signatures according to the definition of[20]because the forgery game is a special case for the full-traceability game.The same is true for the extractability game that PBS needs to have.Therefore,we say that the security attributes that PBGS needs to meet are simulation and traceability.

4 The Scheme

4.1 A ZKPoK Protocol

In this section,we present a ZKPoK protocolbased on the linear relation proof from[14].It will be used in the PBGS scheme and allows a prover to convince a verifier that he is a legitimate group member for a certain policy.

First,fix parametersλ,κ,q,Q,σand polynomial ringR(See our construction of PBGS in Section 4.2).For public informationA,v,G1,G2,u,t,t′,δ,B,y,M,d,hand secret information(p,si,1,si,2,w),the proverPwill convince the verifierVthatPpossesses the secret(p,si,1,si,2,w)satisfying policy relation PCG1,G2((p,M),w)=1.Therefore,the protocol ∏PBGSwe will present should be able to prove the following facts:

•(p,si,1,si,2)is a valid secret pair.

•G1·p+G2·w=M.

•(d,h)is a verifiable ciphertext.

The interaction between the two parties is as follows:

Protocol 1:Zero-knowledge Protocol of Knowledge for PBGS Protocol 1:1.Commitment.P performs the following steps:Selects(yr,y′r)←D3 ξ1 ×D3 ξ1,yB ←D8 ξ1,(ys1,ys2)←D2 ξ2 ×D2 ξ2,ys3 ←D3 ξ3,(yp,yw)←D3 ξ1 ×Dℓ-3 ξ1.ys=(ys1,ys2,ys3)T.Computes w1=aT 1 yr,w′1=aT1 y′r,w2=δaT2 yr-aT 2 y′r,ws=vTys,wB=ByB,wp=G1yp+G2yw.Sends w1,w′1,w2,ws,wB,wp to V.2.Challenge.V generates a challenge c ←C and sends c to P.3.Response.P computes z=rc+yr,z′=r′c+y′r,zs1=s1c+ys1,zs2=s2c+ys2,zs3=(p-r r′ s2)c+ys3,zB=rBc+yB,zp=pc+yp,zw=wc+yw.Run rejection sampling Rej((z,z′,zB,zp,zw)(rc,r′c,rBc,pc,wc),ξ1),Rej((zs1,zs2),(s1c,s2c),ξ2)and Rej(zs3,s3c,ξ3),returns ∏(z,z′,zs1,zs2,zs3,zp,zw,zB,c)to V.4.Verification.V checks: aT1 z=t1c+w1 aT1 z′=t′1c+w′1 δaT2 z-aT2 z′=(δt2-t′2)c+w2 vTzs=uc+ws BzB=yc+wB G1zp+G2zw=Mc+wp||(z,z′,zB,zp,zw)||≤B1 ∧||(zs1,zs2)||≤B2 ∧||zs3||≤B3 The verifier V returns 1 if all of the above equations hold,otherwise it returns 0.

Theorem 1Givenr,r′←D3σ,si,1,si,2←D2σ,p←χ3,w←χℓ-3andG1,G2,u,t,t′,h,d,B,yfixed in Section 4.2,forξ1≥andin Protocol 1 meets the following properties:

• Correctness:The proverPoutputs successfully a transcript with a probability of 1/27+2-100at least.And the verifierVwill accept the transcript with overwhelming probability when the protocol is not aborted.

• Honest-Verifier Zero-Knowledge:An honest verifier can simulate the transcripts with statistically indistinguishable distribution when the protocol is not aborted.

• Special Soundness:A valid opening of commitmentt,t′can be extracted by two accepting transcripts.

Proof.Correctness:IfPis an honest prover,it can be got from Lemma 4 that the probability of rejection sampling is at least 1/27+2-100.The distribution(z,z′,zs1,zs2,zp,zw),zBandzs3is close to,andafter the rejection sampling.And we can get||(z,z′,zB,zp,zw)||≤B1∧||(zs1,zs2)||≤B2∧||zs3||≤B3will be held with an overwhelming probability according to Lemma 3.Therefore,Vwill accept the transcript with overwhelming probability.

Honest-Verifier Zero-Knowledge:We only show that the protocolmeets honest-verifier zero-knowledge when the proverPis not aborted.Since the protocol will be converted to NIZKPoK by Fiat-Shamir transformation and be applied to PBGS.Vcannot get the transcript when the protocol is aborted.Then for a non-abort protocol,there is a probabilistic polynomial time(PPT)simulation algorithmS(A,v,G1,G2,B):

We will get that the transcripts generated by the simulation algorithmS(A,v,G1,G2,B)will be accepted by the verifier with overwhelming probability.In the real protocol,the statistical distance between distribution of(z,z′,zs1,zs2,zp,zw),zB,zs3and distributionis no more than 2-100.Sincew1,w′1,w2,ws,wB,wpare completely determined byA,v,G1,G2,B,t,t′,u,y,the statistical distance between the distribution(w1,w′1,w2,ws,wB,wp,c,z,z′,zs1,zs2,zs3,zp,zw,zB)generated by the simulation algorithmS(A,v,G1,G2,B)and the distribution of real protocol is within 2-100.

Special Soundness:Let(z,z′,zs1,zs2,zs3,zp,zw,zB,c)and(z*,z′*,z*s1,z*s2,z*s3,z*p,z*w,z*B,c*)are two transcripts of real protocol withcc*.We are able to extract a valid openingof commitmentst,t′,whereThen the following equations hold:

The protocolis able to be converted into a NIZKPoK by Fiat-Shamir transformation.In order to do that,we define the hash functionH:{0,1}*→Cthat is used to generate challenge.And we let challengec=H(t,t′,v,A,B,y,δ,G1,G2,w1,w′1,w2,ws,wB,wp,M).Then verifierVrecoversw1,w′1,w2,ws,wB,wpfrom public information and obtainsc′.Ifc′=c,Vaccepts the transcript and outputs 1;otherwiseVreturns 0.

4.2 PBGS Scheme

In this section,we show a scheme of PBGS from lattice specifically.

GSetup(1λ):

Given a security parameterλ,the algorithm setsd=O(λ)as a power of 2,a parameterℓ＞O(logλ),integer boundβ=poly(d)and challenge boundκ＞0,prime modulusq,Q≥Gaussian parameterσ=q1/2·Set polynomial ringR=Z[X]/＜Xd+1＞,set of identity[N]⊆Zq,hash functionH:{0,1}*→C.Let gadget matrixgT=[ 1δ]∈.

PRG1,G2((p,M),w)=1 ⇔G1·p+G2·w=Mmodq,

andp←χ3,messageM∈Rq,witnessw←χℓ-3.

(f) Output gpk=(A,a,a,b,b1,G1,G2,u),gmk=Rand gtk=s.

KeyGen(R,p,i):

Given group master private keyR,policypand memberi∈[N],KGC will generate a signing key pair skp,iin the following way:

(a)(si,1,si,2)←SampleD(a3,b,R,u-aT2p,σ)satisfying:

(b) Output the signing key skp,i=(p,si,1,si,2).

Sign(skp,i,M,w):

Given signing key skp,i,messageM∈Rℓqand witnessw:

•(p,si,1,si,2)is a valid signing key,andvTs′=u.

•G1·p+G2·w=Mmodq.

•(d,h)is a valid verifiable ciphertext so thatBrB=y.

(h) Output the signature ∑=(t,t′,∏,h,d).

Verify(gpk,∑,M):

Given gpk,signature ∑and messageM:

(a) RecoverB1,B2,B,y,v.

(b) Perform the verification in Section 4.1.If the verification algorithm accepts the ∏,output“Valid”;otherwise return“Invalid”.

Open(gtk,∑):

Given tracking key gtk and signatureΣ:

(a) If the algorithm Verify returns“Invalid”for the signatureΣ,output ⊥and terminate;otherwise perform the following steps.

(b) Selectc′←C,set=c-c′,wherecis a challenge defined in Section 4.1.

(d) Computei=t2-·.Ifi∈[N],returni,otherwise return ⊥.

5 Security Analysis

Theorem 2(Correctness)The proposed PBGS scheme is correct with overwhelming probability.

Proof:

1) Verification correctness

For gpk,gmk,gtk ←GSetup(1λ),skp,i←KeyGen(R,p,i),∑←Sign(skp,i,M,w),we computec′=H(t,t′,v,A,B,y,δ,G1,G2,w1,w′1,w2,ws,wB,wp,M)by the Verification equation in Protocol 1.Thenc′=cis hold with an overwhelming probability.Furthermore,the distribution(z,z′,zB,zp,zw),(zs1,zs2),zs3is close torespectively after rejection sampling introduced in Lemma 4.And we have||(z,z′,zB,zp,zw)|| ≤||(zs1,zs2)|| ≤||zs3|| ≤according to Lemma 3.Therefore,the probability of“Invalid←Verify(gpk,∑,M)is negligible.

2) Opening correctness

In signing phase,the signer generates verifiable ciphertext(h,d)by encrypting the randomr.The ciphertext(h,d)will be verified during the Verify phase.If the algorithm Verify returns“Valid”,(h,d)is a valid encryption about random r.Then administrator sets:

c′←C,=c-c′.

And the following equation holds:

According to[26],we know thatwhich isAnd administrator computesr¯c=¯rmodqto open the commitment:

Theorem 3(Simulatability)The proposed PBGS scheme meets simulatability defined in Definition 6 under ROM,if the MLWE1,χproblem is hard.

Proof:We will construct a PPT algorithm SimSign,which returns a simulated signature ∑*by inputting arbitrary messageM∈Rq.Specifically,the SimSign algorithm is similar to honest signature algorithm roughly,except for the following modifications:

1) For commitmentstandt′,we modify the(i,r)as a random(i*,r*).Due to the hiding of commitment in Lemma 6,the algorithm SimSign is still indistinguishable from the honest signature algorithm.

3) For ciphertext(h,d),we seth*=qaandd*=qb1.Then the(h*,d*)is indistinguishable from(h,d)under the MLWE1,χproblem.

As a result,the algorithm SimSign is able to generate a simulated signature ∑*=(t*,t′*,∏*,h*,d*),which is indistinguishable from the legitimate signature generated by the honest signature algorithm.And the SimSign does not need any signing key or policy.

After obtaining the algorithm SimSign,challengerCruns the GSetup(1λ)honestly and sends the gpk and gmk to attackerA.Aadaptively chooses policiesp1,...,pQand queries signing key ofpi.Cruns skp,i←KeyGen(gmk,p,i)and sends skp,itoA.NextAchoosesi∈[Q],M∈Rq,p←χ3,w*←χℓ-3and sends them toC.If PR((p,M),w*)=0,the game will be terminated;otherwiseCcomputes simulated signature←SimSi gn(M*)and legitimate signature←Sign(skp,i,M*,w*).Finally,Cselects a bitb∈{0,1}and sendstoA.

Since the simulated signatureis indist/inguishable from the legitimate signature,the probability thatAcorrectly guess the bitbis 1/2+negl(n).That is,the advantage ofAbreaking the simulatability of our PBGS scheme is negligible.

Theorem 4(Full Traceability) The proposed PBGS scheme meets full traceability defined in Definition 7 under ROM,if the MSIS5,βproblem is hard.

Proof:Assume that an attackerAsuccessfully forges an untraceable signature with non-negligible probabilityε.Then a challengerCwill construct a non-zero solution about the MSIS problem by the result ofAwith non-negligible probability.Specifically,Cinitializes the listΓ,Iand runs the GSetup(1λ)honestly.The gpk and gtk are sent toA.NextCselectsj∈[N],pj.Ahave access to the queries of signing key and signature defined in Definition 7.

Finally,Aoutputs a signature ∑=(t,t′,∏,h,d)about messageM*∈Rq,which satisfiesand ⊥←Open(gtk,∑)orj←Open(gtk,∑),where {pj}/∈Γand(M*,) /∈I.According to the special soundness of Theorem 1,there are two different challengesCcan extractsatisfyingWe will get that the probability of completing the above extraction ofCis at leastby the forking lemma of [32],whereh1≥2 is the length of the hash functionH.For ciphertext(h,d),Cwill decrypt and obtain(,)by the tracking key gtk.According to the soundness of the verifiable encryption scheme from [26],we know thatwill hold with overwhelming probability,which means that Open(gtk,∑)∈Zq.Therefore,the probability of ⊥←Open(gtk,∑)is negligible.Since the set of identity[N]is a uniform distribution,the probability ofi=jin forged signature is 1/N.Assuming thati=j,then:

whereRis master private key.Then:

ThenCperforms algorithm Sample D byRto obtainsj,which fulfillsand is unknown toAin forgery phase.Letwe obtainwhere the probability of=is negligible.ThenChas constructed the equation:

And the bound on the norm of the solution satisfies:

Hence,Cconstructs a solution of MSIS5,βproblem with a probability ofε·Since the probability of successful forgery by attackerAis non-negligible,the probability ofε·is also non-negligible.

6 Efficiency Analysis

In this section,we choose three schemes of GS from lattice to carry out efficiency analysis and comparison with our scheme.We will perform a detailed analysis of the storage overhead of group public key,administrator tracking key,members signing key and signature.Firstly,we fix the security parameterλand the maximum number of membersN.Other parameters will be set as described in Section 4.2.Specifically,we setN=212,ℓ=4,κ=26,dimensiond=212,Gaussian parametermodulusqandQare 236,272respectively.Then we get a root-hermite factor by definition from[33].Such a factor means that the parameters we chose guaranteeλ=93 bits space security against quantum adversaries.The comparison for the storage cost of the GS is listed in Tab.2.

Table 2:Comparison of storage overhead for security level λ=93 bits

Compared with the above three schemes of GS,our construction has lower storage overhead on key and signature to a certain extent.The size of key decreased roughly by 83.13% and the size of signature is also decreased roughly by 46.01%.

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

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.