Yanhua ZHANG， Ximeng LIU， Yupu HU， Yong GAN， Huiwen JIA

1College of Computer and Communication Engineering， Zhengzhou University of Light Industry， Zhengzhou 450001， China

2College of Mathematics and Computer Science， Fuzhou University， Fuzhou 350108， China

3State Key Laboratory of Integrated Service Networks， Xidian University， Xi’an 710071， China

4College of Information Engineering， Zhengzhou University of Technology， Zhengzhou 450044， China

5School of Mathematics and Information Science， Guangzhou University， Guangzhou 510006， China

?E-mail: yhzhang@email.zzuli.edu.cn; hwjia@gzhu.edu.cn

Received Sept. 28， 2020; Revision accepted Mar. 15， 2021; Crosschecked Feb. 21， 2022

Abstract: For group signature (GS)supporting membership revocation， verifier-local revocation (VLR)mechanism seems to be a more flexible choice， because it requires only that verifiers download up-to-date revocation information for signature verification， and the signers are not involved. As a post-quantum secure cryptographic counterpart of classical number-theoretic cryptographic constructions， the first lattice-based VLR group signature (VLR-GS) was introduced by Langlois et al. (2014). However， none of the contemporary lattice-based VLR-GS schemes provide backward unlinkability (BU)， which is an important property to ensure that previously issued signatures remain anonymous and unlinkable even after the corresponding signer (i.e.， member)is revoked. In this study，we introduce the first lattice-based VLR-GS scheme with BU security (VLR-GS-BU)，and thus resolve a prominent open problem posed by previous works. Our new scheme enjoys an O(log N) factor saving for bit-sizes of the group public-key(GPK)and the member’s signing secret-key，and it is free of any public-key encryption. In the random oracle model，our scheme is proven secure under two well-known hardness assumptions of the short integer solution (SIS)problem and learning with errors (LWE) problem.

Key words: Group signature; Lattice-based cryptography; Verifier-local revocation; Backward unlikability; Short integer solution

1 Introduction

Group signature (GS) (Chaum and van Heyst， 1991) has two privacy-preserving properties:anonymity and traceability. The former enables each registered member of a group to issue signature on a message on behalf of the whole group without divulging his/her identity information; the latter enables an opening authority， in cases of any disputes，to revoke the anonymity and track the real identity of a misbehaving member. With these two appealing properties， GS has found several applications in real-life scenarios， such as direct anonymous attestation in trusted computing， anonymous vehicular ad-hoc network online communications，e-commerce systems，and many more.

To design an efficient GS theoretically， three critical cryptographic ingredients are required， in a relatively sophisticated combination. These building blocks consist of a digital signature scheme，CCA-secure public-key encryption， and an effi-cient non-interactive zero-knowledge proof protocol. Since its first introduction three decades ago，much progress has been made in the construction of GS， and some creative schemes based on different mathematical hardness assumptions， with different levels of service functionality and operating efficiency， have been proposed (Bellare et al.， 2003，2005;Boneh and Shacham，2004;Gordon et al.，2010;Bootle et al.，2016;Emura and Hayashi，2018;Huang et al.， 2020).

Supporting membership revocation， i.e.，disabling the signing ability of misbehaving members or honest members who voluntarily leave，is a desirable functionality of many multi-member(or multi-user) signature systems. Revocation not affecting the remaining members is also a non-trivial problem. Specifically， for GS with membership revocation， the verifier-local revocation (VLR)mechanism is a more flexible choice compared with re-initialization of the whole system or a dynamic accumulator， when considering a large group， and more practical and suitable for mobile environments where signers are often off-line or some computationally weak devices (e.g.， smart cards) are pervasively adopted. The concept of VLR group signature(VLR-GS)was first formalized by Boneh and Shacham (2004) and subsequently investigated and extended(Nakanishi and Funabiki，2005，2006;Libert and Vergnaud，2009;Ishida et al.，2018). However， all these constructions operate in the bilinear map setting and they may not be able to resist the effective attack of quantum computers in the future post-quantum cryptography era. As the old saying goes， “don’t put all your eggs in one basket;” it is encouraging to consider some alternative instantiations， post-quantum constructions，e.g.， based on a lattice-based cryptosystem.

