# Group Signature with Verifier-Local Revocation Based on Coding Theory

Authors: Luping Wang; Kai Zhang; Haifeng Qian; Jie Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Group signature with verifier-local revocation (VLR-GS) is a special variant of revocable group signature that not only allows a user to anonymously sign messages but also only requires the verifiers to possess some up-to-date revocation information. To date, a number of VLR-GS schemes have been proposed under bilinear groups and lattices, while they have not yet been instantiated based on coding theory. In this paper, we present a code-based VLR-GS scheme in the random oracle model, which is the first construction to the best of our knowledge. Concretely, our VLR-GS scheme does not rely on the traditional paradigm which utilizes an encryption scheme as a building block and achieves logarithmic-size group signature. To obtain the scheme, we first introduce a new code-based Stern-like interactive zero-knowledge protocol with member revocation mechanism based on syndrome decoding problem. Moreover, we employ the binary Goppa code embedded for our scheme with efficiency and security analysis.


---

## Body

## 1. Introduction

### 1.1. Group Signature

Group signature scheme is a fundamental cryptographic primitive that enables signer anonymity and has been extensively researched since introduced by Chaum and Van Heyst [1]. The anonymity indicates that any group member is allowed to issue signature for documents on behalf of the group, while the identity of the signer is anonymously hidden from a verifier. Concretely, it allows the group members to issue signatures on behalf of the whole group without compromising their identity information. When receiving an issued signing key from the group manager, a signer can generate a group signature on a certain message. Moreover, a verifier can verify the signature by only a group public key and cannot identify who is the actual signer even when the validity of the signature is verified.At the same time, there is a serious problem that should be considered in the real-world applications. If a group member issues signatures for documents where he is not allowed to sign, this member should be revoked from the group. The membership of a revoked user should be canceled. That is to say, how to remove the signing capability of misbehaving users without affecting remaining members is a significant problem. This problem can be encountered in many application scenarios, such as in politics and business. For example, if illegal information sent by a malicious group member is reported, the group administrator will kick the malicious member out of the group after verification to ensure the safety of other legitimate members in the group. A naive method is to rebuild the group signature system for distributing system parameter to the unrevoked members; however, this certainly limits the practicality. Hence, support of membership revocation in group signature is highly desirable, which makes the notion ofrevocable group signature (RGS) to be proposed [2] and widely researched.


### 1.2. Revocable Group Signature

When considering member revocation, how to efficiently and securely revoke the signing ability of misbehaving members in a unrevoked user-unaware way is a major problem in group signature.Traditionally, the revocation information should be sent to both signer and verifier in the revocable group signature schemes [3–5]. Later, the most employed method is the verifier-local revocation technique [6], which only requires the verifier to possess some up-to-date revocation information, that is, the revocation messages are only sent to signature verifier, not the signer. Hence, the VLR-GS is more widely deployed in real-world application due to its high efficiency and flexible operations.Currently, a number of VLG-GS schemes have been proposed based on various security assumptions in thepairing-free, pairing, and lattice setting [7–10], while they have not been studied yet based on coding theory. So, in this paper, we give a generic construction of the code-based VLG-GS scheme, which can resist quantum computer attacks.


### 1.3. Our Contributions

Our main contribution is to give a generic construction for the code-based group signature scheme with support of verifier-local revocation function. For this purpose, we first design a code-based Stern-like interactive zero-knowledge (ZK) identification protocol with member revocation mechanism; this protocol allows the prover to convince the given ciphertext is well formed, and the hidden plaintext satisfies other additional conditions. Then, we utilize the new ZK protocol to construct the code-based revocable group signature scheme. Our structure departs from the traditional “sign-and-encrypt-and-prove” group signature paradigm and deviates from code-based encryptions. So, how to construct an interactive ZK protocol with member revocation mechanism under a code-based security assumption is the main problem we have solved. Finally, we give a formal security proof for its correctness,selfless anonymity (this is a slightly weaker notion than the CPA anonymity and CCA anonymity for group signature, where this work focuses on providing membership revocation functionality for group signature), and traceability and reduce its security to the hardness of the syndrome decoding (SD) problem. By instantiating the scheme with n,k2 Goppa codes with parameter analysis, the public key size and the signature size in the scheme achieve logN⋅On2 and logN⋅On over F2, respectively, where N is the number of group users.


### 1.4. Technique Overview

The main building block of our VLR group signature scheme is an interactive ZK protocol. The protocol allows a prover to convince the verifier that he is a certified group member (i.e., he possesses a valid secret signing key) and that he has not been revoked (i.e., his “revocation token” is not in the verifier’s blacklist). We can repeat the protocol many times to make the soundness error negligibly small.We consider a group of sizeN=2l, and each user is identified by a string d=d1,…,dl∈0,1l denoting the binary representation of his index in the group. To get an extension of d, inspired by the Bonsai tree signature originally proposed by Cash et al. in [11], which was first introduced into the code theory by Ezerman et al. [12], here we adapt and develop their method to manage the Bonsai tree of a difficult code-based problem, and hence a group user with identity d is issued a Bonsai signature under its identity. That is, we have a small vector z∈F2l+1n with z’s Hamming weight wz=r and Ad⋅z⊺=u, where Ad=A0|A1d1|…|Aldl is a subtree defined by d.Theanonymity implies that the signer’s identity d is hidden from the verifier; therefore, the matrix Ad should not be explicitly given. We utilize the extension method in [7]: we add n suitable zero blocks to vector z to obtain an extended vector x=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n, where the added zero blocks are x11−d1,…,xl1−dl, We then have wx=r, and A⋅x⊺=u. Namely x is a solution to the syndrome decoding instance given by the whole Bonsai tree. To prove in zero-knowledge the possession of such a vector x, we adapt the “Stern extension” proof system, and the user identity d is hidden by a “one-time pad” technique. As a result, the user can anonymously prove his group membership.To enablemembership revocation, the secret key x of each group member should make the first block x0 related with A0; then, the revocation token could be formulated as A0⋅x0⊺∈F2n. With well-chosen parameters and sample x0 from a proper distribution, the token can therefore be statistically close to uniform over F2n−k. In fact, when a user is asked to sample a uniformly random vector r0∈F2n and to compute a commitment c0 using a (code-based) collision-resistant hash function COM, for which the value A0⋅r0⊺ is part of the committed string. Depending on the verifier’s challenge, the user will either reveal r0 or r0+x0.


### 1.5. Related Work

Group signature schemes have been well studied based on bilinear pairing [6, 13–17]. In 2018, Ishida et al. and Perera and Koshiba [18, 19] gave two group signature frameworks, respectively, which accorded to the traditional “sign-and-encrypt” paradigm and could achieve a high level of anonymity: (almost) full anonymity. However, because the secure code-based signature scheme cannot be realized for a while, the code-based instantiation scheme cannot be presented. Later, a number of lattice-based and code-based group signature schemes have been proposed, which can resist quantum computer attacks. Gordon et al. [20] designed the first lattice-based group signature scheme whose public key size and signature size are linear in the number of group members N. Recently, there are several efficient lattice-based constructions [7, 21, 22] that have been proposed, whose group public key size and signature size are proportional to logN. The first code-based group signature scheme was proposed by Alamélou et al. in [23], which allows to dynamically add new members during the lifetime of the group. In 2015, Ezerman et al. [12] proposed the first provably secure group signature scheme from code-based assumptions which satisfies CPA anonymity and traceability requirements in the random oracle model, whose security is reduced to the hardness of the syndrome decoding problem. Moreover, the first rank code-based group signature was proposed by Alamélou et al. [24], which achieves dynamic in a relaxed pattern based on the BSZ model of Bellare et al. [13]. Nevertheless, there is no instantiation code-based group signature scheme with support of revocation functionality.The concept of VLR-GS was first considered by Brickell [25] and Kiayias et al. [26] and then formalized by Boneh and Shacham [6]. The state-of-the-art VLR-GS constructions are usually given in the bilinear map. The first lattice-based VLR-GS scheme was given by Langlois et al. [7]. In 2020, Yin et al. [27] proposed a lattice-based VLR-GS scheme and realized full anonymity. However, this property cannot be implemented in code-based group signature scheme temporarily, for the research about code cryptography is not mature as lattice's.


### 1.6. Organization

Section2 recalls some preliminary knowledge for our work, including code-based cryptography and group signature. In Section 3, we introduce a code-based “Stern-like” interactive protocol, which supports member revocation. We construct a code-based VLR group signature scheme and give its security analysis in Section 4. In the end, we conclude our work in Section 5.


## 1.1. Group Signature

Group signature scheme is a fundamental cryptographic primitive that enables signer anonymity and has been extensively researched since introduced by Chaum and Van Heyst [1]. The anonymity indicates that any group member is allowed to issue signature for documents on behalf of the group, while the identity of the signer is anonymously hidden from a verifier. Concretely, it allows the group members to issue signatures on behalf of the whole group without compromising their identity information. When receiving an issued signing key from the group manager, a signer can generate a group signature on a certain message. Moreover, a verifier can verify the signature by only a group public key and cannot identify who is the actual signer even when the validity of the signature is verified.At the same time, there is a serious problem that should be considered in the real-world applications. If a group member issues signatures for documents where he is not allowed to sign, this member should be revoked from the group. The membership of a revoked user should be canceled. That is to say, how to remove the signing capability of misbehaving users without affecting remaining members is a significant problem. This problem can be encountered in many application scenarios, such as in politics and business. For example, if illegal information sent by a malicious group member is reported, the group administrator will kick the malicious member out of the group after verification to ensure the safety of other legitimate members in the group. A naive method is to rebuild the group signature system for distributing system parameter to the unrevoked members; however, this certainly limits the practicality. Hence, support of membership revocation in group signature is highly desirable, which makes the notion ofrevocable group signature (RGS) to be proposed [2] and widely researched.


## 1.2. Revocable Group Signature

When considering member revocation, how to efficiently and securely revoke the signing ability of misbehaving members in a unrevoked user-unaware way is a major problem in group signature.Traditionally, the revocation information should be sent to both signer and verifier in the revocable group signature schemes [3–5]. Later, the most employed method is the verifier-local revocation technique [6], which only requires the verifier to possess some up-to-date revocation information, that is, the revocation messages are only sent to signature verifier, not the signer. Hence, the VLR-GS is more widely deployed in real-world application due to its high efficiency and flexible operations.Currently, a number of VLG-GS schemes have been proposed based on various security assumptions in thepairing-free, pairing, and lattice setting [7–10], while they have not been studied yet based on coding theory. So, in this paper, we give a generic construction of the code-based VLG-GS scheme, which can resist quantum computer attacks.


## 1.3. Our Contributions

Our main contribution is to give a generic construction for the code-based group signature scheme with support of verifier-local revocation function. For this purpose, we first design a code-based Stern-like interactive zero-knowledge (ZK) identification protocol with member revocation mechanism; this protocol allows the prover to convince the given ciphertext is well formed, and the hidden plaintext satisfies other additional conditions. Then, we utilize the new ZK protocol to construct the code-based revocable group signature scheme. Our structure departs from the traditional “sign-and-encrypt-and-prove” group signature paradigm and deviates from code-based encryptions. So, how to construct an interactive ZK protocol with member revocation mechanism under a code-based security assumption is the main problem we have solved. Finally, we give a formal security proof for its correctness,selfless anonymity (this is a slightly weaker notion than the CPA anonymity and CCA anonymity for group signature, where this work focuses on providing membership revocation functionality for group signature), and traceability and reduce its security to the hardness of the syndrome decoding (SD) problem. By instantiating the scheme with n,k2 Goppa codes with parameter analysis, the public key size and the signature size in the scheme achieve logN⋅On2 and logN⋅On over F2, respectively, where N is the number of group users.


## 1.4. Technique Overview

