# An Improved Group Signature Scheme with VLR over Lattices

Authors: Yanhua Zhang; Ximeng Liu; Yupu Hu; Huiwen Jia; Qikun Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

For group signatures (GS) supporting membership revocation, verifier-local revocation (VLR) mechanism is the most flexible choice. As a post-quantum secure cryptographic counterpart of classical schemes, the first dynamic GS-VLR scheme over lattices was put forward by Langlois et al. at PKC 2014; furthermore, a corrected version was shown at TCS 2018. However, both designs are within Bonsai trees and featuring bit-sizes of group public-key and member secret signing key proportional tologN where N is the group size; therefore, both schemes are not suitable for a large group. In this paper, we provide an improved dynamic GS-VLR over lattices, which is efficient by eliminating a OlogN factor for both sizes. To realize the goal, we adopt a more efficient and compact identity-encoding technique. At the heart of our new construction is a new Stern-type statistical zero-knowledge argument of knowledge protocol which may be of some independent cryptographic interest.


---

## Body

## 1. Introduction

Group signatures (GS), first formalized by Chaum and Heyst [1], allow the members to issue signatures on behalf of the group without leaking their identity. A tracing authority could link any valid message-signature pair to the real signer. The anonymity and traceability are of especial importance for GS, and to construct GS schemes with different security, efficiency, and hardness, they have been brought (see, e.g., [2–9]) over the last quarter-century.Up to now, there are five schemes supporting dynamic GS over lattices. At PKC 2014, Langiois et al. [10] introduced the first GS over lattices to support membership revocation with verifier-local revocation (VLR) mechanism. Because of an improper design, there is a flaw of [10], this mistake is completely fixed, and a secure scheme [11] was provided. As an orthogonal problem of membership revocation, enrollment is also noteworthy, and this problem was first resolved by Libert et al. [12]. Later, Ling et al. [13] introduced the first fully dynamic GS over lattices. Recently, Ling et al. [14] proposed the first constant-size and partially dynamic GS over lattices, and Sun and Liu [15] proposed the first lattice-based fully dynamic GS without NIZK.Membership revocation is also noteworthy for GS, and the VLR mechanism is the most flexible choice in the mobile network that allows anonymous authentication. After the first GS-VLR over lattices was given by Langlois et al. [10], some new constructions are proposed [11, 16, 17]. However, all schemes are within Bonsai trees [18] and featuring bit-sizes of group public-key and member secret signing key proportional to logN; therefore, these schemes are not suitable for certain large group, the only two exceptions [19, 20]. However, the constructions of [19, 20] are not free of public-key encryptions. Therefore, these unsatisfactory situations naturally lead a challenging topic on how to design a more efficient GS-VLR over lattices?


### 1.1. Our Construction and Techniques

In this work, we will reply positively to the above problem, and we introduced an improved GS-VLR scheme over lattices. Here, by “improved,” we mean that our construction eliminates aOlogN factor for the sizes of group public-key and member secret signing key. Furthermore, the free of any public-key encryptions also brings reasonable selecting for cryptographic parameters and a clearer proof idea. A detailed comparison between the proposed scheme and previous GS-VLR over lattices is shown in Table 1.Table 1
Comparison of GS-VLR schemes over lattices (N=2ℓ=polyn).
SchemeGpkgskσFree of encryptions[20]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nYes[21]O˜n2O˜nO˜n+ℓNo[22]O˜n2O˜nO˜n+ℓNo[23]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nYes[24]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nNoOursO˜n2O˜nℓ⋅O˜nYesOur scheme is proven secure under the shortest independent vectors problem (SIVP). We adopt an efficient identity-encoding technique [23]. The group is of N=2ℓ members, and the member is marked as id=d1,…,dℓ∈0,1ℓ, a binary representation of his index i∈0,1,…,N−1, i.e., id=Bini∈0,1ℓ where Bini is i’s binary decomposition. In this paper, n is a security parameter and the group public-key Gpk includes a uniform u∈ℤqn and A0,A1,A2∈ℤqn×m. For i∈0,1,…,N−1, not as that in [23] to generate a trapdoor basis matrix as member’s secret-key, we sample a nonzero short vector ei=ei,0,ei,1∈ℤ2m which satisfies Ai⋅ei=umodq and 0<ei|∞≤β, where Ai=A0|A1+iA2∈ℤqn×2m and the member i’s revocation token is created by A0 and ei,0, i.e., grti=A0⋅ei,0modq.The main challenge is how to prove these two core relations with a secure NIZK protocol: (a)A0|A1+iA2⋅ei=umodq and (b) A1i=A0⋅ei,0modq. For (b), we first sample a uniformly random B∈ℤqn×m (a matrix in an oracle), and a short random e∈ℤm (a vector in a learning with errors (LWE) distribution), and let b=BT⋅grti+emodgrt as in [11]. For (a), because ei is an affirmative answer to Ai=A0|A1+iA2,u, an instance of the inhomogeneous short integer solution (ISIS), a simple method to prove i’s validity is to perform a Stern-type statistical zero-knowledge argument of knowledge (ZKAoK) as in [25]. However, the detailed structure of Ai cannot be given to keep i’s anonymity. How to realize a zero-knowledge proof without leaking Ai and ei? First, Ai is transformed into A′ which owns a new shape and is irrelevant to index i, i.e., A′=A0A1gℓ⊗A2∈ℤqn×2ℓ+2m where gℓ=1,2,22,…,2ℓ−1, and thus i=gℓT⋅Bini, and ⊗ is defined in Section 3. Correspondingly, the short vector ei=ei,0,ei,1 is transformed to ei′=ei,0,ei,1,Bini⊗ei,1∈ℤℓ+2m. Thus, to argue the above relation Ai⋅ei=umodq, we instead show that A′⋅ei′=umodq.In a nutshell, by creatively improving an identity-encoding technique and designing a Stern-type zero-knowledge proof protocol, we introduce a more efficient GS-VLR over lattices. Our scheme satisfies the selfless-anonymity and enjoys the low bit-sizes. In addition, the innovative idea in our new construction must be of independent cryptographic interest.


### 1.2. Related Works

In the study by Regev [26] and Gentry et al. [27], GS over lattices have been extensively studied. The first GS over lattices were proposed by Gordon et al. [6], which are with linear sizes of group public-key and signature. Camenisch el al. [7] showed an improvement of public-key for [6]. In 2013, Laguillaumie et al. [24] introduced the first GS with logarithmic signature size over lattices. Later, Ling et al. [28] and Libert et al. [29] provided efficient GS constructions. Libert et al. [21] described the first GS over lattices not requiring trapdoors. Furthermore, GS over lattices with the message-dependent opening, forward-secure, and without noninteractive zero-knowledge (NIZK) were, respectively, shown by Libert et al. [21], Ling et al. [22], Canard et al. [30], and Katsumata and Yamada [31]. For the above GS schemes, all can only support static groups (i.e., no candidate member could join or leave once the group was established).


### 1.3. Remark

This article is the improved version of [32], published in the proceedings of ISC 2019. Obviously, this article is a following work of [32] which is implied but not given clearly. And after [32], a series of rich contents of Zhang et al. [33–35] has developed our protocol to design a GS-VLR over lattices supporting explicit traceability and two new protocols for GS-VLR over lattices with improved anonymity.


### 1.4. Organization

We recall knowledge on GS-VLR and lattices in Section2. Section 3 describes the main techniques utilized in our GS-VLR construction. Our scheme is finally designed and analysed in Section 4.


## 1.1. Our Construction and Techniques

In this work, we will reply positively to the above problem, and we introduced an improved GS-VLR scheme over lattices. Here, by “improved,” we mean that our construction eliminates aOlogN factor for the sizes of group public-key and member secret signing key. Furthermore, the free of any public-key encryptions also brings reasonable selecting for cryptographic parameters and a clearer proof idea. A detailed comparison between the proposed scheme and previous GS-VLR over lattices is shown in Table 1.Table 1
Comparison of GS-VLR schemes over lattices (N=2ℓ=polyn).
SchemeGpkgskσFree of encryptions[20]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nYes[21]O˜n2O˜nO˜n+ℓNo[22]O˜n2O˜nO˜n+ℓNo[23]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nYes[24]ℓ⋅O˜n2ℓ⋅O˜nℓ⋅O˜nNoOursO˜n2O˜nℓ⋅O˜nYesOur scheme is proven secure under the shortest independent vectors problem (SIVP). We adopt an efficient identity-encoding technique [23]. The group is of N=2ℓ members, and the member is marked as id=d1,…,dℓ∈0,1ℓ, a binary representation of his index i∈0,1,…,N−1, i.e., id=Bini∈0,1ℓ where Bini is i’s binary decomposition. In this paper, n is a security parameter and the group public-key Gpk includes a uniform u∈ℤqn and A0,A1,A2∈ℤqn×m. For i∈0,1,…,N−1, not as that in [23] to generate a trapdoor basis matrix as member’s secret-key, we sample a nonzero short vector ei=ei,0,ei,1∈ℤ2m which satisfies Ai⋅ei=umodq and 0<ei|∞≤β, where Ai=A0|A1+iA2∈ℤqn×2m and the member i’s revocation token is created by A0 and ei,0, i.e., grti=A0⋅ei,0modq.The main challenge is how to prove these two core relations with a secure NIZK protocol: (a)A0|A1+iA2⋅ei=umodq and (b) A1i=A0⋅ei,0modq. For (b), we first sample a uniformly random B∈ℤqn×m (a matrix in an oracle), and a short random e∈ℤm (a vector in a learning with errors (LWE) distribution), and let b=BT⋅grti+emodgrt as in [11]. For (a), because ei is an affirmative answer to Ai=A0|A1+iA2,u, an instance of the inhomogeneous short integer solution (ISIS), a simple method to prove i’s validity is to perform a Stern-type statistical zero-knowledge argument of knowledge (ZKAoK) as in [25]. However, the detailed structure of Ai cannot be given to keep i’s anonymity. How to realize a zero-knowledge proof without leaking Ai and ei? First, Ai is transformed into A′ which owns a new shape and is irrelevant to index i, i.e., A′=A0A1gℓ⊗A2∈ℤqn×2ℓ+2m where gℓ=1,2,22,…,2ℓ−1, and thus i=gℓT⋅Bini, and ⊗ is defined in Section 3. Correspondingly, the short vector ei=ei,0,ei,1 is transformed to ei′=ei,0,ei,1,Bini⊗ei,1∈ℤℓ+2m. Thus, to argue the above relation Ai⋅ei=umodq, we instead show that A′⋅ei′=umodq.In a nutshell, by creatively improving an identity-encoding technique and designing a Stern-type zero-knowledge proof protocol, we introduce a more efficient GS-VLR over lattices. Our scheme satisfies the selfless-anonymity and enjoys the low bit-sizes. In addition, the innovative idea in our new construction must be of independent cryptographic interest.


