Benoît Libert

Fabrice Mouhartem

Khoa Nguyen

A Lattice-Based Group Signature Scheme with Message-Dependent Opening

Keywords: Group signatures, anonymity, lattice assumptions

Group signatures are an important anonymity primitive allowing users to sign messages while hiding in a crowd. At the same time, signers remain accountable since an authority is capable of deanonymizing signatures via a process called opening. In many situations, this authority is granted too much power as it can identify the author of any signature. Sakai et al. proposed a flavor of the primitive, called Group Signature with Message-Dependent Opening (GS-MDO), where opening operations are only possible when a separate authority (called "admitter") has revealed a trapdoor for the corresponding message. So far, all existing GS-MDO constructions rely on bilinear maps, partially because the message-dependent opening functionality inherently implies identity-based encryption. This paper proposes the first GS-MDO candidate based on lattice assumptions. Our construction combines the group signature of Ling, Nguyen and Wang (PKC'15) with two layers of identity-based encryption. These components are tied together using suitable zero-knowledge argument systems.

Introduction

Group signatures. Group signatures were introduced by Chaum and van Heyst in 1991 [START_REF] Chaum | Group signatures[END_REF] as a technique allowing users to sign messages while retaining anonymity within a crowd of users they belong to. At the same, misbehaving group members cannot remain unpunished as an authority, called opening authority, is capable of tracing a signature to the user who generated it [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF]. While such a tracing mechanism is necessary to ensure user accountability, it arguably grants excessive power to the opening authority which can retrieve the identity of any well-behaved user from his signature. To address this issue, Sakai et al. [START_REF] Sakai | Group signatures with message-dependent opening[END_REF] suggested an extension, named group signature with message dependent opening (GS-MDO), which provides a refined balance between accountability and privacy. In GS-MDO systems, as formalized in [START_REF] Sakai | Group signatures with message-dependent opening[END_REF], the identity of a signer can only be determined from two pieces of information: the opening authority's secret key and a message-specific token delivered by a separate authority called the admitter. Importantly, neither authority is able to trace any signature alone. Each opening operation has to be approved by the admitter and, at the same time, the latter cannot identify signers by itself as it is denied access to the opening authority's secret key.

A different way to avoid centralizing the opening capability would be to split the opening authority's private key into several shares scattered among multiple servers using techniques from threshold cryptography [START_REF] Desmedt | Threshold cryptosystems[END_REF]. This approach, however, requires all shareholders to run a distributed decryption protocol (indeed, any group signature implies a public-key encryption scheme [START_REF] Abdalla | On the minimal assumptions of group signature schemes[END_REF]) at every single opening operation, even for identical messages. The GS-MDO primitive comes in handy when many signatures have to be opened on the same message. As a motivating example, we can think of access control gates in public transportation. In order to enter a metro station, the user can generate a signature (i.e., on a message specifying the date and time or his ride) proving his possession of a valid subscription without betraying his identity nor leaking any information on his habits (e.g., the frequency of his rides). If an accident occurs or a crime is committed, the police -which embodies the opening authority in this case -can request the opening tokens for to the time period of the incident and determine who was nearby at that time. In such a situation, the threshold opening approach would incur a substantial overhead to open all the signatures generated by commuters in a given time interval. In contrast, the GS-MDO primitive allows de-anonymizing all signatures corresponding to a given message -no matter how many users signed this message -without having the police interact any further with the public transportation company once the latter has revealed a message-specific token.

As another motivating application, we can think of anonymous comments posted on a blog engine, where a moderator can use a token to open all signatures related to forbidden messages. Yet another example consists of anonymous auctions where bidders sign the amount of their bid: in case of equalities, a single token allows identifying the multiple winners of the auction.

As such, message-dependent openings are relevant when the number of signatures to be opened is potentially high. Moreover, it can be seen as providing the dual functionality of traceable signatures [START_REF] Kiayias | Traceable signatures[END_REF]. As introduced by Kiayias, Tsiounis and Yung [START_REF] Kiayias | Traceable signatures[END_REF], traceable signatures allow the group manager to release a user-specific trapdoor using which all the signatures that user created can be identified. This extended capability allows delegating the tracing operation to parallel tracing agents who can detect all the transactions where a misbehaving user is involved without affecting the anonymity of honest users. Group signatures with message-dependent opening can be motivated in a similar way in that the distributed tracing process can be made with respect to the message rather than the users. If a signed message contains information about a specific suspicious transaction, releasing a message-specific trapdoor makes it possible to trace all parties involved in a given transaction determined by the signed message.

Lattice-based cryptography. Since the results of Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and Gentry-Peikert-Vaikuntanathan [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], lattice-based cryptography has emerged (see [START_REF] Peikert | A decade of lattice cryptography[END_REF] and references therein) as a promising alternative to discrete-logarithm or factoringbased technologies. This trend can be explained by the fact that lattices provide Even in the random oracle model, the design of lattice-based group signatures with extra properties remains a non-trivial problem. In particular, no GS-MDO system has been proposed so far. In fact, except the theoretical construction of Sakai et al. [START_REF] Sakai | Group signatures with message-dependent opening[END_REF], all existing solutions [START_REF] Sakai | Group signatures with message-dependent opening[END_REF][START_REF] Ohara | A group signature scheme with unbounded message-dependent opening[END_REF][START_REF] Libert | Group signatures with message-dependent opening in the standard model[END_REF] rely on bilinear maps. For the sake of not putting all one's eggs in the same basket, it is thus important to seek constructions based on different assumptions.

Our Contribution. We propose the first GS-MDO realization based on standard lattice assumptions. The security of our scheme is proved in the random oracle model under SIS and LWE assumptions. We design this scheme by extending the group signature scheme of Ling, Nguyen and Wang [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], which is recalled in Appendix C.1. Not only does this scheme provide one of the most efficient candidates so far, its built-in zero-knowledge arguments turn out to be sufficiently flexible to accommodate our statements in the setting of message-dependent openings. Like [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], our construction proceeds by having each group member's signing key consist of a Boyen [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF] signature for his identity d ∈ {0, 1} . To sign a message M , the user encrypt his identity d using an IND-CCA encryption scheme derived from the Gentry-Peikert-Vaikuntanathan (GPV) IBE [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] via the Canetti-Halevi-Katz (CHK) paradigm [START_REF] Canetti | Chosen-ciphertext security from identity-based encryption[END_REF]. Then, the user provides a ZK argument of possession of a Boyen signature for the message encrypted by the ciphertext, the message being embedded in the Fiat-Shamir challenge to make the proof non-interactive. Our scheme takes advantage of the fact that Ling et al. [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] used an IBE to encrypt the group member's identifier. We add a second encryption layer in order to encrypt the ciphertext under the identity M , which is the message to be signed. Therefore, the GS-MDO functionality can be achieved by combining two instances of the GPV IBE (one for the admitter and the second one for the opening authority). To reveal a message-specific token t M , the admitter can simply output a private key for the identity M , then allowing the opener to retrieve the ciphertext hiding the identity. Then, using the encryption layer as in the Ling et al. scheme [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] allows us to adapt the underlying argument system to our purpose. Now, the challenge is to prove that the entire double-encryption process was conducted properly. To this end, we can leverage the properties of Stern-like protocols [START_REF] Stern | A new paradigm for public key identification[END_REF] and translate the statements to be proved so as to apply the recently proposed framework of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. Our argument system, while addressing a more elaborate relation than in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], is constructed in a simpler and more modular manner. In short, we reduce the entire statement into an assertion of the form P • x = v mod q, where P is a public matrix that depends on the group public key and the outer ciphertext layer, while x is a short vector which is constructed from the witness and has a special structure.

We can also notice that our technique can be used to enable message-dependent opening in the case of dynamically growing groups as well. For instance, the two-layer encryption method can be straightforwardly adapted to the dynamic group signature scheme from Libert et al. [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] which is also built upon the Ling et al. scheme [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] and also relies on Stern-like ZK arguments.

Roadmap. To present our results, the rest of the paper is organized as follows.

In Section 2, we first recall the necessary definitions and security notions. The supporting zero-knowledge argument system is constructed in Section 3. In Section 4, we present our lattice-based GS-MDO scheme.

