Open AccessArticle

Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation^†

Maharage Nisansala Sevwandi Perera

^1,* and

Takeshi Koshiba

Adaptive Communications Research Laboratories, Advanced Telecommunications Research Institute International (ATR), Kyoto 619-0288, Japan

Faculty of Education and Integrated Arts and Sciences, Waseda University, Tokyo 169-8050, Japan

Author to whom correspondence should be addressed.

^†

The paper is an extended version of our paper published in AINA2017. The preliminary version of this work was appeared in the 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA). This paper extends the contribution in AINA2017 with some fixes which were not captured in AINA2017 paper.

Cryptography 2020, 4(4), 33; https://doi.org/10.3390/cryptography4040033

Submission received: 29 October 2020 / Accepted: 25 November 2020 / Published: 30 November 2020

(This article belongs to the Section Cryptography Reviews)

Download

Browse Figure

Versions Notes

Abstract

An efficient member revocation mechanism is a desirable feature when group signature schemes are applied in practical scenarios. Revocation methods, such as verifier-local revocation (VLR), provide an efficient member revocation in applications of group signatures. However, VLR-group signatures rely on a weaker security notion. On the other hand, group signature schemes for static groups gain stronger security with the full-anonymity security notion. Even though an outsider sees the secret signing keys of all group members in the full-anonymity, the signer is still anonymous. Achieving the full-anonymity for VLR group signature schemes is challenging due to the structure of secret signing keys. The secret signing keys of those schemes consist of tokens, which are used to manage revocation. The reveal of tokens may destroy the anonymity of the signers. We obtain stronger security for the lattice-based VLR group signature schemes by providing a new key generation method, which outputs revocation tokens without deriving from the members’ secret signing keys. We propose a new group signature scheme from lattices with VLR, which achieves stronger security than the previous related works. To avoid signature forgeries, we suggest a new zero-knowledge proof system that requires signers to validate themselves. Moreover, we output an efficient tracing mechanism.

Keywords:

lattice-based group signatures; verifier-local revocation; almost-full anonymity; traceability; zero-knowledge proof

1. Introduction

Group signatures, first proposed by Chaum and van Heyst [1], permit members of a group to issue signatures in the name of the group while hiding their information (anonymity). In spite of the group manager, he/she can cancel the anonymity of the signatures and identify the owner of the signature (traceability). In other words, in group signature schemes, the signature receivers can only validate the signatures, he/she cannot identify the signers. Still, in the case of dispute, an authorized person (the group manager) can recognize the signer. Thus, the signer should be anonymous to the receivers (outsiders) and traceable to the authorities (the group manager). These two features (anonymity and traceability) make group signature schemes attractive to many real-life applications, namely, key-card access systems, digital right management, and anonymous printing.

After the group signatures were proposed, many proposals were presented with several improvements and security. For instance, Chen and Pedersen [2] and Ateniese and Tsudik [3] delivered new features such as coalition resistance, exculpability, and framing resistance. Then, Ateniese et al. [4] proposed a provably secure scheme in the random oracle model to overcome the weaknesses of the previous works. Later, Bellare et al. [5] formulated a stronger security model, namely, the BMW03 model, with two security requirements—full anonymity and full traceability, which implies the existing security properties. Even though the BMW03 model is known as the most reliable security model at present, it serves only static groups. By adopting the BMW03 model, several group signatures have been proposed, but constructing a scheme with an efficient member revocation and high-level security is a challenge.

1.1. Member Revocation Approaches

In the real world, almost all group settings are stateless. Member revocation is one of the principal features of a group. Both dismissed and retired members should be restricted from generating signatures on behalf of the group in the future. One naive approach for member revocation is replacing all the keys newly except for the revoking member when he/she is revoked. Thus, any revoked member cannot produce a valid signature because he does not know the new keys. As the re-key generation approach requires the distribution of newly generated keys to all the members, verifiers, and authorities, it is not suitable for groups with large number of members. Bresson and Stern [6] proposed a method which needs signers to show that the public revocation list does not hold his member certificate when signing. Camenisch et al. [7] suggested a revocation method using dynamic accumulators. While the accumulator hashes a broad set of inputs to one shorter value, dynamic accumulators allow the insertion and deletion of inputs dynamically. The technique proposed by Camenisch et al. [7] needs existing members to store revoked user data and to update their membership for each time that a member is revoked. Thus, the proposed method is a burden for existing group members.

Brickell [8] suggested a different revocation approach, titled verifier-local revocation (VLR). Afterwards, Boneh et al. [9] formalized VLR in their group signature scheme. In the VLR mechanism, every member has a revocation token, which identifies his/her status. Thus, the token of a member indicates whether he/she is revoked or not. When a user’s membership is canceled, the revoking user’s token is included on a list called revocation list (RL) and the latest revocation list is sent to the verifiers. The verifiers can use RL to authenticate the signer at the signature verification, i.e., whether the signer is an active member or not. As, in general, the number of verifiers in a group system is lower than the number of group members, the VLR mechanism is appropriate for large groups than other revocation approaches. Due to these possibilities, at the moment, VLR seems to be the most flexible revocation method.

In general, group signature schemes contain KeyGen, Sign, Verify, and Open. On the other hand, any VLR group signature scheme contains only the first three algorithms because instead of Open it has implicit tracing algorithm for tracing signers. The implicit tracing algorithm executes Verify for each user until it returns invalid. Then, the implicit tracing algorithm returns the index of the first user for which Verify returned invalid as the signer of the signature.

Early VLR group signature schemes were constructed on the bilinear mappings. Bilinear mappings are insecure in font of quantum computers. One of the prominent solutions for quantum attacks is lattice-based cryptography. Langlois et al. [10] proposed the first VLR group signature scheme from lattice assumptions.

1.2. Group Signature Schemes from Lattice Assumptions

Cryptography based on lattice assumptions has strong security proofs in reliance on the worst-case hardness of the lattice problems. Thus, lattice cryptography seems to be an outstanding solution against quantum computers. Moreover, the efficient implementation of lattice-based cryptography attracted researches more.

Gordon et al. [11] proposed the first group signature scheme from lattice assumptions. A noticeable disadvantage of this scheme is the linear barrier, i.e., the size of the group signature increases with the number of user N in a group. Thus, the size of the signatures given in the scheme in [11] is

O (N)

. Then, in 2012, Camenisch et al. [12] gave a more secure and efficient scheme with an anonymous attribute token system. However, Camenisch et al.’s scheme [12] also failed to provide a solution for the issue of linear barrier. Finally, Languillaumie et al. [13] resolved the linear barrier issue in their scheme. Thus, the sizes of keys and the signatures are proportional to

log N

in their scheme.

However, the above-mentioned three-group signature schemes from lattices support only static groups. Later, Langlois et al. [10] suggested the first member revocable group signature scheme from lattice assumptions. The scheme in [10] employed Verifier-local Revocation (VLR) as the revocation mechanism. Moreover, their scheme has several advantages over previously proposed works. For instance, the scheme given in [10] is simple, as the signature of the scheme is an all-in-one proof of knowledge. Further, the scheme [10] has shorter signatures and group public keys comparing to previous schemes. Even though the scheme in [10] has several remarkable advantages over the previous works, the security of the scheme is weaker as the scheme satisfies a relaxed security notion called selfless-anonymity. Moreover, like any other VLR group signature scheme, Langlois’s scheme employs the implicit tracing algorithms for tracing signers. The implicit tracing algorithm requires running Verify until the algorithm returns invalid. Thus, tracing a signer in a large group using the implicit tracing mechanism is not efficient.

Most of the schemes proposed after 2003 use the BMW03 model, which is known as the reliable security model at present. Among those schemes, the lattice-based group signature scheme suggested by Ling et al. [14] showed outstanding features. For instance, the size of the public key and the signature of the scheme are relatively shorter. Moreover, the scheme itself simpler because the construction of the scheme is based on Boyen’s signature scheme [15]. Boyen’s signature scheme has a simple construction. In addition to these advantages, the scheme in [14] has a ring variant. However, as the scheme in [14] does not support member registration or member revocation, it is suitable only for static groups.

Later, Nguyen et al. [16] also proposed a simpler group signature scheme for static groups. In their proposal, the security is reduced to the hardness of Short Integer Solution (SIS) and Learning With Errors (LWE) in the random oracle model.

Libert et al. [17] formed a group signature scheme based on lattice assumptions which facilitates member registration. Again, Ling et al. [18] delivered the first fully dynamic group signature scheme from lattices which supports both new user registration and revocation. They used accumulators to manage the member status. However, employing accumulators appears to be less efficient than employing VLR for member withdrawal in large groups. On the other hand, VLR group signatures like that in [10] failed to achieve stronger security described in the BMW03 model. Ishida et al. [19] presented an encryption mechanism to achieve full anonymity for VLR group signature schemes based on general assumptions. On the other hand, Perera et al. [20] proposed a new, stronger security notion for VLR group signature schemes.

The scheme in [20], which was constructed based on general assumptions, provides member revocation with VLR and satisfies stronger security than the security offered in the naive VLR group signature schemes. The scheme given in [20] suggested a security notion, almost-full anonymity. The almost-full anonymity is a controlled version of the full anonymity. In the anonymity game of almost-full anonymity, the adversary gets all the user secret signing keys, as in the full-anonymity game, and it allows revocation query as an additional feature. However, it prevents the adversary from accessing revocation tokens related to the challenging indices and generating the challenging signature for the indices, which are used in the revocation queries. In their scheme, they generated revocation tokens without depending on the secret signing keys of the members. In the VLR group signature scheme given in [10], revocation tokens are part of the particular secret signing keys. As the adversary gets all the users’ secret keys at the anonymity game of the almost-full anonymity, the adversary can create revocation tokens using the information he/she has. VLR schemes become insecure when revocation tokens are generated using secret signing keys and providing the secret keys to the adversary (as in full anonymity). Thus, they [20] delivered a different method to produce revocation tokens, which is independent of the secret signing keys. Later, employing the almost-full anonymity notion, several schemes [21,22,23] were proposed with different aspects. Among them, the scheme in [21] extended the almost-full anonymity notion to a new security notion to operate in fully dynamic group signature schemes with member registration and VLR. However, the scheme in [20] and its application schemes did not provide a concrete solution to secure schemes from forgery members, who replace real revocation token with a random value.

While the schemes mentioned above focused on achieving stronger security for VLR group signature schemes, the schemes provided in [24,25] tried to gain efficient revocation check at signature validation. The size of the revocation list increases dramatically when VLR schemes apply in systems where the members are joining for a short period. Long revocation lists increase the cost of authenticating the signer at the signature verification. To reduce the cost of verifying the signer, Chu et al. [24] proposed time-bound keys. Later, Perera et al. [25] employed Chu’s proposal and presented a VLR group signature scheme with stronger security.

1.3. Our Contribution

In this paper, we present a VLR group signature scheme from lattices with stronger security. We select the almost-full anonymity suggested in [20] to secure our scheme, as it achieves stronger security than the naive VLR group signature schemes with separate token generation. The scheme given in [20] is based on general assumptions. We use modified Boyen’s signature [15] given in [14] to generate revocation token in our lattice-based group signature scheme. Moreover, we use an extra public key parameter for making revocation tokens of the users.

As the tokens are independent of the secret signing keys in the proposing scheme, there is a risk that the revoked users are generating valid signatures with arbitrary tokens. As a solution for this weakness, we present a new zero-knowledge proof system by modifying the existing zero-knowledge proof system given in [26]. Thus, the proposed scheme employs the new protocol to convince the verifiers that the signer is indeed a valid group member with a real and active token.

The implicit tracing algorithm given in VLR group signature schemes is not suitable for large groups because the time consumption is high in tracing a signer. Thus, we use the explicit tracing algorithm in our scheme to identify any signer. Accordingly, we use the group manager’s secret key to find the signers instead of executing Verify a linear time in the number of users as in previous VLR group signature schemes with the implicit tracing algorithm. As the explicit-tracing algorithm helps to capture any signer only decrypting the signature, this can be used for any large groups.

As a result, we propose a group signature scheme from lattice assumptions, which is almost fully secured; supports member revocation and tracing signers efficiently, which provides a new method to generate revocation tokens; and is suitable even for a large group. Moreover, using the proposed zero-knowledge protocol, we secure our scheme from forgery signers.

1.4. Road Map

In Section 2, we provide the preliminaries, and in Section 3, we discuss some of the existing security notions, the difficulty of adapting the BMW03 model to cope with revocation queries, and recall the security notion, almost-full anonymity. In Section 4, we provide a new zero-knowledge interactive protocol which supports the proposing scheme. In Section 5, we provide our VLR group signature scheme from lattices, including a different method for generation of revocation tokens, explicit tracing algorithm, and underlying interactive argument system. The proof of the correctness and the security of the scheme is discussed in Section 6. In Section 7, we conclude the paper and present open problems.

2. Preliminaries

2.1. Notations

We express the set of integers

{1, \dots, i}

for any integer

i \geq 1

[i]

. We declare matrices by bold upper-case letters, vectors by bold lower-case letters, and we work with only column vectors. The concatenation of matrices

A \in R^{n \times m}

and

B \in R^{n \times k}

is expressed by

[A | B] \in R^{n \times (m + k)}

. The concatenation of vectors

x \in R^{m}

and

y \in R^{k}

is represented by

(x ∥ y) \in R^{m + k}

. If D is a finite set,

a \overset{$}{\leftarrow} D

presents that a is selected uniformly at random from D. If D is a probability distribution,

a \overset{$}{\leftarrow} D

indicates that a is drawn according to D.

The security parameter of our scheme is n and the maximum number of expected group users is

N = 2^{ℓ}

. We express the binary representation of each user’s index by a string as

d \in {0, 1}^{ℓ}

. Based on n, we fix the other parameters as below.

Modulus q = $ω (n^{2} log n) .$
Dimension m $\geq 2 n log q$ .
Gaussian parameter $σ$ = $ω (\sqrt{n log q log n})$ .
Integer norm bound $β$ = $⌈ σ \cdot log m ⌉$ s.t ${(4 β + 1)}^{2} \leq q$ .
Number of decomposition p = $⌊ log β ⌋$ + 1.
Sequence of integers: $β_{1} = ⌈ β / 2 ⌉; β_{2} = ⌈ (β - β_{1}) / 2 ⌉$ ; $β_{3} = ⌈ (β - β_{1} - β_{2}) / 2 ⌉; \dots; β_{p} = 1$ .
Number of protocol repetitions t = $ω (log n)$ .

Let

k_{1} : = m + ℓ

and

k_{2} : = n + m + ℓ

. Let

χ

be a b-bounded distribution over

Z

. The norm bound for LWE noises is integer b such that

q / b = ℓ \tilde{O} (n)

Let

H_{1}

{0, 1}^{*} \to Z_{q}^{n \times ℓ}

H_{2}

{0, 1}^{*} \to {1, 2, 3}^{t}

, and

G

{0, 1}^{*} \to Z_{q}^{n \times m}

are hash functions, modeled as random oracles.

2.2. Lattices

For integers

r, m,

prime

q \geq 2

B = [b_{1} | \dots | b_{m}] \in Z_{q}^{r \times m}

, and

z \in Z^{r}

, the lattice

Λ (B)

for

B

is declared as

Λ (B) = {z \equiv B x mod q for some x \in Z_{q}^{m}},

where r is the dimension of the lattice

Λ (B)

Gaussian distribution for a lattice: For a vector

c

and a parameter

s > 0

, the discrete Gaussian distribution