The main building block of our VLR group signature scheme is an interactive ZK protocol. The protocol allows a prover to convince the verifier that he is a certified group member (i.e., he possesses a valid secret signing key) and that he has not been revoked (i.e., his “revocation token” is not in the verifier’s blacklist). We can repeat the protocol many times to make the soundness error negligibly small.We consider a group of sizeN=2l, and each user is identified by a string d=d1,…,dl∈0,1l denoting the binary representation of his index in the group. To get an extension of d, inspired by the Bonsai tree signature originally proposed by Cash et al. in [11], which was first introduced into the code theory by Ezerman et al. [12], here we adapt and develop their method to manage the Bonsai tree of a difficult code-based problem, and hence a group user with identity d is issued a Bonsai signature under its identity. That is, we have a small vector z∈F2l+1n with z’s Hamming weight wz=r and Ad⋅z⊺=u, where Ad=A0|A1d1|…|Aldl is a subtree defined by d.Theanonymity implies that the signer’s identity d is hidden from the verifier; therefore, the matrix Ad should not be explicitly given. We utilize the extension method in [7]: we add n suitable zero blocks to vector z to obtain an extended vector x=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n, where the added zero blocks are x11−d1,…,xl1−dl, We then have wx=r, and A⋅x⊺=u. Namely x is a solution to the syndrome decoding instance given by the whole Bonsai tree. To prove in zero-knowledge the possession of such a vector x, we adapt the “Stern extension” proof system, and the user identity d is hidden by a “one-time pad” technique. As a result, the user can anonymously prove his group membership.To enablemembership revocation, the secret key x of each group member should make the first block x0 related with A0; then, the revocation token could be formulated as A0⋅x0⊺∈F2n. With well-chosen parameters and sample x0 from a proper distribution, the token can therefore be statistically close to uniform over F2n−k. In fact, when a user is asked to sample a uniformly random vector r0∈F2n and to compute a commitment c0 using a (code-based) collision-resistant hash function COM, for which the value A0⋅r0⊺ is part of the committed string. Depending on the verifier’s challenge, the user will either reveal r0 or r0+x0.


## 1.5. Related Work

Group signature schemes have been well studied based on bilinear pairing [6, 13–17]. In 2018, Ishida et al. and Perera and Koshiba [18, 19] gave two group signature frameworks, respectively, which accorded to the traditional “sign-and-encrypt” paradigm and could achieve a high level of anonymity: (almost) full anonymity. However, because the secure code-based signature scheme cannot be realized for a while, the code-based instantiation scheme cannot be presented. Later, a number of lattice-based and code-based group signature schemes have been proposed, which can resist quantum computer attacks. Gordon et al. [20] designed the first lattice-based group signature scheme whose public key size and signature size are linear in the number of group members N. Recently, there are several efficient lattice-based constructions [7, 21, 22] that have been proposed, whose group public key size and signature size are proportional to logN. The first code-based group signature scheme was proposed by Alamélou et al. in [23], which allows to dynamically add new members during the lifetime of the group. In 2015, Ezerman et al. [12] proposed the first provably secure group signature scheme from code-based assumptions which satisfies CPA anonymity and traceability requirements in the random oracle model, whose security is reduced to the hardness of the syndrome decoding problem. Moreover, the first rank code-based group signature was proposed by Alamélou et al. [24], which achieves dynamic in a relaxed pattern based on the BSZ model of Bellare et al. [13]. Nevertheless, there is no instantiation code-based group signature scheme with support of revocation functionality.The concept of VLR-GS was first considered by Brickell [25] and Kiayias et al. [26] and then formalized by Boneh and Shacham [6]. The state-of-the-art VLR-GS constructions are usually given in the bilinear map. The first lattice-based VLR-GS scheme was given by Langlois et al. [7]. In 2020, Yin et al. [27] proposed a lattice-based VLR-GS scheme and realized full anonymity. However, this property cannot be implemented in code-based group signature scheme temporarily, for the research about code cryptography is not mature as lattice's.


## 1.6. Organization

Section2 recalls some preliminary knowledge for our work, including code-based cryptography and group signature. In Section 3, we introduce a code-based “Stern-like” interactive protocol, which supports member revocation. We construct a code-based VLR group signature scheme and give its security analysis in Section 4. In the end, we conclude our work in Section 5.


## 2. Preliminaries

In this section, we present some notations and technical tools used in this work.


### 2.1. Notations

IfS is a finite set, s←$S denotes the operation of picking an element of S uniformly at random and assigning the result to a variable s. Let N be a positive integer, and we denote N⟵1,…,N. Let Bn,r be the set of all vectors x∈F2n such that wx=r, where wx is the Hamming weight of vector x. In addition, we use bold lowercase and capital letters to denote vectors and matrices, respectively.


### 2.2. General Definitions

Definition 1 (linear codes).
An,kn>k linear error-correcting code C over a finite field F2 is a k-dimensional subspace of n-dimensional linear space F2n, and co-dimension is n−k. Let matrix G∈F2k×n be a generator matrix of code C, and the row vectors of G form a base of C, i.e., C=m⋅G∈F2n|m∈F2k.
Note thatG is not unique. In addition, the code C can also be defined by a parity-check matrixH∈F2n−k×n such that C=c∈F2n|H⋅c⊺=0n−k, and hence the check matrix of code C is not unique as well. Besides, any row vector of H is orthogonal to any row vector of the generating matrix G of C, i.e., H⋅G⊺=0. For any vector x∈F2n, define the syndrome of x as s=H⋅x⊺∈F2n−k, where x is a codeword of C if and only if H⋅c⊺=0n−k.
Besides, we say thatG (respectively, H) is in systematic form if it is of the form Ik|A (respectively, In−k|B).Definition 2 (syndrome decoding problem, SDP).
LetH be a parity check matrix for a random n,k linear code over F2 and let a vector s be chosen uniformly at random in F2n−k and an integer r<n. Find a vector x∈Bn,r such that σx=H⋅x⊺=s.
Whenn=nλ,k=kλ,r=rλ, we say that the SD problem H,s,r is hard, if the success probability of any PPT algorithm in solving the problem is at most neglλ.
In our security reduction, the following variant of the left-over hash lemma for matrix multiplication overF2 is used.Lemma 1 (left-over hash lemma [12]).
LetD be a distribution over F2n with min-entropy e. For ε>0 and n−k≤e−2log1/ε−O1, H,H⋅x⊺. H←F∗2n−k×n and x∈F2n is drawn from distribution D, the statistical distance between the distribution of H,H⋅x⊺ and the uniform distribution over F2n−k×n×F2n−k is at most ε.In particular, ifr<n is an integer such that n−k≤lognr−2λ−O1 and D is the uniform distribution over Bn,r (i.e., D has min-entropy lognr), then the statistical distance between the distribution of H,H⋅x⊺ and the uniform distribution over F2n−k×n×F2n−k is at most 2−ε.


### 2.3. Stern’s Protocol

The identification protocols are very important for enhancing the security of network services and smart cards, where the zero-knowledge (ZK) protocol is a convincing primitive to suggest that a protocol can be reused without any security loss.An efficient code-based ZK protocol was first proposed by Stern [28] as shown in Figure 1 (we give a modification with employing hamming metric), which is a 3-pass prover-verifier protocol. The prover P makes a zero-knowledge proof to the verifier V solving a SD instance H,s,r on a low density weight secret z. Let S be the set of all permutations that keep the propositions in Section 3.1. Hence, the protocol suffers a distinguishable issue since a verifier with the knowledge of z is able to check whether a given witness z was actually involved during the protocol or not. Function h is modelled as a random oracle: h:F2∗⟶F2n. Note that the prover and the verifier in the protocol with a cheating probability 2/3 are assumed to be honest, in such a way that, the completeness, soundness, and zero knowledge can be thus achieved [29].Figure 1
Stern’s code-based ZK protocol.Given the public informationH,s,r∈F2n−k×n×F2n−k×ℕ, the prover P needs to prove the knowledge of z∈Bn,r such that H⋅z⊺=s.


### 2.4. Group Signature with Verifier-Local Revocation (VLR-GS)

Generally, a VLR-GS scheme consists of the following three algorithms [6]:(1)
KeyGenλ,N: on inputting a security parameter λ and group size N, this algorithm outputs a group public key gpk, a vector of user secret keys gsk=gsk0,gsk1,…,gskN−1, and a vector of user’s revocation tokens grt=grt0,grt1,…,grtN−1.(2)
Signgpk,gskd,M: on inputting gpk, a user secret key gskd, and a message M∈0,1∗, this algorithm outputs a signature Σ.(3)
Verifygpk,RL,Σ,M: on inputting gpk, a set of revocation tokens RL (a subset of the elements of grt), a signature Σ, and the message M, this algorithm outputs either Valid or Invalid. The output Valid indicates that Σ is a valid signature on message M under gpk, and the signer is a suitable user who has not been revoked.Remark 1.
Any VLR-GS scheme has an implicit tracing algorithm usinggrt as the tracing key, where the tracing algorithm works as follows: when inputting a valid signature Σ on a message M, it reveals the signer of Σ by running Verifygpk,RL=grtd,Σ,M, for d∈0,1l and outputs the first index d∗∈0,1l when the verification algorithm returns Invalid. The tracing algorithm fails if and only if the given signature is verified for all d.


#### 2.4.1. Security Definition

A secure VLR group signature scheme must satisfy the following three requirements:.(1) Correctness. For all gpk,gsk,grt←KeyGen, all d∈0,1l, and all M∈0,1∗,(1)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.(2) Selfless Anonymity. The goal of an adversary A in the selfless anonymity game (i.e., Figure 2) is to determine that a signature is generated by which secret key from two adaptively chosen keys. The challenger randomly chooses a bit b∈0,1 and the adversary A returns a guess b′ on the value. More precisely, A submits two challenge users d0 and d1 and the challenger issues a signature under db.Figure 2
The selfless anonymity notion.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively. OSignd,M returns Signgpk,gskd,M and adds d into SM if user d∈HU, where the set SM is the list of users whose signatures on message M exists. OCorruptd provides a user’s secret key gskd and moves d to CU if user d∈HU. ORevocd provides a user’s revocation token grtd if user d∈HU.The adversaryA may query an oracle with a group public key gpk at any point during its execution, with the exception that it is not allowed to make any corruption or revocation query for user d0 or d1 in the second query stage. The adversary A wins the game when b′=b, and thus the probability of this event is defined as PrExpA,GSself−anon−bλ. Now, we define the advantage of A in the experiment as(2)AdvA,GSself−anonλ≔PrExpA,GSself−anon−1λ=1−PrExpA,GSself−anon−0λ=1.(3) Traceability. The goal of an adversary in the traceability game is to forge a signature that cannot be traced to which group user using the implicit tracing algorithm. Finally, the adversary A outputs a message M∗, a set of revocation tokens RL∗, and a signature Σ∗.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively, and the set U consists of corrupt users which is initially empty. Hence, the adversary A wins the game if (i) Verifygpk,RL∗,Σ∗,M∗=valid; (ii) the (implicit) tracing algorithm fails or traces to a user outside of the coalition U\RL∗; (iii) the signature Σ∗ is nontrivial, i.e., A did not obtain Σ∗ by making a signing query on M∗. The traceability game is formally defined in Figure 3.Figure 3
The traceability notion.The probability thatA wins the game is defined as PrExpA,GStrλ,N. We define the advantage of A as(3)AdvA,GStrλ,N=PrExpA,GStrλ=1.


## 2.1. Notations

IfS is a finite set, s←$S denotes the operation of picking an element of S uniformly at random and assigning the result to a variable s. Let N be a positive integer, and we denote N⟵1,…,N. Let Bn,r be the set of all vectors x∈F2n such that wx=r, where wx is the Hamming weight of vector x. In addition, we use bold lowercase and capital letters to denote vectors and matrices, respectively.


## 2.2. General Definitions

Definition 1 (linear codes).
An,kn>k linear error-correcting code C over a finite field F2 is a k-dimensional subspace of n-dimensional linear space F2n, and co-dimension is n−k. Let matrix G∈F2k×n be a generator matrix of code C, and the row vectors of G form a base of C, i.e., C=m⋅G∈F2n|m∈F2k.
Note thatG is not unique. In addition, the code C can also be defined by a parity-check matrixH∈F2n−k×n such that C=c∈F2n|H⋅c⊺=0n−k, and hence the check matrix of code C is not unique as well. Besides, any row vector of H is orthogonal to any row vector of the generating matrix G of C, i.e., H⋅G⊺=0. For any vector x∈F2n, define the syndrome of x as s=H⋅x⊺∈F2n−k, where x is a codeword of C if and only if H⋅c⊺=0n−k.
Besides, we say thatG (respectively, H) is in systematic form if it is of the form Ik|A (respectively, In−k|B).Definition 2 (syndrome decoding problem, SDP).
LetH be a parity check matrix for a random n,k linear code over F2 and let a vector s be chosen uniformly at random in F2n−k and an integer r<n. Find a vector x∈Bn,r such that σx=H⋅x⊺=s.
Whenn=nλ,k=kλ,r=rλ, we say that the SD problem H,s,r is hard, if the success probability of any PPT algorithm in solving the problem is at most neglλ.
In our security reduction, the following variant of the left-over hash lemma for matrix multiplication overF2 is used.Lemma 1 (left-over hash lemma [12]).
LetD be a distribution over F2n with min-entropy e. For ε>0 and n−k≤e−2log1/ε−O1, H,H⋅x⊺. H←F∗2n−k×n and x∈F2n is drawn from distribution D, the statistical distance between the distribution of H,H⋅x⊺ and the uniform distribution over F2n−k×n×F2n−k is at most ε.In particular, ifr<n is an integer such that n−k≤lognr−2λ−O1 and D is the uniform distribution over Bn,r (i.e., D has min-entropy lognr), then the statistical distance between the distribution of H,H⋅x⊺ and the uniform distribution over F2n−k×n×F2n−k is at most 2−ε.