Background

Notations. Matrices are denoted with bold upper-case letters A and vectors in bold lower-case letters x. We assume that all vectors are column vectors. The concatenation of vectors x ∈ R k and y ∈ R m is denoted by (x y) ∈ R k+m . We denote the column concatenation of matrices A ∈ R n×k and B ∈ R n×m by [A|B]. If dimensions are compatible, u, v denote the inner product of vectors u and v. The identity matrix of order k is denoted by I k , and 0 stands for the zero vector of dimension . If A is a full column rank matrix, we let A denote its Gram-Schmidt orthogonalization. If u ∈ R n , its Euclidean norm is denoted by b and this notation is extended to matrices A ∈ R n×m with columns (a i ) i≤m by A = max i≤m a i . Finally, PPT stands for Probabilistic Polynomial-Time.

Lattices

A lattice Λ is a discrete subgroup of some space R n , which can be seen as the set of integer linear combinations of linearly independent vectors (b i ) i≤n . Over a lattice Λ, and given a parameter σ ∈ R * + , we define the Gaussian distribution of support Λ and parameter σ by

D Λ,σ [b] ∼ exp -π b 2 /σ 2 ,
for all b ∈ Λ. We will use the fact that samples from D Λ,σ are short with overwhelming probability.

Lemma 1 ([4, Le. 1.5]).

For any lattice Λ ⊆ R n and positive real number σ, we have

Pr b← D Λ,σ [ b ≤ √ nσ] ≥ 1 -2 -Ω(n) .
Gentry, Peikert and Vaikuntanathan [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] show that it is possible to efficiently sample from a Gaussian distribution on a lattice support given a sufficiently short basis of this lattice.

Lemma 2 ([12, Le. 2.3]).

There exists a PPT algorithm GPVSample that takes as inputs a basis B of a lattice Λ ⊆ Z n and rational σ ≥ B • Ω( √ log n), and outputs vectors b ∈ Λ with distribution D Λ,σ . Definition 1. Let m ≥ n ≥ 1 and q ≥ 2. For a matrix A ∈ Z n×m q , and a vector

u ∈ Z n q , define Λ q (A) := {x ∈ Z m : ∃s ∈ Z n s.t. A T • s = x mod q} and Λ ⊥ q (A) := {x ∈ Z m : A • x = 0 mod q}, Λ u q (A) := {x ∈ Z m : A • x = u mod q}.
We also use an algorithm that jointly samples an uniform matrix A and a short basis of the lattice Λ ⊥ q (A).

Lemma 3 ([2, Th. 3.2]

). There exists a PPT algorithm GenTrap that takes as inputs 1 n , 1 m and an integer q ≥ 2 with m ≥ Ω(n log q), and outputs a matrix A ∈ Z n×m q and a basis T A of Λ ⊥ q (A) such that A is within statistical distance 2 -Ω(n) to U (Z n×m q ), and

T A ≤ O( √ n log q).
The description of our scheme also uses an algorithm that extends a trapdoor for A ∈ Z n×m q to a trapdoor of any B ∈ Z n×m q whose left n × m submatrix is A.

Lemma 4 ([15, Le. 3.2]

). There exists a PPT algorithm ExtBasis that takes as inputs a matrix B ∈ Z n×m q whose first m columns span Z n q , and a basis T A of Λ ⊥ q (A) where A is the left n × m submatrix of B, and outputs a basis T B of Λ ⊥ q (B) with T B ≤ T A .

Hardness assumptions

We prove the security of our scheme in the ROM among the assumption that both algorithmic problems below are hard, in the sense that they cannot be solved by any PPT algorithm with non-negligible probability nor advantage respectively.

Definition 2. Let m, q, β be functions of a parameter n. The Short Integer Solution problem SIS m,q,β is as follows:

Given A ← U (Z n×m q ), find x ∈ Λ ⊥ q (A) with 0 < x ≤ β.
Definition 3. Let q, α be functions of a parameter n. For s ∈ Z n q (a secret), the distribution A q,α,s over Z n q × Z q is obtained by sampling a ← U (Z n q ) and (a noise) e ← D Z,αq , and returning (a, a, s + e). The Learning With Errors problem LWE q,α is as follows: For s ← U (Z n q ), distinguish between arbitrarily many independent samples from U (Z n q × Z q ) and the same number of independent samples from A q,α,s .

If q ≥ √ nβ and m, β ≤ poly(n), then standard worst-case lattice problems with approximation factors γ = O(β √ n) reduce to SIS m,q,β (see for instance [20, Se. 9]). Similarly, if αq = Ω( √ n), then standard worst-case lattice problems with approximation factors γ = O(α/n) quantumly reduce to LWE q,α (see [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] as well as [START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] for classical analogues).

Group Signature with Message Dependent Opening

We use the syntax of Sakai et al. [START_REF] Sakai | Group signatures with message-dependent opening[END_REF] to describe a GS-MDO, which extends the model of Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF].

Definition 4 (GS-MDO).

A group signature with message-dependent opening is a tuple of algorithms (Keygen, Sign, Verify, TrapGen, Open) such that: Keygen(1 λ , 1 N ): Given a security parameter λ and the number of group members N , outputs the group public key gpk, the opening key ok, the the admitter's private key msk ADM , and a vector of user secret keys gsk = (gsk[d]) N -1 d=0 .

Sign(gpk, gsk[d], M ): Given an user d secret key gsk[d]

and a message M , issue a signature Σ for the message M . Verify(gpk, M, Σ): Given a message M and a signature Σ, output 0 or 1. TrapGen(gpk, msk ADM , M ): Given the admitter key msk ADM , and a message M , output a token t M . Open(gpk, ok, t M , M, Σ): Given the opening key ok, a message M , a token t M for this message, and a signature Σ, return either d ∈ N, or ⊥.

These algorithms must also verify the correctness property, meaning that for all (gpk, gsk, ok, msk ADM ) ← Keygen(1 λ , 1 N ), for all d ∈ {0, . . . , N -1}, and for all M ∈ {0, 1} * , we have w.h.p. Verify(gpk, M, Sign(gpk, gsk[d], M )) = 1 and Open(gpk, ok, TrapGen(gpk, msk

ADM , M ), M, Sign(gpk, gsk[d], M )) = d.
Like in a classical group signature, the scheme must verify Traceability and Anonymity, but since the opening capability is split in two entities, namely the admitter and the opening authority (also known as the group manager), they therefore are two anonymity definitions: the Opener Anonymity and the Admitter Anonymity, which are formalized as follows.

Definition 5 (Traceability). A GS-MDO scheme provides full traceability if, for any λ ∈ N, any N ∈ poly(λ) and any PPT adversary A involved in the experiment below, it holds that Adv

trace A (λ) = Pr[Exp trace A (λ, N ) = 1] ∈ negl(λ). Exp trace A (λ, N ) (gpk, ok, msk ADM , gsk) ← Keygen(λ, N ) st ← (ok, msk ADM , gpk) ; C ← ∅ ; K ← ε ; Cont ← true while (Cont = true) do (Cont, st, j) ← A Sign(gsk[•],•) (choose, st, K) if Cont = true then C ← C ∪ {j} ; K ← K ∪ {gsk[j]} end if (M , σ ) ← A Sign(gsk[•],•) (guess, st) if Verify(gpk, M , σ ) = 0 then Return 0 if Open(gpk, ok, TrapGen(gpk, msk ADM , M ), M , σ ) =⊥ then Return 1 if ∃j ∈ {0, . . . , N -1} such that (Open(gpk, ok, tM , M , σ ) = j ) ∧ (j / ∈ C) ∧ ((j , M
) not queried by A) with tM ← TrapGen(gpk, msk ADM , M ) then Return 1 else Return 0

Definition 6 (Admitter Anonymity). A GS-MDO scheme provides full anonymity against the admitter if, for any λ ∈ N, any N ∈ poly(λ) and any PPT adversary A involved in the experiment hereunder, we have