ρ_{s, c} (x) = e^{{- π ∥ (x - c) / s ∥}^{2}}

. The respective probability density function proportional to

ρ_{s, c}

D_{s, c} (x) = ρ_{s, c} (x) / s^{n}

for all

x \in R^{n}

. The discrete Gaussian distribution with respect to a lattice

Λ

D_{Λ, s, c} (x) = D_{s, c} (x) / D_{s, c} (Λ) = ρ_{s, c} (x) / ρ_{s, c} (Λ)

for all

x \in Λ

. As

Z^{m}

is also a lattice, we can declare a discrete Gaussian distribution for

Z^{m}

. By

D_{Z^{m}, σ}

, the discrete Gaussian distribution for

Z^{m}

around the origin with the standard deviation

σ

is expressed.

2.3. Lattice Hardness Assumptions

Here, we describe the hardness of computational problems of lattices that we use in our scheme. First, we define SIVP problem. Then, we outline the two main average-case problems—LWE and SIS—and the hardness of them. We prove our scheme’s security based on their hardness.

2.3.1. Approximate Shortest Independent Vectors Problem ( $S I V P_{γ}$ )

In general, finding a good basis for a given lattice is called the basis reduction problem and SIVP is one of basis reduction problems.

Definition 1

(Approximate Shortest Independent Vectors Problem -

S I V P_{γ}

[27]). Given a basis B of an n-dimensional lattice

L = L (B)

, finding linearly independent vectors

s_{1}, \dots, s_{n}

S I V P_{γ}

problem, where

∥ s_{i} ∥ \leq γ (n) \cdot λ_{n} (L)

for all i (

λ_{n} (L)

is n-th successive minimum).

2.3.2. Learning With Errors (LWE)

Regev [28] introduced LWE problem, which is a lattice problem that is hard to solve. His work results in a reduction from worst-case lattice problems to a certain learning problem.

Definition 2

(Learning With Errors Problem -

{LWE}_{n, q, χ}

[27]). For integers

n, m \geq 1, q \geq 2

s \in Z_{q}^{n}

, and χ, the distribution

B_{s, χ}

is achieved by sampling uniformly random

b \in Z_{q}^{n}

and

e \leftarrow χ