## 2.3. Stern’s Protocol

The identification protocols are very important for enhancing the security of network services and smart cards, where the zero-knowledge (ZK) protocol is a convincing primitive to suggest that a protocol can be reused without any security loss.An efficient code-based ZK protocol was first proposed by Stern [28] as shown in Figure 1 (we give a modification with employing hamming metric), which is a 3-pass prover-verifier protocol. The prover P makes a zero-knowledge proof to the verifier V solving a SD instance H,s,r on a low density weight secret z. Let S be the set of all permutations that keep the propositions in Section 3.1. Hence, the protocol suffers a distinguishable issue since a verifier with the knowledge of z is able to check whether a given witness z was actually involved during the protocol or not. Function h is modelled as a random oracle: h:F2∗⟶F2n. Note that the prover and the verifier in the protocol with a cheating probability 2/3 are assumed to be honest, in such a way that, the completeness, soundness, and zero knowledge can be thus achieved [29].Figure 1
Stern’s code-based ZK protocol.Given the public informationH,s,r∈F2n−k×n×F2n−k×ℕ, the prover P needs to prove the knowledge of z∈Bn,r such that H⋅z⊺=s.


## 2.4. Group Signature with Verifier-Local Revocation (VLR-GS)

Generally, a VLR-GS scheme consists of the following three algorithms [6]:(1)
KeyGenλ,N: on inputting a security parameter λ and group size N, this algorithm outputs a group public key gpk, a vector of user secret keys gsk=gsk0,gsk1,…,gskN−1, and a vector of user’s revocation tokens grt=grt0,grt1,…,grtN−1.(2)
Signgpk,gskd,M: on inputting gpk, a user secret key gskd, and a message M∈0,1∗, this algorithm outputs a signature Σ.(3)
Verifygpk,RL,Σ,M: on inputting gpk, a set of revocation tokens RL (a subset of the elements of grt), a signature Σ, and the message M, this algorithm outputs either Valid or Invalid. The output Valid indicates that Σ is a valid signature on message M under gpk, and the signer is a suitable user who has not been revoked.Remark 1.
Any VLR-GS scheme has an implicit tracing algorithm usinggrt as the tracing key, where the tracing algorithm works as follows: when inputting a valid signature Σ on a message M, it reveals the signer of Σ by running Verifygpk,RL=grtd,Σ,M, for d∈0,1l and outputs the first index d∗∈0,1l when the verification algorithm returns Invalid. The tracing algorithm fails if and only if the given signature is verified for all d.


### 2.4.1. Security Definition

A secure VLR group signature scheme must satisfy the following three requirements:.(1) Correctness. For all gpk,gsk,grt←KeyGen, all d∈0,1l, and all M∈0,1∗,(1)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.(2) Selfless Anonymity. The goal of an adversary A in the selfless anonymity game (i.e., Figure 2) is to determine that a signature is generated by which secret key from two adaptively chosen keys. The challenger randomly chooses a bit b∈0,1 and the adversary A returns a guess b′ on the value. More precisely, A submits two challenge users d0 and d1 and the challenger issues a signature under db.Figure 2
The selfless anonymity notion.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively. OSignd,M returns Signgpk,gskd,M and adds d into SM if user d∈HU, where the set SM is the list of users whose signatures on message M exists. OCorruptd provides a user’s secret key gskd and moves d to CU if user d∈HU. ORevocd provides a user’s revocation token grtd if user d∈HU.The adversaryA may query an oracle with a group public key gpk at any point during its execution, with the exception that it is not allowed to make any corruption or revocation query for user d0 or d1 in the second query stage. The adversary A wins the game when b′=b, and thus the probability of this event is defined as PrExpA,GSself−anon−bλ. Now, we define the advantage of A in the experiment as(2)AdvA,GSself−anonλ≔PrExpA,GSself−anon−1λ=1−PrExpA,GSself−anon−0λ=1.(3) Traceability. The goal of an adversary in the traceability game is to forge a signature that cannot be traced to which group user using the implicit tracing algorithm. Finally, the adversary A outputs a message M∗, a set of revocation tokens RL∗, and a signature Σ∗.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively, and the set U consists of corrupt users which is initially empty. Hence, the adversary A wins the game if (i) Verifygpk,RL∗,Σ∗,M∗=valid; (ii) the (implicit) tracing algorithm fails or traces to a user outside of the coalition U\RL∗; (iii) the signature Σ∗ is nontrivial, i.e., A did not obtain Σ∗ by making a signing query on M∗. The traceability game is formally defined in Figure 3.Figure 3
The traceability notion.The probability thatA wins the game is defined as PrExpA,GStrλ,N. We define the advantage of A as(3)AdvA,GStrλ,N=PrExpA,GStrλ=1.


## 2.4.1. Security Definition

A secure VLR group signature scheme must satisfy the following three requirements:.(1) Correctness. For all gpk,gsk,grt←KeyGen, all d∈0,1l, and all M∈0,1∗,(1)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.(2) Selfless Anonymity. The goal of an adversary A in the selfless anonymity game (i.e., Figure 2) is to determine that a signature is generated by which secret key from two adaptively chosen keys. The challenger randomly chooses a bit b∈0,1 and the adversary A returns a guess b′ on the value. More precisely, A submits two challenge users d0 and d1 and the challenger issues a signature under db.Figure 2
The selfless anonymity notion.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively. OSignd,M returns Signgpk,gskd,M and adds d into SM if user d∈HU, where the set SM is the list of users whose signatures on message M exists. OCorruptd provides a user’s secret key gskd and moves d to CU if user d∈HU. ORevocd provides a user’s revocation token grtd if user d∈HU.The adversaryA may query an oracle with a group public key gpk at any point during its execution, with the exception that it is not allowed to make any corruption or revocation query for user d0 or d1 in the second query stage. The adversary A wins the game when b′=b, and thus the probability of this event is defined as PrExpA,GSself−anon−bλ. Now, we define the advantage of A in the experiment as(2)AdvA,GSself−anonλ≔PrExpA,GSself−anon−1λ=1−PrExpA,GSself−anon−0λ=1.(3) Traceability. The goal of an adversary in the traceability game is to forge a signature that cannot be traced to which group user using the implicit tracing algorithm. Finally, the adversary A outputs a message M∗, a set of revocation tokens RL∗, and a signature Σ∗.In the experiment, the setsHU and CU consist of the honest users and corrupted users, respectively, and the set U consists of corrupt users which is initially empty. Hence, the adversary A wins the game if (i) Verifygpk,RL∗,Σ∗,M∗=valid; (ii) the (implicit) tracing algorithm fails or traces to a user outside of the coalition U\RL∗; (iii) the signature Σ∗ is nontrivial, i.e., A did not obtain Σ∗ by making a signing query on M∗. The traceability game is formally defined in Figure 3.Figure 3
The traceability notion.The probability thatA wins the game is defined as PrExpA,GStrλ,N. We define the advantage of A as(3)AdvA,GStrλ,N=PrExpA,GStrλ=1.


## 3. The Underlying Zero-Knowledge Interactive System

### 3.1. Some Specific Sets

Before describing the protocol, we introduce several supporting sets of vectors and permutations that will be extensively used throughout this work, which is inspired by Langlois et al. [7]. Let l be a positive integer and N=2l, and we have(1)
Secretd: the set of all x=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n that includes 2l+1 blocks with size n in F2. For any user d=d1,…,dl∈0,1l, the xd has the following l zero blocks 0n:x11−dl, …, xl1−dl.(2)
When givenx=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n, we define the following two permutations of x:(a)
The setS of all permutations that keep the following propositions: if π∈S, then πx=π0x0‖π10x10‖π11x11‖…‖πl0xl0‖πl1xl1, where each permutation πib can transform any word xib for all b∈0,1 and i∈l with same weight that leak any information about their support (in fact, the operation in [29] meets the above proposition: for any x˜,πx˜∈F2n, such that wx˜=wπx˜, it is possible to find a n×n invertible matrix P∈F2n×n such that πx˜=x˜P).(b)
The setT as T=Te|e∈0,1l, where for e=e1,…,el, Te∈T is a permutation: Tex=x0‖x1e1‖x11−e1‖…‖xlel‖xl1−el.When givend,e∈0,1l,π∈S, and x∈F22l+1n, it can be checked that(4)x∈Secretd⇔πx∈Secretd⇔Te∘πx∈Secretd⊕e.Therefore, in the following ZK protocol, to prove thatx∈Secretd for some d∈0,1l and A⋅x⊺=u, one can instead prove that for ∀π∈S,e∈0,1l, it satisfies(5)Te∘πx∈Secretd⊕e,A⋅x⊺=u.


### 3.2. The Interactive Protocol

The interactive protocol generally follows Stern’s protocol whose security is reduced to the SD problem and makes a zero-knowledge proof to a verifierV on a small weight secret z with solving a SD instance A,u,r. The protocol needs to be repeated t=rlogn times to reduce the soundness error negligibly small. The protocol is summarized as follows:(i)
The public parameters consist of a matrixA=A0|A10|A11|…|Al0|Al1∈F2n−k×2l+1n, and a vector u∈F2n−k and r∈ℕ.(ii)
The witness of a prover includes a vectorx=x0‖x10‖x11‖…‖xl0‖xl1∈Secretd for some secret d∈0,1l. The additional input of a verifier is a set RL=uii∈0,…,N−1⊂F2n−k whose cardinality is at most N−1.(iii)
The goal of the prover is to let the verifier convince the following issues with zero knowledge that (1)A⋅x⊺=u and x∈Secretd, while d is kept secret; (2) A0⋅x0⊺∉RL.


#### 3.2.1. Description of the Protocol

LetCOM:0,1∗⟶0,1λ be a collision-resistant hash function to be modelled as a random oracle. The prover’s witness is z=z0‖z10‖z11‖…‖zl0‖zl1∈F22l+1n, for which we employ an additional commitment c0 to enable the revocation mechanism. The prover and the verifier interact as follows.(1)
Commitment: the prover samples a stringe←0,1∗l, a permutation π←S∗, and a vector r=r0‖r10‖r11‖…‖rl0‖rl1←F∗22l+1n. Then, it sends the commitment CMT = c0,c1,c2,c3 to the verifier, where(6)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr,c3=COMTe∘πz+r.(2)
Challenge: the verifier sendsch←1,2,3∗ to the prover.(3)
Response: based on the challenge, the prover computesRSP as(7)Case ch=1:RSP=d⊕e,Te∘πz,Te∘πr,Case ch=2:RSP=e,π,z+r,Case ch=3:RSP=e,π,r.(4)
Verification: receivingRSP, the verifier outputs Valid if and only if the following three conditions hold. Otherwise, he outputs Invalid. The conditions are as follows:(i)
Casech=1: parses RSP and checks(8)Te∘πz∈Secretd⊕e,c2=COMTe∘πr,c3=COMTe∘πz+Te∘πr.(ii)
Casech=2: parses RSP and checks for ∀ui∈RL:(9)c0≠COMe,π,A0⋅z0+r0⊺−ui,c1=COMe,π,A⋅z+r⊺−u,c3=COMTe∘πz+r.(iii)
Casech=3: parses RSP and checks:(10)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr.


#### 3.2.2. Analysis of the Protocol

We use the following theorem to summarize some properties of the interactive protocol.Theorem 1 (see [7]).
IfCOM is a collision-resistant hash function, modelled as a random oracle, then the interactive protocol described in Section 3.2.1 is a ZK protocol of knowledge with perfect completeness, soundness error 2/3, and communication cost l⋅On.In particular, there exists an efficient knowledge extractor that, on inputting a commitment CMT and 3 valid responses (RSP1, RSP2, RSP3) corresponding to all 3 possible values of the challenge ch, outputs a vector y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l, and A0⋅y0⊺∉RL.It can be seen that the given interactive protocol is perfectly complete, i.e., if the prover possesses a valid witnessz, the verifier always outputs Valid according to this protocol. Indeed, given z satisfying z∈Secretd and A⋅z⊺=u, as discussed above, prover can always obtain z satisfying A⋅z⊺=u and Te∘πx∈Secretd⊕e. As a result, prover should always pass verifier’s verification in the case ch=1 and ch=2, and in the case ch=3, it suffices to note that verifier simply checks for honest computations of c1 and c2.Besides, the interactive protocol is statistically zero knowledge ifCOM is modelled as a random oracle [12].


## 3.1. Some Specific Sets