## 1.2. Related Works

In the study by Regev [26] and Gentry et al. [27], GS over lattices have been extensively studied. The first GS over lattices were proposed by Gordon et al. [6], which are with linear sizes of group public-key and signature. Camenisch el al. [7] showed an improvement of public-key for [6]. In 2013, Laguillaumie et al. [24] introduced the first GS with logarithmic signature size over lattices. Later, Ling et al. [28] and Libert et al. [29] provided efficient GS constructions. Libert et al. [21] described the first GS over lattices not requiring trapdoors. Furthermore, GS over lattices with the message-dependent opening, forward-secure, and without noninteractive zero-knowledge (NIZK) were, respectively, shown by Libert et al. [21], Ling et al. [22], Canard et al. [30], and Katsumata and Yamada [31]. For the above GS schemes, all can only support static groups (i.e., no candidate member could join or leave once the group was established).


## 1.3. Remark

This article is the improved version of [32], published in the proceedings of ISC 2019. Obviously, this article is a following work of [32] which is implied but not given clearly. And after [32], a series of rich contents of Zhang et al. [33–35] has developed our protocol to design a GS-VLR over lattices supporting explicit traceability and two new protocols for GS-VLR over lattices with improved anonymity.


## 1.4. Organization

We recall knowledge on GS-VLR and lattices in Section2. Section 3 describes the main techniques utilized in our GS-VLR construction. Our scheme is finally designed and analysed in Section 4.


## 2. Preliminaries

### 2.1. Notations

Table2 refers to the notations used in our work.Table 2
Notations of our work.
NotationDefinitionSkAll permutation ofk elements←RSampling uniformly at random⋅, or ⋅∞Euclidean normℓ2 or the infinity norm ℓ∞Parsee,k1,k2ek1,ek1+1,…,ek2∈ℝk2−k1+1, e=e1,e2,…,en∈ℝn, 1≤k1≤k2≤nlogeLogarithm ofe with base 2PPTProbabilistic polynomial-time


### 2.2. GS-VLR

#### 2.2.1. Syntax of GS-VLR

There are three polynomial-time algorithms:KeyGen1n,N: taking the security parameter n and group size N as input, this PPT algorithm will output group public-key Gpk, members secret signing keys Gsk=gsk0,gsk1,…,gskN−1, and members revocation tokens Grt=grt0,grt1,…,grtN−1.SignGpk,gski,m: taking Gpk and gski of member id with index i∈0,1,…,N−1 and message m∈0,1∗ as input, this PPT algorithm will output a signature σ.VerifyGpk,RL,σ,m: taking Gpk a subset of tokens RL⊆Grt, σ and m∈0,1∗ as input, this deterministic algorithm will output either 0 or 1. 1 means that σ is valid, and the real signer has not been revoked from the group.Correctness and security of GS-VLR: here, there are three main requirements: correctness, selfless-anonymity, and traceability.Correctness: for allGpk,Gsk,Grt outputted by KeyGen, any member i∈0,1,…,N−1, all gski∈Gsk, RL∈Grt, and m∈0,1∗, we have the conditions:(1)VerifyGpk,RL,SignGpk,gski,m,m=1⇔grti∉RL.Selfless-anonymity: in the following game, the goal of adversaryA is to determine which of the two adaptively chosen members id0 with an index i0 and id1 with an index i1 generated σ∗. A is not given either secret-key.Setup: the challenger C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk to A.Queries: A can adaptively make the following queries:(i)
Corruption: taking i as input, C returns gski.(ii)
Signing: taking i and m∈0,1∗ as input, C returns σ⟵SignGpk,gski,m.(iii)
Revocation: take i as input, C returns grti.Challenge: A outputs a message m∈0,1∗ and two distinct members id0 with an index i0 and id1 with an index i1. A should not make corruption query or revocation query at either member. C chooses a bit b⟵R0,1, computes σ∗⟵SignGpk,gskib,m∗ as a valid signature on m∗, and returns it to A.Restrictedqueries: once the challenge σ∗ is obtained, A can make queries as before without the rights to do the corruption or revocation query for id0 or id1 or opening query for m∗,σ∗.Output: A outputs a bit b′∈0,1 and wins if b′=b.AdvAself−anon=Prb′=b−1/2 is defined as A′s advantage in winning the above game. Thus, a GS-VLR satisfies the selfless-anonymity if AdvAself−anon is negligible.Traceability: in the following game, the goal ofA is to forge a signature that cannot be traced to any member in its collation.Setup: C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk,Grt to A. Let initial corruption set Corr=∅.Queries: A can adaptively make the corruption and signing queries as in selfless-anonymity and C additionally adds id with its index i to Corr.Forgery: A outputs a message m∗∈0,1∗, a set of members revocation tokens RL∗⊆Grt and a signature σ∗. A wins if(i)
VerifyGpk,RL∗,σ∗,m∗=1.(ii)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗.(iii)
σ∗ is not obtained by a query on m∗.AdvAtrace=SuccPTA is defined as A′s advantage in winning the above game. Thus, a GS-VLR scheme satisfies the traceability if AdvAtrace is negligible.


### 2.3. Background on Lattices

Ajtai [36] first showed a strategy to generate statistically close to uniform A∈ℤqn×m together with low norm trapdoor basis of Λq⊥A=e∈ℤm|A⋅e=0modq. Subsequently, two new algorithms were given by [37, 38].Lemma 1.
(see [36–38]). Define n≥1, q≥2, and m=2n⌈logq⌉. A PPT algorithm TrapGenq,n,m outputs A and RA, such that A∈ℤqn×m is statistically close to uniform and RA is a trapdoor for Λq⊥A.
Gentry et al. [27] first introduced a method to sample short vector from some discrete Gaussian distribution, and then an improved algorithm was introduced in [38].Lemma 2.
(see [27, 38]). Let n≥1, q≥2, and m=2n⌈logq⌉. Given A∈ℤqn×m, a trapdoor RA of Λq⊥A, a parameter s=ωnlogqlogn, and u∈ℤqn. A PPT algorithm SamplePreA,RA,u,s will output a short e∈ΛquA sampled from a distribution close to DΛquA,s.
The short integer solution (SIS), ISIS (both inℓ∞ norm), and LWE problems are described as follows.Definition 1.
(SIS and ISIS). Given a randomA∈ℤqn×m, a random syndrome u∈ℤqn, and a real β,(i)
SIS: to return a vector e∈ℤm satisfying that A⋅e=0modq, 0≠e∞≤β(ii)
ISIS: to return a vector e∈ℤm satisfying that A⋅e=umodq, e∞≤βLemma 3.
(see [27, 39]). For m,β=polyn,q≥β⋅O˜n, the average-caseISIS problems are at least as hard as the SIVPγ problem in the worst-case to within γ=β⋅O˜nm factor.Definition 2 (LWE).
Given a randoms∈ℤqn, a probability distribution χ∈ℤ, define As,χ by sampling A∈ℤqn×m, e⟵Rχm, outputting A,ATs+e, to make distinguish between As,χ and U∈ℤqn×m×ℤqm. Define β≥n⋅ωlogn, q=pe where p is a prime, e∈ℤ, and χ=Dℤm,s, the LWE problem is as hard as SIVPO˜nq/β.Lemma 4.
(see [40]). Let n≥1 and prime q≥2, assume that m>n+1logn+ωlogn. Matrices A,B⟵Rℤqn×m and R⟵R−1,1m×m. Thus, A,AR,RTe is close to A,B,RTe where e∈ℤqm.Lemma 5.
(see [40]). Let R⟵R−1,1m×m; thus, PrRe∞>e∞⋅ωlogm<neglm where e∈ℝm.Lemma 6.
(see [40]). Let q≥3, A,B⟵Rℤqn×m, and s≥R˜B⋅m⋅ωlogm. Given a trapdoor RB of Λq⊥B, R∈−1,1m×m, and u∈ℤqn. A PPT algorithm SampleRA,B,R,RB,u,s will output e∈ℤ2m distributed statistically close to DΛquA|AR+B,s.


## 2.1. Notations

Table2 refers to the notations used in our work.Table 2
Notations of our work.
NotationDefinitionSkAll permutation ofk elements←RSampling uniformly at random⋅, or ⋅∞Euclidean normℓ2 or the infinity norm ℓ∞Parsee,k1,k2ek1,ek1+1,…,ek2∈ℝk2−k1+1, e=e1,e2,…,en∈ℝn, 1≤k1≤k2≤nlogeLogarithm ofe with base 2PPTProbabilistic polynomial-time


## 2.2. GS-VLR

### 2.2.1. Syntax of GS-VLR

There are three polynomial-time algorithms:KeyGen1n,N: taking the security parameter n and group size N as input, this PPT algorithm will output group public-key Gpk, members secret signing keys Gsk=gsk0,gsk1,…,gskN−1, and members revocation tokens Grt=grt0,grt1,…,grtN−1.SignGpk,gski,m: taking Gpk and gski of member id with index i∈0,1,…,N−1 and message m∈0,1∗ as input, this PPT algorithm will output a signature σ.VerifyGpk,RL,σ,m: taking Gpk a subset of tokens RL⊆Grt, σ and m∈0,1∗ as input, this deterministic algorithm will output either 0 or 1. 1 means that σ is valid, and the real signer has not been revoked from the group.Correctness and security of GS-VLR: here, there are three main requirements: correctness, selfless-anonymity, and traceability.Correctness: for allGpk,Gsk,Grt outputted by KeyGen, any member i∈0,1,…,N−1, all gski∈Gsk, RL∈Grt, and m∈0,1∗, we have the conditions:(1)VerifyGpk,RL,SignGpk,gski,m,m=1⇔grti∉RL.Selfless-anonymity: in the following game, the goal of adversaryA is to determine which of the two adaptively chosen members id0 with an index i0 and id1 with an index i1 generated σ∗. A is not given either secret-key.Setup: the challenger C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk to A.Queries: A can adaptively make the following queries:(i)
Corruption: taking i as input, C returns gski.(ii)
Signing: taking i and m∈0,1∗ as input, C returns σ⟵SignGpk,gski,m.(iii)
Revocation: take i as input, C returns grti.Challenge: A outputs a message m∈0,1∗ and two distinct members id0 with an index i0 and id1 with an index i1. A should not make corruption query or revocation query at either member. C chooses a bit b⟵R0,1, computes σ∗⟵SignGpk,gskib,m∗ as a valid signature on m∗, and returns it to A.Restrictedqueries: once the challenge σ∗ is obtained, A can make queries as before without the rights to do the corruption or revocation query for id0 or id1 or opening query for m∗,σ∗.Output: A outputs a bit b′∈0,1 and wins if b′=b.AdvAself−anon=Prb′=b−1/2 is defined as A′s advantage in winning the above game. Thus, a GS-VLR satisfies the selfless-anonymity if AdvAself−anon is negligible.Traceability: in the following game, the goal ofA is to forge a signature that cannot be traced to any member in its collation.Setup: C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk,Grt to A. Let initial corruption set Corr=∅.Queries: A can adaptively make the corruption and signing queries as in selfless-anonymity and C additionally adds id with its index i to Corr.Forgery: A outputs a message m∗∈0,1∗, a set of members revocation tokens RL∗⊆Grt and a signature σ∗. A wins if(i)
VerifyGpk,RL∗,σ∗,m∗=1.(ii)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗.(iii)
σ∗ is not obtained by a query on m∗.AdvAtrace=SuccPTA is defined as A′s advantage in winning the above game. Thus, a GS-VLR scheme satisfies the traceability if AdvAtrace is negligible.