, and returning the pair (

b, b^{T} \cdot s + e

Search-LWE and Decision-LWE are the two versions of LWE problems. While Search-LWE is for finding the secret s, Decision-LWE id for distinguishing LWE samples and samples chosen according to the uniform distribution. For our scheme we employ Decision-LWE problem.

For

β \geq \sqrt{n} ω (log n)

, a prime power q, and distribution

χ

, solving

L W E_{n, q, χ}

problem is at least as hard as solving

S I V P_{γ}

, where

γ = \tilde{O} (n q / β)

[28,29].

2.3.3. Short Integer Solution ( $S I S_{n, m, q, β}$ )

Ajtai [30] introduced SIS in a seminal work. SIS has served in many applications as identification schemes, one-way hash functions, and digital signatures.

Definition 3

(Short Integer Solution Problem -

{SIS}_{n, m, q, β}

[27,28]). Given m uniformly random vectors

b_{i} \in Z_{q}^{n}

, the columns of a matrix

B \in Z_{q}^{n \times m}

, SIS requires to find a nonzero vector

x \in Λ^{⊥} (B)

which forms

∥ x ∥ \leq β

and

Bx = 0 mod q

SIS problem is for homogeneous systems. Later, Gentry et al. [29] formalized its inhomogeneous version ISIS problem.

Definition 4

(Inhomogeneous Short Integer Solution Problem (

{ISIS}_{n, m, q, β}

) [29]). Given matrix

B \in Z_{q}^{n \times m}

with m uniformly random vectors

a_{i} \in Z_{q}^{n}

and a uniformly random vector

y \in Z_{q}^{n}

{ISIS}_{n, m, q, β}

requires to determine a nonzero vector

x \in Λ_{u}^{⊥} (B)

satisfying

∥ x ∥ \leq β

and

B \cdot x = y mod q

For any m,

β

, and for any

q \geq β \cdot ω (\sqrt{n log n})

, solving

S I S_{n, m, q, β}

and

I S I S_{n, m, q, β}

problems with non-negligible probability is at least as hard as resolving

S I V P_{γ}

challenge, for some

γ = β \cdot \tilde{O} (\sqrt{n})

[29].

2.4. Lattice-Related Trapdoors

For our construction, we require a family of functions such that each function capable of computing with any input but not feasible to invert the given input. Such a family of functions is called one-way functions. Trapdoor functions are one-way functions with secret information (trapdoor). Without this secret information, finding the inverse of the function is hard. We use trapdoor functions in our constructions as no one can identify the inverse of the function without the trapdoor.

We employ SampleD, which is a randomized nearest-plane algorithm discussed in [29,31].

SampleD( $T_{A}$ , A, u, $σ$ ): For any vector u in the image of A, a trapdoor $T_{A}$ , and $σ = ω (\sqrt{n log q log n})$ SampleD samples $x \in Z^{m}$ from the distribution $D_{Z^{m}, σ}$ , such that $A \cdot x = u mod q$ .

The notion of preimage sampleable trapdoor functions (PSTFs) was discussed in [29]. PSTFs are defined by probabilistic polynomial-time algorithms. There are several constructions of PSTFs. We use GenTrap, SamplePre, and ExtBasis given in [13,31,32,33].

GenTrap(n, m, q): For inputs integers $n \geq 1, q \geq 2$ , and $m \geq 2 n log q$ the efficient randomized algorithm GenTrap returns a matrix $A \in Z_{q}^{n \times m}$ and a trapdoor $T_{A}$ . The distribution of A is negl(n)-far from the uniform distribution.
SamplePre(A, $T_{A}$ , u, $σ$ ): For a matrix $A \in Z_{q}^{n \times m}$ , a trapdoor basis $T_{A}$ , a target image $u \in Z_{q}^{n}$ , and the standard deviation $σ = ω (\sqrt{n log q log n})$ , SamplePre samples $e \in Z^{m}$ from a distribution. e is within negligible statistical distance of $D_{Λ \frac{u}{q} (A), σ}$ .
ExtBasis( $T_{A}, B$ ): ExtBasis gets a matrix $B \in Z^{n \times m^{'}}$ and a arbitrary $T_{A}$ of $Λ_{q}^{⊥} (A)$ as inputs, where A is the top $n \times m$ submatrix of B, and returns a basis $T_{B}$ of $Λ_{q}^{⊥} (B)$ with $∥ \tilde{T_{B}} ∥ \leq ∥ \tilde{T_{A}} ∥$ .

Moreover, for the construction of the underlying argument system discussed in Section 5, we employ two techniques: witness decomposition and extension (WitnessDE) and matrix extension (MatrixExt) detailed in [10].

WitnessDE results p vectors $z_{1}, \dots, z_{p} \in SecretExt (d)$ for some $d = d [1] \cdot \cdot \cdot d [ℓ] \in {0, 1}^{ℓ}$ on input x, where x is the witness of the prover d and $d [i]$ is the i-th bit of the binary representation of d.
$SecretExt (d)$ is a set of all vectors $x = (x_{0} ∥ x_{1}^{0} ∥ x_{1}^{1} ∥ \dots ∥ x_{ℓ}^{0} ∥ x_{ℓ}^{1}) \in Σ^{(2 ℓ + 1) 3 m}$ with $2 ℓ + 1$ blocks of size m, where $ℓ + 1$ blocks $x_{0}, x_{1}^{d [1]}, \dots, x_{ℓ}^{d [ℓ]}$ are elements of ${- 1, 0, 1}^{3 m}$ , and remaining blocks are zero-blocks $0^{3 m}$ .
MatrixExt results an extended matrix $A^{*} \in Z_{q}^{n \times (2 ℓ + 1) 3 m}$ on input matrix $A \in Z_{q}^{n \times (2 ℓ + 1) m}$ , where $A^{*}$ is produced by attaching 2m zero-columns to each of the A’s component-matrices.

2.5. VLR Group Signatures

VLR group signatures are for dynamic groups. When a member is revoked, VLR group signatures require distributing the revocation list only to the verifiers. In this section, first, we provide algorithms of group signature schemes for static groups. Then, we present the algorithms of VLR group signature schemes.

Algorithms of the group signature schemes for static settings are as below.

KeyGen(n,N): This randomized PPT algorithm returns a group public key gpk, a group manager secret key gmsk, and group members’ secret keys gsks.
Sign(gpk, gsk[d], M): On input gpk, gsk[d], and a message M, this randomized algorithm returns a signature $Σ$ .
Verify(gpk, M, $Σ$ ): This deterministic algorithm confirms that the received $Σ$ is valid on M.
Open(gmsk, M, $Σ$ ): For given gmsk, M, and $Σ$ Open returns the index of the signer. If Open cannot find the signer, then it returns the failure.

VLR group signature schemes consist of three PPT algorithms [9]. It does not have an Open algorithm as it uses the implicit tracing algorithm to identify the corrupted users.

KeyGen(n,N): On inputs n and N KeyGen outputs gpk, a set of user secret signing keys gsk, and a set of user revocation tokens grt.
Sign(gpk, gsk[d], M): On inputs gpk, gsk[d], and a message M, this randomized algorithm returns a signature $Σ$ .
Verify(gpk, RL, M, $Σ$ ): On inputs gpk, RL, $Σ$ , and M, this algorithm confirms that the $Σ$ is generated on M and signer’s token is not in RL.

Implicit tracing algorithm employs grt as the tracing key. For a given valid (M,

Σ

) pair, authority, that knows all the tracing keys grt, can execute Verify(gpk, RL = grt[i], M,

Σ

) for all users until Verify outputs

I n v a l i d

. The first index that Verify returns

I n v a l i d

is the index of the signer. The implicit tracing algorithm fails if it returns Valid for all the members for the input signature. In the implicit tracing algorithm to detect a single user the group manager has to check almost all users until he/she finds the signer. The time consumption of the implicit tracing algorithm is high. Thus, it is not suitable for large groups.

2.6. Some Other Techniques

The underlying argument system given in Section 5 enables the signer to convince the verifier the validity of the signer, he is not being revoked, and his/her token is true.

We build our scheme based on the construction of Langloi’s scheme [10]. Therefore, our scheme is based on a matrix A = [

A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}

]

\in Z_{q}^{n \times (2 ℓ + 1) m}

and a vector u

\in Z_{q}^{n}

. Each member has a revocation token to confirm their validity to sign on messages. On the other hand, the Revocation List, which is denoted by RL, contains all the revocation tokens of the revoked users. Thus, checking RL the verifiers can validate the signer.

One-time signature scheme

OTS

= (OGen, OSign, OVer): While OGen produces keys,

OSign

generates signature, and OVer allows the verification of the signatures [34]. Thus, OGen creates a signing/verification key pair (osk, ovk) for input

(1^{n})

. On inputs osk and a message M, OSign makes a signature

Σ

. For given ovk, M, and

Σ

, OVer validates

Σ

[35].

OTS

is a one-way function. One-way functions are simpler to implement and are computationally efficient than trapdoor functions. On the other hand,

OTS

schemes are digital signature schemes. Thus it necessary to produce keys for each message. As a result, created keys are unique for the particular messages.

3. Definitions of the Security Notations

First, this section discusses the existing security notions for anonymity. Then, it justifies the difficulties of achieving full-anonymity for VLR schemes with revocation query and defines the almost-full anonymity. Finally, it declares the security notion traceability.

Since Chaum and van Heyst [1] introduced group signatures, more security properties have been considered according to the requirements of different applications of group signature schemes. As a result, we have a large set of security requirements including anonymity, traceability, unlinkability, unforgeability, and collusion resistance whose definitions and relations to each other have not been clearly understood [5].

Simply, anonymity and traceability can be defined as below.

Anonymity: no adversary should be able to determine the index of the signer from its signature, which is produced by one of the indices from two indistinguishable indices.
Traceability: no adversary should be able to produce a fake signature that cannot be traced.

Later, for static group signatures, Bellare et al. [5] formed two security standards: full anonymity and full traceability (the BMW03 model), which implies the existing unformalized requirements. In 2004, for group signatures with VLR, Boneh et al. [9] suggested a relaxed anonymity notions called selfless-anonymity.

3.1. Anonymity

Full anonymity allows the adversary to obtain secret keys of all the users and the verification key. Moreover, he/she can access the opening oracle.
Selfless-anonymity does not provide user secret keys without a request, but allows Signing, Corruption, and Revocation queries.

The selfless-anonymity game between a challenger C and an adversary A is as below.

The adversary is weaker in the selfless-anonymity game than the adversary in full anonymity game because in the selfless-anonymity game the adversary cannot access all the users’ secret signing keys. The adversary has to determine the key which is used to generate the signature in this game.

Initial Phase: The challenger C gets gpk, gsk, and grt from KeyGen algorithm and sends gpk to the adversary A.
Query Phase:A is allowed for the below three queries.
1.
Signing: A queries a signature for any message M and an user index i. Then, C sends back $Σ$ = Sign(gpk, gsk[i], M).
2.
Corruption: A queries the secret signing key of user i, and C gives gsk[i].
3.
Revocation: A asks for the revocation token of user i, and C sends grt[i].
Challenge Phase:A sends a message M and two distinct identities $i_{0}, i_{1}$ , such that A did not make the corruption or revocation queries for $i_{0}, i_{1}$ . Then, C picks a bit b $\overset{$}{\leftarrow}$ {0,1}, produces and returns the signature $Σ^{*}$ = Sign( $gpk, gsk [i_{b}], M$ ).
Restricted Queries:A can do the above queries but with the below conditions.
1.
Signing: A is allowed to query as before.
2.
Corruption: A is not allowed to query for $i_{0}$ or $i_{1}$ .
3.
Revocation: A is not allowed to query for $i_{0}$ or $i_{1}$ .
Guessing Phase:A sends a bit $b^{'}$ as the guess of b. If $b^{'} = b$ , then A wins.

The advantage of A winning the game is

A d v_{A} = | Pr [b^{'} = b] - 1 / 2 |

. We say that any group signature scheme is selfless-anonymous if

A d v_{A}

is negligible.

The first VLR group signature scheme from lattices confines on the selfless-anonymity. Our goal is to present a lattice-based VLR group signature scheme with strong security. A naive adaptation of the full anonymity (BMW03 model) does not go well since it was presented for static groups.

3.2. Coping with Revocation queries for Full Anonymity

Since the full anonymity was originally proposed for static groups, the revocation query is not incorporated in the naive full anonymity game given in the BMW03 model or the other schemes that used the BMW03 model, such as in [14]. Our scheme is for dynamic-groups supporting member revocation. As we wish to make our VLR group signature scheme full-anonymous, we concern a security notion for “full anonymity with revocation query”. On the other hand, we have to deal with the risk of giving revocation tokens to the adversary. Simply adding the revocation query given in the selfless-anonymity to the notion of the full anonymity will make our scheme insecure. The definition of the full anonymity after adding revocation query is as below.

Initial Phase: The challenger C gets gpk, a group manager’s secret key gmsk, and group users’ secret signing keys gsk and revocation tokens grt, and then delivers (gpk, gsk) to the adversary A.
Query Phase:A is allowed to request token (grt) of any user and opening of any signature.
Challenge Phase:A sends a message M and two distinct identities $i_{0}, i_{1}$ . Then, C decides a bit b $\overset{$}{\leftarrow}$ {0,1}, produces and sends back $Σ^{*}$ = $Sign (gpk, gsk [i_{b}], grt [i_{b}], M)$ . The adversary A still is allowed to access opening oracle with any signature except the signature challenged but he/she is not allowed for revocation queries.
Guessing Phase: Finally, A returns a bit $b^{'}$ , the guess of b. If $b^{'} = b$ , then he wins.

Here, if the adversary A calls the challenge phase with the indices whose revocation tokens are already queried, and if we generate the challenging signature without any restrictions, then the adversary A can guess the index that used to generate the challenging signature easily. The adversary A can execute Verify with all the revocation tokens he/she has, and figure the index of the generated signature. The advantage of A in winning the game is

A d v_{A} = | Pr [b^{'} = b] - 1 / 2 |

. As the adversary can obtain the tokens of the challenged indices, he/she can win the game easily. Thus,

A d v_{A}

is not negligible.

In such a way, allowing the adversary A to query any revocation token and generating the challenged signature for the indices, even those indices’ revocation tokens are queried, makes the scheme non-secured.

Because of this problem, we have to consider a security notion which has the restrictions of providing revocation tokens to the adversary. Thus, we use the almost-full anonymity given in [20], which is a restricted version of full anonymity.

3.3. Almost Full Anonymity

The idea of almost full anonymity is depicted in Figure 1. Here, as the naive full anonymity game, the challenger C creates the keys, and gives gpk and gsk to the adversary A. When A accesses the opening oracle with a message–signature pair (M,

Σ

), the oracle outputs

Open (gmsk, M, Σ)

as usual. Furthermore, A can request the token of any user d. Thus, C replies with grt[d]. The revocation query is not in the original notion of full anonymity. Then, A sends two valid identities

i_{0}, i_{1}

with a message M. Then, C chooses one of the two identities, which are not being queried before in revocation query phase, and outputs the signature

Σ^{*}

. Here, signatures are not generated for the indices that have been queried for revocation tokens as the adversary A can use the tokens and execute Verify to check the generated signature. The goal of A is to recognize the index that is employed to produce

Σ^{*}

. He/she is still allowed to access the opening oracle, but without the challenged signature, and he/she can request revocation token of any user except the challenging indices. The almost-full anonymity game between a challenger C and an adversary A is as below.

Initial Phase:C runs the algorithm KeyGen and gets gpk, gmsk, and group members’ secret keys gsk and revocation tokens grt, and then sends (gpk, gsk) to A.
Query Phase:A can ask token of any user, and request the opening of any valid (M, Σ) pair.
Challenge Phase:A sends a message M and two distinct indexes $i_{0}, i_{1}$ , such that A never queried the tokens of them. C chooses a bit b $\overset{$}{\leftarrow}$ {0,1}, creates and sends back $Σ^{*}$ = $Sign (gpk, gsk [i_{b}], grt [i_{b}], M)$ .
The adversary A still can query the opening oracle without the signature challenged, and he/she can request revocation tokens of any user except the indices used for challenge.
Guessing Phase: Finally, A sends a bit $b^{'}$ , the guess of b. If $b^{'} = b$ , then he wins.

We declare the advantage of A in the above game as

A d v_{A} = | Pr [b^{'} = b] - 1 / 2 |

. We say that any group signature is almost-full anonymous if for all polynomial N and for all adversaries, the

A d v_{A}

is negligible in the security parameter n.

Here, we discuss the almost-full anonymity with regards to the full anonymity and the selfless-anonymity. As in any other anonymity game, in the almost-full anonymity game, gpk is given to the adversary A and, as in the full-anonymity, all the user secret signing keys gsk are given to the adversary A at the beginning of the game. Even the member revocation tokens are generated; they are not provided to A in the initial phase. In the query phase, A can access Open as in the full-anonymity and request for revocation tokens as in the selfless-anonymity game. Then, A can output

i_{0}, i_{1}

, which are not used in the revocation query as in the selfless-anonymity. Still, A can access Open but not with the signature challenged, and he/she is permitted for further revocation queries except for indices challenged. Thus, the almost-full anonymity is stronger than the selfless-anonymity as all the users’ secret signing keys are provided to the adversary. However, the almost-full anonymity is not as strong as the full anonymity because we cannot permit the adversary to access all the revocation tokens. However, all the users’ secret signing keys are provided to the adversary. In the full anonymity given in the BMW03 model, all the secret signing keys of the users (the only secret key of the users in that scheme has) are provided to the adversary. However, in the VLR scheme, we have another user’s key called tracing key (revocation token) which cannot disclose to the adversary without any restrictions. Thus we say the almost-full anonymity is a controlled variant of the full anonymity, and it is somewhat weaker than the full anonymity. A scheme to be fully anonymous, all the secret keys (both secret signing keys and revocation tokens) should be given to the adversary at the start of the game. The almost-full anonymity is a reasonable solution for our scheme rather than the selfless-anonymity. An attacker can identify the signer only if he gets hold of the signer’s token. An attacker obtaining the exact signer’ token is as rare.

The VLR group signature scheme in [10], generates revocation tokens grt by taking a part of the secret keys gsk. As we are providing all the users’ secret signing keys to the adversary, and he/she can query revocation tokens, he/she can create challenged indices’ tokens utilizing the secret keys he has. Thus, we take a different way to generate the revocation tokens, as discussed in Section 5. Thus, revocation tokens of our scheme are not derived from the secret signing keys.

3.4. Traceability

The naive definition of traceability in [1] is to determine the correctness of the opening algorithm. Therefore, for a valid signature signed by i with gsk[i], the opening algorithm should return i. Later, traceability appeared with an actual security requirement, that it is not able to create a signature which can not be locate to a group that generated the signature. However, the BMW03 model gave a much stronger notion called full-traceability, which can be regarded as a strong form of traceability and collusion resistance.

In the traceability game, the challenge of the adversary is to form a signature that cannot be traced. Any group signature scheme is traceable if no adversary can win this challenge. Therefore, we say that a VLR group signature scheme is traceable if the adversary cannot forge a signature that can be traced to one of the users in his coalition using the implicit tracing algorithm. The traceability game between a challenger C and an adversary A [10] is as follows.

Initial Phase:C obtains gpk, gsk, and grt. Then, C sends (gpk, grt) to A and sets corruption list U ← ∅.
Query Phase:A is allowed for the below queries.
1.
Signing: A requests a signature by sending a message M and a user index i, and C responds with $Σ$ = Sign(gpk, gsk[i], M).
2.
Corruption: A queries for the secret key of any user i. The challenger C sends gsk[i] after adding i to U.
Challenge Phase:A sends a message $M^{*}$ , a set of revocation tokens ${RL}^{*}$ , and a signature $Σ^{*}$ .
The forgery A wins if the followings are correct.
1.
$Σ^{*}$ is valid on $M^{*}$ with ${RL}^{*}$ .
2.
$Σ^{*}$ traces to some id outside the coalition $U ∖ {RL}^{*}$ or tracing algorithm returns failure symbol.
3.
$Σ^{*}$ is not gained by signing on $M^{*}$ .

The advantage of A is

A d v_{A}^{t r a c e} = | Pr [{Exp}_{A}^{t r a c e} (n, N) = 1] |

, where

{Exp}_{A}^{t r a c e}

is the traceability game between the challenger C and the adversary A. We say that a group signature scheme is traceable if

A d v_{A}^{t r a c e}

is negligible.

4. The Underlying Zero Knowledge Interactive Protocol

In the proposing scheme, as the tokens are separated from the secret signing keys, there is a risk of signers cheating their tokens at the time of signing. For instance, a revoked member can pick a random value as his/her token and generate a signature. As the fake token is not in the revocation list RL, the verifier thinks the signer is an active member. To prevent such forgeries, we require signers to prove that their token is valid. In other words, the signer should prove that for generating the signature he/she used token which is given at the setup stage. As the signer cannot show his token to outsiders, he/she needs a system to generate a proof while hiding his/her private data. Thus, we modify the zero-knowledge protocol given in [26], and provide a new zero-knowledge protocol that can satisfy the proposing scheme’s requirements. Consequently, we present a new protocol as our scheme’s underlying zero-knowledge interactive protocol that proves the signer is valid, his/her token is not revoked, and his/her token is real.

Zero Knowledge Interactive Protocol enables a prover (signer) to prove that he/she is a approved group member who has valid secret keys.

Let COM be the statistically hiding and computationally binding commitment scheme given in [36].

A combined interactive protocol is given in [26]. By using that protocol, a signer can prove the validity of signing, that his/her revocation token is not in the revocation list, and that his/her index is correctly encrypted. However, as we need the signer to prove that his token is real, which cannot be achieved by directly using the method in [26], we need to modify the protocol in [26].

When the protocol in [26] is used in a scheme which supports both VLR and the explicit tracing mechanism, we use public parameters, a matrix A = [

A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}

]

\in Z_{q}^{n \times (2 ℓ + 1) m}

, a vector u ∈

Z_{q}^{n}

, a matrix

B \in Z_{q}^{n \times m}

, a matrix

V \in Z_{q}^{m \times n}

, a vector

v \in Z_{q}^{m}

, a matrix

P \in Z_{q}^{k_{1} \times k_{2}}

, and another vector

c \in Z_{q}^{k_{1}}

. The witness of the prover consists of a vector

x^{(d)} = (x_{0} ∥ x_{1}^{0} ∥ x_{1}^{1} ∥ \dots ∥ x_{ℓ}^{0} ∥ x_{ℓ}^{1}) \in Σ^{(2 ℓ + 1) m}

for some

d \in {0, 1}^{ℓ}

, a vector

e_{1} \in Z^{m}

, a vector

r \in Z_{q}^{n}

, and another vector

e \in Z^{k_{2}}

. The prover has to show the verifier that

A \cdot x = u mod q

{∥ e_{1} ∥}_{\infty} \leq β

and

V \cdot (B \cdot r) + e_{1} = v mod q

while keeping his identity d in secret. Moreover, the prover has to show his identity is correctly encrypted, such that

{∥ e ∥}_{\infty} \leq b

and

P e + (0^{k_{1} - ℓ} ∥ ⌊ q / 2 ⌋ d) = c mod q

In our scheme, we use the modified Boyen’s signature given in [14] to make revocation tokens. In Boyen’s signature schemes, it requires to show the verifier that

A_{(d)} z = u mod q

, while hiding both d and z. The matrix

A_{(d)}

is unique to the users as it is obtained by using user’s index. The vector z is attained by using

A_{(d)}

. We use the same method in our scheme to prove the validity of the revocation token. Thus, in our scheme, we use (

A_{(d)} \cdot t

) as the revocation token of the user and as a result, in addition to the proof given in [26], we should prove that

A_{(d)} \cdot t = w mod q

in zero-knowledge, while keeping both d and t in secret. Here w is a public parameter and t is generated using

A_{(d)}

and w.

Using the method given in [14], we take following steps to prove

A_{(d)} \cdot t = w mod q

, where

A_{(d)} = [A_{0} | \sum_{i = 1}^{ℓ} A_{i}^{d [i]} \cdot d [i]]

Let

\bar{A} = [A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}] \in Z_{q}^{n \times (1 + ℓ) m}

and

t = (x ∥ y) \in Z^{m}

. Thus, we get

w = A_{(d)} \cdot t = A_{0} x + \sum_{i = 1}^{ℓ} A_{i}^{d [i]} \cdot (d [i] y) = \bar{A} \bar{t} mod q

, where

\bar{t} = (x ∥ d_{1} y ∥ \dots ∥ d_{ℓ} y)

We need to argue the position of

\bar{t} \in Z^{(1 + ℓ) m}

in zero-knowledge, for a given (

\bar{A}, w

), such that

∥ \bar{t} ∥_{\infty} \leq β

and

\bar{A} \bar{t} = w mod q .

Let

A^{*} = [A_{0} | 0^{n \times 2 m} | A_{1}^{0} | 0^{n \times 2 m} | A_{1}^{1} | 0^{n \times 2 m} | \dots | A_{ℓ}^{0} | 0^{n \times 2 m} | A_{ℓ}^{1} | 0^{n \times 2 m} | 0^{n \times 3 m ℓ}] \in Z_{q}^{n \times (1 + 2 ℓ) 3 m}

and

t_{j} = (x_{j} ∥ d_{1} y_{j} ∥ \dots ∥ d_{ℓ + 1} y_{j} ∥ \dots ∥ d_{2 ℓ} y_{j} {) \in {- 1, 0, 1}}^{(1 + 2 ℓ) 3 m}

A^{*}

is the extended matrix [10] of

\bar{A}

, and

t_{j}

is the elementary extension [10] of

\bar{t}

We can argue

A^{*} (\sum_{j = 1}^{p} β_{j} t_{j}) = w mod q

Using masking vectors

(r_{t}^{(1)}, \dots, r_{t}^{(p)}) \in Z_{q}^{n \times (1 + 2 ℓ) 3 m}

instead of arguing above we can show,

A^{*} \sum_{j = 1}^{P} β_{j} (t_{j} + r_{t}^{(j)}) - w = A^{*} (\sum_{j = 1}^{p} β_{j} r_{t}^{(j)}) mod q

In our new zero-knowledge protocol the public inputs are a vector A = [

A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}

]

\in Z_{q}^{n \times (2 ℓ + 1) m}

, vector u

\in Z_{q}^{n}

, vector w

\in Z_{q}^{n}

, matrix

V \in Z_{q}^{m \times n}

, vector

v \in Z_{q}^{m}

, matrix

P \in Z_{q}^{k_{1} \times k_{2}}

, and a vector

c \in Z_{q}^{k_{1}}

. The witness of the prover consists of a vector

x^{(d)} = (x_{0} ∥ x_{1}^{0} ∥ x_{1}^{1} ∥ \dots ∥ x_{ℓ}^{0} ∥ x_{ℓ}^{1}) \in Σ^{(2 ℓ + 1) m}

for some

d \in {0, 1}^{ℓ}

, a vector

e_{1} \in Z^{m}

, a vector

t \in Z_{q}^{2 m}

, and another vector

e \in Z^{k_{2}}

. The prover should persuade the verifier that

A \cdot x = u mod q

{∥ e_{1} ∥}_{\infty} \leq β

and

V \cdot (A_{(d)} \cdot t) + e_{1} = v mod q

while hiding prover’s identity d. Moreover, the prover has to show that his/her identity is correctly encrypted, such that

{∥ e ∥}_{\infty} \leq b

and

P e + (0^{k_{1} - ℓ} ∥ ⌊ q / 2 ⌋ d) = c mod q

and token is real, such that

A_{(d)} \cdot t = w mod q

4.1. Preparation Step

The common inputs: Matrices A = [ $A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}$ ] $\in Z_{q}^{n \times (2 ℓ + 1) m}$ , $V \in Z_{q}^{m \times n}$ , and $P \in Z_{q}^{k_{1} \times k_{2}}$ and vectors u, w $\overset{$}{\leftarrow}$ $Z_{q}^{n}$ , $v \in Z_{q}^{m}$ , and $c \in Z_{q}^{k_{1}}$ .
The prover’s inputs: A vector $x = (x_{0} ∥ x_{1}^{0} ∥ x_{1}^{1} ∥ \dots ∥ x_{ℓ}^{0} ∥ x_{ℓ}^{1}) \in {Secret}_{β} (d)$ for some secret $d \in {0, 1}^{ℓ}$ , vector $e_{1} \in Z^{m}$ , vector $t \in Z_{q}^{2 m}$ , and a vector $e \in Z^{k_{2}}$ . We use f instead of $e_{1}$ hereunder to discard the confusing $e_{1}$ with e.
The prover’s target is to prove the verifier in zero-knowledge that
-
$A \cdot x = u mod q$ and $x \in {Secret}_{β} (d)$ .
-
${∥ f ∥}_{\infty} \leq β$ and $V \cdot (A_{(d)} \cdot t) + f = v mod q$ .
-
${∥ e ∥}_{\infty} \leq b$ and $P e + (0^{k_{1} - ℓ} ∥ ⌊ q / 2 ⌋ d) = c mod q$ (b is the norm bound for LWE noises and $\bar{p} = ⌊ log b ⌋ + 1$ ).
-
$A_{(d)} \cdot t = w mod q$ .

Before the interaction, both the prover and the verifier form the public matrices:

A^{*} \leftarrow MatrixExt (A)

V^{*} = V \cdot A \in Z_{q}^{m \times m}

I^{*} \in {0, 1}^{m \times 3 m}

(

I^{*}

is gained by appending 2m zero-columns to the identity matrix of order m),

P^{*} = [P | 0^{k_{1} \times 2 k_{2}}] \in Z_{q}^{k_{1} \times 3 k_{2}}

, and

Q = (\begin{matrix} 0^{(k_{1} - ℓ) \times ℓ} & | & 0^{(k_{1} - ℓ) \times ℓ} \\ ⌊ q / 2 ⌋ I_{ℓ} & | & 0^{ℓ \times ℓ} \end{matrix}) \in {0, ⌊ q / 2 ⌋}^{k_{1} \times 2 ℓ} .

Then, the prover uses the Decomposition-Extension technique provided in [10] with his/her witness vectors as below.

Let $z_{1}, \dots, z_{p} \leftarrow WitnessDE (x)$ .
Let ${\tilde{f}}_{1}, \dots, {\tilde{f}}_{p} \leftarrow EleDec (f)$ , then for each $i \in$ [p], let $f_{i} \leftarrow EleExt ({\tilde{f}}_{i})$ .
Let ${\tilde{e}}_{1}, \dots, {\tilde{e}}_{\bar{p}} \leftarrow EleDec (e)$ , then for each $i \in$ [p], let $e_{i} \leftarrow EleExt ({\tilde{e}}_{i})$ .
Let ${\tilde{t}}_{1}, \dots, {\tilde{t}}_{p} \leftarrow EleDec (t)$ , then for each $i \in$ [p], let $t_{i} \leftarrow EleExt ({\tilde{t}}_{i})$ .

At the interactive protocol, the prover instead convince the verifier that he/she knows

z_{1}, \dots, z_{p} \in {Secret}_{β} (d)

{\tilde{f}}_{1}, \dots, {\tilde{f}}_{p} \in B_{3 m}

{\tilde{t}}_{1}, \dots, {\tilde{t}}_{p} \in B_{3 m}

, and

{\tilde{e}}_{1}, \dots, {\tilde{e}}_{p} \in B_{3 k_{2}}

, such that

\{\begin{matrix} A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot z_{j}) = u mod q; \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot t_{j}) + I^{*} \cdot (\sum_{j = 1}^{P} β_{j} \cdot f_{j}) = v mod q . \\ P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot e_{j}) + Q \cdot d^{*} = P e + (0^{k_{1} - ℓ} | | ⌊ q / 2 ⌋ d) = c mod q . \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot t_{j}) = w mod q; \end{matrix}

4.2. Description of the Protocol

1.

Commitment: The prover samples randomness

ρ_{1}, ρ_{2}, ρ_{3}

for COM and the below uniformly random objects:

\{\begin{matrix} c \overset{$}{\leftarrow} {0, 1}^{ℓ}; \\ π_{z, 1}, \dots, π_{z, p} \overset{$}{\leftarrow} S; π_{f, 1}, \dots, π_{f, p} \overset{$}{\leftarrow} S_{3 m}; π_{t, 1}, \dots, π_{t, p} \overset{$}{\leftarrow} S_{3 m}; \\ π_{e, 1}, \dots, π_{e, \bar{p}} \overset{$}{\leftarrow} S_{3 k_{2}}; τ \overset{$}{\leftarrow} S_{2 ℓ}; \\ r_{z, 1}, \dots, r_{z, p} \overset{$}{\leftarrow} Z_{q}^{(2 ℓ + 1) 3 m}; r_{f, 1}, \dots, r_{f, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; \\ r_{t, 1}, \dots, r_{t, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; r_{e, 1}, \dots, r_{e, \bar{p}} \overset{$}{\leftarrow} Z_{q}^{3 k_{2}}; r_{d} \overset{$}{\leftarrow} Z_{q}^{2 ℓ} . \end{matrix}

(1)

Then, the prover sends the following commitment

CMT = (c_{1}, c_{2}, c_{3})

to the verifier.

\{\begin{matrix} c_{1} = COM (c, {π_{z, j}, π_{f, j}, π_{t, j}}_{j = 1}^{p}), A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{z, j}); \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{t, j}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{f, j}); \\ {π_{e, j},}_{j = 1}^{\bar{p}}; P^{*} (\sum_{j = 1}^{\bar{p}} b_{j} r_{e, j}) + Q r_{d}; τ; ρ_{1}); \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{t, j}), \\ c_{2} = COM ({T_{c} \circ π_{z, j} (r_{z, j}), π_{f, j} (r_{f, j}), π_{t, j} (r_{t, j})}_{j = 1}^{p}; \\ {π_{e, j} (r_{e, j})}_{j = 1}^{\bar{p}}; τ (r_{d}); ρ_{2}), \\ c_{3} = \\ COM ({T_{c} \circ π_{z, j} (z_{j} + r_{z, j}), π_{f, j} (f_{j} + r_{f, j}), π_{t, j} (t_{j} + r_{t, j})}_{j = 1}^{p}; \\ {π_{e, j} (e_{j} + r_{e, j})}_{j = 1}^{\bar{p}}; τ (d^{*} + r_{d}); ρ_{3}) . \end{matrix}

(2)

2.

Challenge: The verifier sends a challenge

C h \overset{$}{\leftarrow} {1, 2, 3}

3.

Response: Based on the challenge, the prover computes and outputs the response RSP as below.

Case $C h = 1$ : Let $d_{1} = d \oplus c$ . For each $j \in [p]$ , let $a_{z, j} = T_{c} \circ π_{z, j} (z_{j}); b_{z, j} = T_{c} \circ π_{z, j} (r_{z, j}); a_{f, j} = π_{f, j} (f_{j}); b_{f, j} = π_{f, j} (r_{f, j}); a_{t, j} = π_{t, j} (t_{j}); b_{t, j} = π_{t, j} (r_{t, j})$ . For each $j \in [\bar{p}]$ , let $a_{e, j} = π_{e, j} (e_{j}); b_{e, j} = π_{e, j} (r_{e, j})$ . Let $a_{d} = τ (d^{*}); b_{d} = τ (r_{d})$ . Then, send

$\begin{matrix} R S P = (d_{1}, {a_{z, j}, b_{z, j}, a_{f, j}, b_{f, j}, a_{t, j}, b_{t, j}}_{j = 1}^{p}, \\ {a_{e, j}, b_{e, j}}_{j = 1}^{\bar{p}}, a_{d}, b_{d}, ρ_{2}, ρ_{3}) . \end{matrix}$

(3)
Case $C h = 2$ : Let $d_{2} = c$ . For each $j \in [p]$ , let $ϕ_{z, j} = π_{z, j}; ϕ_{f, j} = π_{f, j}; ϕ_{t, j} = π_{t, j}; s_{z, j} = z_{j} + r_{z, j}; s_{f, j} = f_{j} + r_{f, j}; s_{t, j} = t_{j} + r_{t, j}$ . For each $j \in [\bar{p}]$ , let $ϕ_{e, j} = π_{e, j}; s_{e, j} = e_{j} + r_{e, j}$ . Let $\hat{τ} = τ$ and $s_{d} = d^{*} + r_{d}$ . Then, send

$\begin{matrix} R S P = (d_{2}, {ϕ_{z, j}, ϕ_{f, j}, ϕ_{t, j}, s_{z, j}, s_{f, j}, s_{t, j}}_{j = 1}^{p}, \\ {ϕ_{e, j}, s_{e, j}}_{j = 1}^{\bar{p}}, \hat{τ}, s_{d}, ρ_{1}, ρ_{3}) \end{matrix}$

(4)
Case $C h = 3$ : Let $d_{3} = c$ . For each $j \in [p]$ , let $ψ_{z, j} = π_{z, j}; ψ_{f, j} = π_{f, j}; ψ_{t, j} = π_{t, j}; h_{z, j} = r_{z, j}; h_{f, j} = r_{f, j}; h_{t, j} = r_{t, j}$ . For each $j \in [\bar{p}]$ , let $ψ_{e, j} = π_{e, j}; h_{e, j} = r_{e, j}$ . Let $\tilde{τ} = τ$ and $h_{d} = r_{d}$ . Then, send

$\begin{matrix} R S P = (d_{3}, {ψ_{z, j}, ψ_{f, j}, ψ_{t, j}, h_{z, j}, h_{f, j}, h_{t, j}}_{j = 1}^{p}, \\ {ψ_{e, j}, h_{e, j}}_{j = 1}^{\bar{p}}, \tilde{τ}, h_{d}, ρ_{1}, ρ_{2}) \end{matrix}$

(5)

4.

The verifier verifies received RSP as below.

$C h = 1$ : Parse RSP as in (3).
Check whether $\forall \in [p] : a_{z, j} \in SecretExt (d_{1}), a_{f, j} \in B_{3 m}$ , $a_{t, j} \in B_{3 m}$ , $\forall j \in [\bar{p}] : a_{d} \in B_{2 ℓ}, a_{e, j} \in B_{3 k_{2}},$ and

$\{\begin{matrix} c_{2} = COM ({b_{z, j}, b_{f, j}, b_{t, j}}_{j = 1}^{p}; {b_{e, j}}_{j = 1}^{\bar{p}}; b_{d}; ρ_{2}), \\ c_{3} = COM ({a_{z, j} + b_{z, j}, a_{f, j} + b_{f, j}, a_{t, j} + b_{t, j}}_{j = 1}^{p}; \\ {a_{e, j} + b_{e, j}}_{j = 1}^{\bar{p}}; {a_{d} + b_{d}}; ρ_{3}) . \end{matrix}$

(6)
$C h = 2$ : Parse RSP as in (4). Check whether

$\{\begin{matrix} c_{1} = COM (d_{2}, {ϕ_{z, j}, ϕ_{f, j}, ϕ_{t, j}}_{j = 1}^{p}, A^{*} (\sum_{j = 1}^{p} β_{j} \cdot s_{z, j}) - u; \\ V^{*} (\sum_{j = 1}^{p} β_{j} \cdot s_{t, j}) + I^{*} (\sum_{j = 1}^{p} β_{j} \cdot s_{f, j}) - v; \\ {ϕ_{e, j}}_{j = 1}^{\bar{p}}; P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot s_{e, j}) + Q s_{d} - c; \hat{τ}; ρ_{1}); \\ A^{*} (\sum_{j = 1}^{p} β_{j} \cdot s_{t, j}) - w, \\ c_{3} = COM ({T_{d_{2}} \circ ϕ_{z, j} (s_{z, j}), ϕ_{f, j} (s_{f, j}), ϕ_{t, j} (s_{t, j})}_{j = 1}^{p}; \\ {ϕ_{e, j} (s_{e, j})}_{j = 1}^{\bar{p}}; \hat{τ} (s_{d}); ρ_{3}) . \end{matrix}$

(7)
$C h = 3$ : Parse RSP as in (5). Check whether

$\{\begin{matrix} c_{1} = COM (d_{3}, {ψ_{z, j}, ψ_{f, j}, ψ_{t, j}}_{j = 1}^{p}, A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{z, j}); \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{t, j}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{f, j}); \\ {ϕ_{e, j}}_{j = 1}^{\bar{p}}; P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot h_{e, j}) + Q h_{d}; \tilde{τ}; ρ_{1}); \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{t, j}), \\ c_{2} = COM ({T_{d_{3}} \circ ψ_{z, j} (h_{z, j}), ψ_{f, j} (h_{f, j}), ψ_{t, j} (h_{t, j})}_{j = 1}^{p}; \\ {ψ_{e, j} (h_{e, j}),}_{j = 1}^{\bar{p}}; \tilde{τ} (h_{d}); ρ_{2}) . \end{matrix}$