Before describing the protocol, we introduce several supporting sets of vectors and permutations that will be extensively used throughout this work, which is inspired by Langlois et al. [7]. Let l be a positive integer and N=2l, and we have(1)
Secretd: the set of all x=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n that includes 2l+1 blocks with size n in F2. For any user d=d1,…,dl∈0,1l, the xd has the following l zero blocks 0n:x11−dl, …, xl1−dl.(2)
When givenx=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n, we define the following two permutations of x:(a)
The setS of all permutations that keep the following propositions: if π∈S, then πx=π0x0‖π10x10‖π11x11‖…‖πl0xl0‖πl1xl1, where each permutation πib can transform any word xib for all b∈0,1 and i∈l with same weight that leak any information about their support (in fact, the operation in [29] meets the above proposition: for any x˜,πx˜∈F2n, such that wx˜=wπx˜, it is possible to find a n×n invertible matrix P∈F2n×n such that πx˜=x˜P).(b)
The setT as T=Te|e∈0,1l, where for e=e1,…,el, Te∈T is a permutation: Tex=x0‖x1e1‖x11−e1‖…‖xlel‖xl1−el.When givend,e∈0,1l,π∈S, and x∈F22l+1n, it can be checked that(4)x∈Secretd⇔πx∈Secretd⇔Te∘πx∈Secretd⊕e.Therefore, in the following ZK protocol, to prove thatx∈Secretd for some d∈0,1l and A⋅x⊺=u, one can instead prove that for ∀π∈S,e∈0,1l, it satisfies(5)Te∘πx∈Secretd⊕e,A⋅x⊺=u.


## 3.2. The Interactive Protocol

The interactive protocol generally follows Stern’s protocol whose security is reduced to the SD problem and makes a zero-knowledge proof to a verifierV on a small weight secret z with solving a SD instance A,u,r. The protocol needs to be repeated t=rlogn times to reduce the soundness error negligibly small. The protocol is summarized as follows:(i)
The public parameters consist of a matrixA=A0|A10|A11|…|Al0|Al1∈F2n−k×2l+1n, and a vector u∈F2n−k and r∈ℕ.(ii)
The witness of a prover includes a vectorx=x0‖x10‖x11‖…‖xl0‖xl1∈Secretd for some secret d∈0,1l. The additional input of a verifier is a set RL=uii∈0,…,N−1⊂F2n−k whose cardinality is at most N−1.(iii)
The goal of the prover is to let the verifier convince the following issues with zero knowledge that (1)A⋅x⊺=u and x∈Secretd, while d is kept secret; (2) A0⋅x0⊺∉RL.


### 3.2.1. Description of the Protocol

LetCOM:0,1∗⟶0,1λ be a collision-resistant hash function to be modelled as a random oracle. The prover’s witness is z=z0‖z10‖z11‖…‖zl0‖zl1∈F22l+1n, for which we employ an additional commitment c0 to enable the revocation mechanism. The prover and the verifier interact as follows.(1)
Commitment: the prover samples a stringe←0,1∗l, a permutation π←S∗, and a vector r=r0‖r10‖r11‖…‖rl0‖rl1←F∗22l+1n. Then, it sends the commitment CMT = c0,c1,c2,c3 to the verifier, where(6)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr,c3=COMTe∘πz+r.(2)
Challenge: the verifier sendsch←1,2,3∗ to the prover.(3)
Response: based on the challenge, the prover computesRSP as(7)Case ch=1:RSP=d⊕e,Te∘πz,Te∘πr,Case ch=2:RSP=e,π,z+r,Case ch=3:RSP=e,π,r.(4)
Verification: receivingRSP, the verifier outputs Valid if and only if the following three conditions hold. Otherwise, he outputs Invalid. The conditions are as follows:(i)
Casech=1: parses RSP and checks(8)Te∘πz∈Secretd⊕e,c2=COMTe∘πr,c3=COMTe∘πz+Te∘πr.(ii)
Casech=2: parses RSP and checks for ∀ui∈RL:(9)c0≠COMe,π,A0⋅z0+r0⊺−ui,c1=COMe,π,A⋅z+r⊺−u,c3=COMTe∘πz+r.(iii)
Casech=3: parses RSP and checks:(10)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr.


### 3.2.2. Analysis of the Protocol

We use the following theorem to summarize some properties of the interactive protocol.Theorem 1 (see [7]).
IfCOM is a collision-resistant hash function, modelled as a random oracle, then the interactive protocol described in Section 3.2.1 is a ZK protocol of knowledge with perfect completeness, soundness error 2/3, and communication cost l⋅On.In particular, there exists an efficient knowledge extractor that, on inputting a commitment CMT and 3 valid responses (RSP1, RSP2, RSP3) corresponding to all 3 possible values of the challenge ch, outputs a vector y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l, and A0⋅y0⊺∉RL.It can be seen that the given interactive protocol is perfectly complete, i.e., if the prover possesses a valid witnessz, the verifier always outputs Valid according to this protocol. Indeed, given z satisfying z∈Secretd and A⋅z⊺=u, as discussed above, prover can always obtain z satisfying A⋅z⊺=u and Te∘πx∈Secretd⊕e. As a result, prover should always pass verifier’s verification in the case ch=1 and ch=2, and in the case ch=3, it suffices to note that verifier simply checks for honest computations of c1 and c2.Besides, the interactive protocol is statistically zero knowledge ifCOM is modelled as a random oracle [12].


## 3.2.1. Description of the Protocol

LetCOM:0,1∗⟶0,1λ be a collision-resistant hash function to be modelled as a random oracle. The prover’s witness is z=z0‖z10‖z11‖…‖zl0‖zl1∈F22l+1n, for which we employ an additional commitment c0 to enable the revocation mechanism. The prover and the verifier interact as follows.(1)
Commitment: the prover samples a stringe←0,1∗l, a permutation π←S∗, and a vector r=r0‖r10‖r11‖…‖rl0‖rl1←F∗22l+1n. Then, it sends the commitment CMT = c0,c1,c2,c3 to the verifier, where(6)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr,c3=COMTe∘πz+r.(2)
Challenge: the verifier sendsch←1,2,3∗ to the prover.(3)
Response: based on the challenge, the prover computesRSP as(7)Case ch=1:RSP=d⊕e,Te∘πz,Te∘πr,Case ch=2:RSP=e,π,z+r,Case ch=3:RSP=e,π,r.(4)
Verification: receivingRSP, the verifier outputs Valid if and only if the following three conditions hold. Otherwise, he outputs Invalid. The conditions are as follows:(i)
Casech=1: parses RSP and checks(8)Te∘πz∈Secretd⊕e,c2=COMTe∘πr,c3=COMTe∘πz+Te∘πr.(ii)
Casech=2: parses RSP and checks for ∀ui∈RL:(9)c0≠COMe,π,A0⋅z0+r0⊺−ui,c1=COMe,π,A⋅z+r⊺−u,c3=COMTe∘πz+r.(iii)
Casech=3: parses RSP and checks:(10)c0=COMe,π,A0⋅r0⊺,c1=COMe,π,A⋅r⊺,c2=COMTe∘πr.


## 3.2.2. Analysis of the Protocol

We use the following theorem to summarize some properties of the interactive protocol.Theorem 1 (see [7]).
IfCOM is a collision-resistant hash function, modelled as a random oracle, then the interactive protocol described in Section 3.2.1 is a ZK protocol of knowledge with perfect completeness, soundness error 2/3, and communication cost l⋅On.In particular, there exists an efficient knowledge extractor that, on inputting a commitment CMT and 3 valid responses (RSP1, RSP2, RSP3) corresponding to all 3 possible values of the challenge ch, outputs a vector y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l, and A0⋅y0⊺∉RL.It can be seen that the given interactive protocol is perfectly complete, i.e., if the prover possesses a valid witnessz, the verifier always outputs Valid according to this protocol. Indeed, given z satisfying z∈Secretd and A⋅z⊺=u, as discussed above, prover can always obtain z satisfying A⋅z⊺=u and Te∘πx∈Secretd⊕e. As a result, prover should always pass verifier’s verification in the case ch=1 and ch=2, and in the case ch=3, it suffices to note that verifier simply checks for honest computations of c1 and c2.Besides, the interactive protocol is statistically zero knowledge ifCOM is modelled as a random oracle [12].


## 4. A Code-Based VLR-GS

In this section, we will describe and analyze our code-based VLR-GS scheme. First, we need to introduce an important tool for our scheme:trapdoor matrix, which permits to find a small weight preimage of the previous random syndrome to which a fixed syndrome is added.Definition 3 (trapdoor matrix [23]).
A trapdoor matrix family is a couple of polynomial algorithmsTrapGen,SampleS such that(i)
TrapGenλ: outputs a pair A,trk∈F2n−k×n×TℛK according to the security parameter λ, where the TℛK is the value range of trk.(ii)
SampleSA,trk,u,r: outputs with a non-negligible probability, some x∈Bn,r such as A⋅x⊺=u assuming A,trk←TrapGenλ, u∈F2n−k and r∈ℕ. Notice that x appears randomly from Bn,r, and it returns ⊥ if no solution is found.(iii)
(Correctness): for allA,trk←TrapGenλ and all vectors u∈F2n−k, we have ASampleSA,trk,u,r=u⊺.(iv)
(One-wayness): for all PPT adversaryA, we have a negligible probability:(11)PrA⋅x⊺=u,x∈Bn,r|A,trk←TrapGenλ;u∈F2n−k;x←Aλ,A,u,r.
Hence, we say thatA is a trapdoor matrix and trk is a trapdoor key if A,trk was generated by TrapGen.


### 4.1. Description of the Scheme

#### 4.1.1. Key Generation

On input the security parameterλ, an expected number of group users N=2l∈polyλ and a positive integer l. The key generation algorithm KeyGenλ,N works as follows:(1)
Select parametersn=nλ, k=kλ, r=rλ for the syndrome decoding problem, such that n−k≤lognr−2λ−O1.(2)
RunTrapGenλ to get a trapdoor matrix A0∈F2n−k×n and a trapdoor key trk.(3)
Sampleu∈F2n−k and Aib←F∗2n−k×n for all b∈0,1,i∈l. Define the matrix A=A0|A10|A11|…|−Al0|Al1∈F2n−k×2l+1n.(4)
For a group user with indexd=d1,…,dl∈0,1l, and do the following: :(a)
Sample vectorsx1d1,…,xldl←B∗n,r and compute z=∑i=1lAidi⋅xidi⊺. Then, sample vector x0∈F2n with x0←SampleSA0,trk,u−z,r. Let x11−d1, …, xl1−dl be zero vectors 0n, and define xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n; if wxd=r, then go to step (b); else, repeat step (a).(b)
Let the secret key of the group manager begmsk=trk, the user secret key be gskd=xd, and the revocation token be grtd=A0⋅x0⊺∈F2n−k.(5)
The algorithm outputsgmsk=trk and gpk,gsk,grt where(12)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.


#### 4.1.2. Signing Algorithm

Letℋ:0,1∗⟶1,2,3t be a hash function, modelled as a random oracle, where t=rlogn is the repeat number of the ZK protocol described in Section 3.2.1. Given gpk=A,u, we use the secret key gskd=x∈Secretd to sign a message M∈0,1∗, and the user runs Signgpk,gskd,M as follows:(1)
Generate a proof that the user is a certified group member and has not been revoked; this is done by repeating the ZK protocol witht times to achieve a negligible soundness error. With the public parameter A,u and prover’s witness x, we make it noninteractive with the Fiat–Shamir heuristic as a triple:(13)Π=CMTii=1t,CH,RSPii=1t,whereCH∈1,2,3t as CH=chii=1t=ℋM,CMTii=1t.(2)
Output the group signature:(14)Σ=M,Π.


#### 4.1.3. Verification Algorithm

On inputtinggpk=A,u, a set of tokens RL=uii∈0,…,N−1⊂F2n−k whose cardinality is at most N−1, a message M∈0,1∗, and a purported group signature Σ on M, the verifier runs the deterministic algorithm Verifygpk,RL,Σ,M as follows:(1)
Parse the group signatureΣ as M,Π as in formula (14).(2)
ReturnInvalid if(15)ch1,…,cht≠ℋM,CMT1,…,CMTt.(3)
Fori=1,…,t, run the verification of the ZK protocol to check the validity of RSPi with respect to CMTi and chi. Output Invalid and terminate, if any of the verification conditions does not hold.(4)
OutputValid.Remark 2.
According to the above key generation algorithm, we can get some observations as follows:(1)
According to Lemma1, the distribution of A0 is statistically close to uniform over F2n−k×n. Hence, the distribution of gpk is statistically close to uniform over F2n−k×2l+1n×F2n−k.(2)
The secret keyxd of a group user indexed by d satisfies A⋅xd⊺=u and xd∈Secretd.(3)
The distribution of revocation tokengrtd is statistically close to uniform over F2n−k, and the tokens of two different group users should be different. In each rare event of conflict, the algorithm simply resamples the key and token for the user indexed by d2.