## 2.2.1. Syntax of GS-VLR

There are three polynomial-time algorithms:KeyGen1n,N: taking the security parameter n and group size N as input, this PPT algorithm will output group public-key Gpk, members secret signing keys Gsk=gsk0,gsk1,…,gskN−1, and members revocation tokens Grt=grt0,grt1,…,grtN−1.SignGpk,gski,m: taking Gpk and gski of member id with index i∈0,1,…,N−1 and message m∈0,1∗ as input, this PPT algorithm will output a signature σ.VerifyGpk,RL,σ,m: taking Gpk a subset of tokens RL⊆Grt, σ and m∈0,1∗ as input, this deterministic algorithm will output either 0 or 1. 1 means that σ is valid, and the real signer has not been revoked from the group.Correctness and security of GS-VLR: here, there are three main requirements: correctness, selfless-anonymity, and traceability.Correctness: for allGpk,Gsk,Grt outputted by KeyGen, any member i∈0,1,…,N−1, all gski∈Gsk, RL∈Grt, and m∈0,1∗, we have the conditions:(1)VerifyGpk,RL,SignGpk,gski,m,m=1⇔grti∉RL.Selfless-anonymity: in the following game, the goal of adversaryA is to determine which of the two adaptively chosen members id0 with an index i0 and id1 with an index i1 generated σ∗. A is not given either secret-key.Setup: the challenger C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk to A.Queries: A can adaptively make the following queries:(i)
Corruption: taking i as input, C returns gski.(ii)
Signing: taking i and m∈0,1∗ as input, C returns σ⟵SignGpk,gski,m.(iii)
Revocation: take i as input, C returns grti.Challenge: A outputs a message m∈0,1∗ and two distinct members id0 with an index i0 and id1 with an index i1. A should not make corruption query or revocation query at either member. C chooses a bit b⟵R0,1, computes σ∗⟵SignGpk,gskib,m∗ as a valid signature on m∗, and returns it to A.Restrictedqueries: once the challenge σ∗ is obtained, A can make queries as before without the rights to do the corruption or revocation query for id0 or id1 or opening query for m∗,σ∗.Output: A outputs a bit b′∈0,1 and wins if b′=b.AdvAself−anon=Prb′=b−1/2 is defined as A′s advantage in winning the above game. Thus, a GS-VLR satisfies the selfless-anonymity if AdvAself−anon is negligible.Traceability: in the following game, the goal ofA is to forge a signature that cannot be traced to any member in its collation.Setup: C runs KeyGen to obtain Gpk,Gsk,Grt and provides Gpk,Grt to A. Let initial corruption set Corr=∅.Queries: A can adaptively make the corruption and signing queries as in selfless-anonymity and C additionally adds id with its index i to Corr.Forgery: A outputs a message m∗∈0,1∗, a set of members revocation tokens RL∗⊆Grt and a signature σ∗. A wins if(i)
VerifyGpk,RL∗,σ∗,m∗=1.(ii)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗.(iii)
σ∗ is not obtained by a query on m∗.AdvAtrace=SuccPTA is defined as A′s advantage in winning the above game. Thus, a GS-VLR scheme satisfies the traceability if AdvAtrace is negligible.


## 2.3. Background on Lattices

Ajtai [36] first showed a strategy to generate statistically close to uniform A∈ℤqn×m together with low norm trapdoor basis of Λq⊥A=e∈ℤm|A⋅e=0modq. Subsequently, two new algorithms were given by [37, 38].Lemma 1.
(see [36–38]). Define n≥1, q≥2, and m=2n⌈logq⌉. A PPT algorithm TrapGenq,n,m outputs A and RA, such that A∈ℤqn×m is statistically close to uniform and RA is a trapdoor for Λq⊥A.
Gentry et al. [27] first introduced a method to sample short vector from some discrete Gaussian distribution, and then an improved algorithm was introduced in [38].Lemma 2.
(see [27, 38]). Let n≥1, q≥2, and m=2n⌈logq⌉. Given A∈ℤqn×m, a trapdoor RA of Λq⊥A, a parameter s=ωnlogqlogn, and u∈ℤqn. A PPT algorithm SamplePreA,RA,u,s will output a short e∈ΛquA sampled from a distribution close to DΛquA,s.
The short integer solution (SIS), ISIS (both inℓ∞ norm), and LWE problems are described as follows.Definition 1.
(SIS and ISIS). Given a randomA∈ℤqn×m, a random syndrome u∈ℤqn, and a real β,(i)
SIS: to return a vector e∈ℤm satisfying that A⋅e=0modq, 0≠e∞≤β(ii)
ISIS: to return a vector e∈ℤm satisfying that A⋅e=umodq, e∞≤βLemma 3.
(see [27, 39]). For m,β=polyn,q≥β⋅O˜n, the average-caseISIS problems are at least as hard as the SIVPγ problem in the worst-case to within γ=β⋅O˜nm factor.Definition 2 (LWE).
Given a randoms∈ℤqn, a probability distribution χ∈ℤ, define As,χ by sampling A∈ℤqn×m, e⟵Rχm, outputting A,ATs+e, to make distinguish between As,χ and U∈ℤqn×m×ℤqm. Define β≥n⋅ωlogn, q=pe where p is a prime, e∈ℤ, and χ=Dℤm,s, the LWE problem is as hard as SIVPO˜nq/β.Lemma 4.
(see [40]). Let n≥1 and prime q≥2, assume that m>n+1logn+ωlogn. Matrices A,B⟵Rℤqn×m and R⟵R−1,1m×m. Thus, A,AR,RTe is close to A,B,RTe where e∈ℤqm.Lemma 5.
(see [40]). Let R⟵R−1,1m×m; thus, PrRe∞>e∞⋅ωlogm<neglm where e∈ℝm.Lemma 6.
(see [40]). Let q≥3, A,B⟵Rℤqn×m, and s≥R˜B⋅m⋅ωlogm. Given a trapdoor RB of Λq⊥B, R∈−1,1m×m, and u∈ℤqn. A PPT algorithm SampleRA,B,R,RB,u,s will output e∈ℤ2m distributed statistically close to DΛquA|AR+B,s.


## 3. Preparations

### 3.1. The Improved Identity-Encoding Technique

The matrixB∈ℤqn×m of [23] is replaced by a random vector u∈ℤqn, i.e., Gpk=A0,A1,A2,u, and i’s secret signing key is a short vector ei=ei,0,ei,1∈ℤ2m that is in a coset of Λq⊥Ai, i.e., ΛquAi=ei∈ℤm|Ai⋅ei=umodq, and i’s revocation token is created by A0 and ei,0, i.e., grti=A0⋅ei,0modq∈ℤqn.To construct a secure Stern-type ZKAoK protocol, we transform the identity-encoding matrixAi=A0|A1+iA2∈ℤqn×2m for i into a new shape. We first give two new notations (we restate that the group is of N=2ℓ members):(i)
gℓ=1,2,22,…,2ℓ−1: a power-of-two vector, for integer i∈0,…,N−1, i=gℓT⋅Bini, where Bini∈0,1ℓ is i’s binary decomposition.(ii)
⊗: given A∈ℤqn×m, e=e1,e2,…,eℓ∈ℤqℓ, and e′∈ℤqm, we define(2)e⊗e′=e1e′,e2e′,…,eℓe′∈ℤqmℓ,e⊗A=e1Ae2A…|eℓA∈ℤqn×mℓ.Thus,Ai is transformed into some public A′ that is irrelevant to index i and(3)A′=A0A1A2π⋯|2ℓ−1A2=A0A1gℓ⊗A2∈ℤqn×ℓ+2m.Correspondingly,ei=ei,0,ei,1 is transformed to ei′=ei,0,ei,1,Bini⊗ei,1∈ℤℓ+2m.Therefore,Ai⋅ei=umodq is transformed into a new shape, (r.1) Ai⋅ei=A′⋅ei′=umodq.As for revocation mechanism, as that in [11], the signer’s grti is bound to an LWE function, (r.2) b=BT⋅grti+e=BTA0⋅ei,0+emodq, B∈ℤqn×m is from an oracle, and e⟵Rχm.In a nutshell, by creatively putting the transformation ideas and the Stern-extension argument system showed by Ling et al. [25] together, we will design a secure zero-knowledge protocol to prove (r.1) and (r.2).


### 3.2. A New Stern-Type Zero-Knowledge Proof Protocol