Adv anon-adm A (λ) = | Pr[Exp anon-adm A (λ, N ) = 1] -1/2| ∈ negl(λ). Exp anon-adm A (λ, N ) (gpk, ok, msk ADM , gsk) ← Keygen(λ, N ) (st, j0, j1, M ) ← A O ok (choose, gpk, gsk, msk ADM ) b ← {0, 1}; σ ← Sign(gpk, gsk[j b ], M ) b ← A O ok (guess, st, σ ) Return 1 if b = b and 0 otherwise
Here, O ok is an oracle that takes as input an arbitrary signature σ = σ and uses ok and msk ADM to return the identity of the signer.

Definition 7 (Opener Anonymity).

A GS-MDO scheme provides full anonymity against the opener if, for any λ ∈ N, any N ∈ poly(λ) and any PPT adversary A involved in the experiment below, it holds that

Adv anon-oa A (λ) = | Pr[Exp anon-oa A (λ, N ) = 1] -1/2| ∈ negl(λ). Exp anon-oa A (λ, N ) (gpk, ok, msk ADM , gsk) ← Keygen(λ, N ) (st, j0, j1, M ) ← A O msk ADM (choose, gpk, gsk, ok) b ← {0, 1}; σ ← Sign(gpk, gsk[j b ], M ) b ← A O msk ADM (guess, st, σ ) Return 1 if b = b and 0 otherwise
In the above notation, O msk ADM (.) is an oracle that returns trapdoors for arbitrary messages M = M chosen by the adversary.

Zero-Knowledge Arguments of Knowledge

We will work with statistical zero-knowledge argument systems, namely, interactive protocols where the zero-knowledge property holds against any cheating verifier, while the soundness property only holds against computationally bounded cheating provers. More formally, let the set of statements-witnesses R = {(y, w)} ∈ {0, 1} * × {0, 1} * be an NP relation. A two-party game P, V is called an interactive argument system for the relation R with soundness error e if the following two conditions hold:

-Completeness. If (y, w) ∈ R then Pr P(y, w), V(y) = 1 = 1. -Soundness. For any PPT P, if (y, w) ∈ R, then Pr[ P(y, w), V(y) = 1] ≤ e.
An argument system is called statistical zero-knowledge if for any V(y), there exists a PPT simulator S(y) producing a simulated transcript that is statistically close to the one of the real interaction between P(y, w) and V(y). A related notion is argument of knowledge, which requires the witness-extended emulation property. For protocols consisting of 3 moves (i.e., commitment-challenge-response), witnessextended emulation is implied by special soundness [START_REF] Groth | Evaluating Security of Voting Schemes in the Universal Composability Framework[END_REF], where the latter assumes that there exists a PPT extractor which takes as input a set of valid transcripts with respect to all possible values of the 'challenge' to the same 'commitment', and outputs w such that (y, w ) ∈ R.

Our statistical zero-knowledge arguments of knowledge (sZKAoK) are Sterntype [START_REF] Stern | A new paradigm for public key identification[END_REF]. In particular, they are Σ-protocols in the generalized sense defined in [START_REF] Jain | Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise[END_REF][START_REF] Benhamouda | Better zero-knowledge proofs for lattice encryption and their application to group signatures[END_REF] (where 3 valid transcripts are needed for extraction, instead of just 2).

The Underlying Zero-Knowledge Argument System

First of all, we recall that the protocol from [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] allows prover P to convince verifier V in ZK that P knows a valid message-signature pair (d, z) for Boyen's signature scheme [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF], and that the binary representation of d is honestly encrypted to a given ciphertext pair (c 1 , c 2 ). The strategy in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] was to extend Stern's protocol [START_REF] Stern | A new paradigm for public key identification[END_REF] (via the Decomposition-Extension technique [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[END_REF]) to prove the statement in a ad-hoc manner. However, their argument system was rather complicated, which makes it somewhat inflexible to be used as a sub-protocol in designing more advanced constructions.

The goal of this section is to construct the statistical zero-knowledge argument of knowledge (sZKAoK) underlying the GS-MDO scheme of Section 4. In our setting, the ciphertext component c 2 is hidden, and P can additionally prove that the secret bits representing c 2 are correctly encrypted to another given ciphertext pair (ĉ 1 , ĉ2 ). By using the new strategy for Stern-like protocols, recently proposed in [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF], we can handle the extended relation, yet the resulting argument system is obtained in a simpler and more modular manner than in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF].

More formally, let n, m, , q, β, b be positive integers and k = log q . Let

H = I ⊗ 1 | 2 | 4 | • • • | 2 k-1 ∈ Z × k q
, and let bin : Z q → {0, 1} k be the function mapping w to its component-wise binary decomposition bin(w). (Note that for all w ∈ Z q , we have H • bin(w) = w.) We define as well the binary decomposition function for integer bin : N → {0, 1} . The relation R gsmdo associated with our protocol is then defined as follows.

     A, {A i } i=0 , B, C ∈ Z n×m q ; G ∈ Z n× q ; Ĝ ∈ Z n× k q ; u ∈ Z n q ; c 1 , ĉ1 ∈ Z m q ; ĉ2 ∈ Z k q ; d = (d 1 , . . . , d ) ∈ {0, 1} ; z ∈ [-β, β] 2m ; s, ŝ ∈ [-b, b] n ; e 1 , ê1 ∈ [-b, b] m ; e 2 ∈ [-b, b] ; ê2 ∈ [-b, b] k ; c 2 ∈ Z q satisfy                A|A 0 + i=1 d i • A i • z = u mod q (1) c 1 = B • s + e 1 mod q; c 2 = G • s + e 2 + q 2 • d mod q (2) ĉ1 = C • ŝ + ê1 mod q; ĉ2 = Ĝ • ŝ + ê2 + q 2 • bin(c 2 ) mod q. ( 3
)
In Section 3.1, we present Stern's protocol from a high-level point of view, according to the abstraction of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. Then, via the transformations performed in Section 3.2, we show how to obtain a ZKAoK for R gsmdo based on this abstract protocol.

Stern's Protocol, from a High-Level Viewpoint

Let D, L, q ≥ 2 be positive integers and let VALID be a subset of {-1, 0, 1} L . Suppose that S is a finite set such that one can associate every π ∈ S with a permutation T π of L elements, satisfying the following condition:

x ∈ VALID ⇐⇒ T π (x) ∈ VALID. (4)
We aim to construct a sZKAoK for the following abstract relation:

R abstract = (P, v), x ∈ Z D×L q × Z D q × VALID : P • x = v mod q.
Note that, Stern's original protocol corresponds to the special case when VALID = {x ∈ {0, 1} L : wt(x) = k} (where wt(•) denotes the Hamming weight and k < L is a given integer), S = S L -hereunder the set of all permutations of L elements, and

T π (x) = π(x).
The equivalence in (4) plays a crucial role in proving in ZK that x ∈ VALID: To do so P samples π ← U (S) and let V check that T π (x) ∈ VALID, while the later cannot learn any additional information about x thanks to the randomness of π. Furthermore, to prove in ZK that the linear equation holds, P samples a masking vector r ← U (Z L q ), sends y = x + r mod q, and convinces V instead that P • y = P • r + v mod q.

The interactive protocol between P(P, v, x) and V(P, v), which employs a statistically hiding and computationally binding string commitment scheme COM (e.g., the SIS-based one from [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]), is described in Figure 1. In each case, V outputs 1 if and only if all the conditions hold. Otherwise, it outputs 0. The properties of the given protocol is summarized in the following lemma.

Lemma 5. The protocol in Figure 1 is a sZKAoK for the relation R abstract with perfect completeness, soundness error 2/3, and communication cost O(L log q). In particular:

-There exists an efficient simulator that, on input (P, v), 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 CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs x ∈ VALID such that P • x = v mod q.