### 4.2. Security and Efficiency Analysis

#### 4.2.1. Security

The correctness, selfless anonymity, and traceability of our VLR-GS are stated in Theorems2–4, respectively.Theorem 2.
The VLR-GS scheme described in Section4.1 is correct with an overwhelming probability.Proof.
According to the correctness requirement, it is necessary to prove that for allgpk=A,u, gsk=gskdd=0N−1, grt=grtdd=0N−1 generated by KeyGenλ,N, all d∈0,1l, and all M∈0,1∗, we have(16)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.
We can observe that , with overwhelming probability, the honest signer indexd∈0,1l can obtain a valid witness x to be used in the underlying argument system. Then, thanks to the perfect completeness of the latter protocol, the Π satisfy formula (5) is a valid triple and the algorithm Verifygpk,RL,Σ,M always outputs Valid for any message M∈0,1∗.
Suppose that the verification algorithm outputsValid, and we have grtd∉RL. If there exists an index i such that grtd=ui, i.e., a group user indexed by i with the secret key xd satisfies A0⋅x0d⊺=ui and xd∈Secretd, the verification algorithm always outputs Invalid since it cannot pass the verification of the interactive protocol described in Section 3.2.1. Finally, the verification algorithm outputs Valid with an overwhelming probability when grtd∉RL.Theorem 3.
The proposed code-based VLR-GS scheme described in Section4.1 is selfless-anonymous under the SD assumption in the random oracle model.Proof.
LetA be any PPT adversary that aims to break the selfless anonymity security of the scheme. We define a sequence of hybrid games G0b,G1b,G2b, and G3, for b∈0,1, whereGameG0b: the original selfless anonymity game in which the bit chosen by the challenger is b.GameG1b: a game similar to G0b, except the game G1b performs signing algorithm in an honest manner, and generates a legitimate signature.GameG2b: a game similar to G1b, except the game G2b replaces the token grtdb with a value selected uniformly random over F2n−k.GameG3: a game executes a proper SD problem instance.
We continue to prove that each of the two games is indistinguishable based on the zero-knowledge property of the underlying argument and the hardness of the SD problem. In the end, the selfless anonymity of our scheme then follows from the fact that gameG3 is independent of the bit b.
GameG0b. The game runs as follows.(1)
RunKeyGenλ,N to obtain gpk,gsk,grt, set RL←∅,Corrupted←∅, and give gpk to the adversary A.(2)
Based on the queries issued byA, we have(i)
IfA queries the signature on any message M and user d, return Σ=Signgpk,gskd,M.(ii)
IfA queries the corruption of user d, set Corrupted≔Corrupted∪d and return gskd.(iii)
IfA queries the revocation of user d, set RL≔RL∪grtd and return grtd.(3)
A outputs a message M∗ and d0,d1 such that d0,d1∉Corrupted, and grtd0,grtd1∉RL.(4)
Generate a signatureΣ=Signgpk,gskdb,M∗=M∗,Π, and return Σ to A.(5)
A can still make queries as before, but not allowed to ask for gskd0, gskd1, grtd0 and grtd1.(6)
Finally,A outputs a bit b′.
GameG1b. This game makes the following modification with respect to Game G0b in Step 4, instead of generating a signature as follows: run the preparation steps of the signing algorithm in an honest manner; then simulate the noninteractive ZK protocol Π∗. This is done by invoking the simulator of the argument in Theorem 1 for each repetition and programming the random oracle ℋ accordingly. Since the underlying argument is statistically zero knowledge, the distribution of Π∗ is statistically close to that of the legitimate Π. Output Σ∗=M∗,Π∗.
It can be seen thatΣ∗ is statistically close to the signature Σ outputted by Step 4 in Game G0b. Hence, we can conclude that Game G1b and Game G0b are statistically indistinguishable.
GameG2b. In this game, we introduce the following modification with respect to game G1b. In G1b, the token grtdb is unknown to A, since it is statistically close to uniform over F2n−k and grtdb=A0⋅x0b⊺ with A0,x0b∈F2n−k×n×F2n. Here, we replace x0b as sb←F∗2n and compute grtdb=A0⋅sb⊺. The remaining of the game is same as in Game G1b.
Hence, we can conclude that GameG2b and Game G1b are statistically indistinguishable.
GameG3. Note that in previous games, the pair (grtdb,sb) is a right SD instance, and hence its distribution is computationally close to the uniform distribution over F2n−k×F2n under the SD assumption. In the game, we let grtdb truly be uniform by sampling v←F∗2n−k and setting grtdb←v. The remaining of the game is same as in Game G2b. Clearly, the advantage of the adversary in this game is 0. Hence, we can conclude that G2b and G3 are computationally indistinguishable if the SD problem is hard.
Finally, based on the combined observations onG0b,G1b,G2b,G3 for the bit b∈0,1, we have(17)G0b≈sG1b≈sG2b≈cG3,where “s” means statistically indistinguishable and “c” means computationally indistinguishable. The result shows that the advantage of an adversary winning in game G0b for b∈0,1 is negligible. This concludes the proof.Theorem 4.
Suppose there is a PPT traceability adversaryA against our VLR-GS scheme with a success probability ξ in the random oracle model; then, there is an algorithm ℱ that solves the SD problem with a success probability polynomially related to ξ.Proof.
Suppose there is an adversaryA that can break the computational blinding property of COM employed by the underlying argument with a non-negligible probability; then, we can use A to solve the SD problem. Therefore, without loss of generality, we assume that COM is a collision-resistant hash function. Now, we construct a PPT algorithm ℱ solving the SD problem with a non-negligible probability, which works as follows.Challenge: the algorithmℱ receives a challenge SD instance, that is, a uniformly random matrix C=C0|C1|…|Cl∈F2n−k×l+1n and a vector u˜∈F2n−k×l+1n, and it wins the challenge if it can produce a nonzero vector x∈F2l+1n such that wx=r and C⋅x⊺=u˜.Setup:ℱ performs the following steps:(1)
Samplez=z0‖z1‖…‖zl∈F2l+1n, where each coordinate of z is sampled from F2 with length n. If wz>r, then repeat the sampling; otherwise, compute u=C⋅z⊺.(2)
RunTrapGenλ with l times and let the outputs be P1,R1,P2,R2,…,Pl,Rl.(3)
Pick a target indexd∗=d∗1,…,d∗l←0,1∗l, and define A=A0|A10|A11|…|Al0|Al1∈F2n−k×2l+1n, where A0=C0 and for each i∈l:Aid∗i=Ci and Ai1−d∗i=Pi.(4)
Define the secret key and revocation token for userd∗ as follows:(18)gskd∗=x0x10x11…xl0xl1∈F22l+1n,where for∀i∈l: x0=z0,xid∗i=zi,xi1−d∗i=0n,grtd∗=A0⋅x0⊺.(5)
Generate the secret key and the revocation token for each userdb≠d∗b, where d=d1,…,dl∈0,1l, as follows:(a)
Letdb1≤b≤l be the first bit from the left where db≠d∗b. Since d≠d∗, then b exists. It follows that Abdb=Ab1−d∗b=Pb.(b)
Samplex0,x1d1,…,xb−1db−1,xb+1db+1, …, xldl←Bn,r and let(19)td=u−A0⋅x0⊺+∑i∈l,i≠bAidi⋅xidi.(c)
Samplexbdb←SampleSRb,trk,td,r.(d)
For eachi∈l, let xi1−di=0n and xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n. If each rare event that wxd>r happens, then repeat the sampling. Otherwise, set gskd=xd and grtd=A0⋅x0⊺∈F2n−k.(6)
Letgpk,gsk,grt be(20)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.Note that by the construction, the distribution ofgpk,gsk,grt is statistically close to that of the real scheme, and the choice of d∗ is hidden from the adversary. Hence, the algorithm ℱ gives gpk,grt to A.Queries: the algorithmℱ answers the queries of A as follows:(i)
Corruption queries: at the beginning, the corruption setU is set to be empty. If A queries the secret key of any user d∈0,1l, then ℱ adds d to the set U and returns gskd.(ii)
Signatures queries: ifA queries a signature of user d on arbitrary message M, then ℱ returns Π=Signgpk,gskd,M. The queries to the random oracles ℋ and G are handled by consistently returning uniformly random values in the respective ranges. For each t≤qℋ, we let rt denote the answer to the t-th query.Forgery: eventually,A outputs a message M∗, a set of tokens RL∗, and a nontrivial forged signature(21)Π∗=CMTii=1⊺,chii=1⊺,RSPii=1⊺,M∗,such thatVerifygpk,RL∗,Π∗,M∗=Valid, and the implicit tracing algorithm fails or traces to a user outside of the coalition U\RL∗. The algorithm ℱ exploits the forgery as follows.(1)
One can argue thatA must have queried ℋ on inputs M∗,CMTii=1⊺; otherwise, the probability behaves as(22)Prch1,…,cht=ℋM∗,CMTii=1⊺≤3−t,for the choice ofd being completely hidden from A’s view. Therefore, the probability is at least ξ−3−t, and there certainly exists t∗≤qℋ such that M∗,CMTii=1t is the t∗-th oracle query.(2)
ℱ picks t∗ as the target forking point and replays A many times with the same random tape and inputs as in the original run. In each rerun, for the first t∗−1A is given the same answers r1,…,rt∗−1 as in the initial run; however, from the t∗-th query onwards, ℱ replies with fresh random values rt∗′,…,rqℋ′←1,2,3∗t. The improved forking lemma of Pointcheval and Vaudenay ([30], Lemma 7) implies that with probability larger than 1/2, the algorithm ℱ can obtain a 3-fork involving the tuple M∗,CMTii=1t after less than 32⋅qℋ/ξ−3−t replays of A. Now, let the answers of ℱ with respect to the 3-fork branches be(23)rt∗1=ch11,…,cht1,rt∗2=ch12,…,cht2,rt∗3=ch13,…,cht3.Intuitively, we can get thatPr∃i∈t:chi1,chi2,chi3=1,2,3=1−7/9t. With the index i, one parses the 3 forgeries corresponding to the fork branches to obtain RSPi1,RSPi2,RSPi3 and make them be 3 valid responses in relation with 3 different challenges for a same CMTi. Since COM is a collision-resistant hash function, we can invoke Theorem 1 to extract y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l and A0⋅y0⊺∉RL.Since the VLR-GS is sound which leads tod=d∗, y∗=y0‖y1d∗1‖…‖yld∗l∈F2l+1n is obtained from removing the zero blocks y11−d∗1,…,yl1−d∗l from y. Note that by the construction, one has C⋅y∗⊺=A⋅y⊺=u=u˜ and y∗∈Bl+1n,r. In other words, y∗ is a valid solution to the challenge SD instance C,u˜,r.Finally, we can conclude that ifA has a success probability ξ with running time T in attacking the traceability of our group signature scheme, then ℱ has the success probability of at least 1/21/N−2/3k1−7/9k with running time at most 32⋅T⋅qℋ/ξ−3−t+polyn,N. This concludes the proof of the traceability property.


#### 4.2.2. Efficiency

The algorithms described in Section4.1 can be implemented in polynomial time by selecting appropriate parameters. Asymptotically, for any n,k2 code and a group with N=2l group members, the public key size is logN⋅On2 over F2, and the group signature size is tlogN⋅On+4λ over F2, where t=rlogn is the number of repetitions of the protocol described in Section 3.2.1.In addition, we have made a comparative analysis of the latest research studies of revocable group signature schemes in Table1. In this table, references [18, 19] are two VLR-GS frameworks with the traditional “sign-and-encrypt” paradigm, which can achieve a high level of anonymity: (almost-) full anonymity. But, the code-based instantiation scheme seems not readily available, as code-based signatures for which there are efficient zero-knowledge proofs of knowledge of message/signature pairs are not known to date. Scheme [27] is a lattice-based VLR-GS scheme; like our scheme, it can resist quantum computer attacks. Scheme [27] achieves full anonymity. However, it cannot be realized in code-based group signature scheme temporarily. The scheme [12] introduced the first provably secure group signature scheme from code-based assumptions in a static group. References [23, 31] are the other two code-based group signature schemes, and they allow to dynamically add new members (weakly dynamic) but cannot realize the membership revocation. In summary, our scheme is the first code-based group signature scheme that realizes membership revocation, but unfortunately, it does not serve member registration. Next, we will consider further constructing a fully dynamic group signature system simultaneously supporting dynamic user enrolments and user revocations.Table 1
The performance comparison with related works.
SchemeTechnologyAnonymityJoinRevocationPostquantum[18]Number theoryFull anonymity×√×[19]Number theory(Almost-) full anonymity√√×[27]LatticeFull anonymity×√√[12]CodeCPA anonymity××√[31]CodeAnonymity√×√[23]CodeSelfless anonymity√×√OursCodeSelfless anonymity×√√