In our new underlying Stern-type ZKP protocol, the decomposition (Dec), extension (Ext), and matrix-extension (Mat-Ext) techniques are adopted. Specific sets are as follows:B2ℓ, B3m, Secβid, and SecExtid∗; permutations such as π,φ∈S3m and τ∈S2ℓ and a composition T are also used. We omit these duplicate concepts, and the detailed definitions can be found in literatures [10, 11, 25]. In addition, we define a series of integers: k=⌊logβ⌋+1,β1=⌈β/2⌉,β2=⌈β−β1/2⌉,…,βk=1.The underlying ZKP protocol between a proverP and any verifier V is as follows:(1)
The inputs includeA′=A0A1gℓ⊗A2∈ℤqn×ℓ+2m, B∈ℤqn×m, u∈ℤqn, and b∈ℤqm.(2)
P′s witnesses include e′=e0′,e1′,Bini⊗e1′∈Secβid corresponding to a secret identity index i∈0,1,…,N−1 and a vector e∈ℤm, an LWE error.(3)
P tries to convince V:(3.1)
A′⋅e′=umodq where e′∈Secβid, while keeping id=Bini∈0,1ℓ secret.(3.2)
b=BTA0⋅e0′+emodq, where 0<e0′∞,π∞≤β.For membership mechanism, i.e.,P′s goal is shown in 3.1. As in [32], P does as follows:(1)
ParseA′=A0A1gℓ⊗A2=A0A1A2⋯2ℓ−1A2, and use Mat-Ext technique to extend it to A∗=A00n×2mA10n×2mA20n×2m⋯2ℓ−1A20n×2m|0n×3mℓ.(2)
Parseid=Bini=d1,d2,…,dℓ, and extend it to id∗=d1,d2,…,dℓ,dℓ+1,…,d2ℓ∈B2ℓ.(3)
Parsee′=e0′,e1′,Bini⊗e1′=e0′,e1′,d1e1′,…,dℓe1′, and use Dec-Ext techniques extending e0′ and e1′ to k vectors e0,1′,e0,2′,…,e0,k′∈B3m and k vectors e1,1′,e1,2′,…,e1,k′∈B3m, respectively. Thus, for j∈1,2,…,k, we define ej′=e0,j′,e1,j′,d1e1,j′,…,dℓe1,j′ and then ej′∈SecExtid∗.P′s goal is transformed into (r.3) A∗⋅∑j=1kβjej′=umodq and ej′∈SecExtid∗.To prove (r.3), as in [32], we take the following 2 steps:(1)
Samplek uniform r1′,r2′,…,rk′⟵Rℤq2ℓ+23m to mask e1′,e2′,…,ek′; thus,(4)A∗⋅∑j=1kβjej′+rj′−u=A∗⋅∑j=1kβjrj′modq.(2)
Sampleπ,φ∈S3m, τ∈S2ℓ; thus, for j∈1,2,…,k, Tπ,φ,τej′∈SecExtτid∗.For revocation mechanism, i.e.,P′s goal is shown in 3.2. P does as follows:(1)
LetB′=BTA0modq∈ℤqm×m and ej,0′=Parseej′,1,m(2)
Parsee=e1,e2,…,em, and use Dec-Ext techniques to extend e to k vectors e1,e2,…,ek∈B3m(3)
DefineB∗=B′Im0n×2mP′s goal is transformed into (r.4):(5)ej∈B3m,b∗=B′⋅∑j=1kβjej,o′+Im|0n×2m⋅∑j=1kβjej=B∗⋅∑j=1kβjej,0′+ejmodq.To prove (r.4), we take the following 3 steps:(1)
Letrj,0=Parserj′,1,m.(2)
Samplek random r1,r2,…,rk⟵Rℤq3m to mask e1,e2,…,ek; thus,(6)B∗⋅∑j=1kβjej,0′+rj,0′,ej+rj−b=B∗⋅∑j=1kβjrj,0′,rjmodq.(3)
Sampleϕ∈S3m; thus, for j∈1,2,…,k, ϕej∈B3m.In our GS-VLR construction, we also adopt a statistically hiding and computationally blinding commitment scheme COM proposed in [41]. The randomness of COM is omitted.(1)
Commitments:P samples some objects as follows:(7)r1′,r2′,…,rk′⟵Rℤq2ℓ+23m;r1,r2,…,rk⟵Rℤq3m;π1,…,πk,φ1,…,φk,ϕ1,…,ϕk∈S3m;τ∈S2ℓ.Letrj,0′=Parserj′,1,m, j∈1,2,…,k. P sends CMT=c1,c2,c3 to V.(8)c1=COMπj,φj,ϕjj=1k;τ;A∗⋅∑j=1kβjrj′;B∗⋅∑j=1kβj⋅rj,0′,rj,c2=COMTπj,φj,τrj′,ϕjrjj=1k,c3=COMTπj,φj,τej′+rj′,ϕjej+rjj=1k..(2)
Challenge:V samples a challenge Ch⟵R1,2,3 and transfers to P.(3)
Response:P does as follows:(i)
Ch=1. For j∈1,2,…,k, let vj′=Tπj,φj,τej′, wj′=Tπj,φj,τrj′, vj=ϕjej, wj=ϕjrj, and tid=τid∗, define RSP=vj′,wj′,vj,wjj=1k,tid(ii)
Ch=2. For j∈1,2,…,k, let π⌢j=πj, φ⌢j=φj, ϕ⌢j=ϕj, τ⌢=τ, xj′=ej′+rj′, and xj=ej+rj, define RSP=π⌢j,φ⌢j,ϕ⌢j,xj′,xjj=1k,τ⌢(iii)
Ch=3. For j∈1,2,…,k, let π˜j=πj, φ˜j=φj, ϕ˜j=ϕj, τ˜=τ, hj′=rj′, and hj=rj, define RSP=π˜j,φ˜j,ϕ˜j,hj′,hjj=1k,τ˜(4)
Verification:V does as follows:(i)
Ch=1. Check that tid∈B2ℓ, vj′∈SecExttid, vj∈B3m, and(9)c2=COMwj′,wjj=1k,c3=COMvj′+wj′,vj+wjj=1k.(ii)
Ch=2. Let xj′=Parsexj′,1,m, check(10)c1=COMπ⌢j,φ⌢j,ϕ⌢jj=1k;τ⌢;A∗⋅∑j=1kβjxj′−u;B∗⋅∑j=1kβjxj,0′,xj−b,c3=COMTπ⌢j,φ⌢j,τ⌢xj′,ϕ⌢jxjj=1k.(iii)
Ch=3. Let hj,0′=Parsehj,0′,1,m, check(11)c1=COMπ˜j,φ˜j,ϕ˜jj=1k;τ˜;A∗⋅∑j=1kβjhj′;B∗⋅∑j=1kβjhj,0′,hj,c3=COMTπ˜j,φ˜j,τ˜hj′,ϕ˜jhjj=1k.If all the conditions hold,V outputs 1. The relation ℛn,k,ℓ,q,m,β is defined as follows:(12)ℛ=A0,A1,A2,B∈ℤqn×m,u∈ℤqn,b∈ℤqm,id=Bini,e∈ℤme′=e0′,e1′,Bini⊗e1′∈Secβid;s.t.0<e′∞,e∞≤βb=BT⋅A0⋅e0′+emodq,A0A1gℓ⊗A2⋅e′=umodq.


### 3.3. Analysis of the Protocol

Theorem 1.
If COM enjoys the properties as in [41], then the proposed protocol is a statistical ZKAoK for ℛn,k,ℓ,q,m,β, its every whole interaction has perfect completeness, soundness error 2/3, argument of knowledge property, and communication cost ℓ⋅O˜n.Proof.
The details were given in [32], published in the proceedings of ISC 2019. The readers can refer to [32] directly; therefore, we omit them here.


## 3.1. The Improved Identity-Encoding Technique

The matrixB∈ℤqn×m of [23] is replaced by a random vector u∈ℤqn, i.e., Gpk=A0,A1,A2,u, and i’s secret signing key is a short vector ei=ei,0,ei,1∈ℤ2m that is in a coset of Λq⊥Ai, i.e., ΛquAi=ei∈ℤm|Ai⋅ei=umodq, and i’s revocation token is created by A0 and ei,0, i.e., grti=A0⋅ei,0modq∈ℤqn.To construct a secure Stern-type ZKAoK protocol, we transform the identity-encoding matrixAi=A0|A1+iA2∈ℤqn×2m for i into a new shape. We first give two new notations (we restate that the group is of N=2ℓ members):(i)
gℓ=1,2,22,…,2ℓ−1: a power-of-two vector, for integer i∈0,…,N−1, i=gℓT⋅Bini, where Bini∈0,1ℓ is i’s binary decomposition.(ii)
⊗: given A∈ℤqn×m, e=e1,e2,…,eℓ∈ℤqℓ, and e′∈ℤqm, we define(2)e⊗e′=e1e′,e2e′,…,eℓe′∈ℤqmℓ,e⊗A=e1Ae2A…|eℓA∈ℤqn×mℓ.Thus,Ai is transformed into some public A′ that is irrelevant to index i and(3)A′=A0A1A2π⋯|2ℓ−1A2=A0A1gℓ⊗A2∈ℤqn×ℓ+2m.Correspondingly,ei=ei,0,ei,1 is transformed to ei′=ei,0,ei,1,Bini⊗ei,1∈ℤℓ+2m.Therefore,Ai⋅ei=umodq is transformed into a new shape, (r.1) Ai⋅ei=A′⋅ei′=umodq.As for revocation mechanism, as that in [11], the signer’s grti is bound to an LWE function, (r.2) b=BT⋅grti+e=BTA0⋅ei,0+emodq, B∈ℤqn×m is from an oracle, and e⟵Rχm.In a nutshell, by creatively putting the transformation ideas and the Stern-extension argument system showed by Ling et al. [25] together, we will design a secure zero-knowledge protocol to prove (r.1) and (r.2).


## 3.2. A New Stern-Type Zero-Knowledge Proof Protocol