Owing to the creative work of Ajtai (1996)，Regev(2005)，and Gentry et al. (2008)，lattice-based cryptography has become a hot field and GS over lattices has been extensively studied.

Lattice-based VLR-GS， introduced by Langlois et al. (2014)， is the first quantum-resistant design that supports revocation. Subsequently， improved schemes were proposed (Zhang et al.， 2016;Gao et al.， 2017; Ling et al.， 2018; Perera and Koshiba， 2018a， 2018b， 2018c)， but the schemes of Langlois et al.(2014)，Ling et al.(2018)，and Perera and Koshiba (2018a， 2018b， 2018c) operate within the Bonsai tree (Cash et al.， 2010)， and feature bit-sizes of group public-key (GPK) and member’s signing secret-key proportional to log N; therefore，none of these constructions are suitable for a large group. As two exceptions， Zhang et al. (2016) and Gao et al. (2017) adopted a new identity-encoding function (Nguyen et al.， 2015) to encode a member’s index and saved a factor O(log N) for both bit-sizes， but both needed a series of sophisticated encryptions in the signing phase， which resulted in stronger hardness assumptions. To overcome these somewhat unsatisfactory situations， Zhang et al. (2019a， 2019b) designed an improved Stern-type zero-knowledge proof (ZKP)for the identity-encoding function and a latticebased VLR-GS achieving smaller key-sizes and explicit traceability.

Backward unlinkability(BU)，a significant security first introduced by Song (2001)for GS supporting membership revocation， ensures that the previously issued signatures will remain anonymous and unlinkable even after the corresponding signer is revoked. BU security is essential to ensure privacy for honest members who voluntarily leave the group or inadvertently lose the signing secret-keys. Note that none of the existing lattice-based VLR-GSs provide BU security， because in a conventional lattice-based VLR-GS，the revocation list(RL)is provided for verification，containing a list of revocation tokens(RTs)for the revoked members. Once a member is revoked，the issued signatures cannot be accepted any more.Following this process，it is fairly easy to test whether two different but legal signatures are issued by the same revoked member by performing the verification algorithm twice with the before-and post-revocation RLs， respectively. As a result， all signatures issued by the revoked member will become linkable， which inevitably undermines privacy. This yields two interesting open questions on lattice-based VLR-GS:Is it possible to design a scheme providing BU security?How can we construct a more efficient scheme for a large group?

In this study， we introduce the first latticebased VLR-GS with BU security (VLR-GS-BU).Our scheme operates on the model of Nakanishi and Funabiki(2005)and is proven secure under two wellknown worst-case hardness assumptions: the short integer solution(SIS)problem and the learning with errors(LWE) problem.

As we discussed earlier， each registered member is given a vector called the RT， which is added to the RL once this member is revoked.Using this unique and immutable vector RT，all signatures issued by the honest revoked members who lose signing secret-keys inadvertently or leave voluntarily can be linked. So，to realize BU security，we require a mechanism in which the RT is updated，which means that each member has many RTs over the lifetime， and the signer may adopt different RTs in the signature algorithm. Once a group member is revoked，the manager can add his/her unused RTs to the RL， and the used ones remain anonymous.Therefore，to achieve BU security，a classical concept called time-periods(TPs)，adopted by Song(2001)to realize forward-secure GS， is introduced in our new member RT design. Let the entire time period TP of each group member be t discrete periods，and the member obtains RT1，RT2，...，RTt， corresponding to the discrete periods 1，2，...，t from the manager.If a member is revoked at period j ∈{1，2，...，t}，all his/her RTs after(and including)the current period，RTj，RTj+1，...，RTt， are added to the RL. Therefore，any signature issued by the revoked member after(and including)j is judged invalid using the verification algorithm，while signatures issued before(not including) j are still valid and remain anonymous.Obviously， BU security holds. Furthermore， during the generation of RTs，the main challenge is to ensure one-way security， which means leaking the revoked member’s RTs at period j，i.e.，RTj，RTj+1，...，RTt，no one including an adversary can compute any RT before period j， i.e.， RT1， or RT2，...， or RTj-1.