(8)

If and only if all the conditions hold, the verifier returns Valid. Otherwise, he/she returns Invalid.

As discussed in [26], we construct an efficient simulator S interacting with a (probably dishonest) verifier

\hat{V}

, such that, only using the public input, S returns a simulated transcript that is statistically close to the one created in the real interaction by the honest prover. Thus, the simulator can successfully imitate the honest prover with probability negligibly far from 2/3.

We provide the analysis of the new underlying zero-knowledge protocol in Appendix A.

5. Our VLR Group Signature Scheme

In our scheme, we generate member revocation tokens using modified Boyen’s signature as in [14]. Even when there is no direct relationship to the secret keys we obtain the revocation tokens by using the member-indices. Thus, each revocation token has a relation to each member’s index, which is unique to the members. According to the scheme described in [10], revocation tokens can be obtained by a part of the public key and a part of the secret key. However, as we are giving all the secret keys to the adversary in the anonymity game, the adversary may construct the challenged indices’ revocation tokens by studying the pattern of the queried revocation tokens and using the secret signing keys he has. Thus, we come with a solution to obtain revocation tokens in our scheme by using modified Boyen’s signature.

Our scheme consists of four algorithms as below.

KeyGen(n,N): On inputs, the security parameter n $\in N$ and the number of group users N, this randomized PPT algorithm outputs a group public key gpk, a group manager secret key gmsk, a set of user secret keys gsk, and a set of user revocation tokens grt.
Sign(gpk, gsk[d], grt[d], M): This algorithm computes a group signature $Σ$ on given M using gpk, signer’s secret signing key gsk[d], and the token grt[d].
Verify(gpk, RL, M, $Σ$ ): This algorithm determines whether the given $Σ$ is a valid on M by employing gpk. Then, it confirms that the signer is active by employing RL.
Open(gmsk, M, $Σ$ ): This algorithm gets the group manager’s secret key gmsk, a message–signature pair (M, $Σ$ ) as inputs and outputs the index of the signer. It returns failure symbol when the user cannot be identified.

5.1. Description of Our Scheme

In this section, we present the construction of our scheme from lattices.

Key Generation:KeyGen(n,N) creates a group public key gpk, a group manager secret key gmsk, group users secret signing keys gsk, and group user tokens grt as below.

1.

Run GenTrap(n, m, q) to obtain a matrix

A_{0} \in Z_{q}^{n \times m}

and a trapdoor

T_{A}

2.

Sample vectors u, w

\overset{$}{\leftarrow}

Z_{q}^{n}

3.

Sample matrices

A_{i}^{b}

\overset{$}{\leftarrow}

Z_{q}^{n \times m}

for each

b \in {0, 1}

and

i \in [ℓ]

4.

Set the matrix A = [

A_{0} | A_{1}^{0} | A_{1}^{1} | \dots | A_{ℓ}^{0} | A_{ℓ}^{1}

]

\in Z_{q}^{n \times (2 ℓ + 1) m}

5.

Execute algorithm GenTrap(n, m, q) from [29] to get a matrix

B \in Z_{q}^{n \times m}

and a trapdoor

