Computers, Materials & Continua DOI:10.32604/cmc.2022.026820
Article

Policy-Based Group Signature Scheme from Lattice

Yongli Tang1, Yuanhong Li1, Qing Ye1,*, Ying Li1 and Xiaojun Wang2

1School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, 454000, China
2School of Electronic Engineering, Dublin City University, Dublin 9, Ireland
*Corresponding Author: Qing Ye. Email: yeqing@hpu.edu.cn
Received: 05 January 2022; Accepted: 23 February 2022

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 O~(λ). 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 message M should be large enough, and the space of policy p could be relatively small; (2) a policy p may simultaneously satisfy a lot of messages M; (3) a message M could possibly satisfy a lot of policies p. 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 policy p∈{0,1}ℓ is allowed to sign a message M∈Z2n, there is a witness w∈{0,1}d satisfying G1⋅p+G2⋅w=M(mod2), wheren−ℓ<d, G1∈Z2n×ℓ is a uniform random matrix, and G2∈Z2n×d is an approximate identity matrix. We define the relation as: PR({0,1}ℓ×Z2n)×{0,1}d→{0,1}. That is,

PR((p,M),w)=1⇔G1⋅p+G2⋅w=Mmod2.

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 policy p, witness w, and signing key s in order to sign a message M that satisfies the policy p, among which the signing key s is obtained by preimage sampling introduced in [24]. Specifically, we first generate a trapdoor R in the setup phase. After that, s is obtained through preimage sampling algorithm, which is executed by KGC through inputting parameters such as the policy p, the identity of signer and the system public key. Then, s and p constitute 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 policy p satisfies 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 commitment Com(i,r) about the signer's identity i and a random r during the signing process. Then the random r will 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 obtain r through using the tracking key to decrypt the ciphertext, and then open the commitment Com(i,r) to obtain the signer's identity i.

2  Preliminaries

2.1 Symbol Definition

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

2.2 MSIS and MLWE

Definition 1 (MSISl,m,β [27]) Given parameters l,m,β and A∈Rql×m, the MSISl,m,β is defined as: Finding z∈Rm such that Az=0 and 0<||z||∞≤β.