In our new underlying Stern-type ZKP protocol, the decomposition (Dec), extension (Ext), and matrix-extension (Mat-Ext) techniques are adopted. Specific sets are as follows:B2ℓ, B3m, Secβid, and SecExtid∗; permutations such as π,φ∈S3m and τ∈S2ℓ and a composition T are also used. We omit these duplicate concepts, and the detailed definitions can be found in literatures [10, 11, 25]. In addition, we define a series of integers: k=⌊logβ⌋+1,β1=⌈β/2⌉,β2=⌈β−β1/2⌉,…,βk=1.The underlying ZKP protocol between a proverP and any verifier V is as follows:(1)
The inputs includeA′=A0A1gℓ⊗A2∈ℤqn×ℓ+2m, B∈ℤqn×m, u∈ℤqn, and b∈ℤqm.(2)
P′s witnesses include e′=e0′,e1′,Bini⊗e1′∈Secβid corresponding to a secret identity index i∈0,1,…,N−1 and a vector e∈ℤm, an LWE error.(3)
P tries to convince V:(3.1)
A′⋅e′=umodq where e′∈Secβid, while keeping id=Bini∈0,1ℓ secret.(3.2)
b=BTA0⋅e0′+emodq, where 0<e0′∞,π∞≤β.For membership mechanism, i.e.,P′s goal is shown in 3.1. As in [32], P does as follows:(1)
ParseA′=A0A1gℓ⊗A2=A0A1A2⋯2ℓ−1A2, and use Mat-Ext technique to extend it to A∗=A00n×2mA10n×2mA20n×2m⋯2ℓ−1A20n×2m|0n×3mℓ.(2)
Parseid=Bini=d1,d2,…,dℓ, and extend it to id∗=d1,d2,…,dℓ,dℓ+1,…,d2ℓ∈B2ℓ.(3)
Parsee′=e0′,e1′,Bini⊗e1′=e0′,e1′,d1e1′,…,dℓe1′, and use Dec-Ext techniques extending e0′ and e1′ to k vectors e0,1′,e0,2′,…,e0,k′∈B3m and k vectors e1,1′,e1,2′,…,e1,k′∈B3m, respectively. Thus, for j∈1,2,…,k, we define ej′=e0,j′,e1,j′,d1e1,j′,…,dℓe1,j′ and then ej′∈SecExtid∗.P′s goal is transformed into (r.3) A∗⋅∑j=1kβjej′=umodq and ej′∈SecExtid∗.To prove (r.3), as in [32], we take the following 2 steps:(1)
Samplek uniform r1′,r2′,…,rk′⟵Rℤq2ℓ+23m to mask e1′,e2′,…,ek′; thus,(4)A∗⋅∑j=1kβjej′+rj′−u=A∗⋅∑j=1kβjrj′modq.(2)
Sampleπ,φ∈S3m, τ∈S2ℓ; thus, for j∈1,2,…,k, Tπ,φ,τej′∈SecExtτid∗.For revocation mechanism, i.e.,P′s goal is shown in 3.2. P does as follows:(1)
LetB′=BTA0modq∈ℤqm×m and ej,0′=Parseej′,1,m(2)
Parsee=e1,e2,…,em, and use Dec-Ext techniques to extend e to k vectors e1,e2,…,ek∈B3m(3)
DefineB∗=B′Im0n×2mP′s goal is transformed into (r.4):(5)ej∈B3m,b∗=B′⋅∑j=1kβjej,o′+Im|0n×2m⋅∑j=1kβjej=B∗⋅∑j=1kβjej,0′+ejmodq.To prove (r.4), we take the following 3 steps:(1)
Letrj,0=Parserj′,1,m.(2)
Samplek random r1,r2,…,rk⟵Rℤq3m to mask e1,e2,…,ek; thus,(6)B∗⋅∑j=1kβjej,0′+rj,0′,ej+rj−b=B∗⋅∑j=1kβjrj,0′,rjmodq.(3)
Sampleϕ∈S3m; thus, for j∈1,2,…,k, ϕej∈B3m.In our GS-VLR construction, we also adopt a statistically hiding and computationally blinding commitment scheme COM proposed in [41]. The randomness of COM is omitted.(1)
Commitments:P samples some objects as follows:(7)r1′,r2′,…,rk′⟵Rℤq2ℓ+23m;r1,r2,…,rk⟵Rℤq3m;π1,…,πk,φ1,…,φk,ϕ1,…,ϕk∈S3m;τ∈S2ℓ.Letrj,0′=Parserj′,1,m, j∈1,2,…,k. P sends CMT=c1,c2,c3 to V.(8)c1=COMπj,φj,ϕjj=1k;τ;A∗⋅∑j=1kβjrj′;B∗⋅∑j=1kβj⋅rj,0′,rj,c2=COMTπj,φj,τrj′,ϕjrjj=1k,c3=COMTπj,φj,τej′+rj′,ϕjej+rjj=1k..(2)
Challenge:V samples a challenge Ch⟵R1,2,3 and transfers to P.(3)
Response:P does as follows:(i)
Ch=1. For j∈1,2,…,k, let vj′=Tπj,φj,τej′, wj′=Tπj,φj,τrj′, vj=ϕjej, wj=ϕjrj, and tid=τid∗, define RSP=vj′,wj′,vj,wjj=1k,tid(ii)
Ch=2. For j∈1,2,…,k, let π⌢j=πj, φ⌢j=φj, ϕ⌢j=ϕj, τ⌢=τ, xj′=ej′+rj′, and xj=ej+rj, define RSP=π⌢j,φ⌢j,ϕ⌢j,xj′,xjj=1k,τ⌢(iii)
Ch=3. For j∈1,2,…,k, let π˜j=πj, φ˜j=φj, ϕ˜j=ϕj, τ˜=τ, hj′=rj′, and hj=rj, define RSP=π˜j,φ˜j,ϕ˜j,hj′,hjj=1k,τ˜(4)
Verification:V does as follows:(i)
Ch=1. Check that tid∈B2ℓ, vj′∈SecExttid, vj∈B3m, and(9)c2=COMwj′,wjj=1k,c3=COMvj′+wj′,vj+wjj=1k.(ii)
Ch=2. Let xj′=Parsexj′,1,m, check(10)c1=COMπ⌢j,φ⌢j,ϕ⌢jj=1k;τ⌢;A∗⋅∑j=1kβjxj′−u;B∗⋅∑j=1kβjxj,0′,xj−b,c3=COMTπ⌢j,φ⌢j,τ⌢xj′,ϕ⌢jxjj=1k.(iii)
Ch=3. Let hj,0′=Parsehj,0′,1,m, check(11)c1=COMπ˜j,φ˜j,ϕ˜jj=1k;τ˜;A∗⋅∑j=1kβjhj′;B∗⋅∑j=1kβjhj,0′,hj,c3=COMTπ˜j,φ˜j,τ˜hj′,ϕ˜jhjj=1k.If all the conditions hold,V outputs 1. The relation ℛn,k,ℓ,q,m,β is defined as follows:(12)ℛ=A0,A1,A2,B∈ℤqn×m,u∈ℤqn,b∈ℤqm,id=Bini,e∈ℤme′=e0′,e1′,Bini⊗e1′∈Secβid;s.t.0<e′∞,e∞≤βb=BT⋅A0⋅e0′+emodq,A0A1gℓ⊗A2⋅e′=umodq.


## 3.3. Analysis of the Protocol

Theorem 1.
If COM enjoys the properties as in [41], then the proposed protocol is a statistical ZKAoK for ℛn,k,ℓ,q,m,β, its every whole interaction has perfect completeness, soundness error 2/3, argument of knowledge property, and communication cost ℓ⋅O˜n.Proof.
The details were given in [32], published in the proceedings of ISC 2019. The readers can refer to [32] directly; therefore, we omit them here.


## 4. Our Improved GS-VLR over Lattices

### 4.1. Description of the Scheme

#### 4.1.1. KeyGen1n,N

Take a security parametern and the group size N as input. Define the prime q=ωn2logn>N, dimension m=2n⌈logq⌉, parameter s=ωnlogqlogn, and integer bound β=⌈s⋅logm⌉ satisfying that 4β+12≤q. This algorithm does as follows:(1)
RunTrapGenq,n,m to get A0∈ℤqn×m and trapdoor RA0.(2)
ChooseA1,A2⟵Rℤqn×m and u⟵Rℤqn.(3)
As in [23], for i∈0,1,…,N−1, let Ai=A0|A1+iA2∈ℤqn×2m and proceed as follows:(3.1)
Chooseei,1⟵RDℤm,s, let ui=A1+iA2⋅ei,1. Run SamplePreA0,RA0,u−ui,s to obtain ei,0∈ℤm.(3.2)
Letei=ei,0,ei,1∈ℤ2m. Thus, Ai⋅ei=umodq and 0<ei∞≤β.(3.3)
Leti’s secret signing key be gski=ei and its token be grti=A0⋅ei,0modq.(4)
OutputGpk=A0,A1,A2,u, Gsk=gsk0,gsk1,…,gskN−1, and Grt=grt0,grt1,…,grtN−1.


#### 4.1.2. SignGpk,gski,m

Choose hash functions:H:0,1∗⟶1,2,3ωlogn, G:0,1∗⟶ℤqn×m, and a β−bounded distribution χ∈ℤ. Take Gpk, m∈0,1∗ as input, a member i with secret-key gski=ei proceeds as follows:(1)
Choosev⟵R0,1n, let B=GA0,A1,A2,u,m,v∈ℤqn×m.(2)
Choosee⟵Rχm, let b=BT⋅grti+e=BTA0⋅ei,0+emodq.(3)
Design a ZKP protocol to prove that the signer is a valid member which is achieved by repeatingωlogn times the underlying protocol as in Section 3.2 with A0,A1,A2,B,u,b and a witness id,gski,e, and then make it noninteractive as Π=CMTjj∈1,2,…,k,CH,RSPjj∈1,2,…,k where CH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k.(4)
Outputσ=m,Π,v,b.


#### 4.1.3. VerifyGpk,RL,σ,m

TakingGpk, m,σ, and RL=grti′0≤i′≤N−1⊆Grt as input, the verifier proceeds as follows:(1)
Parseσ=m,Π,v,b(2)
Check that whetherCH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k(3)
Run step 4 of the protocol in Section3.2 to check the validity of RSPj w.r.t. CMTj and Chj(4)
DefineB=GA0,A1,A2,u,m,v, for grti′∈RL, compute ei′=b−BTgrti′modq, and check that whether ei′∞>β(5)
If all are satisfied, output 1 and acceptσ; otherwise 0


### 4.2. Analysis of the Scheme

#### 4.2.1. Efficiency

