Efficient group signature scheme using lattices

Abstract

Group signature scheme is a cryptographic primitive that allows its registered group users (or members) to generate signatures on behalf of the whole group without revealing their identity. An important feature of a group signature scheme is revocation, which allows an authorized entity called group manager to remove users from the group. Verifier Local Revocation (VLR) is a most commonly used revocation mechanism in group signature schemes because of its simplicity and efficiency. In VLR, the group manager maintains a publicly available revocation list that contains information about the revoked users. The cost of group signature verification is proportional to the size of the revocation list. To decrease the verification cost, it is enough to reduce the size of the revocation list. We use the notion of time bound signing keys for this and propose a dynamic group signature scheme. In the proposed scheme, an expiration time $\tau$ is fixed for the signing key of each group member. A user who is generating signature at time t must prove, he is a valid group member and his signing key is not expired, i.e., $t \le \tau$. Group user after the signing key expiration time are considered as ‘naturally’ revoked. Group users may be revoked before the expiration time if necessary, and it is considered ‘premature’ revocation. Hence, the revocation list needs to include the information about prematurely revoked users only. As a result, the size of the revocation list will be small, particularly in situations where natural revocation accounts for a large proportion of the total revocation.

1 Introduction

Group signatures is an extension of the digital signatures introduced by Chaum and Heyst [8]. A group signature scheme (GSS) consists of a set of potential signers (also called ‘members’ or ‘users’) forming a group. Only members of the group can generate a valid signature anonymously i.e., the identity of the signer is hidden from the signature verifiers but, they will know that the signature is generated by a valid group member (anonymity). In case of any dispute or conflict, the signature can be opened to discover the identity of the signer (tracing). A designated authority known as the group manager is in charge of the group membership. Similarly, an independent opening authority handles signature tracing.

GSS’s are extensively used in many real-world applications like e-voting, privacy-preserving vehicles interaction in VANET, e-auctions, online medical services, anonymous online communication, anonymous authentication in WSN and so on.

In a static GSS, all the potential group members are fixed before the group formation, and they cannot be modified after the group formation. Registration and revocation are the two key requirements of non-static GSS. Registration allows dynamic joining of new members to the group after the group formation. Revocation allows dynamic removal of existing members from the group after the group formation. A partial dynamic GSS allows either registration or revocation but not both. A dynamic GSS supports both registration and revocation.

So, revocation is an important requirement of non-static GSS. Currently, there are two main revocation mechanism which are used in a GSS.

• 1. Using Merkel tree based accumulators [18]. The drawback of this mechanism is, it not suitable for group with large number of users.

• 2. Verifier Local Revocation (VLR): This is the simple and mostly commonly used revocation mechanism in GSS’s.

VLR mechanism was introduced by Brickell [5] in 2003, later it was formalized by Boneh et al. [3]. In VLR mechanism, the group manager maintains a revocation token for each user in the group. To revoke any user, the group manager places the revocation token of the corresponding user in the publicly available revocation list RL. During signature verification, the verifier checks sequentially if the revocation token of the signer is present in RL. Therefore, the signature verification process involves two steps.

1. Membership check: To find if the signer is a valid group member. This can be done in constant time.

2. Revocation check: To find if the signer is revoked or not using RL. The cost of this check is O(r), where r is the number of revoked users (or RL size, since revocation token of all the revoked users are kept in RL).

Hence, the verification cost of GSS which uses VLR for revocation is O(r).

In most real-world applications that uses GSS and VLR, users will remain a member of the group for a set length of time after that they will be revoked. In such circumstances the size of RL (or r) increases over time, which in turn increases the verification cost. This motivated us to think of ways to reduce RL size.

To reduce RL size, we use the concept of time bound signing keys from Chu et.al [9]. In our method, an expiration time $\tau$ is fixed for the signing key of each group member. Any member who is generating signature at time t must prove his signing key expiration time $\tau$ is valid, i.e., $t \le \tau$. As a result, a user whose expiration time $\tau$ has passed cannot produce a signature that the verification algorithm can successfully validate. Such users with expired signing key are considered “naturally” revoked. If required, a user can be revoked before the expiration time $\tau$ by keeping his revocation token in RL. This type of revocation is considered “premature” revocation. Hence RL contains revocation tokens of only prematurely revoked users. This idea significantly reduces the RL size, particularly in situations where natural revocation accounts for a large proportion of the total revocation.

2 Literature survey

In 2010, Gordon et al. [14] proposed the first lattice based GSS. This is static scheme, where each user i is given a verification key and a signing key. Signer signs a message with his signing key using the signature scheme in [13], the resultant signature is encrypted using the variant of Regev encryption scheme [26] and provides NIZK protocol to prove the well-formedness of the ciphertext using. The main drawback of this scheme is public key and the signature size grows linear to N, where N is the number of users in the group. In 2012, Camenisch et al [6] proposed a static scheme by using attribute token system. This scheme achieved stronger anonymity and improved public key size compared to [14]. In 2013, Laguillaumie et al. [15] proposed another scheme improving the size of the signature and the group public key compared to the previous two schemes [6, 14]. The first partial dynamic GSS with revocation was proposed by Langlois et al. [16] in 2014. They used VLR mechanism for revocation. They achieved the asymptotic efficiency almost same as [15]. The main drawback of this scheme is the size of the public key and the secret key is logarithmic to N. In 2015, Nguyen et al. [20] proposed a static scheme which is efficient by $\log N$ factor in group public key and signature size compared to the previous schemes. They used an efficient encoding function to represent user identities which resulted in logarithmic key size. In 2016, Zhang et al. [28] enhanced the work of [20] including VLR based revocation to construct a partial dynamic scheme. This was the most efficient partial dynamic GSS in terms of public key size and secret key compared to all the previous schemes. Till 2016, all the existing lattice-based group signatures were either static or partial dynamic supporting only revocation, i.e., there is no scheme where members can join dynamically. The first partial dynamic scheme with registration was proposed by Libert et al. [17]. This scheme is inefficient in terms of public key size and signature size compared to [20, 28]. In 2017, Ling et al. [18] proposed the first dynamic scheme, using the accumulators to handle registration and revocation. This scheme is inefficient in asymptotic efficiency compared to [20, 22, 28] and it has been discovered that VLR mechanism is more efficient than accumulators for revocation, particularly in large groups. In 2018, one more dynamic scheme was proposed by Perera et al. [22]. However, the size of public key and the size of the secret key are similar to [16, 17] which is inefficient as compared to [20, 28]. In 2021, Abhilash et al. [1] proposed a dynamic scheme using time bound keys similar to our approach. In their scheme the signing key expiration time $\tau$ is kept private i.e., verifiers cannot know about $\tau$ and it was achieved using a binary encoding technique. A main drawback of this scheme is, signature opening cost is proportional to the number of users N in the group. Apart from the above, group signature schemes having different functionalities like message dependent opening [27], forward secure signatures [19], tracing an individual user signatures [25] and without random oracle [24] are also proposed in the literature.

3 Lattices and discrete Gaussian distribution

Before describing the lattice definition, we introduce the notation used in this paper.