### 4.3. Implementation Results

Our code-based VLR group signature scheme can be implemented in polynomial time by selecting parameters carefully. For an,k2 code, a group with N=2l group members, asymptotically, the public key mainly consists of A,u∈F2n−k×2l+1n×F2n−k, and the group public key size is l⋅On2=logN⋅On2 over F2. For the group signature size, the commitment CMT achieves the bit size with 4λ (the security parameter λ should be greater than 80), and for each of the cases ch=1,ch=2, and ch=3, the size of response RSP is 4nl+2n+l, and hence the group signature size is tl⋅On+4λ=tlogN⋅On+4λ over F2, where t is the repetition number of the protocol described in Section 3.2.1. The running time of revocation check (i.e., the check against c0k when chk=2) is linear with the number of revoked users.We present the basic implementation results to demonstrate the feasibility, where the scheme is generic and can be used with any code. The binary Goppa codes are embedded since they constitute well-suited candidates for the instantiating introduced in our scheme. To achieve a 80-bit security level, we set the SD parameters asn,k,r=211,1696,121, so that the distribution of u is 280-close to the uniform distribution over F2n−k and that the SD problem is intractable with respect to the best known attacks. The protocol is repeated at least 140 times to make the soundness error negligibly small (less than 1−2−80.) We employ SHA-3 as an instantiation for the used hash functions, where it leads to the public key of size 8.9×106 bits for 28=256 users and 1.7×107 bits for 216=65536 users. And the signature size is 6.8×107 bits for 28 users and 1.3×108 bits for 216 users, with the bit size of any message M∈0,1∗.


## 4.1. Description of the Scheme

### 4.1.1. Key Generation

On input the security parameterλ, an expected number of group users N=2l∈polyλ and a positive integer l. The key generation algorithm KeyGenλ,N works as follows:(1)
Select parametersn=nλ, k=kλ, r=rλ for the syndrome decoding problem, such that n−k≤lognr−2λ−O1.(2)
RunTrapGenλ to get a trapdoor matrix A0∈F2n−k×n and a trapdoor key trk.(3)
Sampleu∈F2n−k and Aib←F∗2n−k×n for all b∈0,1,i∈l. Define the matrix A=A0|A10|A11|…|−Al0|Al1∈F2n−k×2l+1n.(4)
For a group user with indexd=d1,…,dl∈0,1l, and do the following: :(a)
Sample vectorsx1d1,…,xldl←B∗n,r and compute z=∑i=1lAidi⋅xidi⊺. Then, sample vector x0∈F2n with x0←SampleSA0,trk,u−z,r. Let x11−d1, …, xl1−dl be zero vectors 0n, and define xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n; if wxd=r, then go to step (b); else, repeat step (a).(b)
Let the secret key of the group manager begmsk=trk, the user secret key be gskd=xd, and the revocation token be grtd=A0⋅x0⊺∈F2n−k.(5)
The algorithm outputsgmsk=trk and gpk,gsk,grt where(12)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.


### 4.1.2. Signing Algorithm

Letℋ:0,1∗⟶1,2,3t be a hash function, modelled as a random oracle, where t=rlogn is the repeat number of the ZK protocol described in Section 3.2.1. Given gpk=A,u, we use the secret key gskd=x∈Secretd to sign a message M∈0,1∗, and the user runs Signgpk,gskd,M as follows:(1)
Generate a proof that the user is a certified group member and has not been revoked; this is done by repeating the ZK protocol witht times to achieve a negligible soundness error. With the public parameter A,u and prover’s witness x, we make it noninteractive with the Fiat–Shamir heuristic as a triple:(13)Π=CMTii=1t,CH,RSPii=1t,whereCH∈1,2,3t as CH=chii=1t=ℋM,CMTii=1t.(2)
Output the group signature:(14)Σ=M,Π.


### 4.1.3. Verification Algorithm

On inputtinggpk=A,u, a set of tokens RL=uii∈0,…,N−1⊂F2n−k whose cardinality is at most N−1, a message M∈0,1∗, and a purported group signature Σ on M, the verifier runs the deterministic algorithm Verifygpk,RL,Σ,M as follows:(1)
Parse the group signatureΣ as M,Π as in formula (14).(2)
ReturnInvalid if(15)ch1,…,cht≠ℋM,CMT1,…,CMTt.(3)
Fori=1,…,t, run the verification of the ZK protocol to check the validity of RSPi with respect to CMTi and chi. Output Invalid and terminate, if any of the verification conditions does not hold.(4)
OutputValid.Remark 2.
According to the above key generation algorithm, we can get some observations as follows:(1)
According to Lemma1, the distribution of A0 is statistically close to uniform over F2n−k×n. Hence, the distribution of gpk is statistically close to uniform over F2n−k×2l+1n×F2n−k.(2)
The secret keyxd of a group user indexed by d satisfies A⋅xd⊺=u and xd∈Secretd.(3)
The distribution of revocation tokengrtd is statistically close to uniform over F2n−k, and the tokens of two different group users should be different. In each rare event of conflict, the algorithm simply resamples the key and token for the user indexed by d2.


## 4.1.1. Key Generation

On input the security parameterλ, an expected number of group users N=2l∈polyλ and a positive integer l. The key generation algorithm KeyGenλ,N works as follows:(1)
Select parametersn=nλ, k=kλ, r=rλ for the syndrome decoding problem, such that n−k≤lognr−2λ−O1.(2)
RunTrapGenλ to get a trapdoor matrix A0∈F2n−k×n and a trapdoor key trk.(3)
Sampleu∈F2n−k and Aib←F∗2n−k×n for all b∈0,1,i∈l. Define the matrix A=A0|A10|A11|…|−Al0|Al1∈F2n−k×2l+1n.(4)
For a group user with indexd=d1,…,dl∈0,1l, and do the following: :(a)
Sample vectorsx1d1,…,xldl←B∗n,r and compute z=∑i=1lAidi⋅xidi⊺. Then, sample vector x0∈F2n with x0←SampleSA0,trk,u−z,r. Let x11−d1, …, xl1−dl be zero vectors 0n, and define xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n; if wxd=r, then go to step (b); else, repeat step (a).(b)
Let the secret key of the group manager begmsk=trk, the user secret key be gskd=xd, and the revocation token be grtd=A0⋅x0⊺∈F2n−k.(5)
The algorithm outputsgmsk=trk and gpk,gsk,grt where(12)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.


## 4.1.2. Signing Algorithm

Letℋ:0,1∗⟶1,2,3t be a hash function, modelled as a random oracle, where t=rlogn is the repeat number of the ZK protocol described in Section 3.2.1. Given gpk=A,u, we use the secret key gskd=x∈Secretd to sign a message M∈0,1∗, and the user runs Signgpk,gskd,M as follows:(1)
Generate a proof that the user is a certified group member and has not been revoked; this is done by repeating the ZK protocol witht times to achieve a negligible soundness error. With the public parameter A,u and prover’s witness x, we make it noninteractive with the Fiat–Shamir heuristic as a triple:(13)Π=CMTii=1t,CH,RSPii=1t,whereCH∈1,2,3t as CH=chii=1t=ℋM,CMTii=1t.(2)
Output the group signature:(14)Σ=M,Π.


## 4.1.3. Verification Algorithm

On inputtinggpk=A,u, a set of tokens RL=uii∈0,…,N−1⊂F2n−k whose cardinality is at most N−1, a message M∈0,1∗, and a purported group signature Σ on M, the verifier runs the deterministic algorithm Verifygpk,RL,Σ,M as follows:(1)
Parse the group signatureΣ as M,Π as in formula (14).(2)
ReturnInvalid if(15)ch1,…,cht≠ℋM,CMT1,…,CMTt.(3)
Fori=1,…,t, run the verification of the ZK protocol to check the validity of RSPi with respect to CMTi and chi. Output Invalid and terminate, if any of the verification conditions does not hold.(4)
OutputValid.Remark 2.
According to the above key generation algorithm, we can get some observations as follows:(1)
According to Lemma1, the distribution of A0 is statistically close to uniform over F2n−k×n. Hence, the distribution of gpk is statistically close to uniform over F2n−k×2l+1n×F2n−k.(2)
The secret keyxd of a group user indexed by d satisfies A⋅xd⊺=u and xd∈Secretd.(3)
The distribution of revocation tokengrtd is statistically close to uniform over F2n−k, and the tokens of two different group users should be different. In each rare event of conflict, the algorithm simply resamples the key and token for the user indexed by d2.


## 4.2. Security and Efficiency Analysis

### 4.2.1. Security