T_{B}

6.

For each user

d \in {0, 1, \cdot \cdot \cdot, N - 1}

, produce secret signing keys gsk[d] and revocation tokens grt[d] as below.

(a): Let $d [1] \cdot \cdot \cdot d [ℓ] \in {0, 1}^{ℓ}$ be the binary representation of d.
(b): Sample vectors $x_{1}^{d [1]} \cdot \cdot \cdot x_{ℓ}^{d [ℓ]}$ ← $D_{Z^{m}, σ}$ .
(c): Compute z = $\sum_{i = 1}^{ℓ} A_{i}^{d [i]} \cdot x_{i}^{d [i]} mod$ q.
(d): Get $x_{0} \in Z^{m}$ ← $SampleD (T_{A}, A_{0}, u - z, σ)$ .
(e): Let $x_{1}^{1 - d [1]} \cdot \cdot \cdot x_{ℓ}^{1 - d [ℓ]}$ be zero vectors $0^{m}$ .
(f): Define $x^{(d)} = (x_{0} ∥ x_{1}^{0} ∥ x_{1}^{1} ∥ \dots ∥ x_{ℓ}^{0} ∥ x_{ℓ}^{1}) \in Σ^{(2 ℓ + 1) m}$ .
If $∥ x^{(d)} ∥_{\infty} \leq β$ , then continue. Otherwise, redo from (a).
(g): The user secret signing key is gsk[d] = $x^{(d)}$ .
(h): Compute $A_{(d)} = [A_{0} | \sum_{i = 1}^{ℓ} d_{i} A_{i}^{d [i]}] \in Z_{q}^{n \times 2 m}$ .
(i): Run $ExtBasis (T_{A}, A_{(d)})$ to obtain a short basis $T_{(d)}$ .
(j): Get $t^{(d)} \in Z^{2 m}$ ← $SampleD (T_{(d)}, A_{(d)}, w, σ)$ .
(k): Let the user revocation token be grt[d] = $A_{(d)} \cdot t^{(d)}$ .

Finally, the algorithm returns, gpk =

((A, u, w), B)

, gmsk =

T_{B}

, gsk =

(gsk [0], gsk [1], \dots, gsk [N - 1])

, grt =

(grt [0], grt [1], \dots, grt [N - 1])

Signing: We employ the

OTS

scheme to secure the generating signatures. Then, we employ the underlying argument system to prove that the user is valid. Sign(gpk, gsk[d], grt[d], M) takes gpk, the signer’s secret signing key gsk[d], revocation token grt[d] as inputs and produces

Σ

on a message M as follows.

Let

H_{1}

{0, 1}^{*} \to Z_{q}^{n \times ℓ}

H_{2}

{0, 1}^{*} \to {1, 2, 3}^{t}

, and

G

{0, 1}^{*} \to Z_{q}^{n \times m}

be hash functions, modeled as a random oracle.

1.

Run OGen

(1^{n})

and get (ovk, osk).

2.

Encrypt the signer’s index d as below.

(a): Let G = $H_{1} (ovk)$ .
(b): Sample s ← $χ^{n}$ , $e_{1}$ ← $χ^{m}$ and $e_{2}$ ← $χ^{ℓ}$ .
(c): Compute the ciphertext $(c_{1}, c_{2})$ pair which encrypts the index d
( $c_{1} = B^{T} s + e_{1}$ , $c_{2} = G^{T} s + e_{2} + ⌊ q / 2 ⌋ d$ ).

3.

Sample

ρ

\overset{$}{\leftarrow}

{0, 1}^{n}

, and get V =

G (A, u, w, B, M, ρ) \in Z_{q}^{m \times n}

4.

Compute

v = V \cdot (A_{(d)} \cdot t^{(d)}) + e_{1} mod q

(

{∥ e_{1} ∥}_{\infty} \leq β

with overwhelming probability and

A_{(d)} \cdot t^{(d)}

= grt[d]).

5.

Generate the parameters for the interactive protocol to show the index d is encrypted correctly as follows.

P = (\begin{matrix} \begin{matrix} B^{T} \\ G^{T} \end{matrix} & I_{m + ℓ} \end{matrix}) \in Z_{q}^{k_{1} \times k_{2}}; c = (\begin{matrix} c_{1} \\ c_{2} \end{matrix}) \in Z^{k_{1}}; e = (\begin{matrix} s \\ e_{1} \\ e_{2} \end{matrix}) \in Z^{k_{2}} .

(9)

6.

Repeat the underlying interactive protocol given in Section 4,

t = ω (log n)

times with the public parameters (A, u, w, B, V, v, P, c) and prover’s witness (

x, t, e_{1}, e

) to achieve the soundness error negligible. Then make it non-interactive by employing the Fiat–Shamir heuristic as a triple,

Π

({C M T^{(k)}}_{k = 1}^{t}, C H, {R S P^{(k)}}_{k = 1}^{t})

, where

CH =

({C h^{(k)}}_{k = 1}^{t}) = H_{2} (M, {C M T^{(k)}}_{k = 1}^{t}, c_{1}, c_{2})

7.

Get

OTS; sig = OSig (osk, (c_{1}, c_{2}, Π))

8.

Return the signature

Σ

(ovk, (c_{1}, c_{2}), Π, sig, v, ρ)

Verification: On input gpk, RL=

{{u_{i}}_{i}} \subset Z_{q}^{n}

, M, and

Σ

, the algorithm Verify confirms

Σ

is valid on M and signer is a valid member by executing the following steps.

1.: Parse $Σ$ as $(ovk, (c_{1}, c_{2}), Π, sig, v, ρ$ ).
2.: Get V = $G (A, u, w, B, M, ρ) \in Z_{q}^{m \times n}$ .
3.: If $OVer (ovk, (c_{1}, c_{2}), Π, sig)$ = 0 then output invalid and abort.
4.: Parse $Π$ as $({C M T^{(k)}}_{k = 1}^{t}, {C h^{(k)}}_{k = 1}^{t}, {R S P^{(k)}}_{k = 1}^{t})$ .
5.: If $(C h^{(1)}, \dots, C h^{(t)}) \neq H_{2} (M, {C M T^{(k)}}_{k = 1}^{t}, c_{1}, c_{2})$ , then return invalid else continue.
6.: For $k = 1$ to t execute the verification steps of the commitment scheme in Section 4 with public parameters (A, u, w, B, V, v, P, c) to validate $R S P^{(k)}$ with respect to $C M T^{(k)}$ and $C h^{(k)}$ . If any of the conditions does not hold then return invalid and abort.
7.: For each $u_{i} \in RL$ compute $e_{i}^{^{'}} = v - V \cdot u_{i} mod q$ to verify whether there exists an index i satisfying ${∥ e_{i}^{^{'}} ∥}_{\infty} \leq β$ . If so output invalid.
8.: Return valid.

Open: To identify the signer of the given message M signature

Σ

pair Open(gmsk, M,

Σ

) functions as follows. Here, gmsk =

T_{B}

is the group manager’s secret key and

Σ

(ovk, (c_{1}, c_{2}), Π, sig)