The proof of Lemma 5 employs standard simulation and extraction techniques for Stern-type protocols [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Ling | Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Ezerman | A provably secure group signature scheme from code-based assumptions[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF]. We defer it to Appendix B.

From R gsmdo to R abstract

We show that a sZKAoK for relation R gsmdo in Definition 8 can be derived from the one for relation R abstract from Section 3.1. In the process, we employ the Decomposition-Extension technique from [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[END_REF], which we will formalize as follows.

-For any positive integer i, denote by B 2i the set of all vectors in {0, 1} 2i having exactly i coordinates equal to 1, and denote by B 3i the set of all vectors in {-1, 0, 1} 3i having exactly i coordinates equal to j, for every j ∈ {-1, 0, 1}. -Define, for any integer B > 0, the number δ B := log B + 1 and the sequence B 1 , . . . , B δ B , where

B j = B+2 j-1 2 j for all j ∈ [δ B ].
As noted in [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[END_REF], this sequence satisfies

H m,B =      B 1 . . . B δ B B 1 . . . B δ B . . . B 1 . . . B δ B      ∈ Z m×mδ B ,
and

H * m,B = H m,B 0 m×2mδ B ∈ Z m×3mδ B .
Lemma 6 (Decomposition-Extension). Let m, B be positive integers. Then, there exists an efficient algorithm that on input

vector v ∈ [-B, B] m , outputs vector v * ∈ B 3mδ B such that H * m,B • v * = v. Proof. Let v = (v 1 , . . . , v m ), where v i ∈ [-B, B] for all i ∈ [m]. For each i, one can efficiently find v i,1 , . . . , v i,δ B ∈ {-1, 0, 1} such that δ B j=1 B j • v i,j = v i . Let v = (v 1,1 , . . . , v 1,δ B , v 2,1 , . . . , v 2,δ B , . . . , v m,1 , . . . , v m,δ B ) ∈ {-1, 0, 1} mδ B , then H m,B • v = v. By appending 2mδ B suitable coordinates to v , one can obtain a vector v * ∈ B 3mδ B such that H * m,B • v * = v.
We now transform equations in Definition 8 into a unified equation of the form P•x = v mod q. Regarding Equation ( 1), if we write z as z = (z 1 z 2 ), where z 1 , z 2 ∈ [-β, β] m , and let z * 1 , z * 2 ∈ B 3mδ β be the vectors obtained by applying Lemma 6 to z 1 , z 2 , respectively, then we have:

u = A|A 0 + i=1 d i • A i • z = A • z 1 + A 0 • z 2 + i=1 d i • A i • z 2 mod q = (A • H * m,β ) • z * 1 + (A 0 • H * m,β ) • z * 2 + i=1 (A i • H * m,β ) • (d i • z * 2 ) mod q = A • z mod q,
where

A = A • H * m,β |A 0 • H * m,β |A 1 • H * m,β | . . . |A • H * m,β ∈ Z n×( +2)3mδ β q z = z * 1 z * 2 d 1 • z * 2 . . . d • z * 2 ∈ {-1, 0, 1} (
z * = z d +1 • z * 2 . . . d 2 • z * 2 and A * = A |0 n× 3mδ β ∈ Z n×(2 +2)3mδ β q
, then we have the following equation:

A * • z * = u mod q.
(5)

Meanwhile, we observe that ( 2) and ( 3) can be unified in the following form:

      0 q 2 I 0 0       d +       0 -H 0 q 2 I k       bin(c 2 ) +       B G I m+ 0 0 C Ĝ I m+ k               s e 1 e 2 ŝ ê1 ê2         =       c 1 0 ĉ1 ĉ2       .
For simplicity, we define n 1 = 2m + + k and m 1 = 2m + 2n + + k. In the above unified equation, let

F 1 ∈ Z n1× q , F 2 ∈ Z n1× k q
, and F 3 ∈ Z n1×m1 q be the matrices associated with d, bin(c 2 ), and e = s e 1 e 2 ŝ ê1 ê1 ∈ [-b, b] m1 , respectively. Let c = c 1 0 ĉ1 ĉ2 ∈ Z n1 q , then the equation becomes:

F 1 • d + F 2 • bin(c 2 ) + F 3 • e = c mod q.
We then extend bin(c 2 ) ∈ {0, 1} k to vector bin * (c 2 ) ∈ B 2 k , and apply Lemma 6 to vector e to obtain e * ∈ B 3m1δ b . Furthermore, let y * = d * bin * (c 2 ) e * , and

F * = F 1 |0 n1× |F 2 |0 n1×nk |F 3 • H * m1,b ∈ Z n1×(2 +2 k+3m1δ b ) q
, then we have:

F * • y * = c mod q. ( 6
)
In the last step of our transformations, we let L = (2 + 2)3mδ β + 2 + 2 k + 3m 1 δ b and D = n + n 1 , and define matrix 5) and ( 6) are now unified as:

P = A * 0 0 F * ∈ Z D×L q , vector x = z * y * ∈ {-1, 0, 1} L , vector v = u c ∈ Z D q . Equations (
P • x = v mod q. ( 7
)
Having obtained the desired equation ( 7), we now specify the set VALID to which x belongs, the set S and permutations of L elements {T π : π ∈ S} for which the equivalence (4) holds.

-VALID: the set of all vectors t ∈ {-1, 0, 1} L having the form:

t = t 1 t 2 g 1 • x 2 . . . g 2 • t 2 g t 3 t 4 for some t 1 , t 2 ∈ B 3mδ β , g = (g 1 , . . . , g 2 ) ∈ B 2 , t 3 ∈ B 2 k , t 4 ∈ B 3m1δ b . -S = S 3mδ β × S 3mδ β × S 2 × S 2 k × S 3m1δ b .
-For π = (φ, ψ, τ, σ, η) ∈ S and w = ŵ w w 1 . . . w 2 w ẅ w ∈ Z L q , where ŵ, w, w 1 , . . . ,

w 2 ∈ Z 3mδ β q , w ∈ Z 2 q , ẅ ∈ Z 2 k q , w ∈ Z 3m1δ b q
, we define:

T π (w) = φ( ŵ) ψ( w) ψ(w τ (1) ) . . . ψ(w τ (2 ) ) τ ( w) σ( ẅ) η( w)
as the permutation that transforms w as follows:

1. It rearranges the order of the 2 blocks w 1 , . . . , w 2 according to τ . 2. It then permutes block ŵ according to φ, blocks w, {w i } 2 i=1 according to ψ, block w according to τ , block ẅ according to σ, and block w via η.

By inspection, it can be seen that

x = z * 1 z * 2 d 1 • z * 2 . . . d 2 • z * 2 d * bin * (c
2 ) e * ∈ VALID, and that the property (4) is satisfied, as desired. As a result, we can obtain a sZKAoK for R gsmdo by running the protocol in Figure 1 with common input (P, v) and prover's input x.

Putting everything together, we have the following theorem.

Theorem 1. There exists a Stern-type ZKAoK for the relation R gsmdo with perfect completeness, soundness error 2/3, and communication cost O(L log q). In particular:

-There exists an efficient simulator that, on input (A, {A i } i=0 , B, C, G, Ĝ, u, c 1 , ĉ1 , ĉ2 ), 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 CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs a tuple (d , z , s , ŝ , e 1 , ê 1 , e 2 , ê 2 , c 2 ) such that:

(A, {A i } i=0 , B, C, G, Ĝ, u, c 1 , ĉ1 , ĉ2 ), d , z , s , ŝ , e 1 , ê 1 , e 2 , ê 2 , c 2 ∈ R gsmdo .
The proof of Theorem 1 is straightforward. For simulation, we run the simulator of Lemma 5. For extraction, we run the knowledge extractor of Lemma 5, and then "backtrack" the described above transformations to obtain a satisfying witness for R gsmdo . We thus omit the details.

A GS-MDO Scheme based on Lattice Assumptions

Our scheme is described and analyzed in the model of Sakai et al. [START_REF] Sakai | Group signatures with message-dependent opening[END_REF], which is described in Section 2.3. Our GS-MDO scheme builds on the Ling et al. [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] group signature, which is recalled in Appendix C.1. In order to enable message-dependent openings, we add an encryption layer to the previous scheme using an IBE where the signed message serves as the receiver's identity. The admitter, which holds the master secret key for this IBE, is able to derive a message-specific token consisting of an IBE private key for this "identity". By itself, this information is insufficient to open the signature as it uncovers a second ciphertext embedded in the message space of the initial encryption layer. At the same time, the opening authority only has access to the external encryption layer which prevents it from identifying the signer without the message-specific token. Now, the challenge is to prove that the entire double-encryption process was conducted properly while proving the knowledge of a Boyen signature at the same time. As demonstrated in Section 3, we solve this challenge by leveraging the properties of Stern-like protocols [START_REF] Stern | A new paradigm for public key identification[END_REF] and translating the statements to be proved so as to apply the technique of Section 3.

To encrypt the user's identity d ∈ {0, 1} , we apply a multi-bit variant of the dual Regev system [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] and obtain a first-layer encryption

(c 1 , c 2 ) = B T s + e 1 , G T s + e 2 + q/2 • bin(d) ,
where B ∈ Z n×m q is the master public key of the underlying IBE, e 1 , e 2 are small noise vectors and G ∈ H 1 (ovk) ∈ Z n× q is derived by hashing a one-time signature verification key (recall that, as in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], we achieve anonymity in the CCA2 sense by applying the CHK paradigm [START_REF] Canetti | Chosen-ciphertext security from identity-based encryption[END_REF] using ovk as the receiver's identity). Then, we use a second IBE layer to encrypt the binary decomposition of c 2 ∈ Z q . In this second IBE instance, we use a matrix C ∈ Z n×m q and compute (ĉ 1 , ĉ2 ) = C T ŝ + ê1 , ĜT ŝ + ê2 + q/2 • bin(c 2 ) , for suitable noise vectors ê1 , ê2 and where Ĝ = H 2 (M ) ∈ Z n× log q q is an IBE public key obtained by hashing the "identity" M . (Note that the two IBE layers use distinct random oracles H 1 and H 2 .)

Now, the problem is to demonstrate the proper computation of (c 1 , c 2 ) and (ĉ 1 , ĉ2 ). This can be achieved by proving knowledge of bin(c

2 ) ∈ {0, 1} log q , s, ŝ ∈ Z n , e 1 , ê1 ∈ Z m , e 2 ∈ Z , e 2 ∈ Z log q satisfying:      B T I m 0 0 0 -G T 0 -I H -q/2 • I C T I m 0 0 ĜT I log q q/2 • I log q 0      •      s e1 e2 ŝ ê1 ê2 bin(c2) bin(d)      =     c 1 0 ĉ1 ĉ2     ,
where H is defined as in Section 3. The second and fourth block relations ensure that that c 2 is the message encrypted by ĉ2 while this hidden c 2 encrypts bin(d).

We are left with arguing knowledge of a Boyen signature on bin(d) ∈ {0, 1} , which can be achieved as in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF].

Description of the Scheme

The parameters are set in such a way that the Boyen signature and the GPV IBE scheme function properly and are secure. Let n = O(λ) be the lattice parameter, N = 2 = poly(λ) be the number of group members, q = O( • n 2 ) be a prime modulus, β = O( √ n) be the infinity norm bound for signatures generated by Boyen's scheme [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF], and b such that q/b = • O(n) be the infinity norm bound for LWE noises sampled from error distribution χ.

Keygen(1 λ , 1 N ): This algorithm performs the following steps:

1. Generate a verification key (A, A 0 , . . . , A , u) ∈ (Z n×m q ) +2 × Z n q and a private key T A ∈ Z m×m for Boyen's signature scheme. Then for each d ∈ {0, . . . , 2 -1}, define the corresponding private key

gsk[d] = (v T d,1 | v T d,2
) T ∈ Z 2m to be the Boyen's signature for the message bin(d) = (d 1 , . . . , d ) ∈ {0, 1} using the trapdoor T A . 2. Generate two encryption and decryption key pairs for the GPV-IBE scheme: the matrix B ∈ Z n×m q along with its trapdoor basis T B ∈ Z m×m and the matrix C ∈ Z n×m q with its trapdoor T C ∈ Z m×m using the GenTrap algorithm from Gentry et al. [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] described in Lemma 3. 3. Select a strong one-time signature Π OTS = (OKeygen, OSign, OVer) and hash functions

H 1 : {0, 1} * → Z n× q , H 2 : {0, 1} * → Z n× log q q . 4. Output ok = T B , msk ADM = T C , gsk = gsk[d] N -1 d=0 and gpk = A, {A i } i=0 , u, B, C, Π OTS , H 1 , H 2 ,

Sign(gpk, gsk[d],

M ): To sign M using a group private key gsk[d],

1. Generate a key pair (ovk, osk) ← OKeygen(1 λ ) for the signature Π OTS . 2. Encrypt the message d with respect to the "identity" ovk using the GPV IBE [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. Namely, let G = H 1 (ovk) ∈ Z n× q . Sample s ← χ n ; e 1 ← χ m ; e 2 ← χ , and compute the ciphertext

c 1 = B T s + e 1 , c 2 = G T s + e 2 + q/2 • bin(d) ∈ Z m q × Z q .
3. Using the GPV IBE again, encrypt the ciphertext c 2 w.r.t the "identity" M . In other words, let Ĝ = H 2 (M ) ∈ Z n× log q q

, then sample ŝ ← χ n ; ê1 ← χ m , ê2 ← χ log q and compute the ciphertext

ĉ1 = C T ŝ + ê1 , ĉ2 = ĜT ŝ + ê2 + q/2 • bin(c 2 ) ∈ Z m q × Z log q q .
4. Generate a NIZKAoK Π to prove the possession of a valid messagesignature pair (d, z) for Boyen's signature, and that (ĉ 1 , ĉ2 ) is a correct encryption of c 2 under the identity M , where (c 1 , c 2 ) is a correct encryption of d = bin(d) under the identity ovk. To do this, run the interactive argument system for the relation R gsmdo in Section 3 with public input (A, {A i } i=0 , B, C, G, Ĝ, u, c 1 , ĉ1 , ĉ2 ) and prover's input (d, z, s, ŝ, e 1 , ê1 , e 2 , ê2 , c 2 ). The protocol is repeated t = ω(log n) times to get a negligible soundness error, and then made non-interactive using the Fiat-Shamir heuristic, which gives Π = {Comm j } t j=1 , Chall, {Resp j } t j=1 , where

Chall = H(M, ovk, {Comm j } t j=1 , c 1 , ĉ1 , ĉ2 ) ∈ {1, 2, 3} t .
5. Compute a one-time signature sig = OSign(osk; c 1 , ĉ1 , ĉ2 , Π).

6. Output Σ = ovk, c 1 , ĉ1 , ĉ2 , Π, sig .
Verify(gpk, M, Σ): Σ = (ovk, c 1 , ĉ1 , ĉ2 , Π, sig is verified w.r.t. M as follows:

1. If OVer(ovk; sig; c 1 , ĉ1 , ĉ2 , Π) = 0, return 0. 2. Verify the validity of the proof Π, if it fails, return 0.

3. If everything went correctly, then return 1. TrapGen(gpk, msk ADM , M ): To generate a token t M .

1. If a token for a message M was already queried, answer consistently. 2. Otherwise, derive a key for the identity M using the master secret key T C ∈ Z m×m . Namely compute Ĝ = H 2 (M ), then using SamplePre, compute a small-norm matrix

E M ∈ Z m× log q such that C • E M = Ĝ. 3. Output t M = E M . Open(gpk, ok, t M , Σ, M ):
To open Σ(ovk, c 1 , ĉ1 , ĉ2 , Π, sig using the opening key ok and the token for the message t M , do the following:

1. Decrypt (ĉ 1 , ĉ2 ) using t M : c 2 = H • (ĉ 2 -t M T • ĉ1 ) • (q/2) . 2. Decrypt (c 1 , c 2 ) using ok = T B ∈ Z m×m , namely compute G = H 1 (ovk),
and using SamplePre to get a short-norm matrix F ∈ Z m× such that B • F = G, and finally compute

d = 1 | 2 | 4 | • • • | 2 -1 • (c 2 -F T • c 1 ) • (q/2) .
3. Verify that d belongs to a valid user, if not return ⊥, otherwise return d.

Security

The security of the above construction has been proven in the ROM under LWE and SIS assumptions as evidenced in the following theorems. The proofs of Theorems 2, 3 and 4 are available in Appendix A.

Theorem 2.

In the random oracle model, the above group signature scheme is fully traceable under the assumption that the SIS problem is hard.

Theorem 3. The above group signature scheme is fully anonymous against the admitter under the LWE assumption, and assuming that the one-time signature scheme Π OTS is strongly unforgeable. Game 1. In this game, we make a small modification with respect to Game 0. At the outset of the game, the one-time signature key pair (ovk , osk ) is generated by the challenger. During the game, if A makes a request to open a valid signature of the form ovk , c 1 , ĉ1 , ĉ2 , Π, sig , the challenger outputs a random bit and aborts. However, the strong unforgeability of the one-time signature Π OTS ensures that this is unlikely to happen. Indeed, before the challenge phase, ovk is independent of A's view, and the probability that ovk appears in A's queries is negligible. Furthermore, after seeing the challenge signature Σ , if A comes up with a valid signature of the form ovk , c 1 , ĉ1 , ĉ2 , Π, sig , then sig must be a forged one-time signature, which defeats the strong unforgeability of Π OTS . Then, the probability that the challenger aborts in this experiment is negligible and we have | Pr[S 1 ] -Pr[S 0 ]| ∈ negl(λ). In the upcoming experiments, we will assume without loss of generality that A does not requests for opening of valid signature that includes ovk .

Game 2. We program the random oracle H 1 in the following way. At the beginning of the game, we choose an uniformly random matrix G ∈ Z n× q , and set H 1 (ovk ) = G . As for other queries, for each fresh H 1 queries on ovk, the challenger samples a small norm matrix F ovk ← D m Z ,σ and programs the oracle to have H 1 (ovk) = B • F ovk and subsequent queries are answered consistently. At each H 1 -query, the chosen matrix F ovk is retained for later use. Note that the value H 1 (ovk) is statistically close to the uniform distribution, as in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. From the attacker's view, the output distribution of H 1 thus remains the same as in Game 2. Game 3. In this game, we change the opening algorithm. At the beginning of the game, instead of generating B with a trapdoor, the challenger samples a random B ∈ Z n×m q . We recall that at each fresh queries, we retain the matrix F ovk ∈ Z m× for later use. Upon receiving an adversarial query to open a signature Σ = ovk, c 1 , ĉ1 , ĉ2 , Π, sig , the challenger recovers the corresponding small-norm matrix F ovk which was defined when A first queried H 1 (ovk) (we can assume w.l.o.g. that each opening query on ovk is preceded by hash query on the same ovk). This matrix is used to "decrypt" (c 1 , c 2 ) for the corresponding G = H 1 (ovk). Thanks to Lemma 3, the distribution of (B , G) is statistically close to that of Game 2. Therefore, Game 2 and Game 3 are statistically indistinguishable and Pr[S 3 ] = Pr[S 2 ]. Game 4. We modify the generation of the challenge signature Σ . Instead of faithfully generating the NIZKAoK Π , the challenger simulates it without using the witnesses via the HVZK simulator of the underlying argument system and by programming the random oracle H as in the proof of Theorem 2 (in the unlikely event that H has to be programmed on an input for which it is already defined, the challenger aborts the experiment and outputs 1). Thanks to the statistical zero-knowledge property of the argument scheme, the simulated signature Π produced in this manner is statistically indistinguishable from a real signature. Game 3 is then statistically indistinguishable from Game 4 as long as the challenger does not fail in the simulation of Π . However, such a failure event occurs with negligible probability and we have | Pr[S 4 ] -Pr[S 3 ]| ∈ negl(λ). Game 5. In this game, we change the generation of the ciphertext (c 1 , c 2 ) during the challenge phase in step 2 of the Sign algorithm. Namely, instead of using the real encryption algorithm of GPV IBE, the challenger generates a random ciphertext. In other words, the challenger sets

c 1 := z 1 , c 2 := z 2 + q/2 • bin(d b ),
for randomly chosen (z 1 , z 2 ) ← U (Z m q × Z q ). The hardness of the LWE problem implies that Game 5 is computationally indistinguishable from Game 4. Indeed, distinguishing between these two experiments would require A to distinguish Game 6. Finally we make a conceptual change on the previous game. Namely we sample random (z 1 , z2 ) ∈ Z m q × Z q and set (c 1 , c 2 ) in step 2 of the Sign algorithm to be (z 1 , z2 ). Clearly, Game 6 is statistically indistinguishable from Game 5.

(B | G ) T s 0 + (e T 1 | e T 2 ) T from (z T 1 |z T 2 ) T ,
Since Game 6 does no longer depend on the bit b ∈ {0, 1} identifying the target signer, the advantage of A in Game 6 is then zero, which concludes our proof.

A.3 Proof of Theorem 4: Anonymity against the Opening Authority

Proof. The proof is very similar to the proof of Theorem 3 described in the previous section. We proceed with a sequence of Games that ends in a game where the adversary's advantage is unconditionally zero. The main idea is that in the security game, the adversary has at disposal the secret key of the inside layer of the proof system, meaning that we can view the ciphertext (c 1 , c 2 ) in step 2 of the signing algorithm as a plaintext. For each i, we call S i the event that the adversary wins in Game i.

Game 0. This is the actual security game as described in Definition 6. By hypothesis, the advantage of A in this game is ε = | Pr[S 0 ] -1/2|. Game 1. In this game, we program the random oracle H 2 in the following way. At the beginning of the game, we choose an uniform matrix Ĝ ← U (Z n× log q q ), and in the challenge phase, we set H 2 (M ) = Ĝ 0 . From the attacker's view, the distribution of Ĝ 0 is as in Game 0. As for other H 2 -queries, on a fresh query on the input M , the challenger samples a small-norm matrix E M ← D log q Z n ,σ , sets H 2 (M ) = C • E M mod q and retains the chosen matrix E M for later use.

We notice that the attacker is not allowed to query a token for M . Then, we remark that the value of H 2 (M ) is statistically close to the uniform distribution over Z n log q q as in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. This game is therefore indistinguishable from Game 0:

| Pr[S 1 ] -Pr[S 0 ]| ∈ negl(λ).
Game 2. In this game, we change the way the challenger handles token queries. First, we start by picking a random matrix C ← U (Z n×m q ) at the outset of the game, without generating a GPV trapdoor for it. Then, in order to answer token queries on a message M , the challenger recalls the matrix E M , and hands it as t M . Thanks to Lemma 3, the distribution of t M remains the same as in the real game. Then, Game 1 remains statistically indistinguishable from Game 2. Game 3. Here, in the challenge phase, we modify the generation of the challenge signature Σ . Instead of using the witnesses to generate the NIZK proof Π , we proceed as in the proof of Theorem 2 using the ZK simulator of the underlying argument system to generate the proof Π of the signature Σ = ovk , c 1 , ĉ 1 , ĉ 2 , Π , sig without using the witness. For the same reason as in the proof of Theorem 3, we have that Game 3 is statistically indistinguishable from Game 2. Game 4. In this game, we change the way the challenge signature Σ is generated. Instead of faithfully computing the ciphertext (ĉ 1 , ĉ 2 ) of bin(c 2 ), the challenger samples uniformly random (ẑ 1 , ẑ2 ) ∈ Z n q × Z log q q and sends Game 5. Finally, we make a conceptual change in the signature. Instead of sending (ẑ 1 , ẑ 2 + q/2 bin(c 2 )) in the challenge signature Σ , the challenger samples (z 1 , z 2 ) ← U (Z n q × Z log q q

Σ = ovk , c 1 , ẑ 2 , ẑ 2 + q/2 • bin(c 2 ), Π , sig ,
) and uses them in place of (ẑ 1 , ẑ 2 + q/2 • bin(c 2 )) to construct Σ . Game 5 is indistinguishable from Game 4.

The last game is clearly independent of the challenger's bit b ∈ {0, 1} that determines the signer's identity and it follows that Adv A (Game 5) = 0.

B Proof of Lemma 5

We first restate Lemma 5. 1 is a sZKAoK for the relation R abstract with perfect completeness, soundness error 2/3, and communication cost O(L log q). In particular:

Lemma 7. The protocol in Figure

-There exists an efficient simulator that, on input (P, v), 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 CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs x ∈ VALID such that P • x = v mod q.

Proof. It can be checked that the protocol has perfect completeness: If an honest prover follows the protocol, then he always gets accepted by the verifier. It is also easy to see that the communication cost is bounded by O(L log q). We now will prove that the protocol is a statistical zero-knowledge argument of knowledge for the relation R abstract . Zero-Knowledge Property. We construct a PPT simulator SIM interacting with a (possibly dishonest) verifier V, such that, given only the public input, SIM outputs with probability negligibly close to 2/3 a simulated transcript that is statistically close to the one produced by the honest prover in the real interaction.

The simulator first chooses a random Ch ∈ {1, 2, 3}. This is a prediction of the challenge value that V will not choose. Case Ch = 1: Using basic linear algebra over Z q , SIM computes a vector x ∈ Z L q such that P • x = v mod q. Next, it samples r ← U (Z L q ), π ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then it sends the commitment CMT = C 1 , C 2 , C 3 to V, where We observe that, in every case we have considered above, since COM is statistically hiding, the distribution of the commitment CMT and the distribution of the challenge Ch from V are statistically close to those in the real interaction. Hence, the probability that the simulator outputs ⊥ is negligibly close to 1/3. Moreover, one can check that whenever the simulator does not halt, it will provide an accepted transcript, the distribution of which is statistically close to that of the prover in the real interaction. In other words, we have constructed a simulator that can successfully impersonate the honest prover with probability negligibly close to 2/3. Argument of Knowledge. Suppose that RSP 1 = (t x , t r , ρ 2 , ρ 3 ), RSP 2 = (π 2 , y, ρ 1 , ρ 3 ), RSP 3 = (π 3 , r 3 , ρ 1 , ρ 2 ) are 3 valid responses to the same commitment CMT = (C 1 , C 2 , C 3 ), with respect to all 3 possible values of the challenge. The validity of these responses implies that:

         t x ∈ VALID; C 1 =
COM(π 2 , P • yv; ρ 1 ) = COM(π 3 , P • r 3 ; ρ 1 ); C 2 = COM(t r ; ρ 2 ) = COM(T π3 (r 3 ); ρ 2 ); C 3 = COM(t x + t r ; ρ 3 ) = COM(T π2 (y); ρ 3 ).

Since COM is computationally binding, we can deduce that: t x ∈ VALID; π 2 = π 3 ; t r = T π3 (r 3 ); t x + t r = T π2 (y); P • yv = P • r 3 mod q.

Let x = yr 3 , then we have T π2 (x ) = t x ∈ VALID which implies that x ∈ VALID. Furthermore, we have P • x = P • (yr 3 ) = v mod q.

This concludes the proof.

C Building Blocks

C.1 The Ling-Nguyen-Wang Group Signature

We build our scheme on the [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] group signature scheme, which is described as follows.

Let n be the security parameter, and N = Poly(n) be the maximum expected number of group users. The other parameters are chosen such that Boyen's signature scheme [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF] and the GPV IBE scheme [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] function properly and are secure, like in Section 4.1.

We choose hash functions H 1 : {0, 1} * → Z n× q , which goal is to produce random syndromes for the multi-bit version of GPV, and H : {0, 1} * → {1, 2, 3} t which goal is to provide challenges for the Stern's protocol in the Fiat-Shamir heuristic, and select a one time signature scheme Π OTS = (G, S, V). Let χ denote the b-bounded LWE distribution over Z.

The group signature is described as follows:

Definition 8 .

 8 Define R gsmdo = (A, {A i } i=0 , B, C, G, Ĝ, u, c 1 , ĉ1 , ĉ2 ), d, z, s, ŝ, e 1 , ê1 , e 2 , ê2 , c 2 as a relation where

1 . 2 .

 12 Commitment: P samples r ← U (Z L q ), π ← U (S) and randomness ρ1, ρ2, ρ3 for COM. Then P sends the commitment CMT = C1, C2, C3 to V, where C1 = COM(π, P • r; ρ1), C2 = COM(Tπ(r); ρ2), C3 = COM(Tπ(x + r); ρ3). Challenge: V sends a challenge Ch ← U ({1, 2, 3}) to P. 3. Response: Depending on Ch, P sends the response RSP computed as follows: -Ch = 1: Let tx = Tπ(x), tr = Tπ(r), and RSP = (tx, tr, ρ2, ρ3). -Ch = 2: Let π2 = π, y = x + r, and RSP = (π2, y, ρ1, ρ3). -Ch = 3: Let π3 = π, r3 = r, and RSP = (π3, r3, ρ1, ρ2). Verification: Receiving RSP, the verifier proceeds as follows: -Ch = 1: Check that tx ∈ VALID and C2 = COM(tr; ρ2), C3 = COM(tx + tr; ρ3). -Ch = 2: Check that C1 = COM(π2, P • yv; ρ1), C3 = COM(Tπ 2 (y); ρ3). -Ch = 3: Check that C1 = COM(π3, P • r3; ρ1), C2 = COM(Tπ 3 (r3); ρ2).

Figure 1 :

 1 Figure 1: A ZKAoK for the relation R abstract .

  δ B j=1 B j = B, and any integer in [-B, B] can be expressed as a linear combination of the B j 's with coefficients in {-1, 0, 1}. -Define the following matrices for any positive integers m, B:

Theorem 4 .

 4 The above group signature scheme is fully anonymous against the opener under the LWE assumption. message M along with two identities d 0 = d 1 ∈ {0, 1} . The challenger sends back a challenge signature Σ = ovk , c 1 , ĉ 1 , ĉ 2 , Π , sig ← Sign(gpk, gsk[d b ], M ) for b ∈ {0, 1}. After further queries, the adversary finally outputs a bit b ∈ {0, 1} and wins if b = b . We denote by S 0 the latter event. By hypothesis, Adv A (Game 0) = | Pr[S 0 ] -1/2| = ε.

  which contradicts the decisional LWE assumption. Under the LWE assumption, we have | Pr[S 5 ] -Pr[S 4 ]| ∈ negl(λ).

  as a challenge signature. This game is computationally indistinguishable from Game 3 from the assumed hardness of the decisional LWE problem. The LWE assumption implies that | Pr[S 5 ] -Pr[S 4 ]| ∈ negl(λ).

C 1 =

 1 COM(π, P • r; ρ 1 ), C 2 = COM(T π (r); ρ 2 ), C 3 = COM(T π (x + r); ρ 3 ).Receiving a challenge Ch from V, the simulator responds as follows:-If Ch = 1: Output ⊥ and abort. -If Ch = 2: Send RSP = π, x + r, ρ 1 , ρ 3 . -If Ch = 3: Send RSP = π, r, ρ 1 , ρ 2 .Case Ch = 2: SIM samples x ← U (VALID), r ← U (Z L q ), π ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then it sends the commitment CMT = C 1 , C 2 , C 3 to V, whereC 1 = COM(π, P • r; ρ 1 ), C 2 = COM(T π (r); ρ 2 ), C 3 = COM(T π (x + r); ρ 3 ).Receiving a challenge Ch from V, the simulator responds as follows:-If Ch = 1: Send RSP = T π (x ), T π (r), ρ 2 , ρ 3 . -If Ch = 2: Output ⊥ and abort. -If Ch = 3: Send RSP = π, r, ρ 1 , ρ 2 . Case Ch = 3: SIM samples x ← U (VALID), r ← U (Z L q ), π ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then it sends the commitment CMT = C 1 , C 2 , C 3 to V, where C 2 = COM(T π (r); ρ 2 ), C 3 = COM(T π (x + r); ρ 3 ) as in the previous two cases, whileC 1 = COM(π, P • (x + r) -v; ρ 1 ),Receiving a challenge Ch from V, it responds as follows:-If Ch = 1: Send RSP computed as in the case (Ch = 2, Ch = 1).-If Ch = 2: Send RSP computed as in the case (Ch = 1, Ch = 2).-If Ch = 3: Output ⊥ and abort.

Acknowledgements

The first author was funded by the "Programme Avenir Lyon Saint-Etienne de l'Université de Lyon" in the framework of the programme "Investissements d'Avenir" (ANR-11-IDEX-0007). Khoa Nguyen was supported by the "Singapore Ministry of Education under Research Grant MOE2013-T2-1-041".

A Deferred Proofs of the GS-MDO Scheme

A.1 Proof of Theorem 2: Traceability

Proof. Our proof is similar to the proof of traceability in Ling et al. scheme [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] since adding an additional encryption layer does not alter the power of the reduction.

Let us assume that there exists a PPT adversary A with noticeable advantage ε. By hypothesis, such an adversary can produce a valid signature (M , Σ ) which opens to ⊥ or a non-adversarially controlled user who did not sign M . We construct a reduction B that uses A to produce a forgery for Boyen's signature with advantage polynomially smaller than ε. Since Boyen's signature is secure under SIS assumption, this completes our proof.

Setup. The reduction B is given the verification key (A, A 0 , . . . , A , u) for Boyen's signature. It generates two key pairs (B, T B ), (C, T C ) for the GPV IBE scheme and interacts with A by sending it gpk = A, A 0 , . . . , A , u, B, C , ok = T B and msk ADM = T C .

Queries. Algorithm B initializes Q u ← ∅ and handles A's queries as follow:

-Random Oracle Query. Queries on H, H 1 and H 2 are handled by consistently returning uniformly random values in the respective ranges. In the following, we denote by q k the answer to the k-th H-query. The reduction B then exploits the forgery as follows. We can start by noticing that A must have queried H on input (M, ovk, {Comm j } t j=1 , c 1 , ĉ1 , ĉ2 ) since, otherwise, the probability that (Chall) t i=1 = H(M, ovk, {Comm j } t j=1 , c 1 , ĉ1 , ĉ2 ) is at most 3 -t . With probability at least ε -3 -t , there thus exists an index κ * ≤ Q H such that the κ * -th Oracle query involves the input (M, ovk, {Comm j } t j=1 , c 1 , ĉ1 , ĉ2 ). The reduction B then sets κ * as the forking point: namely, B replays A many times with the same random tape and input as in the original run. In each re-played execution, the first κ * -1 queries receive exactly the same responses r 1 , . . . , r κ * -1 but, beyond that point, all following queries are replied with fresh random values r κ * , . . . , r

The Improved Forking Lemma of Brickell et al. [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] ensures that with probability at least 1/2, B can obtain a 3-fork on H involving the same input tuple (M, ovk, {Comm j } t j=1 , c 1 , ĉ1 , ĉ2 ) with pairwise distinct outputs r

(1)

κ * , r

(3)

With probability 1 -(7/9) t , it can be shown that there exists an index j ∈ {1, . . . , t} for which the j-th bits of r

) must be valid answers with respect to three distinct challenges for the same commitment Comm j . B can now use the knowledge extractor of the underlying argument scheme to obtain witnesses

such that the vector z is a Boyen signature for the message d . Moreover, as required by the traceability game, we must have d / ∈ Q u , which implies that (d , z ) is a forgery for the Boyen signature. Finally, we can notice that, if A has non-negligible success probability and runs in polynomial time, the same holds for B.

A.2 Proof of Theorem 3: Anonymity against the Admitter

Proof. In this proof, the attacker is given the private key of the external encryption layer at the outset of the game. Since this key is also known to the challenger, we can proceed as if this encryption layer did not exist in our proof. The proof thus remains very similar to the proof of anonymity in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF]. Namely, we will proceed via a sequence of games such that Adv A (Game 0) = ε in the first game and Adv A (Game 6) = 0 in the last one. The indistinguishability of all adjacent games is supported by the strong unforgeability of Π OTS , the statistical ZK property of the argument system and the hardness of LWE. For each i, we denote by S i the event that the adversary wins in Game i.

Game 0. This is the real CCA anonymity game against the admitter: the challenger runs Keygen(1 λ , 1 N ) to obtain (gpk, ok = T B , msk ADM = T C , gsk), and then sends (gpk, msk ADM , gsk) to A. Using the decryption keys T B and T C , the challenger can answer all signature opening queries. In the challenge phase, A sends a KeyGen(1 n , 1 N ): Given a dimension n and a number of group users N = 2 :

1. Generate verification key (A, A 0 , . . . , A , u) ∈ (Z n×m q ) +1 × Z n q and signing key T A ∈ Z m×m for Boyen's signature scheme. Then 1. Encrypt the index d with respect to "identity" ovk using the GPV IBE:

with e 1 , e 2 , s ← χ n × χ × χ m , and G = H 1 (ovk). 2. Generate a NIZKPoK Π to show the possession of a valid messagesignature pair (id, z) for Boyen's signature and that (c 1 , c 2 ) is a correct GPV IBE encryption of d with respect to identity ovk. The argument system is described in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF]. The message is embedded in the challenge of the Fiat-Shamir heuristic to construct NIZK proofs. 3. Compute a one-time signature sig = OSign(ovk; c 1 , c 2 , Π). 4. Output the signature Σ = (ovk, (c 1 , c 2 ), Π, sig).

Verify(gpk, M, Σ):

Parse Σ as before. Check that OVer(ovk; sig, (c 1 , c 2 ), Π) = 1, otherwise return 0. Verify that Π is a valid proof, otherwise return 0. If all verifications succeed, return 1.

Open(gmsk, M, Σ):

Given gmsk = T B and a signature Σ = (ovk, (c 1 , c 2 ), Π, sig), this algorithm decrypt (c 1 , c 2 ) using GPV-IBE decryption algorithm with respect to the identity ovk and returns the decrypted identity id.

C.2 The Boyen and Micciancio-Peikert Signatures

This section recalls a variant [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] of Boyen's signature [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF], which we use in our scheme to generate the group user secret key. The scheme is parameterized by , denoting the size of the message that can be signed. The difference between the original scheme and [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] is the use of a vector u ∈ Z m q : instead of computing signatures as short vectors in a message-dependent lattice, Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] use a shifted lattice.

Keygen(1 λ , 1 ): To generate the sk and pk from λ, , this algorithm starts by choosing n = Θ(λ), q = Poly(λ), α -1 = Poly(λ), σ = α • q and m ≥ Ω(n log q).

1. Use GenTrap(1 n , 1 m , q) to generates a matrix A ∈ Z n×m q along with a trapdoor T A ∈ Z m×m . 2. Sample uniformly + 1 matrices A 0 , . . . , A ∈ R Z n×m q .

3. Sample uniformly a vector u ∈ R Z n 1. Use ExtBasis and pk to compute a trapdoor basis T M for the matrix

Use GPVSample to get a vector x ∈ D Λ u q (M),σ . 3. Output x ∈ Z 2m as the signature. Verify(pk, M, x): To verify a signature x w.r.t a message M and a public key pk:

1. Verify that x ≤ σ √ 2m, if not, output 0 (corresponding to a rejection).

Compute the matrix M =

If not, output 0. 4. If everything went correctly, output 1.

C.3 The Gentry-Peikert-Vaikuntanathan IBE

This section recalls the dual Regev cryptosystem, which was proposed by Gentry et al. [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] and readily implies an IBE system due to its "obliviously samplable" public key space.

The multi-bit variant of the GPV IBE uses a hash function H : {0, 1} * → Z n× q modeled as a random oracle, where denotes the bit-length of the message. In the following χ denotes the LWE distribution.

Setup(1 λ ): Using algorithm GenTrap(1 n , 1 m , q), generate a statistically uniform matrix A ∈ Z n×m q with its trapdoor T A ∈ Z m×m consisting of a short basis of Λ ⊥ q (A). Output the master public key mpk := A ∈ Z n×m q and the master secret msk := T A ∈ Z m×m . Extract(A, T A , id): If a private key for the identity id has already been released, return the same sk id . Otherwise, let G = H(id) and use SamplePre to return a small-norm matrix E ∈ Z m× such that A • E = G mod q. Encrypt(A, id, m): To encrypt a message m ∈ {0, 1} w.r.t. identity id. Let G = H(id). We sample s ← χ n , e 1 ← χ m , e 2 ← χ , and output c = A T s + e 1 , G T s + e 2 + q/2 • m ∈ Z m q × Z q .

Dec(E, (c 1 , c 2 )