The correctness, selfless anonymity, and traceability of our VLR-GS are stated in Theorems2–4, respectively.Theorem 2.
The VLR-GS scheme described in Section4.1 is correct with an overwhelming probability.Proof.
According to the correctness requirement, it is necessary to prove that for allgpk=A,u, gsk=gskdd=0N−1, grt=grtdd=0N−1 generated by KeyGenλ,N, all d∈0,1l, and all M∈0,1∗, we have(16)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.
We can observe that , with overwhelming probability, the honest signer indexd∈0,1l can obtain a valid witness x to be used in the underlying argument system. Then, thanks to the perfect completeness of the latter protocol, the Π satisfy formula (5) is a valid triple and the algorithm Verifygpk,RL,Σ,M always outputs Valid for any message M∈0,1∗.
Suppose that the verification algorithm outputsValid, and we have grtd∉RL. If there exists an index i such that grtd=ui, i.e., a group user indexed by i with the secret key xd satisfies A0⋅x0d⊺=ui and xd∈Secretd, the verification algorithm always outputs Invalid since it cannot pass the verification of the interactive protocol described in Section 3.2.1. Finally, the verification algorithm outputs Valid with an overwhelming probability when grtd∉RL.Theorem 3.
The proposed code-based VLR-GS scheme described in Section4.1 is selfless-anonymous under the SD assumption in the random oracle model.Proof.
LetA be any PPT adversary that aims to break the selfless anonymity security of the scheme. We define a sequence of hybrid games G0b,G1b,G2b, and G3, for b∈0,1, whereGameG0b: the original selfless anonymity game in which the bit chosen by the challenger is b.GameG1b: a game similar to G0b, except the game G1b performs signing algorithm in an honest manner, and generates a legitimate signature.GameG2b: a game similar to G1b, except the game G2b replaces the token grtdb with a value selected uniformly random over F2n−k.GameG3: a game executes a proper SD problem instance.
We continue to prove that each of the two games is indistinguishable based on the zero-knowledge property of the underlying argument and the hardness of the SD problem. In the end, the selfless anonymity of our scheme then follows from the fact that gameG3 is independent of the bit b.
GameG0b. The game runs as follows.(1)
RunKeyGenλ,N to obtain gpk,gsk,grt, set RL←∅,Corrupted←∅, and give gpk to the adversary A.(2)
Based on the queries issued byA, we have(i)
IfA queries the signature on any message M and user d, return Σ=Signgpk,gskd,M.(ii)
IfA queries the corruption of user d, set Corrupted≔Corrupted∪d and return gskd.(iii)
IfA queries the revocation of user d, set RL≔RL∪grtd and return grtd.(3)
A outputs a message M∗ and d0,d1 such that d0,d1∉Corrupted, and grtd0,grtd1∉RL.(4)
Generate a signatureΣ=Signgpk,gskdb,M∗=M∗,Π, and return Σ to A.(5)
A can still make queries as before, but not allowed to ask for gskd0, gskd1, grtd0 and grtd1.(6)
Finally,A outputs a bit b′.
GameG1b. This game makes the following modification with respect to Game G0b in Step 4, instead of generating a signature as follows: run the preparation steps of the signing algorithm in an honest manner; then simulate the noninteractive ZK protocol Π∗. This is done by invoking the simulator of the argument in Theorem 1 for each repetition and programming the random oracle ℋ accordingly. Since the underlying argument is statistically zero knowledge, the distribution of Π∗ is statistically close to that of the legitimate Π. Output Σ∗=M∗,Π∗.
It can be seen thatΣ∗ is statistically close to the signature Σ outputted by Step 4 in Game G0b. Hence, we can conclude that Game G1b and Game G0b are statistically indistinguishable.
GameG2b. In this game, we introduce the following modification with respect to game G1b. In G1b, the token grtdb is unknown to A, since it is statistically close to uniform over F2n−k and grtdb=A0⋅x0b⊺ with A0,x0b∈F2n−k×n×F2n. Here, we replace x0b as sb←F∗2n and compute grtdb=A0⋅sb⊺. The remaining of the game is same as in Game G1b.
Hence, we can conclude that GameG2b and Game G1b are statistically indistinguishable.
GameG3. Note that in previous games, the pair (grtdb,sb) is a right SD instance, and hence its distribution is computationally close to the uniform distribution over F2n−k×F2n under the SD assumption. In the game, we let grtdb truly be uniform by sampling v←F∗2n−k and setting grtdb←v. The remaining of the game is same as in Game G2b. Clearly, the advantage of the adversary in this game is 0. Hence, we can conclude that G2b and G3 are computationally indistinguishable if the SD problem is hard.
Finally, based on the combined observations onG0b,G1b,G2b,G3 for the bit b∈0,1, we have(17)G0b≈sG1b≈sG2b≈cG3,where “s” means statistically indistinguishable and “c” means computationally indistinguishable. The result shows that the advantage of an adversary winning in game G0b for b∈0,1 is negligible. This concludes the proof.Theorem 4.
Suppose there is a PPT traceability adversaryA against our VLR-GS scheme with a success probability ξ in the random oracle model; then, there is an algorithm ℱ that solves the SD problem with a success probability polynomially related to ξ.Proof.
Suppose there is an adversaryA that can break the computational blinding property of COM employed by the underlying argument with a non-negligible probability; then, we can use A to solve the SD problem. Therefore, without loss of generality, we assume that COM is a collision-resistant hash function. Now, we construct a PPT algorithm ℱ solving the SD problem with a non-negligible probability, which works as follows.Challenge: the algorithmℱ receives a challenge SD instance, that is, a uniformly random matrix C=C0|C1|…|Cl∈F2n−k×l+1n and a vector u˜∈F2n−k×l+1n, and it wins the challenge if it can produce a nonzero vector x∈F2l+1n such that wx=r and C⋅x⊺=u˜.Setup:ℱ performs the following steps:(1)
Samplez=z0‖z1‖…‖zl∈F2l+1n, where each coordinate of z is sampled from F2 with length n. If wz>r, then repeat the sampling; otherwise, compute u=C⋅z⊺.(2)
RunTrapGenλ with l times and let the outputs be P1,R1,P2,R2,…,Pl,Rl.(3)
Pick a target indexd∗=d∗1,…,d∗l←0,1∗l, and define A=A0|A10|A11|…|Al0|Al1∈F2n−k×2l+1n, where A0=C0 and for each i∈l:Aid∗i=Ci and Ai1−d∗i=Pi.(4)
Define the secret key and revocation token for userd∗ as follows:(18)gskd∗=x0x10x11…xl0xl1∈F22l+1n,where for∀i∈l: x0=z0,xid∗i=zi,xi1−d∗i=0n,grtd∗=A0⋅x0⊺.(5)
Generate the secret key and the revocation token for each userdb≠d∗b, where d=d1,…,dl∈0,1l, as follows:(a)
Letdb1≤b≤l be the first bit from the left where db≠d∗b. Since d≠d∗, then b exists. It follows that Abdb=Ab1−d∗b=Pb.(b)
Samplex0,x1d1,…,xb−1db−1,xb+1db+1, …, xldl←Bn,r and let(19)td=u−A0⋅x0⊺+∑i∈l,i≠bAidi⋅xidi.(c)
Samplexbdb←SampleSRb,trk,td,r.(d)
For eachi∈l, let xi1−di=0n and xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n. If each rare event that wxd>r happens, then repeat the sampling. Otherwise, set gskd=xd and grtd=A0⋅x0⊺∈F2n−k.(6)
Letgpk,gsk,grt be(20)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.Note that by the construction, the distribution ofgpk,gsk,grt is statistically close to that of the real scheme, and the choice of d∗ is hidden from the adversary. Hence, the algorithm ℱ gives gpk,grt to A.Queries: the algorithmℱ answers the queries of A as follows:(i)
Corruption queries: at the beginning, the corruption setU is set to be empty. If A queries the secret key of any user d∈0,1l, then ℱ adds d to the set U and returns gskd.(ii)
Signatures queries: ifA queries a signature of user d on arbitrary message M, then ℱ returns Π=Signgpk,gskd,M. The queries to the random oracles ℋ and G are handled by consistently returning uniformly random values in the respective ranges. For each t≤qℋ, we let rt denote the answer to the t-th query.Forgery: eventually,A outputs a message M∗, a set of tokens RL∗, and a nontrivial forged signature(21)Π∗=CMTii=1⊺,chii=1⊺,RSPii=1⊺,M∗,such thatVerifygpk,RL∗,Π∗,M∗=Valid, and the implicit tracing algorithm fails or traces to a user outside of the coalition U\RL∗. The algorithm ℱ exploits the forgery as follows.(1)
One can argue thatA must have queried ℋ on inputs M∗,CMTii=1⊺; otherwise, the probability behaves as(22)Prch1,…,cht=ℋM∗,CMTii=1⊺≤3−t,for the choice ofd being completely hidden from A’s view. Therefore, the probability is at least ξ−3−t, and there certainly exists t∗≤qℋ such that M∗,CMTii=1t is the t∗-th oracle query.(2)
ℱ picks t∗ as the target forking point and replays A many times with the same random tape and inputs as in the original run. In each rerun, for the first t∗−1A is given the same answers r1,…,rt∗−1 as in the initial run; however, from the t∗-th query onwards, ℱ replies with fresh random values rt∗′,…,rqℋ′←1,2,3∗t. The improved forking lemma of Pointcheval and Vaudenay ([30], Lemma 7) implies that with probability larger than 1/2, the algorithm ℱ can obtain a 3-fork involving the tuple M∗,CMTii=1t after less than 32⋅qℋ/ξ−3−t replays of A. Now, let the answers of ℱ with respect to the 3-fork branches be(23)rt∗1=ch11,…,cht1,rt∗2=ch12,…,cht2,rt∗3=ch13,…,cht3.Intuitively, we can get thatPr∃i∈t:chi1,chi2,chi3=1,2,3=1−7/9t. With the index i, one parses the 3 forgeries corresponding to the fork branches to obtain RSPi1,RSPi2,RSPi3 and make them be 3 valid responses in relation with 3 different challenges for a same CMTi. Since COM is a collision-resistant hash function, we can invoke Theorem 1 to extract y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l and A0⋅y0⊺∉RL.Since the VLR-GS is sound which leads tod=d∗, y∗=y0‖y1d∗1‖…‖yld∗l∈F2l+1n is obtained from removing the zero blocks y11−d∗1,…,yl1−d∗l from y. Note that by the construction, one has C⋅y∗⊺=A⋅y⊺=u=u˜ and y∗∈Bl+1n,r. In other words, y∗ is a valid solution to the challenge SD instance C,u˜,r.Finally, we can conclude that ifA has a success probability ξ with running time T in attacking the traceability of our group signature scheme, then ℱ has the success probability of at least 1/21/N−2/3k1−7/9k with running time at most 32⋅T⋅qℋ/ξ−3−t+polyn,N. This concludes the proof of the traceability property.


### 4.2.2. Efficiency

The algorithms described in Section4.1 can be implemented in polynomial time by selecting appropriate parameters. Asymptotically, for any n,k2 code and a group with N=2l group members, the public key size is logN⋅On2 over F2, and the group signature size is tlogN⋅On+4λ over F2, where t=rlogn is the number of repetitions of the protocol described in Section 3.2.1.In addition, we have made a comparative analysis of the latest research studies of revocable group signature schemes in Table1. In this table, references [18, 19] are two VLR-GS frameworks with the traditional “sign-and-encrypt” paradigm, which can achieve a high level of anonymity: (almost-) full anonymity. But, the code-based instantiation scheme seems not readily available, as code-based signatures for which there are efficient zero-knowledge proofs of knowledge of message/signature pairs are not known to date. Scheme [27] is a lattice-based VLR-GS scheme; like our scheme, it can resist quantum computer attacks. Scheme [27] achieves full anonymity. However, it cannot be realized in code-based group signature scheme temporarily. The scheme [12] introduced the first provably secure group signature scheme from code-based assumptions in a static group. References [23, 31] are the other two code-based group signature schemes, and they allow to dynamically add new members (weakly dynamic) but cannot realize the membership revocation. In summary, our scheme is the first code-based group signature scheme that realizes membership revocation, but unfortunately, it does not serve member registration. Next, we will consider further constructing a fully dynamic group signature system simultaneously supporting dynamic user enrolments and user revocations.Table 1
The performance comparison with related works.
SchemeTechnologyAnonymityJoinRevocationPostquantum[18]Number theoryFull anonymity×√×[19]Number theory(Almost-) full anonymity√√×[27]LatticeFull anonymity×√√[12]CodeCPA anonymity××√[31]CodeAnonymity√×√[23]CodeSelfless anonymity√×√OursCodeSelfless anonymity×√√


## 4.2.1. Security