1.: Let $G = [g_{1} | \dots | g_{ℓ}] = H_{1} (ovk)$ .
2.: Then, for $i \in [ℓ]$ , sample $y_{i} \leftarrow SamplePre (T_{B}, B, g_{i}, σ)$ .
3.: Let $Y = [y_{1} | \dots | y_{ℓ}] \in Z^{m \times ℓ}$ .
4.: Compute $d^{'} = (d_{1}^{'}, \dots, d_{ℓ}^{'}) = c_{2} - Y^{T} c_{1} \in Z_{q}^{ℓ}$ .
5.: For each $i \in [ℓ]$ check whether $d_{i}^{'}$ is closer to 0 than $⌊ q / 2 ⌋ mod$ q. If so $d_{i} = 0$ else 1.
6.: Return index $d = (d_{1}, \dots, d_{ℓ}) \in {0, 1}^{ℓ}$ .

6. Correctness and Security Proof of the Scheme

6.1. Correctness

We use the techniques in [14] and adapt the scheme provided in [10]. Even though we changed the revocation token generation with regards to the work in [10], there is no impact to the correctness of the scheme from new revocation token generation, as we check the signer’s authenticity with RL separately and we prove the honesty of the token independently in zero-knowledge proof.

For all n, N, all (gpk, gmsk, gsk, grt) returned by KeyGen(n, N), all

d \in {0, 1, \dots, N - 1}

, and all

M \in {0, 1}^{*}

, Verify(gpk, RL, M, Sign(gpk, gsk[d], grt[d], M)) = valid;

grt [d] \notin RL

and Open(gmsk, M, Sign(gpk, gsk[d], grt[d], M)) = d.

We use the proof of correctness given in [10]. We prove the correctness of Open additionally.

Lemma 1

([10], Lemma 4). Let

β = poly (n), q \geq {(4 β + 1)}^{2}

and

m \geq 3 n

. Over the randomness of

V \in Z_{q}^{m \times n}

P r [\exists non - zero s \in Z_{q}^{n} : ∥ V \cdot s ∥_{\infty} \leq 2 β] \leq negl (n) .

Proof.

Fix a non-zero vector

s \in Z_{q}^{n}

. Then the vector

V \cdot s

is uniformly distributed over

Z_{q}^{m}

. It then follows that

{P r [∥ V \cdot s ∥}_{\infty} \leq 2 β] \leq \frac{{(4 β + 1)}^{m}}{q^{m}}

. Applying a union-bound get

\begin{matrix} P r [\exists non - zero s \in Z_{q}^{n} : ∥ V \cdot s ∥_{\infty} \leq 2 β] \\ \leq \frac{q^{n} {(4 β + 1)}^{m}}{q^{m}} \leq \frac{1}{{(4 β + 1)}^{m - 2 n}} \leq {(4 β + 1)}^{- n} = negl (n) . □ \end{matrix}

An honest signer is able to obtain a valid witness

(x, t, e_{1}, e

) for the underlying argument system with overwhelming probability. Moreover, the verification algorithm Verify will not return Invalid for the signature check after Step 6, because Step 6 validates the signature using the underlying zero-knowledge interactive protocol. In Step 7 of the verification algorithm Verify, the vector

e_{i}^{'}

for every i can be delivered as

e_{i}^{'} = v - V \cdot u_{i} = V \cdot grt [d] + e_{1} - V \cdot u_{i} = V \cdot (grt [d] - u_{i}) + e_{1} mod q .

If the verification algorithm Verify outputs Valid, that is

∥ e_{i}^{'} ∥_{\infty} \leq β

, for all i. This means

grt [d] \notin RL

. If there exists an index i, where

grt [d] = u_{i}

, then

e_{i}^{'} = e_{1}

. Then, the signature should not pass the Step 7 of the verification process because

∥ e_{i}^{'} ∥_{\infty} = {∥ e_{1} ∥}_{\infty} \leq β

Suppose there is a situation

grt [d] \notin RL

, i.e., for every i, the vector

s_{i} : = grt [d] - u_{i} mod q

is non-zero. According to Lemma 1,

∥ V \cdot s_{i} ∥_{\infty} > 2 β

with overwhelming probability. At the same time,

∥ V \cdot s_{i} ∥_{\infty} \leq ∥ e_{i}^{'} ∥_{\infty} + ∥ e_{1} ∥_{\infty} \leq {∥ e_{i}^{'} ∥}_{\infty} + β

. Thus,

∥ e_{i}^{'} ∥_{\infty} > 2 β - β = β

In our scheme, the revocation token

grt [d] = (A_{(d)} t^{(d)})

of a member d is generated by using the public parameters A and w. Thus, the underlying zero-knowledge protocol of the verification algorithm checks whether the user token satisfies

A_{(d)} t^{(d)} = w mod q

in zero-knowledge. Thus, using the public parameters without revealing the

A_{(d)}

t^{(d)}

the signer should proof that his token is not being faked. On the other hand, because of this condition dishonest signers cannot generate a valid signature with a fake token that passes the signature verification. This confirms that only correct and honestly generated signatures can pass the signature verification.

Moreover, if the index of the signer is correctly encrypted in the ciphertext c at the time of signing, then the tracing algorithm Open returns the index of the signer correctly. Encryption of the index is guaranteed in the signing stage because no member can pass the underlying interactive protocol without correct encryption of the index via a LWE function. In addition to that, Verify returns Invalid if the ciphertext c is not correct encryption of the index because it cannot pass the underlying interactive protocol’s checking without a correct encryption. Thus, this proves the correctness of the encryption of the index and that the tracing algorithm outputs the index of the correct signer.

6.2. Almost-Full Anonymity

Theorem 1.

The proposed VLR group signature scheme Section 5.1 is almost-full anonymous in the random oracle model under the

{LWE}_{n, q, χ}

assumption.

We demonstrate the anonymity of our scheme using eight indistinguishable games, where

A d v_{A} (G_{0}) = ϵ

and

A d v_{A} (G_{7}) = 0

Game

G_{0}

: This is the naive anonymity experiment. Here, we believe that the adversary A has advantage

ϵ

. At the beginning, the challenger C produces keys gpk, gmsk,

gsk [d]_{d \in {0, 1}^{ℓ}}

, and

grt [d]_{d \in {0, 1}^{ℓ}}

using KeyGen(n, N). Then, he/she hand overs gpk and gsk to A. The adversary A is allowed to query revocation tokens and opening of any signature. When A asks for a token of a user d the challenger C outputs grt[d]. When A queries for opening of any signature then C answers with

Open (gmsk, M, Σ)

using gmsk =

T_{B}

. In the challenge phase, A sends a message M and two indices

i_{0}, i_{1} \in {0, 1}^{ℓ}

, such that the adversary A did not make a revocation query for users

i_{0}, i_{1} \in {0, 1}^{ℓ}

. Then, C sends back

Σ^{*} = ({ovk}^{*}, (c_{1}^{*}, c_{2}^{*}), Π^{*}, {sig}^{*}, v^{*}, ρ^{*})

, which is generated using Sign(

gpk, gsk [i_{b}], grt [i_{b}], M

). The adversary A still can query for opening oracle except for challenged indices and he is not allowed for revocation queries with

i_{0}, i_{1}

. The adversary’s challenge is to guess the index, that is employed to produce

Σ^{*}

. Finally, A returns

b^{'}

\in {0, 1}

. If

b^{'} = b

then A wins.

Game

G_{1}

: In this game, a minor modification is done compared to

G_{0}

. The

OTS

key pair (

{ovk}^{*}, {osk}^{*}

), which is created at the signature generation in the real game, is produced at the initial stage of the game. Thus, at the query phase, if A queries for opening oracle with

Σ = (ovk, (c_{1}, c_{2}), Π, sig, v, ρ)

, where

ovk = {ovk}^{*}

then the challenger C sends a random bit and terminates the game. As

{ovk}^{*}

is created at the start, it does not have any relation to the adversary’s queries. Accordingly, the probability of

ovk = {ovk}^{*}

is insignificant. Besides, after the challenge signature

Σ^{*} = (o v k^{*}, (c_{1}^{*}, c_{2}^{*}), Π^{*}, s i g^{*}, v^{*}, ρ^{*})

is sent, if the adversary queries a valid signature

Σ = (o v k, (c_{1}, c_{2}), Π, s i g, v, ρ)

with

ovk = {ovk}^{*}

then sig is a forged one. Therefore, the challenger terminating the game is irrelevant. Without losing the generality we believe that A does not ask for opening of a valid

Σ

with

ovk = {ovk}^{*}

Game

G_{2}

: Here, we replace the encrypting matrices

B

and

G

with randomly obtained

B^{*}

and

G^{*}

, and we program the random oracle

H_{1}

according to B and G. In real anonymity game, B is obtained from GenTrap and G is generated at the signature generation. In this game, we get uniformly random

B^{*} \in Z_{q}^{n \times m}

and

G^{*} \in Z_{q}^{n \times ℓ}

. The challenger samples

Y \leftarrow {(D_{z^{m}, σ})}^{ℓ}

compute

G = B^{*} Y \in Z_{q}^{n \times ℓ}

and program

H_{1} ({ovk}^{*}) = G

to respond the opening oracles querying with

Σ = (ovk, (c_{1}, c_{2}), Π, s i g, v, ρ)

. This G is utilized to respond the opening and (ovk,Y,G) is saved to reuse when A repeats the same queries for

H_{1} (ovk)

. In the challenge phase, program

H_{1} {(ovk)}^{*} = G^{*}

and compute

(c_{1}^{*}, c_{2}^{*})

to make

Σ^{*}

. As the distribution of G is statistically close to uniform over

Z_{q}^{n \times ℓ}

[29] and the distributions of

G^{*}, B^{*}

are statistically close to the real game [29], the games

G_{1}

and

G_{2}

are indistinguishable.

Game

G_{3}

: Without producing the legitimate non-interactive proof

Π

, in this game, C simulates

Π

as discussed in Section 4. For each

k \in [t]

, take a forged challenge

{\bar{C h}}^{(k)}

and execute the interactive protocol. Then, program the random oracle

H_{1}

respectively. The challenging signature

Σ^{*} = ({ovk}^{*}, (c_{1}^{*}, c_{2}^{*}), Π^{*}, {sig}^{*}, v^{*}, ρ^{*})

is statistically close to the signature in the early games because the argument system is statistically zero-knowledge. Therefore,

G_{3}

is indistinguishable from

G_{2}

Game

G_{4}

: The challenger replaces the naive revocation token used to generate the challenged signature

Σ^{*} = ({ovk}^{*}, (c_{1}^{*}, c_{2}^{*}), Π^{*}, s i g^{*}, v^{*}, ρ^{*})

, where

v = V \cdot grt [i_{b}] + e_{1} mod q

, with a vector t sampled uniformly. We compute

v = V \cdot t + e_{1} mod q

, where

t \overset{$}{\leftarrow} Z_{q}^{n}

. V is uniformly random over

Z_{q}^{m \times n}

e_{1}

sampled from the error distribution

χ

, and we replace only

grt [i_{b}]

by t. As the rest of the game is the same as the previous game

G_{3}

, this game is statistically indistinguishable from

G_{3}

Game

G_{5}

: In this game, we obtain

v

uniformly. Thus, we make the revocation token totally independent of the challenging bit b. We sample

y \overset{$}{\leftarrow} Z_{q}^{m}

and set

v = y

. In the above game, the pair (V, v) is a proper

L W E_{n, q, χ}

instance, and in this game we replace v with truly uniformly sampled y. As the

L W E_{n, q, χ}

problem is hard (Section 2), the games

G_{4}

and

G_{5}

are indistinguishable. Suppose there is an algorithm B for solving the

L W E_{n, q, χ}

problem. Then, B can interact with A by answering the queries that A makes. When A queries for the revocation token of any group member, B can simply answer with a value chosen uniformly random such as

y \overset{$}{\leftarrow} Z_{q}^{m}

instead of providing grt. The rest of the game is the same as the original poof given in the previous game. If adversary A can distinguish whether the revocation token is generated or chosen randomly, the algorithm B succeeds. However, this contradicts the hardness of the

L W E_{n, q, χ}

problem.

Game

G_{6}

: In this game, we modify the creation of ciphertext (

c_{1}^{*}, c_{2}^{*}

) uniformly. Let

c_{1}^{*} = x_{1}

and

c_{2}^{*} = x_{2} + ⌊ q / 2 ⌋ d_{b}

, where

x_{1} \in Z^{m}

and

x_{2} \in Z^{ℓ}

are uniformly random and

d_{b}

is the index of the challenger’s bit. As the rest of the game is same as

G_{5}

and the

L W E_{n, q, χ}

problem is hard to solve, the games

G_{5}

and

G_{6}

are indistinguishable. Indeed, if A succeed on distinguishing two games, then A can also solve the LWE problem. That means, he/she can distinguish (

B^{*}, {(B^{*})}^{T} s + e_{1}

) from (

B^{*}, z_{1}

) and (

G^{*}, {(G^{*})}^{T} s + e_{2}

) from (

G^{*}, z_{2}

), which conflicts with the

L W E_{n, q, χ}

assumption.

Game

G_{7}

: The challenger makes the challenging signature

Σ^{*}

totally independent of the bit b. Let

c_{1}^{*} = x_{1}^{'}

and

c_{2}^{*} = x_{2}^{'}

, where

x_{1}^{'} \in Z_{q}^{m}

and

x_{2}^{'} \in Z_{q}^{ℓ}

are uniformly random. The games

G_{6}

and

G_{7}

are statistically indistinguishable. As this game

G_{7}

is independent from the challenger’s bit b, the advantage of the adversary winning the game

A d v_{A}

is 0.

Therefore, the above executed games prove that advantage of the adversary on almost-full anonymity of the scheme is negligible.

This concludes the proof of anonymity.

6.3. Traceability

In the random oracle model, we say that our VLR group signature scheme is traceable if the

{SIS}_{n, (ℓ + 1) m, q, 2 β}^{\infty}

problem is hard.

Lemma 2

([29]). For any m,

β = p o l y (n)

, and for any

q \geq β . ω (\sqrt{n log n})

, solving a random instance of the

{SIS}_{n, m, q, β}^{2}

{ISIS}_{n, m, q, β}^{2}

problem with non-negligible probability is at least as hard as approximating the

{SIVP}_{γ}^{2}

problem on any lattice of dimension n to within certain

γ = β \cdot \tilde{O} (\sqrt{n})

factors.

Theorem 2

([10]). If there is a traceability adversary A with success probability ϵ and running time T, then there is an algorithm

F

that solves the

{SIS}_{n, (ℓ + 1) . m, q, 2 β}^{\infty}

problem with success probability

ϵ^{'} > (1 - {(7 / 9)}^{t}) \cdot 1 / 2 N

, and running time

T^{'} = 32 \cdot T . q_{H} / (ϵ - 3^{- t}) + p o l y (n, N)

, where

q_{H}

is the number of queries to the random oracle

H : {0, 1}^{*} \to {1, 2, 3}^{t}

Based on Lemma 2 and Theorem 2, we prove that the proposed scheme is traceable in the random oracle.

Suppose there is an adversary A who can break the computational binding property of the commitment scheme COM with non-negligible probability. Therefore, A can find answers for the

{SIS}_{n, (ℓ + 1) m, q, 2 β}^{\infty}

problem. Thus, without losing the generality, we believe that COM is computationally binding.

Let forger

F

be a PPT algorithm that solves the

{SIS}_{n, (ℓ + 1) m, q, 2 β}^{\infty}

problem with non-negligible probability.

The forgery

F

is given the verification key (

A, u, w

F

then produces a key pair (

B, T_{B}

) and interacts with the adversary A by sending gpk = (

(A, u), B

) and responding to the A’s queries as below.

Signatures queries: If the adversary A asks a signature of user d on a random message M, then $F$ outputs $Σ = Sign (gpk, gsk [d], grt [d], M)$ = $(ovk, (c_{1}, c_{2}), Π^{'}, sig, v, ρ)$ , where $Π^{'}$ is simulated without using the legitimate secret key and others are generated faithfully. The zero-knowledge property of the given underlying interactive protocol guarantees that $Σ$ is indistinguishable from the legitimate group signature.
Corruption queries: The corruption set CU is initially a empty set. If the adversary A asks the secret signing key of any user d, then $F$ adds d to CU and returns $gsk [d]$ .
Queries to the random oracles $H_{1}$ and $H_{2}$ are handled by consistently returning uniformly random values in ${1, 2, 3}^{t}$ . For each $k \leq q_{H}$ , $r_{k}$ denotes the answer to the k-th query.

Finally, A sends a message

M^{*}

, revocation data

{RL}^{*}

, and a non-trivial forged signature

Σ^{*}

, which fulfills the requirements of the traceability game, where

Σ^{*}

(ovk, (c_{1}, c_{2}), M, ({C M T^{(k)}}_{k = 1}^{t}, {C h^{(k)}}_{k = 1}^{t}, {R S P^{(k)}}_{k = 1}^{t}), sig, v, ρ)

, such that Verify(

gpk, M^{*}, {RL}^{*}, Σ^{*}

) = Valid and Open fails or outputs an user index outside of the coalition

C U ∖ {RL}^{*}

Now let us show how

F

exploits the forgery.

We assume that A always queries

H_{2}

on input

(M, {C M T^{(k)}}_{k = 1}^{t}, c_{1}, c_{2})

before

H_{1}

. Thus, with probability at least

ϵ - 3^{- t}

, there exists certain

k^{*} \leq q_{H}

such that the

k^{*}

-th oracle queries involves the tuple

(M, {C M T^{(k)}}_{k = 1}^{t}, c_{1}, c_{2})

. Then, for any fixed

k^{*}

, execute A many times and input as in the original run. For each repeated execution, A gives the same results for the first

k^{*}

-1 queries as in the initial run and from the

k^{*}

-th query onward he/she outputs fresh random values. As stated in the forking lemma [[37], Lemma 7], with probability larger than 1/2, algorithm

F

can get a 3-fork involving tuple (

M, {C M T^{(k)}}_{k = 1}^{t}, c_{1}, c_{2}

) after less than

32 \cdot q H / (ϵ - 3^{- t})

executions of A. Let the outputs of

F

with respect to the 3-fork branches be

r_{κ^{*}}^{(1)} = (C h_{1}^{(1)}, \dots, C h_{t}^{(1)}); r_{κ^{*}}^{(2)} = (C h_{1}^{(2)}, \dots, C h_{t}^{(2)}); r_{κ^{*}}^{(3)} = (C h_{1}^{(3)}, \dots, C h_{t}^{(3)}) .

A simple computation shows that

P r [\exists j \in {1, \dots, t}] : {C h_{i}^{(1)}, C h_{i}^{(2)}, C h_{i}^{(3)}} = {1, 2, 3} 1 - {(7 / 9)}^{t}

Under the condition of the existence of such index i, one parses the three forgeries related to the fork branches to get (

R S P_{i}^{(1)}, R S P_{i}^{(2)}, R S P_{i}^{(3)}

Then, by employing the knowledge extractor of the underlying argument system, we can obtain vectors (

y, e_{1}^{*}, t^{*}, e^{*}

). We can get (

s^{*}, e_{1}^{*}, e_{2}^{*}

) from

e^{*}

, which satisfy the following.

1.: $y = (y_{0} ∥ y_{1}^{0} ∥ y_{1}^{1} ∥ \dots ∥ y_{ℓ}^{0} ∥ y_{ℓ}^{1}) \in {Secret}_{β} (d)$ for some $d \in {0, 1}^{ℓ}$ , and $A \cdot y = u mod q$ .
2.: $∥ e_{1}^{*} ∥_{\infty} \leq β$ and $V \cdot (A_{(d)} \cdot t) + f^{'} = v mod q$ .
3.: $∥ e^{*} ∥_{\infty} \leq b$ and ( $B^{T} s^{*} + e_{1}^{*} = c_{1} mod q), (G^{T} s^{*} + e_{2}^{*} + ⌊ q / 2 ⌋ d^{*} = c_{2} mod q$ ).
4.: $A_{(d)} \cdot t = w mod q$ .

We can check that (

c_{1}, c_{2}

) is a correct encryption of

d^{*}

, the tracing algorithm Open(

T_{B}, M^{*}, Σ^{*}

) returns

d^{*}

, Verify(

gpk, Σ, M,^{*} grt [j^{*}]

) = Invalid and Verify(

gpk, Σ, M,^{*} {RL}^{*}

) = Valid.

It then follows that

grt [j^{*}] \notin RL

and

j^{*} \notin C U

. As a result, (

y, d^{*}

) is a valid forgery. Furthermore, the analysis of the forgery signature shows that if A has non-negligible success probability returns in polynomial time, then so does

F

This satisfies the proof of traceability.

7. Conclusion and Open Problems

This paper presented a group signature scheme from lattices that provides member revocation facility using VLR, which is the most efficient revocation approach up to now, while being almost-full anonymous. Moreover, the scheme provides an explicit tracing algorithm Open which can be used to trace a signer in a large group efficiently. However, delivering an efficient VLR group signature scheme with full security is a challenging task which is not yet solved.

Author Contributions

Conceptualization, M.N.S.P.; writing—original draft preparation, M.N.S.P.; writing—review and editing, M.N.S.P. and T.K.; supervision, T.K. All authors have read and agreed to the published version of the manuscript.

Funding

This research was supported in part by JSPS Grants-in-Aid for Scientic Research Numbers 16H01705 and 17H01695.

Acknowledgments

Some part of this paper are result of research by Advanced Telecommunications Research Institute International (ATR), Japan.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Analysis of the Underlying Zero-Knowledge Protocol

Let

COM

be a statistically hiding and computationally binding string commitment scheme. The interactive protocol is a zero-knowledge argument of knowledge with perfect completeness and soundness error 2/3 with

(O (ℓ m) log β + O (k_{2}) log b) log q

communication cost. Thus, it satisfies the following.

There exists an efficient simulator that, on input $(A, u, w, B, V, v, P, c)$ , outputs an accepted transcript which is statistically close to that produced by the real prover.
There exists an efficient knowledge extractor that, on input a commitment $C M T$ and three valid responses $(R S P^{(1)}, R S P^{(2)}, R S P^{(3)})$ corresponding to all three possible values of the challenging Ch, outputs vectors ( $y, f^{'}, r^{'}, e^{'}$ ) such that
1.
$y = (y_{0} ∥ y_{1}^{0} ∥ y_{1}^{1} ∥ \dots ∥ y_{ℓ}^{0} ∥ y_{ℓ}^{1}) \in {Secret}_{β} (d)$ for some $d \in {0, 1}^{ℓ}$ , and $A \cdot y = u mod q$ .
2.
$∥ f^{'} ∥_{\infty} \leq β$ and $V \cdot (A_{(d)} \cdot t) + f^{'} = v mod q$ .
3.
$∥ e^{'} ∥_{\infty} \leq b$ and $P e^{'} + (0^{k_{1} - ℓ} ∥ ⌊ q / 2 ⌋ d) = c mod q$ .
4.
$A_{(d)} \cdot t = w mod q$ .

Appendix A.1. Completeness and Soundness

An honest prover, with a valid witness

(x, f, t, e

) for some

d \in {0, 1}^{ℓ}

, can always obtain

z_{1}, \dots, z_{p} \in {Secret}_{β} (d), f_{1}, \dots, f_{p} \in B_{3 m}, t_{1}, \dots, t_{p} \in B_{3 m},

and

e_{1}, \dots, e_{\bar{p}} \in B_{3 k_{2}}

via the Decomposition-Extension technique [10]. If he/she follows the protocol, he/she should always be accepted by the verifier. In this manner, the protocol has perfect completeness.

The protocol admits a soundness error 2/3, which is natural for typical Stern-like protocols. However, this error can be made negligible by repeating the protocol

t = ω (log n)

times in parallel.

Appendix A.2. Communication Cost

The KTX scheme [36] COM outputs an element of

Z_{q}^{n}

. Therefore, the commitment CMT has bit size

3 n log q = \tilde{O} (n)

. The response RSP is executed by p permutations in S, 2p permutations in

S_{3 m}

\bar{p}

permutations in

S_{3 k_{2}}

, one permutation in 2ℓ, p vectors in

Z_{q}^{(2 ℓ + 1) 3 m}

, 2p vectors in

Z_{q}^{3 m}

\bar{p}

vectors in

Z_{q}^{3 k_{2}}

, and one vector in

Z_{q}^{2 ℓ}

In this manner, the bit size of RSP is bounded by (

O (ℓ m) p + O (k_{2}) \bar{p}

)

log q

, where

p = ⌊ log β ⌋ + 1

and

p = ⌊ log b ⌋ + 1

. Thus, the overall communication cost of the protocol is bounded by (

O (ℓ m) log β + O (k_{2}) log b

)

log q

Appendix A.3. Zero-Knowledge Property

If COM is statistically hiding, we can prove that the interactive protocol is statistical zero-knowledge argument.

First, construct a PPT simulator SIM interacting with a verifier

\hat{V}

such that, by giving only the public inputs, SIM outputs with probability close to 2/3 a simulated transcript that is statistically close to the outputs of an honest prover in the real interaction. From the public input (A, u, w, B, V, v, P, c) given by the protocol, both SIM and

\hat{V}

acquire matrices,

A^{*}, V^{*},

I^{*}

P^{*}

, and Q. Then, SIM starts simulation by selecting a random

\bar{C h} \in {1, 2, 3}

. This is a prediction of the challenge value that

\hat{V}

will not choose.

Case \bar{C h} = 1 :

SIM computes the vectors

z_{1}^{'}, \dots, z_{p}^{'} \in Z_{q}^{(2 ℓ + 1) 3 m}

such that

A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot z_{j}^{'}) = u mod q

t_{1}^{'}, \dots, t_{p}^{'} \in Z_{q}^{3 m}

and

f_{1}^{'}, \dots, f_{p}^{'} \in Z_{q}^{3 m}

such that

V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot t_{j}^{'}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot f_{j}^{'}) = v mod q

and

A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot t^{'}) = w mod q

, and

e_{1}^{'}, \dots, e_{\bar{p}}^{'} \in Z_{q}^{3 k}

and

d^{'} \in Z_{q}^{2 ℓ}

, such that

P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot e_{j}^{'}) + Q \cdot d^{'} = c mod q

by using linear algebra.

Then, SIM samples objects given below as in Equation (1).

\{\begin{matrix} c \overset{$}{\leftarrow} {0, 1}^{ℓ}; \\ π_{z, 1}, \dots, π_{z, p} \overset{$}{\leftarrow} S; π_{f, 1}, \dots, π_{f, p} \overset{$}{\leftarrow} S_{3 m}; π_{t, 1}, \dots, π_{t, p} \overset{$}{\leftarrow} S_{3 m}; \\ π_{e, 1}, \dots, π_{e, \bar{p}} \overset{$}{\leftarrow} S_{3 k_{2}}; τ \overset{$}{\leftarrow} S_{2 ℓ}; \\ r_{z, 1}, \dots, r_{z, p} \overset{$}{\leftarrow} Z_{q}^{(2 ℓ + 1) 3 m}; r_{f, 1}, \dots, r_{f, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; \\ r_{t, 1}, \dots, r_{t, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; r_{e, 1}, \dots, r_{e, \bar{p}} \overset{$}{\leftarrow} Z_{q}^{3 k_{2}}; r_{d} \overset{$}{\leftarrow} Z_{q}^{2 ℓ} . \end{matrix}

(A1)

sends commitment

CMT = (c_{1}^{'}, c_{2}^{'}, c_{3}^{'})

\hat{V}

, where

\{\begin{matrix} c_{1}^{'} = COM (c, {π_{z, j}, π_{f, j}, π_{t, j}}_{j = 1}^{p}, A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{z, j}); \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{t, j}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{f, j}); \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot r_{t, j}); \\ {π_{e, j}}_{j = 1}^{\bar{p}}, P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot r_{e, j}) + Q r_{d}; τ; ρ_{1}), \\ c_{2}^{'} = COM ({T_{c} \circ π_{z, j} (r_{z, j}), π_{f, j} (r_{f, j}), π_{t, j} (r_{t, j})}_{j = 1}^{p}; \\ {π_{e, j} (r_{e, j})}_{j = 1}^{\bar{p}}; τ (r_{d}); ρ_{2}), \\ c_{3}^{'} = COM ({T_{c} \circ π_{z, j} (z_{j}^{'} + r_{z, j}), π_{f, j} (f_{j}^{'} + r_{f, j}), π_{t, j} (t_{j}^{'} + r_{t, j})}_{j = 1}^{p}; \\ {π_{e, j} (e_{j}^{'} + r_{e, j})}_{j = 1}^{\bar{p}}; τ (d^{'} + r_{d}); ρ_{3}) . \end{matrix}

(A2)

For a challenge

C h

from

\hat{V}

, SIM responds as follows.

- If

C h

= 1: Output ⊥ and abort.

- If

C h

= 2: Send,

RSP = (

c, {π_{z, j}, π_{f, j}, π_{t, j}, z_{j}^{'} + r_{z, j}, f_{j}^{'} + r_{f, j}, t_{j}^{'} + r_{t, j}}_{j = 1}^{p}, {π_{e, j}, e_{j}^{'} + r_{e, j}}_{j = 1}^{\bar{p}}, d^{'} + r_{d}, τ, ρ_{1}, ρ_{3}

- If

C h

= 3: Send,

RSP = (

c, {π_{z, j}, π_{f, j}, π_{t, j}, r_{z, j}, r_{f, j}, r_{t, j}}_{j = 1}^{p}, {π_{e, j}, r_{e, j}}_{j = 1}^{\bar{p}}, τ, ρ_{1}, ρ_{2}

Case \bar{C h} = 2 :

SIM samples randomness

ρ_{1}, ρ_{2}, ρ_{3}

for COM and

\{\begin{matrix} \hat{d} \overset{$}{\leftarrow} {0, 1}^{ℓ}, c \overset{$}{\leftarrow} {0, 1}^{ℓ}; d^{'} \overset{$}{\leftarrow} B_{2 ℓ}; \\ z_{1}^{'}, \dots, z_{p}^{'} \overset{$}{\leftarrow} SecretExt (d); f_{1}^{'}, \dots, f_{p}^{'} \overset{$}{\leftarrow} B_{3 m}; t_{1}^{'}, \dots, t_{p}^{'} \overset{$}{\leftarrow} B_{3 m}; \\ e_{1}^{'}, \dots, e_{\bar{p}}^{'} \overset{$}{\leftarrow} B_{3 k}; \\ π_{z, 1}, \dots, π_{z, p} \overset{$}{\leftarrow} S; π_{f, 1}, \dots, π_{f, p} \overset{$}{\leftarrow} S_{3 m}; π_{t, 1}, \dots, π_{t, p} \overset{$}{\leftarrow} S_{3 m}; \\ π_{e, 1}, \dots, π_{e, \bar{p}} \overset{$}{\leftarrow} S_{3 k}; \\ r_{z, 1}, \dots, r_{z, p} \overset{$}{\leftarrow} Z_{q}^{(2 ℓ + 1) 3 m}; r_{f, 1}, \dots, r_{f, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; r_{t, 1}, \dots, r_{t, p} \overset{$}{\leftarrow} Z_{q}^{3 m}; \\ r_{e, 1}, \dots, r_{e, \bar{p}} \overset{$}{\leftarrow} Z_{q}^{3 k}; r_{d} \overset{$}{\leftarrow} Z_{q}^{2 ℓ}, τ \overset{$}{\leftarrow} S_{2 ℓ} . \end{matrix}

Next, SIM forms and sends commitment CMT as the same manner as in (A2).

For a challenge

C h

from

\hat{V}

, SIM responds as follows.

- If

C h

= 1: (

\hat{d} \oplus c {T_{c} \circ π_{z, j} (z_{j}^{'}), T_{c} \circ π_{z, j} (r_{z, j}), π_{f, j} (f_{j}^{'}), π_{f, j} (r_{f, j}), π_{t, j} (t_{j}^{'}), π_{t, j} (r_{t, j})}_{j = 1}^{p}, {π_{e, j} (e_{j}^{'}), π_{e, j} (r_{e, j})}_{j = 1}^{\bar{p}}, τ (d^{'}), τ (r_{d})

- If

C h

= 2: Output ⊥ and abort.

- If

C h

= 3: Send, RSP computed as in the case (

\bar{C h} = 1, C h = 3

Case \bar{C h} = 3 :

SIM samples randomness as in

\bar{C h} = 2

and sends the commitment

CMT = (c_{1}^{'}, c_{2}^{'}, c_{3}^{'})

\hat{V}

, where

c_{2}^{'}, c_{3}^{'}

are computed as in (A2), and

\begin{matrix} c_{1}^{'} = COM (c, {π_{z, j}, π_{e, j}, π_{t, j}}_{j = 1}^{p}, A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (z_{j}^{'} + r_{z, j})) - u; \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (t_{j}^{'} + r_{t, j})) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (f_{j}^{'} + r_{f, j})) - v; \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (t_{j}^{'} + r_{t, j})) - w; \\ {π_{e, j}}_{j = 1}^{\bar{p}}; P^{*} \sum_{j = 1}^{\bar{p}} b_{j} (e_{j}^{'} + k_{e, j}) + Q (d^{'} + k_{d}) - c; τ; ρ_{1}) . \end{matrix}

For a challenge

C h

from

\hat{V}

, SIM responds as follows.

- If

C h

= 1: Send, RSP computed as in the case (

\bar{C h} = 2, C h = 1

- If

C h

= 2: Send, RSP computed as in the case (

\bar{C h} = 1, C h = 2

- If

C h

= 3: Output ⊥ and abort.

As COM is statistically hiding, the distribution of the commitment CMT and the distribution of the challenge

C h

from

\hat{V}

for every case considered above are statistically close to those in the real interaction. Therefore, the probability that the simulator outputs ⊥ is negligibly close to 1/3. Thus, the simulator SIM can successfully imitate the honest prover with probability negligibly close to 2/3.

Appendix A.4. Argument of Knowledge

Here, we prove that if COM is computationally binding, then the given protocol is an argument of knowledge. For a given commitment CMT and three valid responses

R S P^{(1)}, R S P^{(2)}, R S P^{(3)}

to all three possible values of the challenge

C h

, a valid witness can be extracted.

\{\begin{matrix} c_{1} = COM (d_{2}, {ϕ_{z, j}, ϕ_{f, j}, ϕ_{t, j}}_{j = 1}^{p}, A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot s_{z, j}) - u; \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot s_{t, j}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot s_{f, j}) - v; \\ A^{*} (\sum_{j = 1}^{p} β_{j} \cdot s_{t, j}) - w; \\ {ϕ_{e, j}}_{j = 1}^{\bar{p}}; P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot s_{e, j}) + Q s_{d} - c; \hat{τ}; ρ_{1}) \\ = COM (d_{3}, {ψ_{z, j}, ψ_{f, j}, ψ_{t, j}}_{j = 1}^{p}, A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{z, j}); \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{t, j}) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{f, j}); \\ A * \cdot (\sum_{j = 1}^{p} β_{j} \cdot h_{t, j}) - w; \\ {ψ_{e, j}}_{j = 1}^{\bar{p}}; P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} \cdot h_{e, j}) + Q h_{d}; \tilde{τ}; ρ_{1}), \\ c_{2} = COM ({b_{z, j}, b_{f, j}, b_{t, j}}_{j = 1}^{p}, {b_{e, j}}_{j = 1}^{\bar{p}}, b_{d}; ρ_{2}) \\ = COM ({T_{d_{3}} \circ ψ_{z, j} (h_{z, j}), ψ_{f, j} (h_{f, j}), ψ_{t, j} (h_{t, j})}_{j = 1}^{p}; \\ {ψ_{e, j} (h_{e, j})}_{j = 1}^{\bar{p}}, \tilde{τ} (h_{d}); ρ_{2}), \\ c_{3} = COM ({a_{z, j} + b_{z, j}, a_{f, j} + b_{f, j}, a_{t, j} + b_{t, j}}_{j = 1}^{p}; \\ {a_{e, j} + b_{e, j}}_{j = 1}^{\bar{p}}, {a_{d} + b_{d}}; p_{3}) \\ = COM ({T_{d_{2}} \circ ψ_{z, j} (s_{z, j}), ψ_{f, j} (s_{f, j}), ψ_{t, j} (s_{t, j})}_{j = 1}^{p}; \\ {ψ_{e, j} (s_{e, j})}_{j = 1}^{\bar{p}}, \tilde{τ} (s_{d}); ρ_{3}) . \end{matrix}

The computational binding property of COM implies that

\{\begin{matrix} d_{2} = d_{3}; \\ a_{d} \in B_{2 ℓ}; \hat{τ} = \tilde{τ}; b_{d} = \tilde{τ} (h_{d}); a_{d} + b_{d} = \hat{τ} (s_{d}); \\ \forall j \in [p] : ϕ_{z, j} = ψ_{z, j}; b_{z, j} = T_{d_{2}} \circ ϕ_{z, j} (h_{z, j}) a n d \\ a_{z, j} + b_{z, j} = T_{d_{2}} \circ ϕ_{z, j} (s_{z, j}); \\ \forall j \in [p] : ϕ_{f, j} = ψ_{f, j}; b_{f, j} = ϕ_{f, j} (h_{f, j}) a n d a_{f, j} + b_{f, j} = ϕ_{f, j} (s_{f, j}); \\ \forall j \in [p] : ϕ_{t, j} = ψ_{t, j}; b_{t, j} = ϕ_{t, j} (h_{t, j}) a n d a_{t, j} + b_{t, j} = ϕ_{t, j} (s_{t, j}); \\ \forall j \in [\bar{p}] : ϕ_{e, j} = ψ_{e, j}; b_{e, j} = ϕ_{e, j} (h_{e, j}) a n d a_{e, j} + b_{e, j} = ϕ_{e, j} (s_{e, j}); \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (s_{z, j} - h_{z, j})) = u mod q; \\ V^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (s_{t, j} - h_{t, j})) + I^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (s_{f, j} - h_{f, j})) = v mod q; \\ A^{*} \cdot (\sum_{j = 1}^{p} β_{j} \cdot (s_{t, j} - h_{t, j})) = w mod q; \\ P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} s_{e, j}) + Q s_{d} - c = P^{*} \cdot (\sum_{j = 1}^{\bar{p}} b_{j} h_{e, j}) + Q h_{d} mod q . \end{matrix}

For each

j \in [p]

, let

y_{j}^{'} = (s_{z, j} - h_{z, j})

. Then,

T_{d_{2}} \circ ϕ_{z, j} (y_{j}^{'}) = T_{d_{2}} \circ ϕ_{z, j} (s_{z, j}) - T_{d_{2}} \circ ϕ_{z, j} (h_{z, j}) = a_{z, j} \in SecretExt (d_{1}) .

Thus,

ϕ_{z, j} (y_{j}^{'}) \in SecretExt (d_{1} \oplus d_{2})

. Let

\bar{d} = d_{1} \oplus d_{2}

, then for all

j \in [p]

y_{j}^{'} \in SecretExt (\bar{d})

, as the permutation

ϕ_{z, j} \in S

preserves the arrangements of the blocks of

y_{j}^{'}

. By removing the last

2 m

coordinates in each

3 m

-block of

y^{'}

obtain vectors

y^{'} \sum_{j = 1}^{p} β_{j} \cdot y_{j}^{'} \in Z_{q}^{(2 ℓ + 1) 3 m}

, and

y \in Z^{(2 ℓ + 1) m}

. Now, we can declare

{∥ y ∥}_{\infty} \leq ∥ y^{'} ∥_{\infty} \leq \sum_{j = 1}^{p} β_{j} \cdot {∥ y_{j} ∥}_{\infty} = \sum_{j = 1}^{p} β_{j} \cdot 1 = β .

Moreover, as

y_{j}^{'} \in SecretExt (\bar{d})

for all

j \in [p]

, we have that

y \in {Secret}_{β} (\bar{d})

and,

A \cdot y = A^{*} \cdot y^{'} = A^{*} \cdot \sum_{j = 1}^{p} β_{j} \cdot y_{j} = A^{*} (\sum_{j = 1}^{p} β_{j} \cdot (s_{z, j} - h_{z, j})) = u mod q .

For each

j \in [p]

, let

f_{j}^{'} = (s_{f, j} - h_{f, j})

. Then

ϕ_{f, j} (f_{j}^{'}) = ϕ_{f, j} (s_{f, j}) - ϕ_{e, j} (h_{f, j}) = a_{f, j} \in B_{3 m}

, which implies that

f_{j}^{'} \in B_{3 m}

. Let

\hat{f} = \sum_{j = 1}^{p} β_{j} \cdot f_{j}^{'} \in Z^{3 m}

and by dropping the last

2 m

coordinates from

\hat{f}

obtain

f^{'} \in Z^{m}

. We can declare

∥ f^{'} ∥_{\infty} \leq ∥ \hat{f} ∥_{\infty} \leq \sum_{j = 1}^{p} β_{j} \cdot ∥ f_{j}^{'} {∥ |}_{\infty} = \sum_{j = 1}^{p} β_{j} \cdot 1 = β .

Moreover, for each

j \in [p]

, let

t_{j}^{'} = (s_{t, j} - h_{t, j})

. Then,

ϕ_{t, j} (t_{j}^{'}) = ϕ_{t, j} (s_{t, j}) - ϕ_{t, j} (h_{t, j}) = a_{t, j} \in B_{3 m}

, which implies that

t_{j}^{'} \in B_{3 m}

. Let

\hat{t} = \sum_{j = 1}^{p} β_{j} \cdot t_{j}^{'} \in Z^{3 m}

and by dropping the last

2 m

coordinates from

\hat{t}

obtain

t^{'} \in Z^{m}

. We can declare

∥ t^{'} ∥_{\infty} \leq ∥ \hat{t} ∥_{\infty} \leq \sum_{j = 1}^{p} β_{j} \cdot {∥ t_{j}^{'} ∥}_{\infty} = \sum_{j = 1}^{p} β_{j} \cdot 1 = β .

We can obtain the relation

V^{*} \cdot \hat{t} + I^{*} \cdot \hat{f} = v mod q \Leftrightarrow V^{*} \cdot (A_{(d)} \cdot t^{'}) + f^{'} = v mod q .

and

A^{*} \cdot \sum_{j = 1}^{p} β_{j} \cdot t_{j}^{'} = A_{(d)} \cdot t^{'} = w mod q .

Let

d^{*} = s_{d} - h_{d} = {\hat{τ}}^{- 1} (a_{d})

. Then, it follows that

d^{*} \in B_{2 ℓ}

. Now, let

d^{*} = (d_{1}, \dots, d_{ℓ}, d_{ℓ + 1}, \dots, d_{2 ℓ})

and let

d = (d_{1}, \dots, d_{ℓ}) \in {0, 1}^{ℓ}

For each

j \in [\bar{p}]

, let

e_{j}^{'} = (s_{e, j} - h_{e, j})

. Then

ϕ_{e, j} (e_{j}^{'}) = ϕ_{e, j} (s_{e, j}) - ϕ_{e, j} (h_{e, j}) = a_{e, j} \in B_{3 k}

, which implies that

e_{j}^{'} \in B_{3 k}

. Let

\hat{e} = \sum_{j = 1}^{\bar{p}} b_{j} \cdot e_{j}^{'}

and by dropping the last

2 k

coordinates from

\hat{e}

obtain

e^{'} \in Z^{k}

. We can declare,

∥ e^{'} ∥_{\infty} \leq ∥ \hat{e} ∥_{\infty} \leq \sum_{j = 1}^{\bar{p}} b_{j} \cdot {∥ e_{j}^{'} ∥}_{\infty} = \sum_{j = 1}^{p} b_{j} \cdot 1 = b .

Now,

∥ e^{'} ∥_{\infty} \leq b

, and

P^{*} e^{'} + Q d^{*}

P e^{'} + (0^{k - ℓ} ∥ ⌊ q / 2 ⌋ d) = c mod q

References

Chaum, D.; van Heyst, E. Group Signatures. In EUROCRYPT 1991; LNCS; Springer: Berlin/Heidelberg, Germany, 1991; Volume 547, pp. 257–265. [Google Scholar]
Chen, L.; Pedersen, T.P. New group signature schemes. In Workshop on the Theory and Application of Cryptographic Techniques; LNCS; Springer: Berlin/Heidelberg, Germany, 1994; Volume 950, pp. 171–181. [Google Scholar]
Ateniese, G.; Tsudik, G. Group signatures á la carte. In Proceedings of the Symposium on Discrete Algorithms: Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 17–19 January 1999; Volume 17, pp. 848–849. [Google Scholar]
Ateniese, G.; Camenisch, J.; Joye, M.; Tsudik, G. A Practical and Provably Secure Coalition-Resistant Group Signature Scheme. In CRYPTO 2000; LNCS; Springer: Berlin/Heidelberg, Germany, 2000; Volume 1880, pp. 255–270. [Google Scholar]
Bellare, M.; Micciancio, D.; Warinschi, B. Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions. In EUROCRYPT 2003; LNCS; Springer: Berlin/Heidelberg, Germany, 2003; Volume 2656, pp. 614–629. [Google Scholar]
Bresson, E.; Stern, J. Efficient Revocation in Group Signatures. In PKC 2001; LNCS; Springer: Berlin/Heidelberg, Germany, 2001; Volume 1992, pp. 190–206. [Google Scholar]
Camenisch, J.; Lysyanskaya, A. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In CRYPTO 2002; LNCS; Springer: Berlin/Heidelberg, Germany, 2002; Volume 2442, pp. 61–76. [Google Scholar]
Brickell, E. An Efficient Protocol for Anonymously Providing Assurance of the Container of the Private Key; Submitted to Trusted Computing Group: Beaverton, OR, USA, 2003. [Google Scholar]
Boneh, D.; Shacham, H. Group Signatures with Verifier-Local Revocation. In Proceedings of the ACM-CCS 2004, Washington, DC, USA, 25–29 October 2004; pp. 168–177. [Google Scholar]
Langlois, A.; Ling, S.; Nguyen, K.; Wang, H. Lattice-Based Group Signature Scheme with Verifier-Local Revocation. In PKC 2014; LNCS; Springer: Berlin/Heidelberg, Germany, 2014; Volume 8383, pp. 345–361. [Google Scholar]
Gordon, S.D.; Katz, J.; Vaikuntanathan, V. A Group Signature Scheme from Lattice Assumptions. In ASIACRYPT 2010; LNCS; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6477, pp. 395–412. [Google Scholar]
Camenisch, J.; Neven, G.; Rückert, M. Fully Anonymous Attribute Tokens from Lattices. In SCN 2012; LNCS; Springer: Berlin/Heidelberg, Germany, 2012; Volume 12, pp. 57–75. [Google Scholar]
Laguillaumie, F.; Langlois, A.; Libert, B.; Stehlé, D. Lattice-Based Group Signatures with Logarithmic Signature Size. In ASIACRYPT 2013; LNCS; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8270, pp. 41–61. [Google Scholar]
Ling, S.; Nguyen, K.; Wang, H. Group Signatures from Lattices: Simpler, Tighter, Shorter, Ring-Based. In PKC 2015; LNCS; Springer: Berlin/Heidelberg, Germany, 2015; Volume 9020, pp. 427–449. [Google Scholar]
Boyen, X. Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More. In PKC 2010; LNCS; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6056, pp. 499–517. [Google Scholar]
Nguyen, P.Q.; Zhang, J.; Zhang, Z. Simpler Efficient Group Signatures from Lattices. In PKC 2015; LNCS; Springer: Berlin/Heidelberg, Germany, 2015; Volume 9020, pp. 401–426. [Google Scholar]
Libert, B.; Ling, S.; Mouhartem, F.; Nguyen, K.; Wang, H. Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions. In ASIACRYPT 2016; LNCS; Springer: Berlin/Heidelberg, Germany, 2016; Volume 10032, pp. 373–403. [Google Scholar]
Ling, S.; Nguyen, K.; Wang, H.; Xu, Y. Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease. In ACNS 2017; LNCS; Springer: Cham, Switzerland, 2017; Volume 10355, pp. 293–312. [Google Scholar]
Ishida, A.; Sakai, Y.; Emura, K.; Hanaoka, G.; Tanaka, K. Fully Anonymous Group Signature with Verifier-Local Revocation. In SCN2018; LNCS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11035, pp. 23–42. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Fully Dynamic Group Signature Scheme with Member Registration and Verifier-local Revocation. In ICMC 2018; PROMS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 253, pp. 399–415. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Achieving Almost-Full Security for Lattice-Based Fully Dynamic Group Signatures with Verifier-Local Revocation. In ISPEC 2018; LNCS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11125, pp. 229–247. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Achieving Strong Security and Verifier-Local Revocation for Dynamic Group Signatures from Lattice Assumptions. In STM 2018; LNCS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11091, pp. 3–19. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Achieving Strong Security and Member Registration for Lattice-based Group Signature Scheme with Verifier-local Revocation. J. Internet Serv. Inf. Secur. 2018, 8, 1–15. [Google Scholar] [CrossRef]
Chu, C.K.; Liu, J.K.; Huang, X.; Zhou, J. Verifier-local revocation group signatures with time-bound keys. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, Seoul, Korea, 2–4 May 2012; pp. 26–27. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Almost-Fully Secured Fully Dynamic Group Signatures with Efficient Verifier-Local Revocation and Time-Bound Keys. In IDCS 2018; LNCS; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11226, pp. 134–147. [Google Scholar]
Perera, M.N.S.; Koshiba, T. Zero-Knowledge Proof for Lattice-Based Group Signature Schemes with Verifier-Local REVOCATION. In NBiS 2018; LNDECT; Springer: Berlin/Heidelberg, Germany, 2018; Volume 22, pp. 772–782. [Google Scholar]
Peikert, C. A Decade of Lattice Cryptography. Found. Trends Theor. Comput. Sci. 2016, 10, 283–424. [Google Scholar] [CrossRef]
Regev, O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In STOC 2005; ACM Press: New York, NY, USA, 2005; pp. 84–93. [Google Scholar]
Gentry, C.; Peikert, C.; Vaikuntanathan, V. Trapdoors for Hard Lattices and New Cryptographic Constructions. In ACM STOC 08; ACM: New York, NY, USA, 2008; pp. 197–206. [Google Scholar]
Ajtai, M. Generating hard instances of lattice problems. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 22–24 May 1996; pp. 99–108. [Google Scholar]
Micciancio, D.; Peikert, C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In EUROCRYPT 2012; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7237, pp. 700–718. [Google Scholar]
Agrawal, S.; Boyen, X.; Vaikuntanathan, V.; Voulgaris, P.; Wee, H. Functional Encryption for Threshold Functions (or Fuzzy IBE) from Lattices. In PKC 2012; LNCS; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7293, pp. 280–297. [Google Scholar]
Cash, D.; Hofheinz, D.; Kiltz, E.; Peikert, C. Bonsai Trees, or How to Delegate a Lattice Basis. In Eurocrypt 2010; LNCS; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6110, pp. 523–552. [Google Scholar]
Naor, D.; Shenhav, A.; Wool, A. One-time signatures revisited: Have they become practical? IACR Cryptol. Eprint Arch. 2005, 2005, 442. [Google Scholar]
Chow, S.S.; Wong, D.S. Anonymous Identification and Designated-Verifiers Signatures from Insecure Batch Verification. In EuroPKI 2007; LNCS; Springer: Berlin/Heidelberg, Germany, 2007; Volume 4582, pp. 203–219. [Google Scholar]
Kawachi, A.; Tanaka, K.; Xagawa, K. Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems. In ASIACRYPT 2008; LNCS; Springer: Berlin/Heidelberg, Germany, 2008; Volume 5350, pp. 372–389. [Google Scholar]
Pointcheval, D.; Vaudenay, S. On Provable Security for Digital Signature Algorithms; Ecole Normale Supérieure, Laboratoire d’Informatique: Paris, France, 1996. [Google Scholar]

Figure 1. Almost-full anonymity.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Perera, M.N.S.; Koshiba, T. Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation. Cryptography 2020, 4, 33. https://doi.org/10.3390/cryptography4040033

AMA Style

Perera MNS, Koshiba T. Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation. Cryptography. 2020; 4(4):33. https://doi.org/10.3390/cryptography4040033

Chicago/Turabian Style

Perera, Maharage Nisansala Sevwandi, and Takeshi Koshiba. 2020. "Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation" Cryptography 4, no. 4: 33. https://doi.org/10.3390/cryptography4040033

APA Style

Perera, M. N. S., & Koshiba, T. (2020). Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation. Cryptography, 4(4), 33. https://doi.org/10.3390/cryptography4040033

Article Menu

Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation †

Abstract

1. Introduction

1.1. Member Revocation Approaches

1.2. Group Signature Schemes from Lattice Assumptions

1.3. Our Contribution

1.4. Road Map

2. Preliminaries

2.1. Notations

2.2. Lattices

2.3. Lattice Hardness Assumptions

2.3.1. Approximate Shortest Independent Vectors Problem ( S I V P γ )

2.3.2. Learning With Errors (LWE)

2.3.3. Short Integer Solution ( S I S n , m , q , β )

2.4. Lattice-Related Trapdoors

2.5. VLR Group Signatures

2.6. Some Other Techniques

3. Definitions of the Security Notations

3.1. Anonymity

3.2. Coping with Revocation queries for Full Anonymity

3.3. Almost Full Anonymity

3.4. Traceability

4. The Underlying Zero Knowledge Interactive Protocol

4.1. Preparation Step

4.2. Description of the Protocol

5. Our VLR Group Signature Scheme

5.1. Description of Our Scheme

6. Correctness and Security Proof of the Scheme

6.1. Correctness

6.2. Almost-Full Anonymity

6.3. Traceability

7. Conclusion and Open Problems

Author Contributions

Funding

Acknowledgments

Conflicts of Interest

Appendix A. Analysis of the Underlying Zero-Knowledge Protocol

Appendix A.1. Completeness and Soundness

Appendix A.2. Communication Cost

Appendix A.3. Zero-Knowledge Property

Appendix A.4. Argument of Knowledge

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Almost Fully Secured Lattice-Based Group Signatures with Verifier-Local Revocation^†

2.3.1. Approximate Shortest Independent Vectors Problem ( $S I V P_{γ}$ )

2.3.3. Short Integer Solution ( $S I S_{n, m, q, β}$ )