For our new scheme, three public matrices are needed for identity-encoding; thus, the bit-sizes ofGpk, gsk, and σ are O˜n2, O˜n, and logN⋅O˜n, respectively. Compared with previous GS-VLR schemes over lattices, the OlogN factor for the bit-sizes of Gpk and gsk in the new construction is eliminated; meanwhile, it is also free of any encryptions.Theorem 2.
With an overwhelming probability, the scheme in Section4.1 is correct.Proof.
A memberi owning a valid witness ei′,e∈Secβid×χm can return a signature meeting the first three steps of Verify. As for step 4, the vector ei′ can be expressed as follows:(13)ei′=b−BTgrti=BTgrti+e−BTgrti′=BT⋅grti−grti′+emodq.(1)
To prove thatgrti∉RL⇒VerifyGpk,RL,SignGpk,gski,m,m=1.Suppose thatgrti∉RL; to prove that with an overwhelming probability, step 4 is satisfied, i.e., ei′∞>β and VerifyGpk,RL,SignGpk,gski,m,m=1. For all grti′∈RL, the following is the establishment: BTgrti−grti′=ei′−emodq. Defining si′=grti−grti′modq, we have that BTsi′∞≤ei′∞+e∞≤ei′∞+β. In addition, according to [11], BTsi′∞>2β with an overwhelming probability; thus, ei′∞>2β−β=β.(2)
To prove thatVerifyGpk,RL,SignGpk,gski,m,m=1⇒grti′∈RL.
Suppose thatVerifyGpk,RL,SignGpk,gski,m,m=1. For every grti′∈RL, we have that ei′∞>β. Therefore, if there is index i′ satisfying that grti=grti′, we have that ei′=e. Thus, ei′∞=π∞≤β and σ fails the step 4 of Verify. So, it is obviously a conflict. This concludes the correctness proof.Theorem 3.
IfCOM enjoys the property of statistically hiding as in [41], the proposed scheme is selfless-anonymous in the random oracle model.Proof.
A series of games is established as follows:Game 0:C proceeds as follows:(1)
RunKeyGen to get Gpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1. Set RL=∅ and Corr=∅, and send Gpk to A(2)
ForA′s corruption queries for a member i, C sets Corr=Corr∪i and returns gski; for A′s signing queries on m for i, C outputs σ⟵SignGpk,gski,m; for A′s revocation queries for i, C sets RL=RL∪grti and outputs gski to A(3)
A outputs a message m∈0,1∗, members i0 and i1, for b∈0,1, ib∉Corr and grtib∉RL(4)
C chooses b⟵R0,1, generates σ∗⟵SignGpk,gskib,m∗=m∗,Π,v,b, and outputs it(5)
A makes queries as before without the rights to ask for gskib or grtib for each b∈0,1(6)
Finally,A outputs a bit b′∈0,1Game 1:C simulates step 4 of Sign by programming the oracle:(1)
Choosev⟵R0,1n and e⟵Rχm; let B=GA0,A1,A2,u,m,v and b=BT⋅grtib+emodq(2)
ProgramHm∗,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k=Chjj∈1,…,k; other algorithms are as in the proof of Theorem 1(3)
Outputσ⌢∗=m∗,Π∗,v,bGame 2:C defines b=BT⋅r+emodq, so b is close to the one in Game 1, and thus Game 2 is statistically indistinguishable with Game 1.Game 3:C defines B,b⟵RU, so B,b is close to the one in Game 2. Thus, Games 3 and 2 are computationally indistinguishable. Furthermore, the advantage AdvAself−anon is 0.
According to the indistinguishability of Games 1, 2, and 3, the advantageAdvAself−anon in Game 1 is negligible; therefore, our new scheme satisfies the definition of selfless-anonymity.Theorem 4.
SupposeSIS within β′=polym factor is hard, the proposed scheme is traceable.Proof.
Suppose with an advantageε, a forger ℱ breaks the scheme. By using ℱ, we construct an efficient A to solve a SIS instance A⌢∈ℤqn×m within β′=2β⋅1+ωlogm factor.


#### 4.2.2. Setup

A proceeds as follows:(1)
Choosee0∗,e1∗⟵RDℤm,s, R⟵R−1,1m×m, and i∗∈0,1,…,N−1(2)
RunTrapGen to get A2∈ℤqn×m and a trapdoor RA2(3)
DefineA0=A⌢, A1=A0⋅R−i∗A2modq, and u=A0⋅e0∗+R⋅e1∗modq(4)
Fori=i∗, let gski∗=e0∗,e1∗ and grti∗=A0⋅e0∗modq(5)
Fori∈0,1,…,N−1/i∗, let Ai=A0|A1+i⋅A2, run SampleRA0,A2,R,RA2,u,s to obtain ei=ei,0,ei,1∈ℤ2m, and let gski=ei, grti=A0⋅ei,0modq(6)
LetGpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1, transfer Gsk and Grt to ℱ


#### 4.2.3. Queries

ℱ proceeds as follows:(1)
Corruption. Taking i as input, A outputs grti and adds i to Corr.(2)
Signing. Taking i and m∈0,1∗ as input, A outputs σ⟵SignGpk,gski,m. In particular, the values in 1,2,3ωlogn are sampled as responses to H. Let rd be a reply to the d-th (d≤qH) query (here, qH is the whole number of oracle queries for H).


#### 4.2.4. Forgery

ℱ returns m∗∈0,1∗, RL∗⊆Grt, and a forged σ∗=m∗,Π∗,v∗,b∗ which satisfies the following:(1)
VerifyGpk,RL∗,σ∗,m∗=1(2)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗ℱ proceeds as in [11]; let B=GA0,A1,A2,u,m∗,v∗∈ℤqn×m. A obtains a 3-fork involving Δ=m∗,A0,A1,A2,u,B∗,b∗,CMTjj∈1,…,k after at most 32⋅qH/ε−3−k operations of ℱ.With the help of an extractorK in the proof of Theorem 1, we get a valid(14)witness=id=Bini∈0,1ℓ,ei=ei,0,ei,1∈ℤ2m,e∗∈ℤm,such that(1)
A0|A1+iA2⋅ei=umodq and ei∈Secβid(2)
b∗=B∗T⋅A0⋅ei,0+e∗modq and 0<e∗∞≤βIn the following, we show two cases:(1)
Ifi≠i∗ (the probability is at most N−1/N), A aborts.(2)
Ifi=i∗, A returns e⌢=e0∗−ei∗,0+R⋅e1∗−ei∗,1. Thus, we have that(15)A⌢⋅e⌢=A0⋅e0∗−ei∗,0+R⋅e1∗−ei∗,1=A0⋅e0∗+R⋅e1∗︸u−A0⋅ei∗,0+R⋅ei∗,1︸u=0modq.In the followings, we show that with a high probability,e⌢≠0modq and ||e⌢||∞≤polym.(1)
e⌢∞≤polym: for j∈0,1, ei∗∞,ei∗,j∞≤β and R⟵R−1,1m×m; thus, we have that(16)e⌢∞≤1+ωlogm⋅2β=polym.(2)
e⌢≠0modq: since σ∗=m∗,Π∗,v∗,b∗ is a forged signature, the implicit-tracing does not succeed or returns a member not included in Corr/RL∗.(2.1)
If the implicit-tracing will not succeed,VerifyGpk,grti∗,σ∗,m∗=1 will indicate that(17)A0⋅ei∗,0modq≠grti∗=A0⋅e0∗modqei∗,0≠e0∗.(2.2)
If the implicit-tracing returns a member not included inj∗∉Corr/RL∗, we have that VerifyGpk,grtj∗,σ∗,m∗=0 and VerifyGpk,RL∗,σ∗,m∗=1. Thus, we get the conclusions as follows:(2.2.1)
grtj∗≠RL∗; thus, j∗∈Corr.(2.2.2)
Sinceb−B∗T⋅grtj∗∞=B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤β, e∗∞≤β. So, B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤2β, and based on [23], we come to the conclusion that with an overwhelming probability, grtj∗=A0⋅ei∗,0modq.Next, we consider the following:(2.2.3)
Ifℱ has never requested gski∗, e0∗,e1∗ will not be known to ℱ; thus, we have that e0∗,e1∗≠ei∗,0,ei∗,1 with overwhelming probability.(2.2.4)
Ifℱ has requested gski∗, we have that i∗∈Corr, i∗≠j∗, grti∗≠grtj∗, and e0∗≠ei∗,0.According to the previous analysis, the same as in [32], for the different cases in 2.1 and 2.2.4 (suppose e1∗=ei∗,1) and in 2.1, 2.2.3, and 2.2.4 (suppose e1∗≠ei∗,1), we have the conclusion that with probability 1−exp−O˜n, e⌢≠0modq. Therefore, based on the above analysis, we come to the conclusion that with a probability ε′≥ε/2N⋅1−7/9k⋅1−exp−O˜n, e⌢ will satisfy A⌢⋅e⌢=0modq and 0≠e⌢∞≤2β⋅1+ωlogm=β′=polym.


## 4.1. Description of the Scheme

### 4.1.1. KeyGen1n,N

Take a security parametern and the group size N as input. Define the prime q=ωn2logn>N, dimension m=2n⌈logq⌉, parameter s=ωnlogqlogn, and integer bound β=⌈s⋅logm⌉ satisfying that 4β+12≤q. This algorithm does as follows:(1)
RunTrapGenq,n,m to get A0∈ℤqn×m and trapdoor RA0.(2)
ChooseA1,A2⟵Rℤqn×m and u⟵Rℤqn.(3)
As in [23], for i∈0,1,…,N−1, let Ai=A0|A1+iA2∈ℤqn×2m and proceed as follows:(3.1)
Chooseei,1⟵RDℤm,s, let ui=A1+iA2⋅ei,1. Run SamplePreA0,RA0,u−ui,s to obtain ei,0∈ℤm.(3.2)
Letei=ei,0,ei,1∈ℤ2m. Thus, Ai⋅ei=umodq and 0<ei∞≤β.(3.3)
Leti’s secret signing key be gski=ei and its token be grti=A0⋅ei,0modq.(4)
OutputGpk=A0,A1,A2,u, Gsk=gsk0,gsk1,…,gskN−1, and Grt=grt0,grt1,…,grtN−1.


### 4.1.2. SignGpk,gski,m

Choose hash functions:H:0,1∗⟶1,2,3ωlogn, G:0,1∗⟶ℤqn×m, and a β−bounded distribution χ∈ℤ. Take Gpk, m∈0,1∗ as input, a member i with secret-key gski=ei proceeds as follows:(1)
Choosev⟵R0,1n, let B=GA0,A1,A2,u,m,v∈ℤqn×m.(2)
Choosee⟵Rχm, let b=BT⋅grti+e=BTA0⋅ei,0+emodq.(3)
Design a ZKP protocol to prove that the signer is a valid member which is achieved by repeatingωlogn times the underlying protocol as in Section 3.2 with A0,A1,A2,B,u,b and a witness id,gski,e, and then make it noninteractive as Π=CMTjj∈1,2,…,k,CH,RSPjj∈1,2,…,k where CH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k.(4)
Outputσ=m,Π,v,b.


### 4.1.3. VerifyGpk,RL,σ,m

TakingGpk, m,σ, and RL=grti′0≤i′≤N−1⊆Grt as input, the verifier proceeds as follows:(1)
Parseσ=m,Π,v,b(2)
Check that whetherCH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k(3)
Run step 4 of the protocol in Section3.2 to check the validity of RSPj w.r.t. CMTj and Chj(4)
DefineB=GA0,A1,A2,u,m,v, for grti′∈RL, compute ei′=b−BTgrti′modq, and check that whether ei′∞>β(5)
If all are satisfied, output 1 and acceptσ; otherwise 0


## 4.1.1. KeyGen1n,N