Notations: Upper case letter in bold is used to represent a matrix (for example ${\varvec{{B}}}$) and lower case letter in bold is used to represent vectors in column format (for example ${\varvec{{v}}}$). Row concatenation of two matrices ${\varvec{{A}}} \in \mathbb {Z}^{n \times m}$ and ${\varvec{{A}}}_1 \in \mathbb {Z}^{p \times m}$ is represented by $[{\varvec{{A}}}|{\varvec{{A}}}_1] \in \mathbb {Z}^{(n+p) \times m}$. And column concatenation of two matrices ${\varvec{{A}}} \in \mathbb {Z}^{n \times m}$ and ${\varvec{{A}}}_1 \in \mathbb {Z}^{n \times p}$ is represented by $[{\varvec{{A}}}||{\varvec{{A}}}_1] \in \mathbb {Z}^{n \times {(m+p)}}$. ${\varvec{{B}}}^{\text {T}}$ represents the transpose of a matrix ${\varvec{{B}}}$. The $l_2$ and $l_\infty$ norms are represented by $\Vert \cdot \Vert$ and $\Vert \cdot \Vert _\infty$ respectively. For any $K \in \mathbb {Z}^+$, the set $\{1,... , K\}$ is denoted by [K] .

Lattice: Let ${\varvec{{b}}}_1,{\varvec{{b}}}_2,...,{\varvec{{b}}}_m$ be a set of linearly independent vectors over $\mathbb {R}^n$. The lattice $\varLambda$ generated by ${\varvec{{B}}}=[{\varvec{{b}}}_1|{\varvec{{b}}}_2|,...,|{\varvec{{b}}}_m] \in \mathbb {R}^{n \times m}$ is defined as:

$$\begin{aligned} \begin{aligned} \varLambda ({\varvec{{B}}})=&\left\{ \sum _{i}{\varvec{{b}}}_i \cdot z_i:z_i \in \mathbb {Z} \ \forall \ i \in [m] \right\} \end{aligned} \end{aligned}$$

Thus, $\varLambda ({\varvec{{B}}})$ is the set of all integer combination of m linearly independent vectors over $\mathbb {R}^n$.

Most lattice based cryptographic constructions are based on $q-ary$ lattices, as the problems defined on them are hard on average. The definition of three such $q-ary$ lattices are given below.

Definition 1

For integers $m\ge n \ge 1$, prime $q \ge 2$, matrix ${\varvec{{B}}} \in \mathbb {Z}_q^{n \times m}$ and ${\varvec{{u}}} \in \mathbb {Z}_q^n$ define following three lattice,

$$\begin{aligned} \begin{aligned}&\varLambda _q({\varvec{{B}}})=\{{\varvec{{e}}} \in \mathbb {Z}^m: \exists {\varvec{{y}}} \in \mathbb {Z}_q^n \text { s.t. } {\varvec{{B}}}^{\text {T}}{\varvec{{y}}}=e \mod q\} \\&\varLambda _q^\bot ({\varvec{{B}}})=\{{\varvec{{y}}} \in \mathbb {Z}^m: {\varvec{{B}}}{\varvec{{y}}}={\varvec{{0}}} \mod q\} \\&\varLambda _q^{{\varvec{{u}}}}({\varvec{{B}}})=\{{\varvec{{y}}} \in \mathbb {Z}^m: {\varvec{{B}}}{\varvec{{y}}}={\varvec{{u}}} \mod q\} \end{aligned} \end{aligned}$$

Next, we review several well known algorithms related to lattices and discrete Gaussian distribution which are used in the construction of our scheme.

GenTrap is a randomized algorithm that can be used to generate a short basis for a lattice generated by a matrix ([2], Theorem 3.2). This short basis acts as a trapdoor in our scheme.

ExtRandBasis is an randomized algorithm that can be used to obtain a trapdoor for an extended matrix using a known trapdoor and its matrix ([7], Lemma 3).

SampleD is a randomized algorithm that can be used to generate lattice vectors sampled from a discrete Gaussian distribution ([13], Theorem 4.1). And samples obtained according to the discrete Gaussian distribution are short with overwhelming probability.

Short Integer Solutions (SIS) ([4, 21]) and Learning With Errors (LWE) [21] are the two well know hard problems in lattice based cryptography. The security of our scheme is based on the hardness of these two lattice problems.

For a lattice $\varLambda$ and Gaussian parameter $\sigma \in \mathbb {R}^+$, we use the notation ${\varvec{{y}}} \hookleftarrow D_{\varLambda ,\sigma }({\varvec{{y}}})$ to indicate the lattice vector ${\varvec{{y}}}$ sampled from Gaussian distribution centred at origin.

Table 1 Parameters of the scheme

4 Proposed scheme

We propose a dynamic group signature scheme using lattices. Our scheme supports both revocation and registration. For revocation VLR mechanism is used and the idea of time bound keys is used reduces RL size. For registration we use the Join algorithm similar to [17]. In our scheme, time is represented as integers and different time formats such as YYMMDD or YYMM or YYMMDDTT can be used. For example, in YYMMDD time format $t=200310$ denotes 10 March 2020, $\tau =210515$ denotes 15 May 2021, note that $t \le \tau$. Unlike [1], the signing key expiration time $\tau$ of any group member is public in our scheme. Hence, everyone including verifiers knows $\tau$.

The proposed dynamic GSS consists of six algorithms namely KeyGen, Join, Revoke, Sign, Verify and Open. The detailed description of these algorithms are given in this section.

Symbol $\lambda >0$ denote the security parameter, d denotes the time format and $N \in poly(\lambda )$ denotes the maximum expected number of group members. Fix the parameters of the proposed scheme as shown in Table 1. Let $\chi$ be a B-bounded distribution over $\mathbb {Z}.$

4.1 KeyGen($\lambda , N, d$)

The KeyGen algorithm is executed by a trusted party. This algorithm generates group public key (gpk), group manager secret key (gmsk) and opening authority secret key (oask). The steps to generate these values are shown below.

• Run GenTrap(n, m, q) to get a matrix ${\varvec{{A}}} \in \mathbb {Z}_q^{n \times m}$ and short basis ${\varvec{{T}}}_{{\varvec{{A}}}}$ for lattice $\varLambda _q^\bot ({\varvec{{A}}})$. Once again run GenTrap(n, m, q) to get ${\varvec{{B}}} \in \mathbb {Z}_q^{n \times m}$ and short basis ${\varvec{{T}}}_{{\varvec{{B}}}}$ for lattice $\varLambda _q^\bot ({\varvec{{B}}})$.

• Sample the following matrices uniformly,

  ${\varvec{{A}}}_1, {\varvec{{A}}}_2, {\varvec{{C}}}, {\varvec{{C}}}_1, {\varvec{{C}}}_2, {\varvec{{D}}}$ over $\mathbb {Z}_q^{n \times m}$, ${\varvec{{F}}}$ over $\mathbb {Z}_q^{4n \times 4m}$,

  ${\varvec{{D}}}_0$,${\varvec{{D}}}_1$ over $\mathbb {Z}_q^{2n \times 2m}$.

  Sample a vector ${\varvec{{u}}}$ uniformly over $\mathbb {Z}_q^n$.

• Fix the group public and private parameters,

  $gpk=({\varvec{{A}}},{\varvec{{A}}}_1, {\varvec{{A}}}_2, {\varvec{{B}}},{\varvec{{C}}}, {\varvec{{C}}}_1, {\varvec{{C}}}_2, {\varvec{{D}}},{\varvec{{D}}}_0, {\varvec{{D}}}_1, {\varvec{{F}}},{\varvec{{u}}},$ $H, H_0,H_1,H_2)$, $gmsk={\varvec{{T}}}_{\varvec{{A}}}$, and $oask={\varvec{{T}}}_{\varvec{{B}}}$.