We first construct a lattice-based Stern-type interactive ZKP for all membership relations. Then the protocol is repeated ω(log n)times to reduce the soundness error to some negligible value and transform it into a non-interactive one， also， a signature using the Fiat-Shamir paradigm in the random oracle model. To summarize， by incorporating an efficient and improved FRD，a creative RT design，and a corresponding Stern-type statistical ZKP protocol into lattice-based VLR-GS，we introduce the first latticebased VLR-GS-BU， and thus resolve a prominent open problem.

2 Preliminaries

Table 1 refers to some notations used in this paper.

2.1 Parameters

Our lattice-based VLR-BU-GS scheme involves three main parameters: a security parameter n， the maximum number of members(i.e.，group size)N =2?= poly(n)， and the number of TPs t = poly(n).The other parameters are listed in Table 2.

Table 1 Notations used in this paper

Table 2 Parameters of our VLR-GS-BU scheme

2.2 VLR-GS definition and security model

In this subsection，we present the definition and security model of VLR-GS with BU security， which is extended from Boneh and Shacham (2004) and Nakanishi and Funabiki (2005).

Definition 1(VLR-GS-BU) A VLR-GS with BU security consists of three algorithms:

1. KeyGen(1n，N，t): a PPT algorithm takes as input security parametern， group sizeN， and number of time-periodst， and outputs Gpk， a set of signing secret-keys Gsk=(gsk0，gsk1，...，gskN-1)，and a set of RTs Grt=(grt0，1，grt0，2，...，grtN-1，t).Here，grti，jdenotes the RTjfor member id with indexiat periodj.

2.Sign(Gpk，j，gski，m): a PPT algorithm takes as input Gpk， a signing secret-keygski， current periodjfor id with indexi，and a messagem ∈{0，1}*，and outputs a signatureσ.

3. Verify(Gpk，j，RLj，σ，m): a deterministic algorithm takes as input Gpk， a set of RTs for periodj， RLj， a signatureσ， and a messagem ∈{0，1}*，and outputs either invalid or valid. Valid indicates thatσis a valid signature onmat periodj，and the signer has not been revoked at periodj.

Remark 1Any VLR-GS，as introduced by Boneh and Shacham (2004)， has an implicit-tracing algorithm: given a message-signature pair (m，σ) for periodj， the party owning Grt can determine the signer ofσby executing the verification algorithm successively， i.e.， Verify(Gpk，j，RLj=grti，j，σ，m)fori= 0，1，...，N， and outputting the first indexi* ∈{0，1，...，N-1}when the verification algorithm returns invalid.

A VLR-GS-BU scheme has three properties:correctness，BU-anonymity，and traceability.

Definition 2(Correctness) A VLR-GS-BU scheme is correct if for all (Gpk， Gsk， Grt) outputted by KeyGen， all periodsj ∈{1，2，...，t}， any member with indexi ∈{0，1，...，N -1}，all RLj ?Grt， andm ∈{0，1}*， we have

Definition 3(BU-anonymity) A VLR-GS scheme is BU-anonymous if no PPT adversaryAhas a non-negligible advantagein the following game(between a challengerCandA):

1. Initialization:Cgets (Gpk，Gsk，Grt) using KeyGen and provides Gpk toA(not including Gsk).

2. Query phase: at the beginning of a timeperiodj ∈{1，2，...，t}，CdeclaresjtoA， andjmust be incremental. During periodj，Aadaptively makes a polynomially bounded number of queries:

Signing: requesting for a signature on a messagem ∈{0，1}*for id with an indexiat periodj，Creturnsσ ←Sign(Gpk，j，gski，m).

Corrupting: requesting for a signing secret-key for id with an indexi，CreturnsgskitoA.

Revoking: requesting for a revocation token RTjof id with an indexifor current periodj，Creturnsgrti，jtoA.

3. Challenge:Aoutputs a periodj* ∈{1，2，...，t}， a messagem* ∈{0，1}*， and two distinct members id0and id1， with indicesi0andi1， respectively.Acannot make a corrupting query or a revoking query at either member; i.e.， the secret-keys of id0and id1cannot be corrupted， and id0and id1have not been revoked before or atj*.Cchooses a bitb ∈{0，1}， definesσ*using Sign(Gpk，j*，gskib，m*)as a challenge onm*by idb， and returns it toA.

4. Restricted query: once σ*is obtained，A can still make queries as before，but with restrictions that do not allow a corrupting query or a revoking query for id0or id1for the periods before (and including)j*， i.e.， in incremental form， and the opening query for (m*，σ*).