Take a security parametern and the group size N as input. Define the prime q=ωn2logn>N, dimension m=2n⌈logq⌉, parameter s=ωnlogqlogn, and integer bound β=⌈s⋅logm⌉ satisfying that 4β+12≤q. This algorithm does as follows:(1)
RunTrapGenq,n,m to get A0∈ℤqn×m and trapdoor RA0.(2)
ChooseA1,A2⟵Rℤqn×m and u⟵Rℤqn.(3)
As in [23], for i∈0,1,…,N−1, let Ai=A0|A1+iA2∈ℤqn×2m and proceed as follows:(3.1)
Chooseei,1⟵RDℤm,s, let ui=A1+iA2⋅ei,1. Run SamplePreA0,RA0,u−ui,s to obtain ei,0∈ℤm.(3.2)
Letei=ei,0,ei,1∈ℤ2m. Thus, Ai⋅ei=umodq and 0<ei∞≤β.(3.3)
Leti’s secret signing key be gski=ei and its token be grti=A0⋅ei,0modq.(4)
OutputGpk=A0,A1,A2,u, Gsk=gsk0,gsk1,…,gskN−1, and Grt=grt0,grt1,…,grtN−1.


## 4.1.2. SignGpk,gski,m

Choose hash functions:H:0,1∗⟶1,2,3ωlogn, G:0,1∗⟶ℤqn×m, and a β−bounded distribution χ∈ℤ. Take Gpk, m∈0,1∗ as input, a member i with secret-key gski=ei proceeds as follows:(1)
Choosev⟵R0,1n, let B=GA0,A1,A2,u,m,v∈ℤqn×m.(2)
Choosee⟵Rχm, let b=BT⋅grti+e=BTA0⋅ei,0+emodq.(3)
Design a ZKP protocol to prove that the signer is a valid member which is achieved by repeatingωlogn times the underlying protocol as in Section 3.2 with A0,A1,A2,B,u,b and a witness id,gski,e, and then make it noninteractive as Π=CMTjj∈1,2,…,k,CH,RSPjj∈1,2,…,k where CH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k.(4)
Outputσ=m,Π,v,b.


## 4.1.3. VerifyGpk,RL,σ,m

TakingGpk, m,σ, and RL=grti′0≤i′≤N−1⊆Grt as input, the verifier proceeds as follows:(1)
Parseσ=m,Π,v,b(2)
Check that whetherCH=Chjj∈1,2,…,k=Hm,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k(3)
Run step 4 of the protocol in Section3.2 to check the validity of RSPj w.r.t. CMTj and Chj(4)
DefineB=GA0,A1,A2,u,m,v, for grti′∈RL, compute ei′=b−BTgrti′modq, and check that whether ei′∞>β(5)
If all are satisfied, output 1 and acceptσ; otherwise 0


## 4.2. Analysis of the Scheme

### 4.2.1. Efficiency

For our new scheme, three public matrices are needed for identity-encoding; thus, the bit-sizes ofGpk, gsk, and σ are O˜n2, O˜n, and logN⋅O˜n, respectively. Compared with previous GS-VLR schemes over lattices, the OlogN factor for the bit-sizes of Gpk and gsk in the new construction is eliminated; meanwhile, it is also free of any encryptions.Theorem 2.
With an overwhelming probability, the scheme in Section4.1 is correct.Proof.
A memberi owning a valid witness ei′,e∈Secβid×χm can return a signature meeting the first three steps of Verify. As for step 4, the vector ei′ can be expressed as follows:(13)ei′=b−BTgrti=BTgrti+e−BTgrti′=BT⋅grti−grti′+emodq.(1)
To prove thatgrti∉RL⇒VerifyGpk,RL,SignGpk,gski,m,m=1.Suppose thatgrti∉RL; to prove that with an overwhelming probability, step 4 is satisfied, i.e., ei′∞>β and VerifyGpk,RL,SignGpk,gski,m,m=1. For all grti′∈RL, the following is the establishment: BTgrti−grti′=ei′−emodq. Defining si′=grti−grti′modq, we have that BTsi′∞≤ei′∞+e∞≤ei′∞+β. In addition, according to [11], BTsi′∞>2β with an overwhelming probability; thus, ei′∞>2β−β=β.(2)
To prove thatVerifyGpk,RL,SignGpk,gski,m,m=1⇒grti′∈RL.
Suppose thatVerifyGpk,RL,SignGpk,gski,m,m=1. For every grti′∈RL, we have that ei′∞>β. Therefore, if there is index i′ satisfying that grti=grti′, we have that ei′=e. Thus, ei′∞=π∞≤β and σ fails the step 4 of Verify. So, it is obviously a conflict. This concludes the correctness proof.Theorem 3.
IfCOM enjoys the property of statistically hiding as in [41], the proposed scheme is selfless-anonymous in the random oracle model.Proof.
A series of games is established as follows:Game 0:C proceeds as follows:(1)
RunKeyGen to get Gpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1. Set RL=∅ and Corr=∅, and send Gpk to A(2)
ForA′s corruption queries for a member i, C sets Corr=Corr∪i and returns gski; for A′s signing queries on m for i, C outputs σ⟵SignGpk,gski,m; for A′s revocation queries for i, C sets RL=RL∪grti and outputs gski to A(3)
A outputs a message m∈0,1∗, members i0 and i1, for b∈0,1, ib∉Corr and grtib∉RL(4)
C chooses b⟵R0,1, generates σ∗⟵SignGpk,gskib,m∗=m∗,Π,v,b, and outputs it(5)
A makes queries as before without the rights to ask for gskib or grtib for each b∈0,1(6)
Finally,A outputs a bit b′∈0,1Game 1:C simulates step 4 of Sign by programming the oracle:(1)
Choosev⟵R0,1n and e⟵Rχm; let B=GA0,A1,A2,u,m,v and b=BT⋅grtib+emodq(2)
ProgramHm∗,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k=Chjj∈1,…,k; other algorithms are as in the proof of Theorem 1(3)
Outputσ⌢∗=m∗,Π∗,v,bGame 2:C defines b=BT⋅r+emodq, so b is close to the one in Game 1, and thus Game 2 is statistically indistinguishable with Game 1.Game 3:C defines B,b⟵RU, so B,b is close to the one in Game 2. Thus, Games 3 and 2 are computationally indistinguishable. Furthermore, the advantage AdvAself−anon is 0.
According to the indistinguishability of Games 1, 2, and 3, the advantageAdvAself−anon in Game 1 is negligible; therefore, our new scheme satisfies the definition of selfless-anonymity.Theorem 4.
SupposeSIS within β′=polym factor is hard, the proposed scheme is traceable.Proof.
Suppose with an advantageε, a forger ℱ breaks the scheme. By using ℱ, we construct an efficient A to solve a SIS instance A⌢∈ℤqn×m within β′=2β⋅1+ωlogm factor.


### 4.2.2. Setup

A proceeds as follows:(1)
Choosee0∗,e1∗⟵RDℤm,s, R⟵R−1,1m×m, and i∗∈0,1,…,N−1(2)
RunTrapGen to get A2∈ℤqn×m and a trapdoor RA2(3)
DefineA0=A⌢, A1=A0⋅R−i∗A2modq, and u=A0⋅e0∗+R⋅e1∗modq(4)
Fori=i∗, let gski∗=e0∗,e1∗ and grti∗=A0⋅e0∗modq(5)
Fori∈0,1,…,N−1/i∗, let Ai=A0|A1+i⋅A2, run SampleRA0,A2,R,RA2,u,s to obtain ei=ei,0,ei,1∈ℤ2m, and let gski=ei, grti=A0⋅ei,0modq(6)
LetGpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1, transfer Gsk and Grt to ℱ


### 4.2.3. Queries

ℱ proceeds as follows:(1)
Corruption. Taking i as input, A outputs grti and adds i to Corr.(2)
Signing. Taking i and m∈0,1∗ as input, A outputs σ⟵SignGpk,gski,m. In particular, the values in 1,2,3ωlogn are sampled as responses to H. Let rd be a reply to the d-th (d≤qH) query (here, qH is the whole number of oracle queries for H).


### 4.2.4. Forgery

ℱ returns m∗∈0,1∗, RL∗⊆Grt, and a forged σ∗=m∗,Π∗,v∗,b∗ which satisfies the following:(1)
VerifyGpk,RL∗,σ∗,m∗=1(2)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗ℱ proceeds as in [11]; let B=GA0,A1,A2,u,m∗,v∗∈ℤqn×m. A obtains a 3-fork involving Δ=m∗,A0,A1,A2,u,B∗,b∗,CMTjj∈1,…,k after at most 32⋅qH/ε−3−k operations of ℱ.With the help of an extractorK in the proof of Theorem 1, we get a valid(14)witness=id=Bini∈0,1ℓ,ei=ei,0,ei,1∈ℤ2m,e∗∈ℤm,such that(1)
A0|A1+iA2⋅ei=umodq and ei∈Secβid(2)
b∗=B∗T⋅A0⋅ei,0+e∗modq and 0<e∗∞≤βIn the following, we show two cases:(1)
Ifi≠i∗ (the probability is at most N−1/N), A aborts.(2)
Ifi=i∗, A returns e⌢=e0∗−ei∗,0+R⋅e1∗−ei∗,1. Thus, we have that(15)A⌢⋅e⌢=A0⋅e0∗−ei∗,0+R⋅e1∗−ei∗,1=A0⋅e0∗+R⋅e1∗︸u−A0⋅ei∗,0+R⋅ei∗,1︸u=0modq.In the followings, we show that with a high probability,e⌢≠0modq and ||e⌢||∞≤polym.(1)
e⌢∞≤polym: for j∈0,1, ei∗∞,ei∗,j∞≤β and R⟵R−1,1m×m; thus, we have that(16)e⌢∞≤1+ωlogm⋅2β=polym.(2)
e⌢≠0modq: since σ∗=m∗,Π∗,v∗,b∗ is a forged signature, the implicit-tracing does not succeed or returns a member not included in Corr/RL∗.(2.1)
If the implicit-tracing will not succeed,VerifyGpk,grti∗,σ∗,m∗=1 will indicate that(17)A0⋅ei∗,0modq≠grti∗=A0⋅e0∗modqei∗,0≠e0∗.(2.2)
If the implicit-tracing returns a member not included inj∗∉Corr/RL∗, we have that VerifyGpk,grtj∗,σ∗,m∗=0 and VerifyGpk,RL∗,σ∗,m∗=1. Thus, we get the conclusions as follows:(2.2.1)
grtj∗≠RL∗; thus, j∗∈Corr.(2.2.2)
Sinceb−B∗T⋅grtj∗∞=B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤β, e∗∞≤β. So, B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤2β, and based on [23], we come to the conclusion that with an overwhelming probability, grtj∗=A0⋅ei∗,0modq.Next, we consider the following:(2.2.3)
Ifℱ has never requested gski∗, e0∗,e1∗ will not be known to ℱ; thus, we have that e0∗,e1∗≠ei∗,0,ei∗,1 with overwhelming probability.(2.2.4)
Ifℱ has requested gski∗, we have that i∗∈Corr, i∗≠j∗, grti∗≠grtj∗, and e0∗≠ei∗,0.According to the previous analysis, the same as in [32], for the different cases in 2.1 and 2.2.4 (suppose e1∗=ei∗,1) and in 2.1, 2.2.3, and 2.2.4 (suppose e1∗≠ei∗,1), we have the conclusion that with probability 1−exp−O˜n, e⌢≠0modq. Therefore, based on the above analysis, we come to the conclusion that with a probability ε′≥ε/2N⋅1−7/9k⋅1−exp−O˜n, e⌢ will satisfy A⌢⋅e⌢=0modq and 0≠e⌢∞≤2β⋅1+ωlogm=β′=polym.