The correctness, selfless anonymity, and traceability of our VLR-GS are stated in Theorems2–4, respectively.Theorem 2.
The VLR-GS scheme described in Section4.1 is correct with an overwhelming probability.Proof.
According to the correctness requirement, it is necessary to prove that for allgpk=A,u, gsk=gskdd=0N−1, grt=grtdd=0N−1 generated by KeyGenλ,N, all d∈0,1l, and all M∈0,1∗, we have(16)Verifygpk,RL,Signgpk,gskd,M,M=Valid⇔grtd∉RL.
We can observe that , with overwhelming probability, the honest signer indexd∈0,1l can obtain a valid witness x to be used in the underlying argument system. Then, thanks to the perfect completeness of the latter protocol, the Π satisfy formula (5) is a valid triple and the algorithm Verifygpk,RL,Σ,M always outputs Valid for any message M∈0,1∗.
Suppose that the verification algorithm outputsValid, and we have grtd∉RL. If there exists an index i such that grtd=ui, i.e., a group user indexed by i with the secret key xd satisfies A0⋅x0d⊺=ui and xd∈Secretd, the verification algorithm always outputs Invalid since it cannot pass the verification of the interactive protocol described in Section 3.2.1. Finally, the verification algorithm outputs Valid with an overwhelming probability when grtd∉RL.Theorem 3.
The proposed code-based VLR-GS scheme described in Section4.1 is selfless-anonymous under the SD assumption in the random oracle model.Proof.
LetA be any PPT adversary that aims to break the selfless anonymity security of the scheme. We define a sequence of hybrid games G0b,G1b,G2b, and G3, for b∈0,1, whereGameG0b: the original selfless anonymity game in which the bit chosen by the challenger is b.GameG1b: a game similar to G0b, except the game G1b performs signing algorithm in an honest manner, and generates a legitimate signature.GameG2b: a game similar to G1b, except the game G2b replaces the token grtdb with a value selected uniformly random over F2n−k.GameG3: a game executes a proper SD problem instance.
We continue to prove that each of the two games is indistinguishable based on the zero-knowledge property of the underlying argument and the hardness of the SD problem. In the end, the selfless anonymity of our scheme then follows from the fact that gameG3 is independent of the bit b.
GameG0b. The game runs as follows.(1)
RunKeyGenλ,N to obtain gpk,gsk,grt, set RL←∅,Corrupted←∅, and give gpk to the adversary A.(2)
Based on the queries issued byA, we have(i)
IfA queries the signature on any message M and user d, return Σ=Signgpk,gskd,M.(ii)
IfA queries the corruption of user d, set Corrupted≔Corrupted∪d and return gskd.(iii)
IfA queries the revocation of user d, set RL≔RL∪grtd and return grtd.(3)
A outputs a message M∗ and d0,d1 such that d0,d1∉Corrupted, and grtd0,grtd1∉RL.(4)
Generate a signatureΣ=Signgpk,gskdb,M∗=M∗,Π, and return Σ to A.(5)
A can still make queries as before, but not allowed to ask for gskd0, gskd1, grtd0 and grtd1.(6)
Finally,A outputs a bit b′.
GameG1b. This game makes the following modification with respect to Game G0b in Step 4, instead of generating a signature as follows: run the preparation steps of the signing algorithm in an honest manner; then simulate the noninteractive ZK protocol Π∗. This is done by invoking the simulator of the argument in Theorem 1 for each repetition and programming the random oracle ℋ accordingly. Since the underlying argument is statistically zero knowledge, the distribution of Π∗ is statistically close to that of the legitimate Π. Output Σ∗=M∗,Π∗.
It can be seen thatΣ∗ is statistically close to the signature Σ outputted by Step 4 in Game G0b. Hence, we can conclude that Game G1b and Game G0b are statistically indistinguishable.
GameG2b. In this game, we introduce the following modification with respect to game G1b. In G1b, the token grtdb is unknown to A, since it is statistically close to uniform over F2n−k and grtdb=A0⋅x0b⊺ with A0,x0b∈F2n−k×n×F2n. Here, we replace x0b as sb←F∗2n and compute grtdb=A0⋅sb⊺. The remaining of the game is same as in Game G1b.
Hence, we can conclude that GameG2b and Game G1b are statistically indistinguishable.
GameG3. Note that in previous games, the pair (grtdb,sb) is a right SD instance, and hence its distribution is computationally close to the uniform distribution over F2n−k×F2n under the SD assumption. In the game, we let grtdb truly be uniform by sampling v←F∗2n−k and setting grtdb←v. The remaining of the game is same as in Game G2b. Clearly, the advantage of the adversary in this game is 0. Hence, we can conclude that G2b and G3 are computationally indistinguishable if the SD problem is hard.
Finally, based on the combined observations onG0b,G1b,G2b,G3 for the bit b∈0,1, we have(17)G0b≈sG1b≈sG2b≈cG3,where “s” means statistically indistinguishable and “c” means computationally indistinguishable. The result shows that the advantage of an adversary winning in game G0b for b∈0,1 is negligible. This concludes the proof.Theorem 4.
Suppose there is a PPT traceability adversaryA against our VLR-GS scheme with a success probability ξ in the random oracle model; then, there is an algorithm ℱ that solves the SD problem with a success probability polynomially related to ξ.Proof.
Suppose there is an adversaryA that can break the computational blinding property of COM employed by the underlying argument with a non-negligible probability; then, we can use A to solve the SD problem. Therefore, without loss of generality, we assume that COM is a collision-resistant hash function. Now, we construct a PPT algorithm ℱ solving the SD problem with a non-negligible probability, which works as follows.Challenge: the algorithmℱ receives a challenge SD instance, that is, a uniformly random matrix C=C0|C1|…|Cl∈F2n−k×l+1n and a vector u˜∈F2n−k×l+1n, and it wins the challenge if it can produce a nonzero vector x∈F2l+1n such that wx=r and C⋅x⊺=u˜.Setup:ℱ performs the following steps:(1)
Samplez=z0‖z1‖…‖zl∈F2l+1n, where each coordinate of z is sampled from F2 with length n. If wz>r, then repeat the sampling; otherwise, compute u=C⋅z⊺.(2)
RunTrapGenλ with l times and let the outputs be P1,R1,P2,R2,…,Pl,Rl.(3)
Pick a target indexd∗=d∗1,…,d∗l←0,1∗l, and define A=A0|A10|A11|…|Al0|Al1∈F2n−k×2l+1n, where A0=C0 and for each i∈l:Aid∗i=Ci and Ai1−d∗i=Pi.(4)
Define the secret key and revocation token for userd∗ as follows:(18)gskd∗=x0x10x11…xl0xl1∈F22l+1n,where for∀i∈l: x0=z0,xid∗i=zi,xi1−d∗i=0n,grtd∗=A0⋅x0⊺.(5)
Generate the secret key and the revocation token for each userdb≠d∗b, where d=d1,…,dl∈0,1l, as follows:(a)
Letdb1≤b≤l be the first bit from the left where db≠d∗b. Since d≠d∗, then b exists. It follows that Abdb=Ab1−d∗b=Pb.(b)
Samplex0,x1d1,…,xb−1db−1,xb+1db+1, …, xldl←Bn,r and let(19)td=u−A0⋅x0⊺+∑i∈l,i≠bAidi⋅xidi.(c)
Samplexbdb←SampleSRb,trk,td,r.(d)
For eachi∈l, let xi1−di=0n and xd=x0‖x10‖x11‖…‖xl0‖xl1∈F22l+1n. If each rare event that wxd>r happens, then repeat the sampling. Otherwise, set gskd=xd and grtd=A0⋅x0⊺∈F2n−k.(6)
Letgpk,gsk,grt be(20)gpk=A,u,gsk=gsk0,gsk1,…,gskN−1,grt=grt0,grt1,…,grtN−1.Note that by the construction, the distribution ofgpk,gsk,grt is statistically close to that of the real scheme, and the choice of d∗ is hidden from the adversary. Hence, the algorithm ℱ gives gpk,grt to A.Queries: the algorithmℱ answers the queries of A as follows:(i)
Corruption queries: at the beginning, the corruption setU is set to be empty. If A queries the secret key of any user d∈0,1l, then ℱ adds d to the set U and returns gskd.(ii)
Signatures queries: ifA queries a signature of user d on arbitrary message M, then ℱ returns Π=Signgpk,gskd,M. The queries to the random oracles ℋ and G are handled by consistently returning uniformly random values in the respective ranges. For each t≤qℋ, we let rt denote the answer to the t-th query.Forgery: eventually,A outputs a message M∗, a set of tokens RL∗, and a nontrivial forged signature(21)Π∗=CMTii=1⊺,chii=1⊺,RSPii=1⊺,M∗,such thatVerifygpk,RL∗,Π∗,M∗=Valid, and the implicit tracing algorithm fails or traces to a user outside of the coalition U\RL∗. The algorithm ℱ exploits the forgery as follows.(1)
One can argue thatA must have queried ℋ on inputs M∗,CMTii=1⊺; otherwise, the probability behaves as(22)Prch1,…,cht=ℋM∗,CMTii=1⊺≤3−t,for the choice ofd being completely hidden from A’s view. Therefore, the probability is at least ξ−3−t, and there certainly exists t∗≤qℋ such that M∗,CMTii=1t is the t∗-th oracle query.(2)
ℱ picks t∗ as the target forking point and replays A many times with the same random tape and inputs as in the original run. In each rerun, for the first t∗−1A is given the same answers r1,…,rt∗−1 as in the initial run; however, from the t∗-th query onwards, ℱ replies with fresh random values rt∗′,…,rqℋ′←1,2,3∗t. The improved forking lemma of Pointcheval and Vaudenay ([30], Lemma 7) implies that with probability larger than 1/2, the algorithm ℱ can obtain a 3-fork involving the tuple M∗,CMTii=1t after less than 32⋅qℋ/ξ−3−t replays of A. Now, let the answers of ℱ with respect to the 3-fork branches be(23)rt∗1=ch11,…,cht1,rt∗2=ch12,…,cht2,rt∗3=ch13,…,cht3.Intuitively, we can get thatPr∃i∈t:chi1,chi2,chi3=1,2,3=1−7/9t. With the index i, one parses the 3 forgeries corresponding to the fork branches to obtain RSPi1,RSPi2,RSPi3 and make them be 3 valid responses in relation with 3 different challenges for a same CMTi. Since COM is a collision-resistant hash function, we can invoke Theorem 1 to extract y=y0‖y10‖y11‖…‖yl0‖yl1∈F22l+1n satisfying A⋅y⊺=u, where y∈Secretd for some d∈0,1l and A0⋅y0⊺∉RL.Since the VLR-GS is sound which leads tod=d∗, y∗=y0‖y1d∗1‖…‖yld∗l∈F2l+1n is obtained from removing the zero blocks y11−d∗1,…,yl1−d∗l from y. Note that by the construction, one has C⋅y∗⊺=A⋅y⊺=u=u˜ and y∗∈Bl+1n,r. In other words, y∗ is a valid solution to the challenge SD instance C,u˜,r.Finally, we can conclude that ifA has a success probability ξ with running time T in attacking the traceability of our group signature scheme, then ℱ has the success probability of at least 1/21/N−2/3k1−7/9k with running time at most 32⋅T⋅qℋ/ξ−3−t+polyn,N. This concludes the proof of the traceability property.


## 4.2.2. Efficiency

The algorithms described in Section4.1 can be implemented in polynomial time by selecting appropriate parameters. Asymptotically, for any n,k2 code and a group with N=2l group members, the public key size is logN⋅On2 over F2, and the group signature size is tlogN⋅On+4λ over F2, where t=rlogn is the number of repetitions of the protocol described in Section 3.2.1.In addition, we have made a comparative analysis of the latest research studies of revocable group signature schemes in Table1. In this table, references [18, 19] are two VLR-GS frameworks with the traditional “sign-and-encrypt” paradigm, which can achieve a high level of anonymity: (almost-) full anonymity. But, the code-based instantiation scheme seems not readily available, as code-based signatures for which there are efficient zero-knowledge proofs of knowledge of message/signature pairs are not known to date. Scheme [27] is a lattice-based VLR-GS scheme; like our scheme, it can resist quantum computer attacks. Scheme [27] achieves full anonymity. However, it cannot be realized in code-based group signature scheme temporarily. The scheme [12] introduced the first provably secure group signature scheme from code-based assumptions in a static group. References [23, 31] are the other two code-based group signature schemes, and they allow to dynamically add new members (weakly dynamic) but cannot realize the membership revocation. In summary, our scheme is the first code-based group signature scheme that realizes membership revocation, but unfortunately, it does not serve member registration. Next, we will consider further constructing a fully dynamic group signature system simultaneously supporting dynamic user enrolments and user revocations.Table 1
The performance comparison with related works.
SchemeTechnologyAnonymityJoinRevocationPostquantum[18]Number theoryFull anonymity×√×[19]Number theory(Almost-) full anonymity√√×[27]LatticeFull anonymity×√√[12]CodeCPA anonymity××√[31]CodeAnonymity√×√[23]CodeSelfless anonymity√×√OursCodeSelfless anonymity×√√


## 4.3. Implementation Results

Our code-based VLR group signature scheme can be implemented in polynomial time by selecting parameters carefully. For an,k2 code, a group with N=2l group members, asymptotically, the public key mainly consists of A,u∈F2n−k×2l+1n×F2n−k, and the group public key size is l⋅On2=logN⋅On2 over F2. For the group signature size, the commitment CMT achieves the bit size with 4λ (the security parameter λ should be greater than 80), and for each of the cases ch=1,ch=2, and ch=3, the size of response RSP is 4nl+2n+l, and hence the group signature size is tl⋅On+4λ=tlogN⋅On+4λ over F2, where t is the repetition number of the protocol described in Section 3.2.1. The running time of revocation check (i.e., the check against c0k when chk=2) is linear with the number of revoked users.We present the basic implementation results to demonstrate the feasibility, where the scheme is generic and can be used with any code. The binary Goppa codes are embedded since they constitute well-suited candidates for the instantiating introduced in our scheme. To achieve a 80-bit security level, we set the SD parameters asn,k,r=211,1696,121, so that the distribution of u is 280-close to the uniform distribution over F2n−k and that the SD problem is intractable with respect to the best known attacks. The protocol is repeated at least 140 times to make the soundness error negligibly small (less than 1−2−80.) We employ SHA-3 as an instantiation for the used hash functions, where it leads to the public key of size 8.9×106 bits for 28=256 users and 1.7×107 bits for 216=65536 users. And the signature size is 6.8×107 bits for 28 users and 1.3×108 bits for 216 users, with the bit size of any message M∈0,1∗.


## 5. Conclusion

In this work, we propose the first code-based group signature scheme with membership revocation, whose security is reduced to the hardness of the syndrome decoding problem. The main idea of our work is to build a new Stern-like interactive identification protocol with member revocation mechanism. Our structure departs from the traditional “sign-and-encrypt-and-prove” group signature paradigm and does not rely on a specific encryption primitive.To the best of our knowledge, the construction presented here is the first one for code-based group signature scheme that supports member revocation, although it could still be improved for efficiency. In the future work, we will focus on improving the current building in terms of performance (for example, achieving both dynamic registration and efficient revocation of users), efficiency (for example, making the group signature size less dependent or independent of the group size), and CCA anonymity.Moreover, in terms of practical application, group signature scheme with membership revocation is a useful cryptographic primitive. With the development of the openness of wireless network, the mobile device and application (app) security are increasingly important [32], and authentication and anonymity issues in mobile environments must be concerned. The network communication between mobile users and cloud servers may suffer from various attacks, such as impersonation attack and password guessing attack. So, it is indispensable to establish an authentication and key agreement (AKA) protocol to protect the conversations between the users with mobile devices and remote servers in various application environments. To be practical, a two-factor/multifactor AKA protocol [33, 34] must satisfy the following security goals: (1) truly two-factor/multifactor security, that is, if an attacker gains any part of the authentication factors, the attacker cannot successfully figure out the remaining factors; (2) anonymity and untraceability, including identity protection and user untraceability; (3) local and secure password update. Actually, the unforgeability, anonymity, and other attributes of an AKA protocol just meet the security requirements of a VLR-GS scheme. So, we firmly believe that the application research studies of VLR-GS system in mobile device authentication and two-factor/multifactor authentication schemes are worthy of discussion in the future. Moreover, we can consider using a zero-knowledge proof protocol to ensure the security of user identity, utilizing a key encapsulation mechanism to protect the session-key security in an AKA protocol.



---

*Source: 3259767-2021-08-21.xml*