5. Guessing: A outputs a bit b*∈{0，1}， and wins if b*=b.

The advantage of A in the above game is defined as

Definition 4(Traceability) A VLR-GS-BU scheme is traceable if no PPT adversary A has a nonnegligible advantagein the following game:

1. Initialization: C gets (Gpk，Gsk，Grt) using KeyGen， and provides (Gpk，Grt) to A. Also， an initial corruption set Corr=?is defined.

2. Query phase: A adaptively makes a polynomially bounded number of queries:

Signing: requesting for a signature on a message m ∈{0，1}*for id with an index i at period j， C returns σ using Sign(Gpk，j，gski，m).

Corrupting: requesting for the signing secretkey of id with an index i，C returns gskiand adds id with its index i to Corr.

3. Forgery: A outputs m*∈{0，1}*， a period j*， a set of tokensGrt， and a signature σ*.A wins the game if Verifyvalid.

The implicit-tracing algorithm fails，or traces to a member outside(Because σ*cannot be traced tocan also be modified to Corr).

The signature σ*is non-trivial; i.e.， A has not obtained σ*by making a signing query on m*.

The advantage of A in this game is defined as its probability of winning， denoted bySuccPTA.

2.3 Background on lattices

Definition 5(Lattices) For positive integers n，m，q ≥2， and a randoman m-dimensional q-ary orthogonal latticeis defined as

For s ＞0， the Gaussian function on Rmwith center c is

For c ∈Rm， the discrete Gaussian distribution over Λ is

where DΛ，s，cis denoted as DΛ，sif c=0.

Lemma 1(Gentry et al.，2008) For integers n，q ≥

3. The min-entropy of DZm，sis at least m-1.

Ajtai (1996)introduced how to obtain a matrix A statistically close to uniform together with a low Gram-Schmidt norm basis forThen two improvements were investigated by Alwen and Peikert(2011)and Micciancio and Peikert(2012).

Lemma 2(Alwen and Peikert，2011;Micciancio and Peikert，2012) Let n ≥1，q ≥2，and m=2n.There exists a PPT algorithm TrapGen(q，n，m)that outputsand RA， such that A is statistically close to a uniform matrix inand RAis a trapdoor for orthogonal lattice

Now let us recall two important facts and a new sampling algorithm that is used in the security proofs of this work:

2.H1is computed in polynomial time， i.e.，nlogq.

3 Preparations

In this section we describe the main techniques and provide the main building block in our new design of a Stern-type statistical ZKP. First， we adopt the design techniques in Zhang et al. (2019a，2019b)for member identity encoding. Thus，only a constant number of public matrices are included in Gpk， e.g.，Gpk=(A，A0，A1)(actually，two more matricesB0andB1are needed in our scheme). We focus on describing our design of member RTs to achieve BU security.

3.1 New design of RTs

The FRD functionH1in Definition 8 is adopted to realize two essential conditions (many RTs generated over TPs and one-way security)for member RTs with BU security. Thus， for member id with an indexi，tdifferent TPs andtdifferent encoding matricesH1(TP1)，H1(TP2)，...，H1(TPt)are achieved. Further， to avoid some deadly attacks of the underlying SIS problem and BU security， we sample two random matricesas perturbations. So， for time periodj，the revocation token RTjof member id isgrti，j=(B0+H1(TPj)B1)ei，0modq， whereei，0is a short Gaussian vector (see the descriptions in Section 4.1 andei，0is the first part of the signing secret-keyei=(ei，0，ei，1)∈Z(2m))satisfying

So，grti，jis generated from the member’s signing secret-key. For the revocation mechanism， as stated by Ling et al. (2018)， due to a flaw in Langlois et al. (2014) that an inequality test method was adopted to check whether the signer’s RT belongs to a given RL， a new and corrected technique which realizes revocation by binding the signer’s RT to an LWE function (in our design， the concept of TP is adopted， and for id with an indexiat periodj，RTj=grti，j)was proposed:

whereBis from a random oracle as in Ling et al. (2018) ande0∈Zmis sampled from an LWE errorχm.

Putting all innovative ideas，design approaches，and the Stern-type argument system introduced by Ling et al.(2013)together，we have designed a Sterntype interactive ZKP protocol to prove Eqs. (1)and(2)， which is described in the next subsection.