## 4.2.1. Efficiency

For our new scheme, three public matrices are needed for identity-encoding; thus, the bit-sizes ofGpk, gsk, and σ are O˜n2, O˜n, and logN⋅O˜n, respectively. Compared with previous GS-VLR schemes over lattices, the OlogN factor for the bit-sizes of Gpk and gsk in the new construction is eliminated; meanwhile, it is also free of any encryptions.Theorem 2.
With an overwhelming probability, the scheme in Section4.1 is correct.Proof.
A memberi owning a valid witness ei′,e∈Secβid×χm can return a signature meeting the first three steps of Verify. As for step 4, the vector ei′ can be expressed as follows:(13)ei′=b−BTgrti=BTgrti+e−BTgrti′=BT⋅grti−grti′+emodq.(1)
To prove thatgrti∉RL⇒VerifyGpk,RL,SignGpk,gski,m,m=1.Suppose thatgrti∉RL; to prove that with an overwhelming probability, step 4 is satisfied, i.e., ei′∞>β and VerifyGpk,RL,SignGpk,gski,m,m=1. For all grti′∈RL, the following is the establishment: BTgrti−grti′=ei′−emodq. Defining si′=grti−grti′modq, we have that BTsi′∞≤ei′∞+e∞≤ei′∞+β. In addition, according to [11], BTsi′∞>2β with an overwhelming probability; thus, ei′∞>2β−β=β.(2)
To prove thatVerifyGpk,RL,SignGpk,gski,m,m=1⇒grti′∈RL.
Suppose thatVerifyGpk,RL,SignGpk,gski,m,m=1. For every grti′∈RL, we have that ei′∞>β. Therefore, if there is index i′ satisfying that grti=grti′, we have that ei′=e. Thus, ei′∞=π∞≤β and σ fails the step 4 of Verify. So, it is obviously a conflict. This concludes the correctness proof.Theorem 3.
IfCOM enjoys the property of statistically hiding as in [41], the proposed scheme is selfless-anonymous in the random oracle model.Proof.
A series of games is established as follows:Game 0:C proceeds as follows:(1)
RunKeyGen to get Gpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1. Set RL=∅ and Corr=∅, and send Gpk to A(2)
ForA′s corruption queries for a member i, C sets Corr=Corr∪i and returns gski; for A′s signing queries on m for i, C outputs σ⟵SignGpk,gski,m; for A′s revocation queries for i, C sets RL=RL∪grti and outputs gski to A(3)
A outputs a message m∈0,1∗, members i0 and i1, for b∈0,1, ib∉Corr and grtib∉RL(4)
C chooses b⟵R0,1, generates σ∗⟵SignGpk,gskib,m∗=m∗,Π,v,b, and outputs it(5)
A makes queries as before without the rights to ask for gskib or grtib for each b∈0,1(6)
Finally,A outputs a bit b′∈0,1Game 1:C simulates step 4 of Sign by programming the oracle:(1)
Choosev⟵R0,1n and e⟵Rχm; let B=GA0,A1,A2,u,m,v and b=BT⋅grtib+emodq(2)
ProgramHm∗,A0,A1,A2,u,B,b,CMTjj∈1,2,…,k=Chjj∈1,…,k; other algorithms are as in the proof of Theorem 1(3)
Outputσ⌢∗=m∗,Π∗,v,bGame 2:C defines b=BT⋅r+emodq, so b is close to the one in Game 1, and thus Game 2 is statistically indistinguishable with Game 1.Game 3:C defines B,b⟵RU, so B,b is close to the one in Game 2. Thus, Games 3 and 2 are computationally indistinguishable. Furthermore, the advantage AdvAself−anon is 0.
According to the indistinguishability of Games 1, 2, and 3, the advantageAdvAself−anon in Game 1 is negligible; therefore, our new scheme satisfies the definition of selfless-anonymity.Theorem 4.
SupposeSIS within β′=polym factor is hard, the proposed scheme is traceable.Proof.
Suppose with an advantageε, a forger ℱ breaks the scheme. By using ℱ, we construct an efficient A to solve a SIS instance A⌢∈ℤqn×m within β′=2β⋅1+ωlogm factor.


## 4.2.2. Setup

A proceeds as follows:(1)
Choosee0∗,e1∗⟵RDℤm,s, R⟵R−1,1m×m, and i∗∈0,1,…,N−1(2)
RunTrapGen to get A2∈ℤqn×m and a trapdoor RA2(3)
DefineA0=A⌢, A1=A0⋅R−i∗A2modq, and u=A0⋅e0∗+R⋅e1∗modq(4)
Fori=i∗, let gski∗=e0∗,e1∗ and grti∗=A0⋅e0∗modq(5)
Fori∈0,1,…,N−1/i∗, let Ai=A0|A1+i⋅A2, run SampleRA0,A2,R,RA2,u,s to obtain ei=ei,0,ei,1∈ℤ2m, and let gski=ei, grti=A0⋅ei,0modq(6)
LetGpk=A0,A1,A2,u, Gsk=gsk0,…,gskN−1, and Grt=grt0,…,grtN−1, transfer Gsk and Grt to ℱ


## 4.2.3. Queries

ℱ proceeds as follows:(1)
Corruption. Taking i as input, A outputs grti and adds i to Corr.(2)
Signing. Taking i and m∈0,1∗ as input, A outputs σ⟵SignGpk,gski,m. In particular, the values in 1,2,3ωlogn are sampled as responses to H. Let rd be a reply to the d-th (d≤qH) query (here, qH is the whole number of oracle queries for H).


## 4.2.4. Forgery

ℱ returns m∗∈0,1∗, RL∗⊆Grt, and a forged σ∗=m∗,Π∗,v∗,b∗ which satisfies the following:(1)
VerifyGpk,RL∗,σ∗,m∗=1(2)
The implicit-tracing does not succeed or returns a member not included inCorr/RL∗ℱ proceeds as in [11]; let B=GA0,A1,A2,u,m∗,v∗∈ℤqn×m. A obtains a 3-fork involving Δ=m∗,A0,A1,A2,u,B∗,b∗,CMTjj∈1,…,k after at most 32⋅qH/ε−3−k operations of ℱ.With the help of an extractorK in the proof of Theorem 1, we get a valid(14)witness=id=Bini∈0,1ℓ,ei=ei,0,ei,1∈ℤ2m,e∗∈ℤm,such that(1)
A0|A1+iA2⋅ei=umodq and ei∈Secβid(2)
b∗=B∗T⋅A0⋅ei,0+e∗modq and 0<e∗∞≤βIn the following, we show two cases:(1)
Ifi≠i∗ (the probability is at most N−1/N), A aborts.(2)
Ifi=i∗, A returns e⌢=e0∗−ei∗,0+R⋅e1∗−ei∗,1. Thus, we have that(15)A⌢⋅e⌢=A0⋅e0∗−ei∗,0+R⋅e1∗−ei∗,1=A0⋅e0∗+R⋅e1∗︸u−A0⋅ei∗,0+R⋅ei∗,1︸u=0modq.In the followings, we show that with a high probability,e⌢≠0modq and ||e⌢||∞≤polym.(1)
e⌢∞≤polym: for j∈0,1, ei∗∞,ei∗,j∞≤β and R⟵R−1,1m×m; thus, we have that(16)e⌢∞≤1+ωlogm⋅2β=polym.(2)
e⌢≠0modq: since σ∗=m∗,Π∗,v∗,b∗ is a forged signature, the implicit-tracing does not succeed or returns a member not included in Corr/RL∗.(2.1)
If the implicit-tracing will not succeed,VerifyGpk,grti∗,σ∗,m∗=1 will indicate that(17)A0⋅ei∗,0modq≠grti∗=A0⋅e0∗modqei∗,0≠e0∗.(2.2)
If the implicit-tracing returns a member not included inj∗∉Corr/RL∗, we have that VerifyGpk,grtj∗,σ∗,m∗=0 and VerifyGpk,RL∗,σ∗,m∗=1. Thus, we get the conclusions as follows:(2.2.1)
grtj∗≠RL∗; thus, j∗∈Corr.(2.2.2)
Sinceb−B∗T⋅grtj∗∞=B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤β, e∗∞≤β. So, B∗T⋅A0⋅ei∗,0−grtj∗+e∗∞≤2β, and based on [23], we come to the conclusion that with an overwhelming probability, grtj∗=A0⋅ei∗,0modq.Next, we consider the following:(2.2.3)
Ifℱ has never requested gski∗, e0∗,e1∗ will not be known to ℱ; thus, we have that e0∗,e1∗≠ei∗,0,ei∗,1 with overwhelming probability.(2.2.4)
Ifℱ has requested gski∗, we have that i∗∈Corr, i∗≠j∗, grti∗≠grtj∗, and e0∗≠ei∗,0.According to the previous analysis, the same as in [32], for the different cases in 2.1 and 2.2.4 (suppose e1∗=ei∗,1) and in 2.1, 2.2.3, and 2.2.4 (suppose e1∗≠ei∗,1), we have the conclusion that with probability 1−exp−O˜n, e⌢≠0modq. Therefore, based on the above analysis, we come to the conclusion that with a probability ε′≥ε/2N⋅1−7/9k⋅1−exp−O˜n, e⌢ will satisfy A⌢⋅e⌢=0modq and 0≠e⌢∞≤2β⋅1+ωlogm=β′=polym.


## 5. Conclusion

In this work, we introduced an improved GS-VLR scheme over lattices. By adopting a compact identity-encoding technique and a corresponding Stern -type statistical ZKP protocol, the group public-key and member secret signing key in our new construction enjoy the shorter bit-sizes; furthermore, the new design is free of any public-key encryptions, and thus it is more flexible to allow anonymous authentication in the mobile network, especially, for a group with a mass of members. Achieving a stronger security (e.g., almost-full anonymity or full anonymity) for GS-VLR over lattices is our future work.



---

*Source: 9988939-2021-10-21.xml*