Give gmsk to the group manager and oask to the opening authority.

4.2 Join($U_i$,GM)

A user $U_i$ uses this interactive algorithm to become group member. Let (upk[i], usk[i]) denote the public and private key of a digital signature scheme possessed by $U_i$. Any $U_i$ who wish to become a group member runs this interactive algorithm. The steps of this algorithm are explained in this section.

• 1. User $U_i$ sample ${\varvec{{z}}}_i \hookleftarrow D_{\mathbb {Z}^{4m},\sigma }$ and computes a syndrome

  $$\begin{aligned}{\varvec{{v}}}_i={\varvec{{F}}}{\varvec{{z}}}_i \mod q \in \mathbb {Z}_q^{4n}. \end{aligned}$$

  Next, generate a digital signature $dsig_i$ on ${\varvec{{v}}}_i$ using usk[i] and send $({\varvec{{v}}}_i, dsig_i, upk[i])$ to GM.

• 2. GM verifies if $dsig_i$ is a valid digital signature on ${\varvec{{v}}}_i$. If valid, GM performs the following steps, otherwise it aborts:

  • Fix an identity $i \in [N]$ and generate an identity dependent matrix ${\varvec{{A}}}_i$ as

    $$\begin{aligned} \qquad \qquad {\varvec{{A}}}_i=[{\varvec{{A}}}|{\varvec{{A}}}_1+i{\varvec{{A}}}_2] \in \mathbb {Z}_q^{n \times 2m}. \end{aligned}$$

    Next, find a short basis ${\varvec{{T}}}_{{\varvec{{A}}}_i}$ for lattice $\varLambda _q^{\bot }({\varvec{{A}}}_i)$ by running ExtRandBasis$({\varvec{{A}}}_i,{\varvec{{T}}}_A,[{\varvec{{A}}}_1+i{\varvec{{A}}}_2], \sigma$) algorithm.

  • Fix an expiration time $\tau _i \in \mathbb {N}$ for $U_i$’s signing key. Let $\varvec{\tau _i}^\prime = [\varvec{\tau _{i1}}^\prime ||\varvec{\tau _{i2}}^\prime ]= H_2(\tau _i) \in \{0,1\}^{2m}$, where $\varvec{\tau _{i1}}^\prime ,\varvec{\tau _{i2}}^\prime \in \{0,1\}^m$. Compute another identity dependent matrix ${\varvec{{C}}}_i$ as,

    $$\begin{aligned} {\varvec{{C}}}_i=[{\varvec{{C}}}|{\varvec{{C}}}_1+i{\varvec{{C}}}_2] \in \mathbb {Z}_q^{n \times 2m}. \end{aligned}$$

    Compute ${\varvec{{f}}}_i = {\varvec{{C}}}_i \varvec{\tau _i}^\prime \in \mathbb {Z}_q^n$.

  • Sample ${\varvec{{s}}}_i \hookleftarrow D_{\mathbb {Z}^{2m},\sigma }$ and find ${\varvec{{d}}}_i=[{\varvec{{d}}}_{i1}||{\varvec{{d}}}_{i2}]$ using SampleD$({\varvec{{A}}}_i,{\varvec{{T}}}_{{\varvec{{A}}}_i},{\varvec{{u}}}+{\varvec{{f}}}_i+{\varvec{{D}}}bin({\varvec{{w}}}_i),\sigma )$ algorithm such that

    $$\begin{aligned} \begin{aligned} {\left\{ \begin{array}{ll} &{}{\varvec{{A}}}_i{\varvec{{d}}}_i={\varvec{{u}}}+{\varvec{{f}}}_i+{\varvec{{D}}}bin({\varvec{{w}}}_i) \mod q, \\ &{} \Vert {\varvec{{s}}}_i\Vert _{\infty } \le \beta , \; \; \Vert {\varvec{{d}}}_i\Vert _{\infty } \le \beta . \end{array}\right. } \end{aligned} \end{aligned}$$

    (1)

    where, ${\varvec{{w}}}_i={\varvec{{D}}}_0bin({\varvec{{v}}}_i)+{\varvec{{D}}}_1{\varvec{{s}}}_i \mod q$.

  • Generate the revocation token for $U_i$,

    $grt_i={\varvec{{A}}}{\varvec{{d}}}_{i1} \mod q$.

    Fix the group membership certificate as

    $cert_i=(i, {\varvec{{f}}}_i, {\varvec{{d}}}_i, {\varvec{{s}}}_i, grt_i)$ and send $(cert_i,\tau _i)$ to $U_i$.

    Finally GM stores $transcript_i=(i, {\varvec{{v}}}_i, cert_i, \tau _i,$ $dsig_i, upk[i])$ in a transcripts database. It is a private database maintained by GM which contains all the transcripts of communication between $U_i$ and GM including coin tosses used by GM.

• 3. Upon receiving $(cert_i, \tau _i)$, $U_i$ generates matrix ${\varvec{{A}}}_i$ and checks whether Eq. 1 is satisfied. If true, $U_i$ sets its signing key $gsk_i={\varvec{{z}}}_i$.

4.3 Revoke(gpk, gmsk, PRU, RL)

Group manager can prematurely revoke group users before the signing key expiration time. Here, PRU is the set of users who needs to be revoked prematurely. For each user in PRU, GM looks for their revocation token in transcripts database and keeps in RL. GM finally publishes the updated RL.

4.4 Sign($gpk, {\varvec{{m}}}, t_s,\tau _i, gsk_i, cert_i$)

User $U_i$ having $cert_i=(i, {\varvec{{f}}}_i, {\varvec{{d}}}_i, {\varvec{{s}}}_i, grt_i)$ and signing key $gsk_i={\varvec{{z}}}_i$ with expiration time $\tau _i$ can generate a signature $\varSigma$ on message ${\varvec{{m}}} \in \{0,1\}^*$ at the current time (or signature generation time) $t_s$ and $t_s \le \tau _i$ as follows:

• Sample ${\varvec{{y}}}_1$ is uniformly chosen over $\mathbb {Z}^m$. Compute a matrix ${\varvec{{G}}}_0=H_0({\varvec{{y}}}_1) \in \mathbb {Z}_q^{n \times 2m}$. Note that, ${\varvec{{v}}}_i={\varvec{{F}}}{\varvec{{z}}}_i \mod q \in \mathbb {Z}_q^{4n}$ contains the signing key, $gsk_i = {\varvec{{z}}}_i \in \mathbb {Z}^{4m}$ is encrypted using Dual-Regev Encryption Scheme [13]. In particular, choose $({\varvec{{e}}}_0,{\varvec{{s}}}_1,{\varvec{{s}}}_2)$ according to $(\chi ^n,\chi ^m, \chi ^{2m})$ respectively and generate ciphertext ${\varvec{{c}}}_{{\varvec{{v}}}_i}$,

  $$\begin{aligned} \begin{aligned} \quad {\varvec{{c}}}_{{\varvec{{v}}}_i}&= ({\varvec{{c}}}_1, {\varvec{{c}}}_2)\\ {}&=({\varvec{{B}}}^\text {T}{\varvec{{e}}}_0+{\varvec{{s}}}_1, {\varvec{{G}}}_0^\text {T}{\varvec{{e}}}_0+{\varvec{{s}}}_2+bin({\varvec{{v}}}_i)\frac{q}{2}). \end{aligned} \end{aligned}$$

• Compute ${\varvec{{A}}}^\prime \leftarrow \text {H}_1({\varvec{{m}}},gpk,{\varvec{{y}}}_1)$. Generate the commitment for revocation token $grt_i$ as,

  $$\begin{aligned} \quad {\varvec{{b}}}_{grt}={\varvec{{A}}}^\prime grt_i+{\varvec{{e}}}^\prime \mod q \text { where, } {\varvec{{e}}}^\prime \hookleftarrow \chi ^m. \end{aligned}$$

• Generate a NIZK protocol $\varPi$ similar to [1, 17] to prove the following

  • Identity $i \in [N],$ and Eq. 1 is satisfied for the matrix ${\varvec{{A}}}_i$ and vectors ${\varvec{{f}}}_i, {\varvec{{d}}}_{i},{\varvec{{s}}}_i$.

  • Cipher text ${\varvec{{c}}}_{{\varvec{{v}}}_i}$ is the correction encryption of $bin({\varvec{{v}}}_i)$ and vectors ${\varvec{{e}}}_0,{\varvec{{s}}}_1,{\varvec{{s}}}_2$ has infinity norm bound B.

  • ${\varvec{{b}}}_{grt}$ is the correct commitment for the revocation token $grt_i$.

  Repeat the protocol for $t=\omega (\log n)$ times to make soundness error negligible and then converted it to a non-interactive protocol using Fiat-Shamir heuristic [11] i.e., $\varPi =(CMT,CH,RESP)$, where

  $$\begin{aligned} CH=(cha_1,...,cha_t)= H(CMT,{\varvec{{m}}},{\varvec{{c}}}_{{\varvec{{v}}}_i},t_s,\tau _i,{\varvec{{y}}}_1). \end{aligned}$$

Output the signature, $\varSigma =({\varvec{{c}}}_{{\varvec{{v}}}_i},\varPi ,t_s,\tau _i,{\varvec{{b}}}_{grt},{\varvec{{y}}}_1)$.

4.5 Verify($gpk,{\varvec{{m}}},\varSigma ,t_s,RL$)

Verifier can check the validity of a signature $\varSigma =({\varvec{{c}}}_{{\varvec{{v}}}_i},\varPi ,$ $t_s,\tau _i,{\varvec{{b}}}_{grt},{\varvec{{y}}}_1)$ using this algorithm. It checks the below three conditions.

• 1. $t_s \le \tau _i$.

• 2. Compute ${\varvec{{A}}}^\prime \leftarrow \text {H}_1({\varvec{{m}}},gpk,{\varvec{{y}}}_1)$. For each revocation token ${\varvec{{x}}}_j \in RL$, compute ${\varvec{{c}}}_j = {\varvec{{b}}}_{grt}-{\varvec{{A}}}^\prime {\varvec{{x}}}_j$ and return 0 if any $||{\varvec{{c}}}_{j}||_{\infty } \le \beta$. This is the revocation check step that ensures signer is not prematurely revoked.

• 3. $\varPi$ is a valid protocol.

If any one of the above three conditions are not satisfied then return 0, otherwise return 1.

4.6 Open($gpk,oask,{\varvec{{m}}},\varSigma$)

Opening authority runs this algorithm to find the identity of the signer who generated a signature $\varSigma =({\varvec{{c}}}_{{\varvec{{v}}}_i},\varPi ,$ $t_s,\tau _i,{\varvec{{b}}}_{grt},{\varvec{{y}}}_1)$. It decrypts the ciphertext ${\varvec{{c}}}_{{\varvec{{v}}}_i}$ using ${\varvec{{T}}}_{\varvec{{B}}}$ (oask) and obtains $bin({\varvec{{v}}}_i)$. The steps to extract ${\varvec{{v}}}_i$ fro cipher text ${\varvec{{c}}}_{{\varvec{{v}}}_i}$ is given below.

• 1. Let ${\varvec{{G}}}_0=H_0({\varvec{{y}}}_1) \in \mathbb {Z}_q^{n \times 2m}$, using ${\varvec{{T}}}_{\varvec{{B}}}$ compute a small norm matrix ${\varvec{{E}}}_0 \in \mathbb {Z}^{m \times 2m}$, where ${\varvec{{B}}} {\varvec{{E}}}_0 = {\varvec{{G}}}_0 \mod q.$

• 2. Obtain $bin({\varvec{{v}}}_i) = ({\varvec{{c}}}_2-\frac{{\varvec{{E}}}_0^{\text {T}} {\varvec{{c}}}_1}{\frac{q}{2}})$.

Next, compute ${\varvec{{v}}}_i= \mathbf{H} \ bin({\varvec{{v}}}_i)$.¹ In transcripts database look for the record $transcript_i=(i, {\varvec{{v}}}_i, cert_i,grt_i, dsig_i, upk[i])$ that contains ${\varvec{{v}}}_i$ for some i. If found, return the corresponding i, otherwise return $\bot$.

4.7 Correctness

Correctness of the proposed scheme is proved in this section. Correctness ensures, if a group signature $\varSigma$ is generated by a non revoked member $U_i$ at time $t_s$ whose expiration time is $\tau _i$ with $t_s \le \tau _i$, then $\varSigma$ is valid and the opening of $\varSigma$ traces to $U_i$. This is explained clearly in the below definition.

Theorem 1

$\forall \ U_i,RL,{\varvec{{m}}} \in \{0,1\}^*$, $(gpk, gmsk, oask) \leftarrow \text {KeyGen}(\lambda ,N,d)$; $\ (gsk_i, cert_i, \tau _i)$ $\leftarrow \text {Join};$ and $\varSigma \leftarrow \text {Sign}(gpk, {\varvec{{m}}}, t_s,\tau _i, gsk_i, cert_i)$; we have Verify$(gpk,{\varvec{{m}}},\varSigma ,t_s,RL) = 1 \Longleftrightarrow (grt_i \notin RL) \wedge (t_s \le \tau _{i}),$ and $\text {Open}(gpk, oask, {\varvec{{m}}}, \varSigma )=i.$

Proof

Initially, we prove

$$\begin{aligned} \text {Verify}(gpk,{\varvec{{m}}},\varSigma ,t_s,RL) = 1 \Longleftrightarrow (grt_i \notin RL) \wedge (t_s \le \tau _{i}) \end{aligned}$$

(IF Condition) Step 1 of Verify algorithm implies $t_s \le \tau _i$. Step 2 in Verify algorithm, guarantees $\Vert {\varvec{{c}}}_j\Vert _\infty > \beta$ for each revocation tokens in RL, which implies $grt_i \notin RL$. In step 3, the NIZK protocol $\varPi$ validates that $U_i$’s signing key expiration time $\tau _i$ is indeed set by the group manager and not forged by the signer. This ensures $t_s \le \tau _i$.

(ONLY IF condition) Verify algorithm returns 1 iff three conditions of that algorithm are satisfied. Step 1 and 3 are valid by completeness property of $\varPi$ and $t_s \le \tau _i$ condition. Let ${\varvec{{s}}}_j=grt_i-{\varvec{{x}}}_j$ for each ${\varvec{{x}}}_j \in RL$. Since $grt_i \notin RL$, all ${\varvec{{s}}}_j$ are non-zero vectors. We know, for each ${\varvec{{x}}}_j \in RL$

$$\begin{aligned} \begin{aligned} {\varvec{{c}}}_j={\varvec{{b}}}_{grt}-{\varvec{{A}}}^\prime {\varvec{{x}}}_j ={\varvec{{A}}}^\prime grt_j+{\varvec{{e}}}^\prime -{\varvec{{A}}}^\prime {\varvec{{x}}}_j ={\varvec{{A}}}^\prime {\varvec{{s}}}_j+{\varvec{{e}}}^\prime \end{aligned} \end{aligned}$$

Therefore, by triangular inequality $\Vert {\varvec{{A}}}^\prime {\varvec{{s}}}_j\Vert _\infty \le \Vert {\varvec{{c}}}_j\Vert _\infty +\Vert {\varvec{{e}}}^\prime \Vert _\infty$. And By Lemma 4 in [16], $Pr[\Vert {\varvec{{A}}}^\prime {\varvec{{s}}}_j\Vert _\infty \le 2\beta ] \le negl(n)$. Hence, we get $\Vert {\varvec{{c}}}_j\Vert _\infty > \beta$ for all revocation tokens in RL. So, step 2 in Verify algorithm is satisfied. Therefore, Verify algorithm returns 1 with high probability. $\square$

By correctness of decryption algorithm of Dual-Regev encryption scheme, Open algorithm correctly returns the identity of the signer.

5 Security definitions

We follow the security model of Emura et al. [10]. The notion of security in a group signature scheme can be understood through three attacks namely framing attack (frameability), tracing attack (traceability) and selfless-anonymity. Definitions of these three attacks and security of our scheme against these attacks will be explained in this section. Before that, we define shared variables and oracles whose access may be given to the adversary $\mathcal {A}$ in different attacks.

Variables:

• $H_u$: This set contains honest users of the group.

• $C_u$: This set contains corrupted users of the group.

• Sigs: This list contains the signing queries made by $\mathcal {A}$.

Oracles:

• $\varvec{Add_{user} }$: Adversary $\mathcal {A}$ can add an honest user to the group using this oracle. It takes identity i as input and computes $gsk_i, cert_i, \tau _i$ by running the Join algorithm locally. Later i is kept in $H_u$ set.

• $\varvec{Q_{gm}}$ : $\mathcal {A}$ acts as a corrupt user i and involves in Join protocol with this oracle. In the end, $\mathcal {A}$ gets $cert_i,\tau _i$ and fixes its $gsk_i$. Later i is kept in $C_u$ set.

• $\varvec{Q_{user }}$: In this $\mathcal {A}$ acts as a corrupted GM and involves in Join protocol with an honest user i. Later i is kept in $H_u$ set.

• $\varvec{Get_{reg}}$: This oracle returns $(grt_i, \tau _i)$ on input index i. It returns $\bot$ if no such i exists.

• $\varvec{Revoke}$: $\mathcal {A}$ can revoke honest users of his choice using this oracle.

• $\varvec{G_{sign}}$: This oracle takes identity i, a message ${\varvec{m}}$ as input and returns signature $\varSigma \text { on } {\varvec{m}}$ to $\mathcal {A}$. Later $({\varvec{{m}}}, \varSigma , t_s)$ kept in Sigs list, here $t_s$ is current time.

• $\varvec{Get_{gmsk}}$: Returns gmsk to $\mathcal {A}$.

• $\varvec{Get_{oask}}$: Returns oask to $\mathcal {A}$.

• $\varvec{Get_{usk}}$: This oracle takes i as input and returns $(gsk_i, cert_i)$ to $\mathcal {A}$. Also, i is kept in $C_u$ set. It returns $\bot$ if no such i exists.

5.1 Traceability

In the traceability attack, $\mathcal {A}$ has access to $Get_{oask}, Q_{gm},$ $G_{sign}, Get_{reg}, Revoke$ oracles. In the end $\mathcal {A}$ should generate signature that is opened to a user not controlled by him or forge the secret key expiration time of the traced user. This is explained clearly in the experiment, $Exp_{\mathcal {A}}^{trace}(\lambda )$ shown below.

A scheme is secure against traceability if the advantage of $\mathcal {A}$, $Adv^{trace}_{ \mathcal {A} }(\lambda ):=Pr[Exp_{\mathcal {A}}^{trace}(\lambda )=1]$ is negligible. The security of the proposed scheme against this attack is proved below.

Proof

Assume an adversary $\mathcal {A}$ successfully achieves tracing attack on our scheme with a non negligible $\epsilon$ probability. Then, we construct an algorithm $\mathcal {B}$ that solves SIS instance for matrix $\bar{{\varvec{{A}}}}=[\bar{{\varvec{{A}}}}_1||\bar{{\varvec{{A}}}}_2||\bar{{\varvec{{A}}}}_3] \in \mathbb {Z}_q^{n \times 3m}$ with non-negligible probability. $\square$

An identity $i^*$ is uniformly chosen over [N] and $\tau _{i^*}$ be the signing key expiration time of $i^*$. Next, $\mathcal {B}$ runs the KeyGen algorithm as follows.

KeyGen:

• Fix ${\varvec{{A}}}=\bar{{\varvec{{A}}}}_1$, ${\varvec{{C}}}=\bar{{\varvec{{A}}}}_3$. Generate $({\varvec{{B}}}, {\varvec{{T}}}_{{\varvec{{B}}}})$ and $({\varvec{{A}}}_2, {\varvec{{T}}}_{{\varvec{{A}}}_2})$ by running GenTrap(n, m, q) algorithm twice.

• Sample the following matrices uniformly, ${\varvec{{C}}}_2$ over $\mathbb {Z}_q^{n \times m}$, ,${\varvec{{D}}}_0$ over $\mathbb {Z}_q^{2n \times 2m}$, ${\varvec{{F}}}$ over $\mathbb {Z}_q^{4n \times 4m}$, and ${\varvec{{R}}}, {\varvec{{R}}}_1, {\varvec{{R}}}_2$ over $\{-1,1\}^{m \times m}$.

• Compute ${\varvec{{A}}}_1={\varvec{{A}}}{\varvec{{R}}}-i^*{\varvec{{A}}}_2$, ${\varvec{{C}}}_1={{\varvec{{C}}}}{\varvec{{R}}}_1-i^*{\varvec{{C}}}_2$, ${\varvec{{D}}}=\bar{{\varvec{{A}}}}_2{\varvec{{R}}}_2, {\varvec{{u}}}={\varvec{{A}}}{\varvec{{e}}} \mod q$, where ${\varvec{{e}}} \hookleftarrow D_{\mathbb {Z}^m, \sigma }$.

• Fix $gpk=({\varvec{{A}}}, {\varvec{{A}}}_1, {\varvec{{A}}}_2, {\varvec{{B}}}, {\varvec{{C}}}, {\varvec{{C}}}_1, {\varvec{{C}}}_2, {\varvec{{D}}}, {\varvec{{D}}}_0, {\varvec{{u}}}, {\varvec{{F}}},$ $H,H_0,H_1,H_2)$, $\ gmsk={\varvec{{T}}}_{{\varvec{{A}}}_2} \text { and } oask = {\varvec{{T}}}_{{\varvec{{B}}}}$.

Queries: In this section we explain how $\mathcal {B}$ answers to $\mathcal {A}$’s queries.

• $Q_{gm}:$ Increment n by 1, generate identity dependent matrix ${\varvec{{A}}}_n=[{\varvec{{A}}}|{\varvec{{A}}}_1+n{\varvec{{A}}}_2]$ and ${\varvec{{C}}}_n=[{\varvec{{C}}}|{\varvec{{C}}}_1+n{\varvec{{C}}}_2]$. Fix an expiration time $\tau _n$ for $U_n$’s signing key and find ${\varvec{{f}}}_n$ similar to KeyGen algorithm in Sect. 4.1. Using ${\varvec{{T}}}_{{\varvec{{A}}}_2}$ and SampleD algorithm obtain ${\varvec{{d}}}_n$ such that Eq. 1 is satisfied for identity matrix $n, {\varvec{{A}}}_n, {\varvec{{f}}}_n, {\varvec{{w}}}_n$. Generate the revocation token as in KeyGen of Sect. 4.1 and send $(cert_n, \tau _n)$ to $\mathcal {A}$. Finally include n to $C_u$ set.

• $Get_{oask}:$ Return oask to $\mathcal {A}$.

• $G_{sign}:$ Abort if $i=i^*$ or $i \in C_u$, otherwise recall $(gsk_i,\tau _i,cert_i)$ and generate signature using Sign algorithm. Add $(m, \varSigma ,t_s)$ to Sigs, where $t_s$ is current time.

• Revoke :  Abort if $i=i^*$, otherwise $\mathcal {B}$ finds $grt_i$ in transcripts database and places it in RL.

• $Get_{reg}:$ $\mathcal {B}$ looks for i’s record in transcripts database and returns $(grt_i,\tau _i)$.

Forgery: $\mathcal {A}$ outputs $({\varvec{{m}}}^*, \varSigma ^*, t_s^*, RL^*)$ such that $\text {Verify }(gpk, {\varvec{{m}}}^*, \varSigma ^*,t_S^*, RL^*)=1$.

Let $\text {Open}(gpk, oask,{\varvec{{m}}}^*, \varSigma ^*)=j$, if $j \in C_u$ or $j \ne i^*$ abort. Otherwise, parse $\varSigma ^*=({\varvec{{c}}}_{{\varvec{{v}}}_j}^*,\varPi ^*,t_s^*,\tau _{j^*},{\varvec{{b}}}_{grt}^*,{\varvec{{y}}}_1^*)$ and $\varPi ^*=(\text {CMT}, \text {CH}, \text {RESP})$.

We claim, $\mathcal {A}$ should have made a query to the random oracle H on input $(CMT, {\varvec{{m}}}^*,{\varvec{{c}}}_{{\varvec{{v}}}_j}^*,t_s^*,\tau _{j^*},{\varvec{{y}}}_1^*)$ with overwhelming probability. Otherwise,

$$\begin{aligned} \begin{aligned} Pr[CH{=}(cha_1,...,cha_t){=}H(CMT,{\varvec{{m}}}^*,{\varvec{{c}}}_{{\varvec{{v}}}_j}^*,t_s^*,\tau _{j^*},{\varvec{{y}}}_1^*)] \le \frac{1}{3^t} \end{aligned} \end{aligned}$$

Above probability is negligible, therefore with $\epsilon -\frac{1}{3^{t}}$ probability, $\mathcal {A}$ should have made queries to the random oracle H on input $(CMT,{\varvec{{m}}}^*,{\varvec{{c}}}_{{\varvec{{v}}}_j}^*,t_s^*,\tau _{j^*},{\varvec{{y}}}_1^*)$. Let $h^* \le \{1,2,..., Q_\text {H}\}$ be the index of this specific query, where $Q_\text {H}$ is total number of hash queries made by $\mathcal {A}$. Now $\mathcal {B}$ picks $q_h$ as target point and replay $\mathcal {A}$ many times with the same input and random tape. For the first $h^*-1$ queries, it replies to $\mathcal {A}$ with $(r_1,...,r_{h^*-1})$ same as the original run and from ${h^*}$-th query, it replies with fresh answers $(r_h^*, ... ,r_{Q_H})$ which are uniformly chosen over $\{1,2,3\}$. By improved forking lemma [23] with probability greater than $\frac{1}{2}$, $\mathcal {B}$ obtains three forking branches involving the tuple $(CMT,{\varvec{{m}}}^*,{\varvec{{c}}}_{{\varvec{{v}}}_j}^*,t_s^*,\tau _{j^*},{\varvec{{y}}}_1^*)$ and let the answers of $\mathcal {B}$ corresponding to three fork branches be

$$\begin{aligned} \begin{aligned}&r_{h^*}^{(1)}=(cha_1^{(1)},...,cha_t^{(1)}), r_{h^*}^{(2)}=(cha_1^{(2)},...,cha_t^{(2)}),\\&r_{h^*}^{(3)}=(cha_1^{(3)},...,cha_t^{(3)}) \end{aligned} \end{aligned}$$

It can be easily shown that,

$$\begin{aligned} \begin{aligned} Pr[\{\exists l \in [t]: (cha_l^{(1)}, cha_l^{(2)}, cha_l^{(3)})=\{1,2,3\}]= 1-(\frac{7}{9})^t. \end{aligned} \end{aligned}$$

If such an index l exists, one parses the 3 forgeries corresponding to the fork branches to obtain $(\text {RESP}_l^{(1)},$ $\text {RESP}_l^{(2)},\text {RESP}_l^{(3)})$. They are the three valid responses with respect to three different challenges but for the single commitment $CMT_l$. Now $\mathcal {B}$ can extract the witness $(j,{\varvec{{f}}}_j, {\varvec{{d}}}_j, {\varvec{{w}}}_{j})$ using witness extraction procedure. If $j\ne i^*$ then $\mathcal {B}$ aborts, otherwise we will show how $\mathcal {B}$ solves SIS instance below.

We know,

$$\begin{aligned} \begin{aligned} {\varvec{{A}}}_j {\varvec{{d}}}_j={\varvec{{u}}} +{\varvec{{f}}}_j +{\varvec{{D}}} bin( {\varvec{{w}}}_j) \mod q\\ \text {where, }{\varvec{{w}}}_j={\varvec{{D}}}_0bin({\varvec{{v}}}_j)+{\varvec{{D}}}_1{\varvec{{s}}}_j \mod q. \end{aligned} \end{aligned}$$

Above equation can be simplified by substituting corresponding vales as below.

$$\begin{aligned}&\begin{aligned}&{\varvec{{A}}}_j {\varvec{{d}}}_j -{\varvec{{C}}}_j \varvec{\tau _j^\prime } -{\varvec{{D}}} bin( {\varvec{{w}}}_j)-{\varvec{{u}}} =0 \mod q.\\&[\bar{{\varvec{{A}}}}_1|\bar{{\varvec{{A}}}}_1{\varvec{{R}}}][{\varvec{{d}}}_{j1}|| {\varvec{{d}}}_{j2}] - [\bar{{\varvec{{A}}}}_3|\bar{{\varvec{{A}}}}_3{\varvec{{R}}}_1][\varvec{\tau _{j1}^\prime }||\varvec{\tau _{j2}^\prime }]- \\&\qquad \qquad \bar{{\varvec{{A}}}}_2{\varvec{{R}}}_2bin( {\varvec{{w}}}_j )- \bar{{\varvec{{A}}}}_1{\varvec{{e}}} =0 \mod q. \\&\bar{{\varvec{{A}}}}_1({\varvec{{d}}}_{j1}+ {\varvec{{R}}}{\varvec{{d}}}_{j2}-{\varvec{{e}}}) +\bar{{\varvec{{A}}}}_2(-{\varvec{{R}}}_2bin({\varvec{{w}}}_j)) + \\&\qquad \qquad \bar{{\varvec{{A}}}}_3(-(\varvec{\tau _{j1}^\prime }+{\varvec{{R}}}_1\varvec{\tau _{j2}^\prime })) = 0 \mod q. \end{aligned} \\&\begin{aligned} \text { Let } \bar{{\varvec{{x}}}}=({\varvec{{d}}}_{j1}+ {\varvec{{R}}}{\varvec{{d}}}_{j2}-{\varvec{{e}}}||-{\varvec{{R}}}_2bin({\varvec{{w}}}_j)||-(\varvec{\tau _{j1}^\prime }+{\varvec{{R}}}_1\varvec{\tau _{j2}^\prime })). \end{aligned} \end{aligned}$$

Therefore, $\bar{{\varvec{{A}}}}\bar{{\varvec{{x}}}}=0 \mod q \text { and } \Vert \bar{{\varvec{{x}}}}\Vert \le (m+1)\beta \sqrt{3m}$. Thus $\mathcal {B}$ found the short vector $\bar{{\varvec{{x}}}}$ for the matrix $\bar{{\varvec{{A}}}}$ solving a SIS instance.

5.2 Frameability

In Frameability attack, $\mathcal {A}$ has access to $Get_{gmsk},$ $Q_{user}, Get_{reg}, Get_{usk}, G_{sign}$ oracles. In the end $\mathcal {A}$ has to generate a signature that is opened to an honest non-revoked user and the signatures should not be queried earlier using $G_{sign}$ query. This is explained clearly in the experiment, $Exp_{\mathcal {A}}^{non{\text {-}}frame}(\lambda )$.

A scheme is secure against frameablility if the advantage of $\mathcal {A}$, $Adv^{non{\text {-}}frame}_{ \mathcal {A} }(\lambda ):=Pr[Exp_{\mathcal {A}}^{non{\text {-}}frame}(\lambda )=1]$ is negligible. The security of the proposed scheme against this attack is proved below.

Proof

Similar to previous proof, assume there is an adversary $\mathcal {A}$ who achieves framing attack on our scheme with a non negligible $\epsilon$ probability. Then, we construct an algorithm $\mathcal {B}$ that solves SIS instance for matrix $\bar{{\varvec{{A}}}} \in \mathbb {Z}_q^{4n \times 4m}$ with non-negligible probability. $\square$

KeyGen: $\mathcal {B}$ runs KeyGen algorithm similar to Sect. 4.1 to get (gpk, gmsk, oask) with one modification. Instead of uniformly choosing ${\varvec{{F}}} \in \mathbb {Z}_q^{4n \times 4m}$, we assign ${\varvec{{F}}}=\bar{{\varvec{{A}}}}$.

Queries: In this section we explain how $\mathcal {B}$ answers to $\mathcal {A}$’s queries.

• $Get_{gmsk}:$ return gmsk to $\mathcal {A}$.

• $Q_{user}:$ $\mathcal {A}$ after corrupting the group manager involves in join protocol with a honest user i . For each query, $\mathcal {B}$ plays the role of honest user in join protocol. After successful join i is kept in Hu set.

• $G_{sign}:$ Abort if $i=i^*$ or $i \in C_u$, otherwise recall $(gsk_i,\tau _i,cert_i)$ and generate signature using Sign algorithm. Add $(m, \varSigma ,t_s)$ to Sigs, where $t_s$ is current time.

• $Get_{reg}:$On input index i, $\mathcal {B}$ looks for i in transcripts database and returns $(grt_i,\tau _i)$.

• $Get_{usk}:$ On input index i, $\mathcal {B}$ looks for i in transcripts database and returns $(gsk_i,cert_i)$. Further, i is kept in $C_u$ set.

Forgery: $\mathcal {A}$ outputs a forgery $({\varvec{{m}}}^*, \varSigma ^*, t_s^*, RL^*, i^*)$ such that $\text {Verify}(gpk, {\varvec{{m}}}^*, \varSigma ^*,t_s^*, RL^*)=1$ and $\text {Open}(gpk, oask,{\varvec{{m}}}^*, \varSigma ^*)=i^*$. $\mathcal {A}$ has to frame user $i^*$, even though $i^*$ did not sign $\varSigma ^*$. If $i^* \in C_u$ abort, otherwise parse $\varSigma ^*=({\varvec{{c}}}_{{\varvec{{v}}}_i}^*,\varPi ^*,t_s^*,\tau _{i^*},{\varvec{{b}}}_{grt}^*,{\varvec{{y}}}_1^*)$.

Since we are assuming $\mathcal {A}$ succeeds in framing experiment, the Open algorithm (Sect. 4.6) with input ${\varvec{{m}}}^*, \varSigma ^*$ must decrypts and obtain the vector ${\varvec{{v}}}_{i^*}$. Also, recall $\mathcal {B}$ has fixed ${\varvec{{F}}}{\varvec{{z}}}_{i^*}={\varvec{{v}}}_{i^*}$ when answering $Q_{user}$ on behalf of $i^*$.

Because of the similar argument given in the Forgery part of Traceability proof (Sect. 5.1), by running witness extraction procedure $\mathcal {A}$ can extract the witness ${\varvec{{z}}}^\prime \in \mathbb {Z}^{4m}$ such that ${\varvec{{v}}}_{i^*}={\varvec{{F}}}{\varvec{{z}}}^\prime$. Because of statistical witness indistinguishability property of stern extension protocol, ${\varvec{{z}}}^\prime \ne {\varvec{{z}}}_{j^*}$ with overwhelming probability. Let $\bar{{\varvec{{x}}}}={\varvec{{z}}}^\prime -{\varvec{{z}}}_{j^*}$, and $\Vert \bar{{\varvec{{x}}}}\Vert \le 2\beta \sqrt{m}=\beta _1$ is a short vector. Hence $\mathcal {B}$ solves a SIS instance ${\varvec{{F}}} \bar{{\varvec{{x}}}}=0 \mod q$.

5.3 Selfless-anonymity

In selfless-anonymity, $\mathcal {A}$ works in two phases: play and guess. In the first phase, $\mathcal {A}$ has access to $Add_{user}, Get_{usk}, G_{sign}, Revoke$ oracles. At the end of this phase, $\mathcal {A}$ returns a challenge message ${\varvec{{m}}}^*$ and two different non-revoked identities $(i_0,i_1) \in H_u$, with similar expiration time i.e., $\tau _{i_0} = \tau _{i_1}$. After this $\mathcal {A}$ gets a challenge signature $\varSigma ^*$ on ${\varvec{{m}}}^*$ signed by one of the users, $i_0$ or $i_1$ chosen randomly. In the second stage, $\mathcal {A}$ has to correctly identify the signer of $\varSigma ^*$. This is explained clearly in the experiment $Exp_{\mathcal {A}}^{anon \hbox {-} b}(\lambda )$ shown below.

A scheme is secure against selfless-anonymity if the advantage, $Adv^{anon \hbox {-} b}_{ \mathcal {A} }(\lambda ):=|Pr[Exp_{\mathcal {A}}^{anon \hbox {-} }(\lambda )=1] -\frac{1}{2}|$ is negligible for $\mathcal {A}$. The security of the proposed scheme against this attack is proved below.

Proof

A series of games are defined to prove the security against selfless anonymity. Each game is similar to the previous game with few modifications except the first game. $\square$

$G^{(b)}$: This game is identical to the original anonymity game. By running KeyGen algorithm $\mathcal {B}$ generates generates (gpk, gmsk, oask) and and replies to polynomial number of queries from $\mathcal {A}$. Later $\mathcal {A}$ gets challenge signature $\varSigma ^*=({\varvec{{c}}}_{{\varvec{{v}}}_i}^*,\varPi ^*,t_s^*,\tau _{i^*},{\varvec{{b}}}_{grt}^*,{\varvec{{y}}}_1^*)$ on challenge message ${\varvec{{m}}}^*$ in the play stage.

$G_1^{(b)}$: $\mathcal {B}$ programs the random oracle $H_0$ in the following way. At the start of the game, $\mathcal {B}$ chooses a matrix ${\varvec{{G}}}^*$ uniformly over $\mathbb {Z}_q^{n \times 2m}$ and set $H_0(y^*) = {\varvec{{G}}}^*$. From $\mathcal {A}$ view, the distribution of ${\varvec{{G}}}^*$ is statistically close to the one in the real attack game as in [13]. To answer opening queries for any signature $\varSigma$ with ${\varvec{{y}}}_1$, $\mathcal {B}$ samples a small norm matrix ${\varvec{{E}}}_{0,{\varvec{{y}}}_1} \hookleftarrow D_{\mathbb {Z}^{m}, \sigma }^{2m}$ and programs the oracle such that, $H_0({\varvec{{y}}}_1) = {\varvec{{B}}} {\varvec{{E}}}_{0, {\varvec{{y}}}_1} \mod q$. $\mathcal {B}$ keeps track of $({\varvec{{y}}}_1 ,{\varvec{{G}}}^*, {\varvec{{E}}}_{0, {\varvec{{y}}}_1})$ to be reused, if $\mathcal {A}$ request the same query for $H_0({\varvec{{y}}}_1)$. The $\mathcal {A}$ view remains the same as $G_1^{(b)}$, analogous to the security proof of the Dual-Regev Encryption scheme [13].

$G_2^{(b)}$: In this game, $\mathcal {B}$ changes the way of handling opening queries. At the beginning of the game it chooses a matrix ${\varvec{{B}}}^* \in \mathbb {Z}_q^{n \times m}$, which is used later in place of ${\varvec{{B}}}$. To answer opening queries for signature $\varSigma$ with ${\varvec{{y}}}_1$, $\mathcal {B}$ recalls the small-norm matrices ${\varvec{{E}}}_{0, {\varvec{{y}}}_1}$ which were defined when $\mathcal {A}$ first queried for $\mathcal {H}_0({\varvec{{y}}}_1)$. Now matrices ${\varvec{{B}}}^*, {\varvec{{E}}}_{0, OVK}$ are used to answer opening queries corresponding to $\varSigma$ with ${\varvec{{y}}}_1$. The distribution of ${\varvec{{G}}}_0 = \mathcal {H}_0({\varvec{{y}}}_1)$ is statistically close to the uniform. Therefore this game is statistically indistinguishable from $G_2^{(b)}$.

Table 2 Comparison of lattice based group signature schemes

$G_3^{(b)}$: In this game, the NIZK protocol $\varPi$ is replaced by a simulator output denoted Simul. Hence, the transcripts of $\varPi$, is obtained by simulator output Simul. Because of statistical zero knowledge property of $\varPi$, the transcripts of $\varPi$ and Simul are statistically indistinguishable. As a result, the $\varSigma ^*$ generated in this game and $\varSigma ^*$ of $G_2^{(b)}$ are computationally indistinguishable.

$G_4^{(b)}$: In original game revocation token is computed as $b_{grt} = {\varvec{{A}}}^\prime grt_i+{\varvec{{e}}}_1$, instead it is computed as $b_{grt} = {\varvec{{A}}}^\prime {\varvec{{s}}}+{\varvec{{e}}}_1$ in this game, where ${\varvec{{s}}}$ is uniformly chosen over $\mathbb {Z}_q^{n}$. The challenge cipher text ${\varvec{{c}}}_{{\varvec{{v}}}_i}^*$ is generated as $({\varvec{{c}}}_1^*, {\varvec{{c}}}_2^*) = ({\varvec{{r}}}_1, {\varvec{{r}}}_2 + bin({\varvec{{v}}}_{i_b})\frac{q}{2})$, where vectors ${\varvec{{r}}}_1, {\varvec{{r}}}_2$ are uniformly chosen over $\mathbb {Z}_q^{m}, \mathbb {Z}_q^{2m}$ respectively. $\varSigma ^*$ generated in this game is computationally indistinguishable to $\varSigma ^*$ in $G_3^{(b)}$ because of ([13], Lemma 2.10) and hardness of decision version of LWE.

$G_5$: In this game, further changes are made to generation of revocation token commitment $b_{grt}$ and ciphertext ${\varvec{{c}}}_{{\varvec{{v}}}_i}^*$. In this game, $b_{grt}$ is uniformly chosen over $\mathbb {Z}_q^{m}$. Ciphertext, $({\varvec{{c}}}_1^*, {\varvec{{c}}}_2^*) = ({\varvec{{r}}}_3, {\varvec{{r}}}_4)$, where ${\varvec{{r}}}_3, {\varvec{{r}}}_4$ are chosen uniformly from $\mathbb {Z}_q^{m}, \mathbb {Z}_q^{2m}$ respectively.

The challenge signature $\varSigma ^*$ generated in the game $G_5$ is independent of both the identities $i_0 \text { and } i_1$. And the $\varSigma ^*$ in the game $G^{(b)}$ is computationally indistinguishable with $\varSigma ^*$ generated in the game $G_5$. Hence, the advantage of $\mathcal {A}$ is negligible.

6 Results comparison

A detailed comparison of the proposed scheme with existing lattice based GSS is shown in Table 2. Here, $r_{pre}$ denotes RL size in the proposed scheme and in [1]. And r denotes RL size in existing VLR based GSS. We know, $r_{pre}<< r$ especially when natural revocation accounts for a significant fraction of total revocation.

The proposed scheme has the following advantages over the existing group signature schemes built using lattices and VLR.

• The signature verification cost of our scheme is efficient because of the natural revocation.

• The cost of opening algorithm is constant in our scheme because of explicit tracing, where as it is proportional to group size in [1, 12, 16, 28].

• Our scheme can be used to build very large groups, since revocation mechanism is simple and very efficient compared to the existing schemes.

7 Conclusion

In this paper, we proposed a lattice based dynamic group signature scheme with VLR and time bound keys. In the proposed scheme, an expiry time is fixed for every group member’s signing key. Because of this, a group member with an expired signing key cannot produce a valid signature, and he is naturally revoked. This greatly decreases the revocation list size, which makes verification process significantly efficient in terms of cost. The security of the proposed scheme is proved based on the hardness assumptions of LWE and SIS in the random oracle model. Inclusion of additional features like backward unlinkability, selective unlinkability or message dependent opening are the future works.