3.2 Underlying ZKP protocol

This subsection introduces an underlying interactive Stern-type statistical ZKP protocol that allowsP(a member id with indexi)to convinceVthatPis indeed a valid member who signsm ∈{0，1}*.

In our design of the underlying Stern-type ZKP protocol，decomposition(Dec)，extension(Ext)，and matrix-extension(Mat-Ext)techniques are adopted.Specific sets，e.g.，B2?，B3m，Secβ(id)，SecExt(id*)，permutations， e.g.，π，φ ∈S3m，τ ∈S2?， and a compositionFare used. We omit all these duplicate concepts and the detailed definitions can be found in the literature (Ling et al.， 2013， 2018; Zhang et al.，2016，2019a，2019b;Gao et al.，2017).

We first define a function Bin to denote a binary representation of a member’s index，i.e.，the member id=Bin(i)∈{0，1}?fori ∈{0，1，...，N-1}，whereN= 2?= poly(n) is the group size. In addition， we define a series of integers

The underlying ZKP protocol betweenPandVcan be summarized as follows:

2. Sample permutationsπ，φ ∈S3m，τ ∈S2?，and it can be checked that

where id* ∈B2?is an extension of id=Bin(i).

For the revocation mechanism (i.e.，P’s goal isg2)， the following steps are taken:

So，P’s goal is transformed into a new relation:

To prove Eq. (4)， we take the following three steps:

3. Sample one permutationφ ∈S3m，and it can be checked thatφ(e0，r)∈B3m.

Putting all the techniques together， we design an interactive Stern-type statistical ZKP protocol.In our lattice-based VLR-GS-BU， we also use a statistically hiding and computationally blinding commitment scheme(COM)proposed by Kawachi et al.(2008).

The protocol betweenP(a member id with an indexi)andVis as follows:

Commitments:Ppicks the randomness of COM，and several objects:

Response: depending on Ch，Preplies as follows:

Verification: after receiving RSP，Vbegins to check the following:

Finally，Vreturns valid if all the conditions hold;otherwise，it returns invalid.

The associated relationR(n，k，?，t，q，m，β) in the above protocol is defined as

3.3 Analysis of the protocol

We summarize the main properties of the above protocol in the following theorem，including communication cost， perfect completeness， statistical ZK，and argument of knowledge:

Theorem 1Let COM be a statistically hiding and computationally binding commitment scheme. Then the proposed protocol is a statistical ZK argument of knowledge for the relationR(n，k，?，t，q，m，β)，where each round has perfect completeness， soundness error of 2/3， the argument of knowledge property，and communication cost

ProofThe proof includes the following aspects:

Communication cost:

1. The output of COM，a vector ofhas bitsizesnlogq， and thusPsends three commitments amounting to 3nlogqbits.

2. The challenge Ch can be represented by 2 bits.

3. The response RSP fromPconsists of:(1)one permutation inS2?;(2)3kpermutations inS3m;

(3) 2kvectors in2kvectors inand one vector in{0，1}2?.

So， the bit-size of RSP is bounded byO(?mk)logq. Recall thatk=■logβ」+1. The communication cost of the proposed Stern-type statistical ZKP protocol is bounded byO(?mlogβ)logq=

Perfect completeness:

Given a public tuple(A，A0，A1，u，B，B0，B1，j，bj)，if an honestPhas witness=(id=Bin(i)，e′i ∈Secβ(id)，e0∈Zm) and follows the proposed protocol， it can generate an efficient Stern-type statistical ZKP satisfying the verification process， and is accepted byVwith a high probability.

The inputs and witness are transformed intoA*，Pusing the Dec，Ext，and Mat-Ext techniques;thus，these results satisfy the following new structures:

As in Zhang et al. (2019a， 2019b)， to show thatPcan pass all verification checks correctly for each Ch∈{1，2，3}with a high probability without considering the checks for correct computations， we need only to note that:

3. Ch=3. We need to consider the checks for correct computations，and obviously these are true.

According to the previous discussions， the proposed protocol enjoys perfect completeness.

Statistical ZK:

As in Zhang et al. (2019a，2019b)，we should design a PPT simulator ?Sthat interacts with verifierV′(may be dishonest) to output a simulated transcript that is statistically close to the one generated by honestPin the real interaction with a probability negligibly close to 2/3. The design is as follows:

(3) Sample the randomness of COM，θ1，θ2，θ3，and several random vectors and permutations:

(5)Send CMT to V′.

After receiving Ch ∈ {1，2，3}， S? replies as follows:

(1)If Ch=1，output ⊥and abort.

(2)If Ch=2，send

(3)If Ch=3，send

(1) Sample the randomness of COM， θ1， θ2， θ3，and several random vectors and permutations:

(3)Send CMT to V′.

After receiving Ch ∈ {1，2，3}， ?S replies as follows:

(1)If Ch=1， send

(2)If Ch=2， output ⊥and abort.

(3)If Ch=3，send

(1) Sample the randomness of COM， θ1， θ2， θ3，and several random vectors and permutations:

(3)Send CMT to V′.

After receiving Ch ∈ {1，2，3}， ?S replies as follows:

(1)If Ch=1，send

(2)If Ch=2，send

(3)If Ch=3，output ⊥and abort.

Based on a statistically hiding property of COM，the distributions of CMT， Ch， and RSP are statistically close to those in the real interaction， and ?S outputs ⊥and aborts with a probability negligibly close to 1/3. Furthermore， once ?S does not halt， a valid transcript will be given，and the distribution of the transcript is statistically close to that in the real interaction， so ?S can impersonate an honest P with a probability negligibly close to 2/3.

Argument of knowledge:

To prove that the proposed protocol is an argument of knowledge for the relationR(n，k，?，t，q，m，β)， we need to prove that the given protocol satisfies the special soundness property.

If there is aP′(may be cheating) who can respond to three challenges correctly corresponding to the same commitment CMT with the inputsΔ=(A，A0，A1，B，B0，B1，u，j，bj)，then there is an extractorKwho can produce

Indeed， based on three valid RSP1， RSP2， and RSP3given byP′， the extractorKcan extract

Based on the computationally binding property of COM，the extractorKcan deduce

which is a valid witness forR=(n，k，?，t，m，β，p，t).

4 VLR-GS-BU scheme

In this section，we describe a lattice-based VLRGS-BU scheme and prove the construction satisfying three requirements， correctness， BU-anonymity，and traceability， as defined in Section 2.1. The parameters will also be specified.

4.1 Description of the scheme

KeyGen(1n，N，t): input a parametern， group sizeN= 2?= poly(n)， and number of periodst=poly(n); other parameters are as listed in Table 2.This algorithm works as follows:

1. Run TrapGen(q，n，m) to obtainand a trapdoorRA.

(4) Let the signing secret-key of member id be gski=ei ∈Z2m，and the revocation token be grti={grti，1，grti，2，...，grti，t}.

4. Output:

Gpk=(A，A0，A1，B0，B1，u，G，H1，H2)，

Gsk=(gsk0，gsk1，...，gskN-1)，

Grt=(grt0，grt1，...，grtN-1).

Sign(Gpk，j，gski，m): letχ ∈Z be aβ-bounded distribution. Take Gpk， current periodj， andm ∈{0，1}*as inputs; a member id with indexiand secret-key gski=eiproceeds as follows:

3. Generate a ZKP protocol in which the signer id is a valid member. This is achieved by repeating the protocol in Section 3.2ω(logn) times withΔ= (A，A0，A1，u，B，B0，B1，j，bj) and a witness (id，gski，e0)， and making it non-interactive aswhere CH =

4. Outputσ=(m，j，Π，v，bj).

Verify(Gpk，j，RLj，m，σ): input Gpk， a signatureσonm ∈{0，1}*， and a set of tokens RLj={grti′，j，grti′，j+1，...，grti′，t}i′≤N-1?Grt for timeperiodj; the verifier proceeds as follows:

1. Parseσ=(m，j，Π，v，bj).

2. ComputeB=G(A，A0，A1，B0，B1，u，m，v).

3. If CH/=H2(m，Δ)， return invalid.

4. Forr= 1 toκ， run the verification steps of the protocol as in Section 3.2 to check the validity of RSPrwith respect to CMTrand Chr. If any condition does not hold， return invalid.