Lemma 1 [27] For anyβ=poly(d), m≥1, ε>0, γ≥βd⋅l⋅ω(log⁡d⋅l)⋅ln⁡(2d(1+1/1εε)/ln⁡(2d(1+1/1εε)ππ) and q≥βd⋅m, MSISl,m,β is as difficult as the SIVPγ problem at least.

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

Lemma 2 [27] For m,n>0, α∈(0,1), ε>0, γ=8d⋅n⋅ω(log⁡d/log⁡dαα)⋅ln⁡(2d(1+1/1εε)/ln⁡(2d(1+1/1εε)ππ) and q≥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 parameter m to resist known attacks. Therefore, the assumptions will be simply written MSISl,β and MLWEn,χ by omitting the m, where the l and n represent the module ranks for MSIS and MLWE, respectively.

2.3 Discrete Gaussian Distribution and Rejection Sampling

Given any σ>0, vector c∈R and function ρσ,c(x)=exp⁡(−π||x−c||2σ2). Then the Gaussian distribution Dσ,c centered in c is described as:

Dσ,c(x)=ρσ,c(x)ρσ,c(Z) where ρσ,c(Z)=∑x∈Zρσ,c(x).

We will simply write Dσ when c=0. And if the polynomial x∈R, x←Dσ is defined as every coefficient of x obeying distribution Dσ.

Lemma 3 [14] For any σ>0, positive integer n and k>0, the following formulas holds:

(1)   Pr[x←Dσ:|x|>kσ]≤2e−k2/2.

(2)   Pr[x←Dσn:||x||>σ2n]<2−n/4.

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

Lemma 4 [14,29,30] For V={v∈Rn:||v||<t}, b∈Rn and σ≥11||b||, a procedure will be run by sampling y←Dσn 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 of z and Dσn is within 2−100 when the Algorithm 1 outputs 1.

2.4 Trapdoor from Lattice

Lemma 5 [16,24,31] Given positive integer n, m, q, i, parameter σ=q1/m⋅O(nd+md), polynomial A∈1R1×n and R←χn×m. Set the gadget matrix gT=[1q1/m…q(m−1)/m]. Let B=AR∈R1×m, we will get a basis S∈Z(n+m)d×(n+m) for Λ⊥={x∈Rn+m|[A|AR+igT]⋅x=0(modq)}, which fulfills ||S~||≤(s1(R)+1)δ2+1 after Gram-Schmidt orthogonalization, where δ=⌈q⌉ and s1(R) means maximal singular value of R. And then for any polynomial vector u∈R, there is an algorithm SampleD(A,B,R,u,σ), which is able to sample from distribution D[A|AR+igT],σ,u⊥ with a certain probability.

2.5 Commitments

Definition 3 (Commitment [25]) Given challenge space C={c:c∈R,||c||1=κ,||c||∞=1}, public matrices A1=[InA′1]∈Rqn×k, A2=[0l×nIlA′2]∈Rql×k. For the message m∈Rql to be committed and the random r←χk, an effective commitment will be generated as follows:

Com(m,r)=[t1t2]=[A1A2]r+[0m].

If the following equation holds:

c[t1t2]=[A1A2]r+c[0m], where ||r||≤Bcom and c∈C¯,

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

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

(1)   (Binding) Let κ≥maxc∈C⁡(||c||1), if an attacker A who has advantage ε in outputting a commitment through two valid (m,r,c) and (m′,r′,c′) such that m≠m′, there is an algorithm A′ who has advantage ε in solving the MSISn,4κBCom within the same time.

(2)   (Hiding) For m,m′∈Rql, if an attacker A has advantage ε in distinguishing between Com(m,r) and Com(m′,r′), there is an algorithm A′ that has advantage ε/ε22 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, policy p and member identity i∈[N] as inputs, outputs a signing key skp,i of member i about the policy p.

(3)   Sign (skp,i,M,w): It takes the signing key skp,i, a message M and a witness w as 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 message M as inputs, outputs “Valid” if the signature ∑ is a valid signature on message M, or “Invalid” otherwise.

(5)   Open (gtk,∑): It takes the tracking key gtk and a signature ∑ as inputs, outputs the identity i of 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:

Pr[‘‘Invalid″←Verify(gpk,∑,M)|gpk,gmk,gtk←Gsetup(1λ)skp,i←KeyGen(gmk,p,i)∑←Sign(skp,i,M,w)]≤negl(n).

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

Pr[⊥←Open(gtk,∑)|gpk,gmk,gtk←Gsetup(1λ)skp,i←KeyGen(gmk,p,i)∑←Sign(skp,i,M,w)‘‘Valid″←Verify(gpk,∑,M)]≤negl(n).

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 GamePBGS,ASIM(n) is defined by the following processes between an adversary A and a challenger C:

Setup: C runs the algorithm GSetup (1λ) honestly by inputting the security parameter λ, and returns gpk and gmk to A.

Queries: A is allowed to query adaptively the signing key for policy p and member i∈[N], and C sends skp,i generated by running algorithm KeyGen(gmk,p,i) to A.

Challenge: A returns i∈[N], M∗ and w∗. If PR((p,M),w)=0, the game will be aborted. Otherwise, C computes ∑0←SimSign(M∗) and ∑1←Sign(skp,i,M∗,w∗). Then C selects random bit b∈{0,1} and returns ∑b to A.

Finalization: A returns a guess b′∈{0,1}. If b′=b, the game outputs 1.

The advantage of A in simulatability game is defined as:

AdvPBGS,ASIM(n)=|Pr[GamePBGS,ASIM(n)⇒1]−1/2|.

If AdvPBGS,ASIM(n) is negligible, we call that the PBGS scheme meets simulatability.

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 GamePBGS,ATRACE(n) is defined by the following processes between an adversary A and a challenger C:

Setup: C runs honestly the algorithm GSetup (1λ) and initializes two lists Γ and I. Then C sends gpk and gtk to A.

Queries: A have access to the following queries:

• Request for the signing key of member i∈[N] and policy p. C returns skp,i←KeyGen(gmk,p,i) to A and sets Γ←Γ∪{(p,i)}.

• Request for the signature about any message M on identity i and policy p. C returns ∑M←SimSign(M) to A and sets I←I∪{(M,∑M)}.

Finalization: A returns (M∗,∑∗). If ‘‘Invalid″←Verify(gpk,∑∗,M∗) or (M∗,∑∗)∈I, the game outputs 0. Otherwise, C runs algorithm Open. The game outputs 1 if the algorithm Open returns ⊥ or returns i, where {(p,i)}∉Γ. While in other cases, the game returns 0.

The advantage of A in full traceability game is written by:

AdvPBGS,ATRACE(n)=Pr[GamePBGS,ATRACE(n)⇒1].

If AdvPBGS,ATRACE(n) is negligible, we call that the PBGS scheme meets full traceability.

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 message M, only one policy p satisfies 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 protocol ∏PBGS based 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 ring R (See our construction of PBGS in Section 4.2). For public information A,v,G1,G2,u,t,t′,δ,B,y,M,d,h and secret information (p,si,1,si,2,w), the prover P will convince the verifier V that P possesses the secret (p,si,1,si,2,w) satisfying policy relation PCG1,G2((p,M),w)=1. Therefore, the protocol ∏PBGS we 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:

Theorem 1 Given r,r′←Dσ3, si,1,si,2←Dσ2, p←χ3, w←χℓ−3 and G1,G2,u,t,t′,h,d,B,y fixed in Section 4.2, for ξ1≥11κ(14+ℓ)d, ξ2≥11κ4dσ, ξ3≥11κ(d24σ+2dσ) and B1≥2(14+ℓ)dξ1, B2≥22dξ2, B3≥6dξ3, the protocol ∏PBGS in Protocol 1 meets the following properties:

• Correctness: The prover P outputs successfully a transcript with a probability of 1/12727+2−100 at least. And the verifier V will 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 commitment t,t′ can be extracted by two accepting transcripts.

Proof.

Correctness: If P is an honest prover, it can be got from Lemma 4 that the probability of rejection sampling is at least 1/12727+2−100. The distribution (z,z′,zs1,zs2,zp,zw), zB and zs3 is close to Dξ114+ℓ, Dξ24 and Dξ33 after the rejection sampling. And we can get ||(z,z′,zB,zp,zw)||≤B1∧||(zs1,zs2)||≤B2∧||zs3||≤B3 will be held with an overwhelming probability according to Lemma 3. Therefore, V will accept the transcript with overwhelming probability.

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

c←C.

z,z′,zs1,zs2,zp,zw←Dξ1,zB←Dξ2,zs3←Dξ3.

w1=a1Tz−t1c,w′1=a1Tz′−t1′c,w2=δa2Tz−a2Tz′−(δt2−t2′)c.

ws=vTzs−uc,wB=BzB−yc,wp=G1zp+G2zw−Mc.

Output(w1,w′1,w2,ws,wB,wp,c,z,z′,zs1,zs2,zs3,zp,zw,zB).

We will get that the transcripts generated by the simulation algorithm S(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, zs3 and distribution Dξ114+ℓ, Dξ24, Dξ33 is no more than 2−100. Since w1,w′1,w2,ws,wB,wp are completely determined by A,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 algorithm S(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′∗,zs1∗,zs2∗,zs3∗,zp∗,zw∗,zB∗,c∗) are two transcripts of real protocol with c≠c∗. We are able to extract a valid opening ((z¯,z¯′,z¯s1,z¯s2,z¯s3,z¯p,z¯w,z¯B),i¯,c¯) of commitments t,t′, where z¯=z−z∗, z¯′=z′−z′∗, z¯s1=zs1−zs1∗, z¯s2=zs2−zs2∗, z¯s3=zs3−zs3∗, z¯p=zp−zp∗, z¯w=zw−zw∗, z¯B=zB−zB∗, c¯=c−c∗, i¯∈Zq. Then the following equations hold:

c¯t=Com(c¯i¯,z¯),c¯t′=Com(c¯i¯δ,z¯′),

c¯y=Bz¯B,c¯u=vTz¯s,c¯M=G1z¯p+G2z¯w,

such that ||(z¯,z¯′,z¯B,z¯p,z¯w)||≤2B1, ||z¯s1,z¯s2||≤2B2, ||z¯s3||≤2B3. This completes the proof.

The protocol ∏PBGS is able to be converted into a NIZKPoK by Fiat-Shamir transformation. In order to do that, we define the hash function H:{0,1}∗→C that is used to generate challenge. And we let challenge c=H(t,t′,v,A,B,y,δ,G1,G2,w1,w′1,w2,ws,wB,wp,M). Then verifier V recovers w1,w′1,w2,ws,wB,wp from public information and obtains c′. If c′=c, V accepts the transcript and outputs 1; otherwise V returns 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 sets d=O(λ) as a power of 2, a parameter ℓ>O(log⁡λ), integer bound β=poly(d) and challenge bound κ>0, prime modulus q,Q≥βd, Gaussian parameter σ=q1/2⋅O(d). Set polynomial ring R=Z[X]/<Xd+1>, set of identity [N]⊆Zq, hash function H:{0,1}∗→C. Let gadget matrix gT=[1δ]∈Rq1×2.

(a) Select a1=[1a1a2]∈Rq3, a2=[01a3]∈Rq3. Let A=[a1a2]∈Rq2×3.

(b) Select a←Rq2, R←χ2×2. Let bT=aTR∈Rq1×2.

(c) Select (s0,1,s0,2,s0,3)←Dσ2×Dσ2×Dσ3. Set u=[aTbTa2T][s0,1s0,2s0,3].

(d) Select a←RQ, (s,e)←χ3×χ3. Set b1=[b1b2b3]=as+e∈RQ3.

(e) Select G1←Rq1×3, G2∈Rq1×(ℓ−3), where G2 is an approximate identity matrix. Define policy relation PRG1,G2:(χ3×Rq)×χℓ−3→{0,1}, where:

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

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

KeyGen (R,p, i):

Given group master private key R, policy p and member i∈[N], KGC will generate a signing key pair skp,i in the following way:

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

[aT|bT+igT][si,1si,2]=u−a2Tp, where (si,1,si,2)∈Dσ2×Dσ2.

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

Sign (skp,i,M,w):

Given signing key skp,i, message M∈Rqℓ and witness w:

(a) If PRG1,G2((p,M),w)≠1, then return ⊥; otherwise perform the following steps.

(b) Select (r,r′)←χ3×χ3. Set t=[t1t2]=Com(i,r), t′=[t′1t′2]=Com(iδ,r′).

(c) Set vT=[aT|bT+[t2|t′2]|a2T]∈Rq1×7, s′=[si,1si,2p−[r|r′]si,2]∈Rq7 satisfying vTs′=u.

(d) Select sB←χ, e1←χ, e2←χ3, set h=q(asB+e1) and d=q(b1sB+e2)+r.

(e) Set B1=[qaq000000qb10q00100qb200q0010qb3000q001]∈RQ4×8, B2=[00000a1T]∈Rq1×8 and B=[B1B2].

(f) Set rB=[sBe1e2r]∈Rq8 and y=[hdt1]∈RQ4×Rq satisfying BrB=y.

(g) Generate a NIZKPoK ∏=(z,z′,zB,zs1,zs2,zs3,zp,zw,c) to show the possession of (p,si,1,si,2,w,rB) satisfying:

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

• G1⋅p+G2⋅w=Mmodq.

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

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

Verify (gpk,∑,M):

Given gpk, signature ∑ and message M:

(a) Recover B1,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) Select c′←C, set c¯=c−c′, where c is a challenge defined in Section 4.1.

(c) Set r¯=(d−hs)c¯modQ. If ||r¯||∞≤Q/4κ, r¯=r¯modq; otherwise return ⊥.

(d) Compute i=t2−a2Tr¯⋅c¯−1. If i∈[N], return i, 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 compute c′=H(t,t′,v,A,B,y,δ,G1,G2,w1,w′1,w2,ws,wB,wp,M) by the Verification equation in Protocol 1. Then c′=c is hold with an overwhelming probability. Furthermore, the distribution (z,z′,zB,zp,zw), (zs1,zs2), zs3 is close to Dξ114+ℓ, Dξ24, Dξ33 respectively after rejection sampling introduced in Lemma 4. And we have ||(z,z′,zB,zp,zw)||≤2(14+ℓ)dξ1, ||(zs1,zs2)||≤22dξ2, ||zs3||≤6dξ3 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 random r. 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¯=c−c′.

And the following equation holds:

r¯=(d−hs)c¯modQ=pc¯(b1sB+e2)+rc¯−psc¯(asB+e1)modQ=pc¯(asBs+sBe+e2)−pc¯(asBs+e1s)+rc¯modQ=pc¯(sBe+e2−e1s)+rc¯modQ.