5. For each grti′，j ∈RLj， computeei′=bj -BTgrti′，jmodq. If there exists an indexi′≤N -1 such that‖ei′‖∞≤β， then return invalid.

6. Return valid.

4.2 Analysis of the scheme

Efficiency: we first analyze the space complexity of our lattice-based VLR-GS-BU scheme with respect to the security parametern.

Gpk needs only (A，A0，A1) and a vectorufor identity-encoding， two matrices (B0，B1) and an FRD functionH1for the new RT design， and two hash functionsG，H2modeled as random oracles.So，the bit-size of Gpk isO(3nmlogq+2nmlogq+

The member signing secret-key gskiis a Gaussian vectorei ∈Z2mof bit-sizeO(2m)=

The member revocation token grtiis composed oft= poly(n) vectors grti，jof bit-size

The signatureσ= (m，j，Π，v，bj) is of bit-size

Next，we analyze the computation complexity of our lattice-based VLR-GS-BU scheme with respect ton. Here， we letr ＜Ndenote the number of revoked members in the RL andtdenote the number of time periods.

The KeyGen procedure involves one TrapGen operation， for each member， one SamplePre operation，tFRD operations for the vector overandt+ 1 matrix-vector multiplication operations overThus， the computation complexity is

The Sign procedure involves one hash function operation， one matrix-vector multiplication operation， and a proof of the corresponding noninteractive zero-knowledge (NIZK) in Section 3.2.Thus， the computation complexity is

The Verify procedure involves two hash function operations，rmatrix-vector multiplication operations，and a verification of the corresponding NIZK in Section 3.2. Thus， the computation complexity is

The detailed comparisons between our construction and previous lattice-based VLR-GS schemes，in terms of asymptotic efficiency， functionality， and security，are given in Table 3 and Figs. 1 and 2.

Table 3 Comparison of known lattice-based VLR-GS schemes (N =2?)

Our lattice-based VLR-GS enjoys better asymptotic efficiency (except a relatively high cost for

our KeyGen procedure involving extratFRD andtmatrix-vector multiplication operations). Specifically，we have achieved BU security for the first time.For correctness， BU-anonymity， and traceability，we show the following three theorems. The proof details are given in Appendix.

Fig. 1 Comparison of the 10 schemes in terms of|Gpk| (a)， |gsk| (b)， and |σ| (c)

Fig. 2 Comparison of the 10 schemes in terms of KeyGen cost (a)， Sign cost (b)， and Verify cost (c)

Theorem 2The proposed scheme is correct with an overwhelming probability.

Theorem 3If COM enjoys the statistically hiding property， the proposed scheme is BU-anonymous in the random oracle model.

Theorem 4If theproblem is hard，then the proposed scheme is traceable in the random oracle model.

5 Conclusions

In this study， we proposed the first latticebased VLR-GS scheme with BU security， and thus resolved a prominent open problem. By adopting an injective encoding function with FRD， a compact identity-encoding technique， and the corresponding Stern-type statistical ZKP protocol creatively， our new scheme enjoys aO(logN) factor saving for bit-sizes of GPK and member’s signing secret-key，and is free of any public-key encryption. Moreover，with BU security， it is more suitable for some large groups with better security.

Contributors

Yanhua ZHANG and Huiwen JIA designed the research. Yanhua ZHANG processed the data and drafted the paper. Ximeng LIU helped organize the paper. Yupu HU and Yong GAN revised and finalized the paper.

Compliance with ethics guidelines

Yanhua ZHANG， Ximeng LIU， Yupu HU， Yong GAN，and Huiwen JIA declare that they have no conflict of interest.

Appendix: Proofs for VLR-GS-BU

Proof of Theorem 2

For the first four steps of Verify， a member id with an identity indexihaving a valid witnesscan return a signature meeting it. As for step 5，ei′can be expressed as

1. Prove grti，j /∈RLj ?Verify(·)=valid.

Suppose that grti，j /∈RLj. We need to prove that with an overwhelming probability， step 5 is satisfied; i.e.， Verify(Gpk，j，RLj， Sign(Gpk，j，gski，m)，m)=valid and||ei′||∞＞β. For all grti′，j ∈RLj， we haveBT(grti，j -grti′，j) =ei′ -e0modq.Letsi′，j= grti，j -grti′，j. We have‖BTsi′，j‖∞≤‖ei′‖∞+‖e0‖∞≤‖ei′‖∞+β. According to Lemma 4 of Ling et al.(2018)，we have

2. Prove Verify(·)=valid?grti，j /∈RLj.

Assume Verify(·) = valid; for all grti′，j ∈RLj，we have‖ei′‖∞＞β. If there isi′satisfying grti，j=grti′，j， we haveei′=e0and‖ei′‖∞=‖e0‖∞≤β.Thus， a contradiction exists and the above relation holds with probability 1.

Proof of Theorem 3

A list of games is established as follows:

Game 0:Chonestly proceeds as follows:

1. Run KeyGen to obtain (Gpk，Gsk，Grt). Set RL=?， Corr=?，and send Gpk toA.

2. ForA’s signing queries onm ∈{0，1}*of memberi ≤N -1 forj ∈{1，2，...，t}，Creturnsσusing Sign(Gpk，j，gski，m); forA’s corruption queries in periodi，Csets Corr = Corr∪{id，i}and returns gski; forA’s revocation queries for periodj，Csets RL=RL∪{grti，j}and returns it.

3.Aoutputs a messagem* ∈{0，1}*， a periodj* ∈{1，2，...，t}， and two indicesi0，i1， and?b ∈{0，1}，grtib，1，grtib，2，...，grtib，j* /∈RL.

4.Cpicksand generates a signatureσ*= Sign(Gpk，j*，gskib，m*) =(m*，j*，Π，v，bj*).

5.Amakes queries as before without the right to ask for gskibor grtib，j ?b ∈{0，1}and eachj ∈{1，2，...，j*}.

6.Aoutputsb′∈{0，1}.

Game 1:Csimulates step 4 of Game 0 by programming the oracle:

2. DefineB=G(A，A0，A1，B0，B1，u，m*，v)andbj*=BTgrtib，j*+e0modq.

3. ProgramH2， andΠ*is statistically close toΠ.

Game 2:Cdefinesbj*=BTr+e0，sobj*is close statistically to the one in Game 1， and thus Game 2 is statistically indistinguishable from Game 1.

Game 3:Cgetsis close to the one in Game 2. Games 3 and 2 are computationally indistinguishable. Furthermore，the advantage

According to the indistinguishability of Games 1–3， the advantagein Game 1 is negligible;i.e.， our new scheme is BU-anonymous.

Proof of Theorem 4

Suppose that a forgerF*breaks the scheme with advantage∈; usingF*， we design an efficientAto solve theproblem.

Setup:Aproceeds as follows:

9. Let Gpk=(A，A0，A1，B0，B1，u，H1，H2，G)，Gsk = (gsk0，gsk1，...，gskN-1)， and Grt =(grt0，grt1，...，grtN-1)， and send(Gpk，Grt) toF*.

Queries:F*proceeds as follows:

1. Corrupting: take id with an indexias input;Aoutputs gskiand adds(id，i)to Corr.

2. Signing: takem ∈{0，1}*ofiat periodjas input;Aoutputsσusing Sign(Gpk，j，gski，m). In particular， the values in{1，2，3}κ=ω(logn)are sampled as responses toH2. Letrdbe a reply to thedth(d ≤qH2) query; here，qH2is the whole number of queries toH2.

Forgery:F*returnsm* ∈{0，1}*， RL*j* ?Grt for periodj*，and a forgedσ*=(m*，j*，Π*，v*，b*j*)，which satisfies the following:

1. Verify(Gpk，j*，σ*，m*)=valid.

2. The implicit-tracing does not succeed， or returns a member not included in

3.Ahas not obtainedσ*by a signing query.

F*proceeds as in Zhang et al. (2019b). LetB*=G(A，A0，A1，B0，B1，u，m*，v*).Aobtains a 3-fork involving

after at most 32qH2/(∈-3-κ)executions ofF*. With the help of an extractorKas described in the argument of knowledge，we obtain a valid witness=(id=Bin(i)∈{0，1}?，ei= (ei，0，ei，1)∈Z2m，e0∈Zm)such that:

Thus， we show two cases:

1. Ifi/=i*(the probability is at most 1-1/N)，Aaborts.

We now show that with a high probability， ?e/=0modqand‖?e‖≤poly(m):