Benoît Libert

San Ling

Fabrice Mouhartem

Khoa Nguyen

Huaxiong Wang

Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions

Keywords: Lattice-based cryptography, anonymity, signatures with efficient protocols, dynamic group signatures, anonymous credentials

A recent line of works -initiated by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010) -gave lattice-based realizations of privacy-preserving protocols allowing users to authenticate while remaining hidden in a crowd. Despite five years of efforts, known constructions remain limited to static populations of users, which cannot be dynamically updated. For example, none of the existing lattice-based group signatures seems easily extendable to the more realistic setting of dynamic groups. This work provides new tools enabling the design of anonymous authentication systems whereby new users can register and obtain credentials at any time. Our first contribution is a signature scheme with efficient protocols, which allows users to obtain a signature on a committed value and subsequently prove knowledge of a signature on a committed message. This construction, which builds on the lattice-based signature of Böhl et al. (Eurocrypt'13), is well-suited to the design of anonymous credentials and dynamic group signatures. As a second technical contribution, we provide a simple, round-optimal joining mechanism for introducing new members in a group. This mechanism consists of zero-knowledge arguments allowing registered group members to prove knowledge of a secret short vector of which the corresponding public syndrome was certified by the group manager. This method provides similar advantages to those of structure-preserving signatures in the realm of bilinear groups. Namely, it allows group members to generate their public key on their own without having to prove knowledge of the underlying secret key. This results in a two-round join protocol supporting concurrent enrollments, which can be used in other settings such as group encryption.

Introduction

Lattice-based cryptography is currently emerging as a promising alternative to traditional public-key techniques. During the last decade, it has received a permanent interest (see [START_REF] Peikert | A decade of lattice cryptography[END_REF] and references therein) due to its numerous advantages. Not only does it seemingly resist quantum attacks, it also provides a better asymptotic efficiency than its relatives based on conventional number theory. While enabling advanced functionalities (like fully homomorphic [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] or attribute-based/predicate encryption [START_REF] Gorbunov | Attribute-based encryption for circuits[END_REF][START_REF] Gorbunov | Predicate encryption for circuits from lwe[END_REF] for circuits) that remain elusive outside the lattice world, lattice-based primitives tend to interact with zeroknowledge proofs [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF] less smoothly than their counterparts in abelian groups endowed with a bilinear map (see, e.g., [START_REF] Boneh | Short group signatures[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF][START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF][START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF][START_REF] Abe | Structurepreserving signatures and commitments to group elements[END_REF]) or groups of hidden order [START_REF] Ateniese | A practical and provably secure coalition-resistant group signature scheme[END_REF][START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF][START_REF] Camenisch | A signature scheme with efficient protocols[END_REF][START_REF] Camenisch | On the portability of generalized schnorr proofs[END_REF]. Arguably, this partially arises from the fact that lattices have far less algebraic structure than, e.g., pairing-friendly cyclic groups. It is not surprising that the most efficient zero-knowledge proofs for lattice-related languages [START_REF] Benhamouda | Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings[END_REF] take advantage of the extra algebraic structure available in the ring setting [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF]. A consequence of the scarcity of truly efficient zero-knowledge proofs in the lattice setting is that, in the context of anonymity and privacy-preserving protocols, lattice-based cryptography has undergone significantly slower development than in other areas like functional encryption [START_REF] Gorbunov | Attribute-based encryption for circuits[END_REF][START_REF] Gorbunov | Predicate encryption for circuits from lwe[END_REF]. While natural realizations of ring signatures [START_REF] Rivest | How to leak a secret[END_REF] showed up promptly [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Brakerski | A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model[END_REF] after the seminal work of Gentry, Peikert and Vaikuntanathan (GPV) [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], viable constructions of lattice-based group signatures [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF] remained lacking until the work of Gordon, Katz and Vaikuntanathan [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF] in 2010. Despite recent advances in the area [START_REF] Langlois | Lattice-based group signature scheme with verifier-local revocation[END_REF][START_REF] Benhamouda | Better zero-knowledge proofs for lattice encryption and their application to group signatures[END_REF][START_REF] Nguyen | Simpler efficient group signatures from lattices[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], lattice-based group signatures and other privacy-preserving primitives remain substantially less practical and powerful in terms of functionalities than their siblings based on traditional number theoretic problems [START_REF] Ateniese | A practical and provably secure coalition-resistant group signature scheme[END_REF][START_REF] Boneh | Short group signatures[END_REF][START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF][START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] for which solutions even exist [START_REF] Boyen | Compact group signatures without random oracles[END_REF][START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF][START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF][START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] outside the random oracle methodology. For example, we still have no convenient realization of group signature supporting dynamic groups [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF][START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] or anonymous credentials [START_REF] Chaum | Security without identification: Transactions ssystem to make big brother obsolete[END_REF][START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF].

In this paper, we address the latter two problems by first proposing a latticebased signature with efficient protocols in the fashion of Camenisch and Lysyanskaya [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF]. To ease its use in the design of dynamic group signatures, we design a zero-knowledge argument system that allows a user to prove knowledge of a signature on a public key for which the user knows the underlying secret key.

Related Work. Anonymous credentials were first suggested by Chaum [START_REF] Chaum | Security without identification: Transactions ssystem to make big brother obsolete[END_REF] and efficiently realized by Camenisch and Lysyanskaya [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF][START_REF] Camenisch | A signature scheme with efficient protocols[END_REF]. They involve one or more credential issuer(s) and a set of users who have a long-term secret key which constitutes a their digital identity and pseudonyms that can be seen as commitments to their secret key. Users can dynamically obtain credentials from an issuer that only knows users' pseudonyms and obliviously certifies users' secret keys as well as (optionally) a set of attributes. Later on, users can make themselves known to verifiers under a different pseudonym and demonstrate possession of the issuer's signature on their secret key without revealing neither the signature or the key. Anonymous credentials typically consist of a protocol whereby the user obtains the issuer's signature on a committed message, another protocol for proving that two commitments open to the same value (which allows proving that the same secret underlies two distinct pseudonyms) and a protocol for proving possession of a secret message-signature pair.

The first efficient constructions were given by Camenisch and Lysyanskaya under the Strong RSA assumption [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF][START_REF] Camenisch | A signature scheme with efficient protocols[END_REF] or using bilinear groups [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF]. Other solutions were subsequently given with additional useful properties such as noninteractivity [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], delegatability [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF], a better efficiency in the private key setting [START_REF] Chase | Algebraic macs and keyed-verification anonymous credentials[END_REF], or support for efficient attributes [START_REF] Camenisch | Efficient attributes for anonymous credentials[END_REF] (see [START_REF] Camenisch | Formal treatment of privacy-enhancing credential systems[END_REF] and references therein). Anonymous credentials with attributes are often obtained by having the issuer obliviously sign a multi-block message (Msg 1 , . . . , Msg N ), where one block is the secret key while other blocks contain public or private attributes. Note that, for the sake of keeping the scheme compatible with zero-knowledge proofs, the blocks (Msg 1 , . . . , Msg N ) cannot be simply hashed before getting signed using a ordinary, single-block signature.

Group signatures are a central anonymity primitive, introduced by Chaum and van Heyst [START_REF] Chaum | Group signatures[END_REF] in 1991, which allows members of a group managed by some authority to sign messages in the name of the entire group. At the same time, users remain accountable for the messages they sign since an opening authority can identify them if they misbehave.

Ateniese, Camenisch, Joye and Tsudik [START_REF] Ateniese | A practical and provably secure coalition-resistant group signature scheme[END_REF] provided the first scalable construction meeting the security requirements that can be intuitively expected from the primitive, although clean security notions were not available yet at that time. Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] filled this gap by providing suitable security notions for static groups, which were subsequently extended to the dynamic setting3 by Kiayias and Yung [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] and Bellare, Shi and Zhang [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]. In these models, efficient schemes have been put forth in the random oracle model [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF][START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF] (the ROM) and in the standard model [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF][START_REF] Abe | Structurepreserving signatures and commitments to group elements[END_REF][START_REF] Abe | Constantsize structure-preserving signatures: Generic constructions and simple assumptions[END_REF] Lattice-based group signatures were put forth for the first time by Gordon, Katz and Vaikuntanathan [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF] whose solution had linear-size signatures in the number of group members. Camenisch, Neven and Rückert [START_REF] Camenisch | Fully anonymous attribute tokens from lattices[END_REF] extended [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF] so as to achieve anonymity in the strongest sense. Laguillaumie et al. [START_REF] Laguillaumie | Lattice-based group signatures with logarithmic signature size[END_REF] decreased the signature length to be logarithmic in the number N gs of group members. While asymptotically shorter, their signatures remained space-consuming as, analogously to the Boyen-Waters group signature [START_REF] Boyen | Compact group signatures without random oracles[END_REF], their scheme encrypts each bit of the signer's identity individually. Simpler and more efficient solutions with O(log N ) signature size were given by Nguyen, Zhang and Zhang [START_REF] Nguyen | Simpler efficient group signatures from lattices[END_REF] and Ling, Nguyen and Wang [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF]. In particular, the latter scheme [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] achieves significantly smaller signatures by encrypting all bits of the signer's identity at once. Benhamouda et al. [START_REF] Benhamouda | Better zero-knowledge proofs for lattice encryption and their application to group signatures[END_REF] described a hybrid group signature that simultaneously relies on lattice assumptions (in the ring setting) and discrete-logarithm-related assumptions. Recently, Libert, Ling, Nguyen and Wang [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] obtained substantial efficiency improvements via a construction based on Merkle trees which eliminates the need for GPV trapdoors [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. For the time being, all known group signatures are designed for static groups and analyzed in 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], where no new group member can be introduced after the setup phase. To date, it remains an open problem to design a lattice-based system that supports dynamically growing population of users in the models of [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF][START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF].

Our Contributions. Our first result is a lattice-based signature with efficient protocols for multi-block messages. Namely, we provide a way for a user to obtain a signature on a committed N -block message (Msg 1 , . . . , Msg N ) as well as a protocol for proving possession of a valid message-signature pair. The signature and its companion protocols can serve as a building block for constructing lattice-based anonymous credentials and can potentially find other applications in the design of compact e-cash systems [START_REF] Camenisch | Compact e-cash[END_REF] under lattice assumptions. The main application that we consider in this paper is the construction of a lattice-based group signature scheme for dynamic groups. While less efficient than the recent proposal of [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF], our scheme is competitive with the solution of Ling, Nguyen and Wang [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] which is one of the most efficient candidates based on standard (i.e., non-ideal) lattices in static groups. In particular, it features O(log N gs )-size signatures for groups of up to N gs members and only lengthens the signatures of [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] by a (small) constant factor. We prove the security of our system in the random oracle model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF] under the Short Integer Solution (SIS) and Learning-With-Errors (LWE) assumptions.

To simplify the use of our signature scheme in the design of our dynamic group signatures, we also develop a zero-knowledge argument system allowing a group member to prove knowledge of a secret key (consisting of a short Gaussian vector) and a membership certificate issued by the group manager on the corresponding public key. This method can be seen as a lattice-based analogue of structurepreserving signatures in that it allows a signer to sign public keys without hashing them while remaining oblivious of the underlying secret key. Our zero-knowledge argument system and the signature scheme allow us to construct a dynamic joining protocol -which allows the group manager to dynamically introduce new group members by issuing a membership certificate on their public keywhich does not require any proof of knowledge on behalf of the prospective user. As a result, the joining protocol is round-optimal: only one message is sent in each direction when the new user interacts with the group manager. 4 Besides being the first lattice-based group signatures for dynamic groups, our scheme thus remains secure in the setting advocated by Kiayias and Yung [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF], where many users want to join at the same time and concurrently interact with the group manager. We believe that, analogously to structure-preserving signatures [START_REF] Abe | Structurepreserving signatures and commitments to group elements[END_REF][START_REF] Abe | Constantsize structure-preserving signatures: Generic constructions and simple assumptions[END_REF], the combination of our signature scheme and zero-knowledge arguments can serve as a building blocks for other primitives, including group encryption [START_REF] Kiayias | Group encryption[END_REF][START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF] or adaptive oblivious transfer [START_REF] Green | Universally composable adaptive oblivious transfer[END_REF].

Our Techniques. Our signature scheme with efficient protocols builds on the SIS-based signature of Böhl et al. [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF], which is itself a variant of Boyen's signature [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF]. Recall that the latter scheme involves a public key containing matrices A, A 0 , . . . , A ∈ Z n×m q and signs an -bit message Msg ∈ {0, 1} by computing a short vector

v ∈ Z 2m such that [A | A 0 + j=1 Msg[i]A j ] • v = 0 m mod q.
The variant of Böhl et al. [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] only uses a constant number of matrices A, A 0 , A 1 ∈ Z n×m q . Each signature is associated with a single-use tag tag (which is only used in one signing query in the proof) and the public key involves an extra matrix D ∈ Z n×m q and a vector u ∈ Z n q . An message Msg is signed by first applying a chameleon hash function h = CMHash(Msg, s) ∈ {0, 1} m and signing h by

computing a short v ∈ Z m such that [A | A 0 + tag • A 1 ] • v = u + D • h mod q.
Our scheme extends the latter scheme -modulo the use of a larger number of matrices {A j } j=0 as in Boyen's scheme -so that a signature on N -block message (Msg 1 , . . . , Msg N ) ∈ ({0, 1}) N consists of a tag τ ∈ {0, 1} and a short vector

v ∈ Z 2m such that [A | A 0 + j=1 τ [j]•A j ]•v = u+CMHash(Msg 1 , . . . , Msg N , s),
where the chamelon hash function computes

c M = D 0 • s + N k=1 D k • Msg k ∈ Z n
q , for some integer vector s, before re-encoding c M ∈ Z n q into {0, 1} m . In order to obtain a signature scheme akin to the one of Camenisch-Lysyanksaya [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF], our idea is to have the tag τ ∈ {0, 1} play the same role as the prime exponent in Strong-RSA-based schemes [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF]. In the security proof of [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF], we are faced with two situations: either the adversary produces a signature on a fresh tag τ , or it recycles a tag τ (i) used by the signing oracle for a new, unsigned message (Msg 1 , . . . , Msg N ). In the former case, the proof can proceed as in Boyen's proof [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF]. In the latter case, the reduction must guess upfront which tag τ (i † ) the adversary will choose to re-use and find a way to properly answer the i † -th signing query without using the vanished trapdoor (for other queries, the Agrawal et al. technique [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] applies to compute a suitable v using a trapdoor hidden in {A j } j=0 ). Böhl et al. [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] solve this problem by "programming" the vector u ∈ Z n q in a special way and achieve full security using chameleon hashing. To adapt this idea in the context of signatures with efficient protocols, we have to overcome two difficulties. The first one is to map c M ∈ Z n q back in the domain of the chameleon hash function while preserving the compatiblity with zero-knowledge proofs. To solve this problem, we extend a technique used in [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] in order to build a "zero-knowledge-friendly" chameleon hash function. This function hashes a vector (Msg 1 , . . . , Msg N ) by choosing m = n log q and outputting h = bin(D 0 •s+

N k=1 D k •Msg k ) ∈ {0, 1} m
where, for any vector v ∈ Z n q , bin(v) ∈ {0, 1} m denotes the vector obtained by replacing each coordinate of v by its binary decomposition. If we define the matrix H = 1 | 2 | . . . | 2 log q ⊗I n , we can prove that h = CMHash(Msg 1 , . . . , Msg N , s, w) by demonstrating knowledge of short vectors (Msg 1 , . . . ,

Msg N , s, h) such that H • w = D 0 • s + N k=1 D k • Msg k ,
which boils down to arguing knowledge of a solution to the ISIS problem [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF]. Then, we extend the techniques of [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] to prove knowledge of (τ, v, s) and (Msg 1 , . . . ,

Msg N ) satisfying [A | A 0 + j=1 τ [j]•A j ]•v = u+CMHash(Msg 1 , . . . , Msg N , s)
, without revealing any of the witnesses. In a nutshell, we show that most of the involved statements are equivalent to asserting that a short integer vector x satisfies an equation of the form P • x = v mod q, for some public matrix P and vector v, and belongs to a set VALID of short vectors with a particular structure. While the small-norm property of x is provable using standard techniques (e.g., [START_REF] Lyubashevsky | Lattice-Based Identification Schemes Secure Under Active Attacks[END_REF]), we prove its membership of VALID by leveraging the combinatorial properties of Stern-like protocols [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF] and playing with their underlying permutations.

The second problem arises when, analogously to [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF], we extend the scheme into a protocol for signing committed messages. In this case, the signer must first additively re-randomize the user's commitment c U = D 0 • s + N k=1 D k • Msg k before generating a signature on the hidden messages. This is indeed neccessary to provide the reduction with a backdoor allowing to correctly answer the i †th signing query by "programming" the randomness s of the chameleon hash. One difficulty is that the randomness of the commitment (like the one of the chameleon hash function) is a discrete Gaussian vector which, unlike vectors of finite field elements, cannot easily be programmed in a statistically indistinguishable manner: this technique indeed affects the standard deviation of the Gaussian vector s in exactly one signing query. Using integer commitments, Camenisch and Lysyanskaya [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF] address a similar problem by letting the signer's randomness be exponentially larger than the initial randomness of the user's commitment: this allows the distribution of the "programmed" randomness to be statistically close to that of the sum of the two contributions of the signer and the user in the real scheme. While a similar technique, called "smudging", has been used in the lattice setting by Asharov et al. [START_REF] Asharov | Multiparty computation with low communication, computation and interaction via threshold FHE[END_REF]Lemma 2.1], it requires the modulus q to be exponentially large as well. Here, we adopt a more efficient solution, inspired by the results of Bai et al. [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF], which is to apply an analysis based on the Rényi divergence rather than the statistical distance. In short, the probability preservation property of the Rényi divergence tells us that, if some event E occurs with noticeable probability in some probability space P , so does it in a different probability space Q for which the second order Rényi divergence R 2 (P ||Q) is sufficiently small. In our setting, R 2 (P ||Q) is precisely polynomially bounded since the two probability spaces only diverge in one signing query.

Our dynamic group signature scheme avoids these difficulties because the group manager does not have to obliviously sign messages: instead of signing the user's secret key as usually done in anonymous credentials, the group manager creates a membership certificate consistig of a signature on the user's public key. Our zero-knowledge argument system accommodates the requirements of our group signature in the following way. In the joining protocol that dynamically introduces new group members, the prospective user i chooses a membership secret consisting of a short discrete Gaussian vector z i ∈ Z m . This user generates a public syndrome v i = F • z i mod q, for some public matrix F, which constitutes his public key. In order to certify v i ∈ Z n q , the group manager computes a coordinatewise binary expansion of v i so as to obtain a vector bin(v i ) ∈ {0, 1} n log q . The latter vector is then signed using our variant of the Böhl et al. signature. Using the resulting signature (τ, v, s) as a membership certificate, the group member will be able to sign a message by proving that: (i) He holds a valid signature (τ, v, s) on some secret binary message bin(v i ); (ii) The latter vector bin(v i ) is the binary expansion of some syndrome v i ∈ Z q of which he knows a GPV pre-image z i ∈ Z m . We remark that condition (ii) can be proved by providing evidence that, if we define

H = I n ⊗ [1 | 2 | . . . | 2 log q ], we have v i = H • bin(v i ) = F • z i mod q,
for some short vector z i ∈ Z m and some binary bin(v i ) ∈ {0, 1} n log q . As was previously noticed in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], the framework of Stern-like protocols [START_REF] Stern | A new paradigm for public key identification[END_REF] and its extensions to lattices [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] is well-suited to efficiently argue such statements, especially for conditions of the form bin(v i ) ∈ {0, 1} n log q . The fact that the underlying chameleon hash function smoothly interacts with Stern-like zeroknowledge proofs is the poperty that maintains the user's capability of efficiently proving knowledge of the underlying secret key.

Organization. In the forthcoming sections, we first provide some background in Section 2. Our lattice-based signature with efficient protocols is presented in Section 3, where we also give protocols for obtaining a signature on a committed message and proving knowledge of a signature on a committed message. Section 4 uses our signature scheme in the design of dynamic group signatures. In Section 5, we finally provide the details of the zero-knowledge arguments for the statements to be proved in our protocols of Section 3 and 4.

Background and Definitions

In the following, all vectors are denoted in bold lower-case letters, whereas bold upper-case letters will be used for matrices. If b ∈ R n , its euclidean norm will be denoted by b . This notation is extended to matrices

B ∈ R m×n with columns (b i ) i≤n by B = max i≤n b i . If B is full column-rank, we let B denote the Gram-Schmidt orthogonalisation of B.
When S is a finite set, we denote by U (S) the uniform distribution over S and by x ← U (S) the action of sampling x according to this distribution.

Lattices

A (full-rank) lattice L is the set of all integer linear combinations of some linearly independent basis vectors (b i ) i≤n belonging to some R n . We work with q-ary lattices, for some prime q. Definition 1. Let m ≥ n ≥ 1, a prime q ≥ 2 and A ∈ Z n×m q and u ∈ Z n q , define Λ q (A) := {e ∈ Z m | ∃s ∈ Z n q s.t. A T • s = e mod q} as well as

Λ ⊥ q (A) := {e ∈ Z m | A • e = 0 n mod q}, Λ u q (A) := {e ∈ Z m | A • e = u mod q}
For any t ∈ Λ u q (A), Λ u q (A) = Λ ⊥ q (A) + t so that Λ u q (A) is a shift of Λ ⊥ q (A). For a lattice L, a vector c ∈ R n and a real σ > 0, define ρ σ,c (x) = exp(-π xc 2 /σ 2 ). The discrete Gaussian distribution of support L, parameter σ and center c is defined as D L,σ,c (y) = ρ σ,c (y)/ρ σ,c (L) for any y ∈ L. We denote by D L,σ (y) the distribution centered in c = 0. We will extensively use the fact that samples from D L,σ are short with overwhelming probability.

Lemma 1 ([8, Le. 1.5]). For any lattice L ⊆ R n and positive real number σ > 0, we have

Pr b← D L,σ [ b ≤ √ nσ] ≥ 1 -2 -Ω(n) .
As shown by Gentry et al. [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], Gaussian distributions with lattice support can be sampled from efficiently, given a sufficiently short basis of the lattice.

Lemma 2 ([23, Le. 2.3]

). There exists a PPT (probabilistic polynomial-time) algorithm GPVSample that takes as inputs a basis B of a lattice L ⊆ Z n and a rational σ ≥ B • Ω( √ log n), and outputs vectors b ∈ L with distribution D L,σ .

Lemma 3 ([4, Th. 3.2]). There exists a PPT algorithm TrapGen 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).
Lemma 3 is often combined with the sampler from Lemma 2. Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] recently proposed a more efficient approach for this combined task, which should be preferred in practice but, for the sake of simplicity, we present our schemes using TrapGen.

We also make use of 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 ([34,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 .
In our security proofs, analogously to [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF][START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] we also use a technique due to Agrawal, Boneh and Boyen [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] that implements an all-but-one trapdoor mechanism (akin to the one of Boneh and Boyen [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF]) in the lattice setting.

Lemma 5 ([3, Th. 19]

). There exist a PPT algorithm SampleRight that takes as input matrices A, C ∈ Z n×m q , a low-norm matrix R ∈ Z m×m , a short basis T C ∈ Z m×m of Λ ⊥ q (C), a vector u ∈ Z n q and a rational σ such that σ ≥ T C • Ω( √ log n), and outputs vectors b ∈ Z 2m such that A A • R + C •b = u mod q and with distribution statistically close to D L,σ where L denotes the shifted lattice {x ∈ Z 2m :

A A • R + C • x = u mod q}.

Computational Problems

The security of our schemes provably relies (in the ROM) on the assumption that both algorithmic problems below are hard, i.e., cannot be solved in polynomial time with non-negligible probability and non-negligible 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, e.g., [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Se. 9]). Similarly, if αq = Ω( √ n), standard worst-case lattice problems with approximation factors γ = O(α/n) quantumly reduce [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][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] to LWE q,α .

A Lattice-Based Signature with Efficient Protocols

Our scheme can be seen as a variant of the Böhl et al. signature [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF], where each signature is a triple (τ, v, s), made of a tag τ ∈ {0, 1} and integer vectors (v, s)

satisfying [A | A 0 + j=1 τ [j] • A j ] • v = u + D • h mod q, where A, D ∈ Z n×m q
are public random matrices and h ∈ {0, 1} m is a chameleon hash of the message which is computed using randomness s. A difference is that, while [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] uses a short single-use tag τ ∈ Z q , we need the tag to be an -bit string τ ∈ {0, 1} which will assume the same role as the prime exponent of Camenisch-Lysyanskaya signatures [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF] in the security proof.

We show that a suitable chameleon hash function makes the scheme compatible with Stern-like zero-knowledge arguments [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] for arguing possession of a valid message-signature pair. Section 5 shows how to translate such a statement into asserting that a short witness vector x with a particular structure satisfies a relation of the form P • x = v mod q, for some public matrix P and vector v. The underlying chameleon hash can be seen as a composition of the SISbased chameleon hash of [34, Section 4.1] with a technique used in [START_REF] Papamanthou | Streaming Authenticated Data Structures[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF]: on input of a message (m 1 , . . . , m N , s), it outputs the binary decomposition of

D 0 • s + N k=1 D k • m k
mod q, for some discrete Gaussian vector s.

Description

We assume that messages are vectors of N blocks Msg = (m 1 , . . . , m N ), where each block is an 2m-bit string

m k = m k [1] . . . m k [2m] ∈ {0, 1} 2m for k ∈ {1, . . . , N }.
For each vector v ∈ Z L q , we denote by bin(v) ∈ {0, 1} L log q the vector obtained by replacing each coordinate of v by its binary representation.

Keygen(1 λ , 1 N ): Given a security parameter λ > 0 and the number of blocks N = poly(λ), choose the following parameters: n = O(λ); a sufficiently large modulus q = poly(n); dimension m = 2n log q ; an integer = Θ(λ); and Gaussian parameters σ = Ω( √ n log q log n), σ 0 = 2 √ 2(N + 1)σm 3/2 , and σ 1 = σ 2 0 + σ 2 . Define the message space as ({0, 1} 2m ) N . 1. Run TrapGen(1 n , 1 m , q) to get A ∈ Z n×m q and a short basis T A of Λ ⊥ q (A). This basis allows computing short vectors in Λ ⊥ q (A) with a Gaussian parameter σ.

Next, choose + 1 random A 0 , A 1 , . . . , A ← U (Z n×m q ). 2. Choose random matrices D ← U (Z n×m q ), D 0 , D 1 , . . . , D N ← U (Z 2n×2m q )
as well as a random vector u ← U (Z n q ). The private key consists of SK := T A and the public key is

P K := A, {A j } j=0 , {D k } N k=0 , D, u .
Sign SK, Msg) : To sign an N -block message Msg = (m 1 , . . . , m N ) ∈ {0, 1} 2m N , 1. Choose a random binary string τ ← U ({0, 1} ). Then, using SK := T A , compute a short delegated basis T τ ∈ Z 2m×2m for the matrix

A τ = [A | A 0 + j=1 τ [j]A j ] ∈ Z n×2m q . (1)
2. Choose a discrete Gaussian vector s ← D Z 2m ,σ1 . Compute the vector c M ∈ Z 2n q as a chamelon hash of (m 1 , . . . , m N ). Namely, compute

c M = D 0 • s + N k=1 D k • m k ∈ Z 2n q ,
which is used to define

u M = u + D • bin(c M ) ∈ Z n q .
Then, using the delegated basis

T τ ∈ Z 2m×2m , sample a short vector v ∈ Z 2m in D Λ u M q (Aτ ),σ . Output the signature sig = (τ, v, s) ∈ {0, 1} × Z 2m × Z m . Verify P K, Msg, sig : Given P K, a message Msg = (m 1 , . . . , m N ) ∈ ({0, 1} m ) N and a purported signature sig = (τ, v, s) ∈ {0, 1} × Z 2m × Z 2m , return 1 if A τ • v = u + D • bin(D 0 • s + N k=1 D k • m k ) mod q. ( 2
)
and v < σ √ 2m, s < σ 1 √ 2m.
When the scheme is used for obliviously signing committed messages, the security proof follows Bai et al. [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF] in that it applies an argument based on the Rényi divergence in one signing query. This argument requires to sample s from a Gaussian distribution whose standard deviation σ 1 is polynomially larger than σ. We note that, instead of being included in the public key, the matrices {D k } N k=0 can be part of common public parameters shared by many signers. Indeed, only the matrices (A, {A i } i=0 ) should be specific to the user who holds the secret key SK = T A . In Section 3.3, we use a variant where {D k } N k=0 belong to public parameters.

Security Analysis

The security analysis in Theorem 1 requires that q > . Theorem 1. The scheme is secure under chosen-message attacks under the SIS assumption.

Proof. The prove the result, we will distinguish two kinds of attacks:

Type I attacks are attacks where, in the adversary's forgery sig = (τ , v , s ), τ did not appear in any output of the signing oracle.

Type II attacks are such that, in the adversary's forgery sig = (τ , v , s ), τ is recycled from an output sig (i ) = (τ (i ) , v (i ) , s (i ) ) of the signing oracle, for some index i ∈ {1, . . . , Q}. However, if Msg = (m 1 , . . . , m N ) and

Msg (i ) = (m (i ) 1 , . . . , m (i )
N ) denote the forgery message and the i -th signing query, respectively, we have

D 0 •s + N k=1 D k •m k = D 0 •s (i ) + N k=1 D k •m (i ) k .
Type III attacks are those where the adversary's forgery sig = (τ , v , s ) recycles τ from an output sig (i ) = (τ (i ) , v (i ) , s (i ) ) of the signing oracle (i.e., τ (i ) = τ for some index i ∈ {1, . . . , Q}) and we have the collision

D 0 • s + N k=1 D k • m k = D 0 • s (i ) + N k=1 D k • m (i ) k . (3)
Type III attacks imply a collision for the chameleon hash function of Kawachi et al. [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]: if (3) holds, a short vector of

Λ ⊥ q ([D 0 | D 1 | . . . | D N ]) is obtained as s T -s (i ) T | m 1 T -m (i ) 1 T | . . . | m N T -m (i ) N T T ,
so that a collision breaks the SIS assumption.

The security against Type I attacks is proved by Lemma 6 which applies the same technique as in [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF][START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. In particular, the prefix guessing technique of [START_REF] Hohenberger | Short and stateless signatures from the RSA assumption[END_REF] allows keeping the modulus smaller than the number Q of adversarial queries as in [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. In order to deal with Type II attacks, we can leverage the technique of [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF]. In Lemma 7, we prove that Type II attack would also contradict SIS. Lemma 6. The scheme is secure against Type I attacks if the SIS m,q,β assumption holds for β = m 3/2 σ(σ 1 + N/ √ 2) + m 1/2 (σ + σ 1 ) + ( + 1)σm. (The proof is given in Appendix B.2.) Lemma 7. The scheme is secure against Type II attacks if the SIS m,q,β assumption holds for

β = m 3/2 2σ 2 ( + 2) + N σ/ √ 2 + 2σ 1 m 1/2 . (The proof is detailed in Appendix B.3.)

Protocols for Signing a Committed Value and Proving Possession of a Signature

We first show a two-party protocol whereby a user can interact with the signer in order to obtain a signature on a committed message.

In order to prove that the scheme still guarantees unforgeability for obliviously signed messages, we will assume that each message block m k ∈ {0, 1} 2m is obtained by encoding the actual message

M k = M k [1] . . . M k [m] ∈ {0, 1} m as m k = ( Mk [1], M k [1], . . . , Mk [m], M k [m]
). Namely, each 0 (resp. each 1) is encoded as a pair (1, 0) (resp. (0, 1)). The reason for this encoding is that the proof of Theorem 2 requires that at least one block m k of the forgery message is 1 while the same bit is 0 at some specific signing query. We will show that the correctness of this encoding can be efficiently proved using Stern-like protocols.

To sign committed messages, a first idea is exploit the fact that our signature of Section 3.1 blends well with the SIS-based commitment scheme suggested by Kawachi et al. [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]. In the latter scheme, the commitment key consists of matrices

(D 0 , D 1 ) ∈ Z 2n×2m q × Z 2n×2m q
, so that message m ∈ {0, 1} 2m can be committed to by sampling a Gaussian vector s ← D Z 2m ,σ and computing

C = D 0 • s + D 1 • m ∈ Z 2n
q . This scheme extends to commit to multiple messages (m 1 , . . . , m N ) at once by computing

C = D 0 • s + N k=1 D k • m k ∈ Z 2n
q using a longer commitment key (D 0 , D 1 , . . . , D N ) ∈ (Z 2n×2m q ) N +1 . It is easy to see that the resulting commitment remains statistically hiding and computationally binding under the SIS assumption.

In order to make our construction usable in the definitional framework of Camenisch et al. [START_REF] Camenisch | Formal treatment of privacy-enhancing credential systems[END_REF], we assume common public parameters (i.e., a common reference string) and encrypt all witnesses of which knowledge is being proved under a public key included in the common reference string. The resulting ciphertexts thus serve as statistically binding commitments to the witnesses. To enable this, the common public parameters comprise public keys

G 0 ∈ Z n× q , G 1 ∈ Z n×2m q
for multi-bits variants of the dual Regev cryptosystem [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] and all parties are withheld access to the underlying private keys. In order to prove that the content of a perfectly hiding commitment c m is consistent with encrypted values, the protocols of Ling et al. [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF] come in handy.

Global-Setup: Let B = √ nω(log n) and let χ be a B-bounded distribution (i.e., it outputs integer samples with norm at most B with overwhelming probability). Let p > σ • ω(log n) upper-bounds entries of vectors sampled from the distribution D Z 2m ,σ . Generate two public keys for the dual Regev encryption scheme in its multi-bit variant. These keys consists of a public random matrix B ← U (Z n×m q ) and random matrices

G 0 = B • E 0 ∈ Z n× q , G 1 = B • E 1 ∈ Z n×2m q
, where E 0 ∈ Z m× and E 1 ∈ Z m×2m are short Gaussian matrices with columns sampled from D Z m ,σ . These matrices will be used to encrypt integer vectors of dimension and 2m, respectively. Finally, generate public parameters CK := {D k } N k=0 consisting of uniformly random matrices D k ← U (Z 2n×2m q ) for a statistically hiding commitment to vectors in ({0, 1} 2m ) N . Return public parameters consisting of

par := { B ∈ Z n×m q , G 0 ∈ Z n× q , G 1 ∈ Z n×2m q , CK}.
Protocol: The signer S, who holds a key pair P K := {A, {A j } j=0 , D, u}, SK := T A , interacts with the user U who has a message (m 1 , . . . , m N ), in the following interactive protocol.

1. U samples s ← D Z 2m ,σ and computes c m = D 0 • s + N k=1 D k • m k ∈ Z 2n q
which is sent to S as a commitment to (m 1 , . . . , m N ). In addition, U encrypts {m k } N k=1 and s under the dual-Regev public key (B, G 1 ) by computing for all k ∈ {1, . . . , N }:

c k = (c k,1 , c k,2 ) = B T • s k,0 + e k,1 , G T 1 • s k,0 + e k,2 + m k • q/2 ∈ Z m q × Z 2m q (4)
for randomly chosen s k,0 ← χ n , e k,1 ← χ m , e k,2 ← χ 2m , and

c s = (c s ,1 , c s ,2 ) = B T • s 0 + e 0,1 , G T 1 • s 0 + e 0,2 + s • q/p ∈ Z m q × Z 2m q (5)
where s 0 ← χ n , e 0,1 ← χ m , e 0,2 ← χ 2m . The ciphertexts {c k } N k=1 and c s are sent to S along with c m . Then, U generates an interactive zero-knowledge argument to convince S that c m is a commitment to (m 1 , . . . , m N ) with the randomness s such that {m k } N k=1 and s were honestly encrypted to {c k } N i=1 and c s , as in ( 4) and [START_REF] Asharov | Multiparty computation with low communication, computation and interaction via threshold FHE[END_REF]. For convenience, this argument system will be described in Section 5.3, where we demonstrate that, together with other zeroknowledge protocols used in this work, it can be derived from a Sternlike [START_REF] Stern | A new paradigm for public key identification[END_REF] protocol constructed in Section 5.1.

If the argument of step 1 properly verifies, S samples s

← D Z 2m ,σ0
and computes a vector

u m = u + D • bin c m + D 0 • s ∈ Z n q .
Next, S randomly picks τ ← {0, 1} and uses T A to compute a delegated basis

T τ ∈ Z 2m×2m for the matrix A τ ∈ Z n×2m q of (1). Using T τ ∈ Z 2m×2m , S samples a short vector v ∈ Z 2m in D u M Λ ⊥ (Aτ ),σ . It returns the vector (τ, v, s ) ∈ {0, 1} × Z 2m × Z 2m to U . 3. U computes s = s + s over Z and verifies that A τ • v = u + D • bin D 0 • s + N k=1 D k • m k mod q.
If so, it outputs (τ, v, s). Otherwise, it outputs ⊥.

Note that, if both parties faithfully run the protocol, the user obtains a valid signature (τ, v, s) for which the distribution of s is D Z 2m ,σ1 , where σ 1 = σ 2 + σ 2 0 . In order to prove possession of a message-signature pair, the user runs the following protocol.

Prove: On input of a signature (τ, v = (v T 1 | v T 2 ) T , s) ∈ {0, 1} × Z 2m × Z 2m on the message (m 1 , . . . , m N ), the user does the following. 1. Using (B, G 0 ) and (B, G 1 ) generate perfectly binding commitments to τ ∈ {0, 1} , {m k } N k=1 , v 1 , v 2 ∈ Z m and s ∈ Z 2m . Namely, compute c τ = (c τ,1 , c τ,2 ) = B T • s τ + e τ,1 , G T 0 • s τ + e τ,2 + τ • q/2 ∈ Z m q × Z q , c k = (c k,1 , c k,2 ) = B T • s k,0 + e k,1 , G T 1 • s k,0 + e k,2 + m k • q/2 ∈ Z m q × Z 2m q ∀k ∈ {1, . . . , N } for where s τ ← χ n , e τ,1 ← χ m , e τ,2 ← χ , s k,0 ← χ n , e k,1 ← χ m , e k,2 ← χ 2m
, as well as

c v1 = (c v1,1 , c v1,2 ) = B T • s v1 + e v1,1 , G T 1 • s v1 + e v1,2 + v 1 • q/p ∈ Z m q × Z m q c v2 = (c v2,1 , c v2,2 ) = B T • s v2 + e v2,1 , G T 1 • s v2 + e v2,2 + v 2 • q/p ∈ Z m q × Z m q c s = (c s,1 , c s,2 ) = B T • s 0 + e 0,1 , G T 1 • s 0 + e 0,2 + s • q/p ∈ Z m q × Z 2m q ,
where s v1 ,

s v2 ← χ n , e v1,1 , e v1,2 ← χ m , e v2,1 , e v2,2 ← χ m , s 0 ← χ n , e 0,1 ← χ m , e 0,2 ← χ 2m . 2. Prove in zero-knowledge that c τ , c s , c v1 , c v2 , {c k } N
k=1 encrypt a valid message-signature pair. In Section 5.4, we show that this involved zeroknowledge protocol can be derived from the statistical zero-knowledge argument of knowledge for a simpler, but more general relation that we explicitly present in Section 5.1. The proof system can be made statistically ZK for a malicious verifier using standard techniques (assuming a common reference string, we can use [START_REF] Damgård | Efficient concurrent zero-knowledge in the auxiliary string model[END_REF]). In the random oracle model, it can be made non-interactive using the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

We require that the adversary be unable to prove possession of a signature of a message (m 1 , . . . , m N ) for which it did not legally obtain a credential by interacting with the issuer. Note that the messages that are blindly signed by the issuer are uniquely defined since, at each signing query, the adversary is required to supply perfectly binding commitments {c k } N k=1 to (m 1 , . . . , m N ). In instantiations using interactive proofs, we do not consider it as a forgery if the adversary simply replays a proof generated by a honest prover.

The proof of Theorem 2 makes crucial use of the Rényi divergence using arguments in the spirit of Bai et al. [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF]. The reduction has to guess upfront the index i ∈ {1, . . . , Q} of the specific signing query for which the adversary will re-use τ (i ) . For this query, the reduction will have to make sure that the simulation trapdoor of Agrawal et al. [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] (used by the SampleRight algorithm of Lemma 5) vanishes: otherwise, the adversary's forgery would not be usable for solving SIS. This means that, as in the proof of [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF], the reduction must answer exactly one signing query in a different way, without using the trapdoor. While Böhl et al. solve this problem by exploiting the fact that they only need to prove security against non-adaptive forgers, we directly use a built-in chameleon hash function mechanism which is implicitly realized by the matrix D 0 and the vector s. Namely, in the signing query for which the Agrawal et al. trapdoor [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] cancels, we assign a special value to the vector s ∈ Z 2m , which depends on the adaptively-chosen signed message (Msg

(i ) 1 , . . . , Msg (i ) N ) and some Gaussian matrices {R k } N k=1 hidden behind {D k } N k=1 .
One issue is that this results in a different distribution for the vector s ∈ Z m . However, we can still view s as a vector sampled from a Gaussian distribution centered away from 0 2m . Since this specific situation occurs only once during the simulation, we can apply a result proved in [START_REF] Langlois | GGHLite: More efficient multilinear maps from ideal lattices[END_REF] which upper-bounds the Rényi divergence between two Gaussian distributions with identical standard deviations but different centers. By choosing the standard deviation σ 1 of s ∈ Z 2m to be polynomially larger than that of the columns of matrices {R k } N k=1 , we can keep the Rényi divergence between the two distributions of s (i.e., the one of the simulation and the one of the real game) sufficiently small to apply the probability preservation property (which still gives a polynomial reduction since the argument must only be applied on one signing query). Namely, the latter implies that, if the Rényi divergence R 2 (s real ||s sim ) is polynomial, the probability that the simulated vector s sim ∈ Z 2m passes the verification test will only be polynomially smaller than in the real game and so will be the adversary's probability of success.

Another option would have been to keep the statistical distance between s real and s sim negligible using the smudging technique of [START_REF] Asharov | Multiparty computation with low communication, computation and interaction via threshold FHE[END_REF]. However, this would have implied to use an exponentially large modulus q since σ 1 should have been exponentially larger than the standard deviations of the columns of {R k } N k=1 .

Theorem 2. Under the SIS assumption, the above protocols are secure protocols for obtaining a signature on a committed message and proving possession of a valid message-signature pair. (The proof is given in Appendix B.4.) Theorem 3. The scheme provides anonymity under the LWE assumption. (The proof is given in Appendix B.5.)

A Dynamic Lattice-Based Group Signature

In this section, the signature scheme of Section 3 is used to design a group signature for dynamic groups using the syntax and the security model of Kiayias and Yung [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF], which is recalled in Appendix A.

In the notations hereunder, for any positive integers n, and q ≥ 2, we define the "Powers-of-2" matrix H n×n log q ∈ Z n×n log q q as:

H = [1 | 2 | 4 | . . . | 2 log q -1 ] ⊗ I n =      1 2 4 . . . 2 log q -1 1 2 4 . . . 2 log q -1 . . . 1 2 4 . . . 2 log q -1     
. Also, for each vector v ∈ Z n q , we define bin(v) ∈ {0, 1} n log q to be the vector obtained by replacing each entry of v by its binary expansion. Note that v = H n×n log q • bin(v) for any v ∈ Z n q . In our scheme, each user's group membership certificate is a signature generated by the group manager on the user's public key. Since the group manager only needs to sign known (rather than committed) messages, we can use a simplified version of the signature, where the underlying chameleon hash function does not have to choose the discrete Gaussian vector s with a larger standard deviation than other vectors.

A key component of the scheme is the two-message joining protocol whereby the group manager admits new group members by signing their public key. The first message is sent by the new user U i who samples a membership secret consisting of a short vector z i ← D Z 4m ,σ (where m = 2n log q ), which is used to compute a syndrome

v i = F • z i ∈ Z 4n
q for some public matrix F ∈ Z 4n×4m q . This syndrome v i ∈ Z 4n q must be signed by U i using his long term secret key usk[i] (as in [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF][START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], we assume that each user has a long-term key upk[i] for a regular signature scheme, which is registered in some PKI) and will uniquely identify U i . In order to generate a membership certificate for v i ∈ Z 4n q , the group manager GM signs its binary expansion bin(v i ) ∈ {0, 1} 4n log q using the signature scheme of Section 3.

Equipped with his membership certificate (τ, d, s) ∈ {0, 1} × Z 2m × Z 2m , the new group member U i can sign a message using a Stern-type protocol for demonstrating his knowledge a valid certificate for which he also knows the secret key associated with the certified public key v i ∈ Z 4n q . This boils down to providing evidence that the membership certificate is a valid signature on some binary message bin(v i ) ∈ {0, 1} 4n log q for which he also knows a short

z i ∈ Z 4m such that v i = H 4n×2m • bin(v i ) = F • z i ∈ Z 4n
q . Interestingly, the process does not require any proof of knowledge of the membership secret z i during the joining phase, which is round-optimal. Analogously to the Kiayias-Yung technique [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF] and constructions based on structure-preserving signatures [START_REF] Abe | Structurepreserving signatures and commitments to group elements[END_REF], the joining protocol thus remains secure in environments where many users want to register at the same time in concurrent sessions.

We remark that a similar Stern-like protocol could also be directly used to prove knowledge of a Boyen signature [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF] on a binary expansion of the user's syndrome v i ∈ Z 4n q while preserving the user's ability to prove knowledge of a short z i ∈ Z 4m such that F • z i = v i mod q. However, this would require considerably longer private keys containing 4n • log q matrices {A j } j=0 of dimension n × m each (i.e., we would need = Θ(n • log q)). In contrast, by using the signature scheme of Section 3, we only need the group public key Y to contain = log N gs matrices in Z n×m q . Since the number of users N gs is polynomial, we have log N gs n, which results in a much more efficient scheme.

Description of the Scheme

Setup(1 λ , 1 Ngs ): Given a security parameter λ > 0 and the maximal number of group members N gs = 2 ∈ poly(λ), choose parameters n = O(λ); modulus q = poly(n); dimensions m = 2n log q ; Gaussian parameter σ = Ω( √ n log q log n); infinity norm bounds β = σω( √ log m) and B = √ nω(log n). Let χ be a B-bounded distribution. Choose a hash function H : {0, 1} * → {1, 2, 3} t for some t = ω(log n), which will be modeled as a random oracle in the security analysis. Then, do the following.

1. Generate a key pair for the signature scheme of Section 3.1 for signing single-block messages. Namely Run TrapGen(1 n , 1 m , q) to get A ∈ Z n×m q and a short basis T A of Λ ⊥ q (A). This basis allows computing short vectors in Λ ⊥ q (A) with a Gaussian parameter σ

≥ T A •ω( √ log m). Next, choose random matrices A 0 , A 1 , . . . , A , D ← U (Z n×m q ), D 0 , D 1 ← U (Z 2n×2m q )
and a vector u ← U (Z n q ). 2. Choose an additional random matrix F ← U (Z 4n×4m q ) uniformly. Looking ahead, this matrix will be used to ensure security against framing attacks. 3. Generate a master key pair for the Gentry-Peikert-Vaikuntanathan IBE scheme in its multi-bit variant. This key pair consists of a statistically uniform matrix B ∈ Z n×m q and a short basis T B ∈ Z m×m of Λ ⊥ q (B). This basis will allow us to compute GPV private keys with a Gaussian parameter σ GPV ≥ T B • √ log m. 4. Choose a one-time signature scheme Π OTS = (G, S, V) and a hash function H 0 : {0, 1} * → Z n×2m q , that will be modeled as random oracles in the security analysis. The group public key is defined as

Y := A, {A j } j=0 , B, , D, D 0 , D 1 , F, u, Π OTS , H, H 0 .
The opening authority's private key is S OA := T B and the private key of the group manager consists of S GM := T A . The algorithm outputs Y, S GM , S OA .

Join (GM,Ui) : the group manager GM and the prospective user U i run the following interactive protocol: [J user (λ, Y), J GM (λ, St, Y, S GM )] 1. U i samples a discrete Gaussian vector z i ← D Z 4m ,σ and computes v i = F • z i ∈ Z 4n q . He sends the vector v i ∈ Z 4n q , whose binary representation bin(v i ) consists of 4n log q = 2m bits, together with an ordinary digital signature sig i = Sign usk[i] (v i ) to GM. 2. J GM verifies that v i was not previously used by a registered user and that sig i is a valid signature on v i w.r.

A idi = A A 0 + j=1 id i [j]A j ∈ Z n×2m q . (6)
Then, GM runs T idi ← ExtBasis(A idi , T A ) to obtain a short delegated basis T idi of Λ ⊥ q (A idi ) ∈ Z 2m×2m . Finally, GM samples a short vector s i ← D Z 2m ,σ and uses the obtained delegated basis T idi to compute a short vector

d i = d i,1 d i,2 ∈ Z 2m such that A idi d i • = A A 0 + j=1 id i [j]A j • d i = u + D • bin D 0 • bin(v i ) + D 1 • s i mod q. ( 7
)
The triple (id i , d i , s i ) is sent to U i . Then, J user verifies that the received (id i , d i , s i ) satisfies [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF] and that d i ∞ ≤ β, s i ∞ ≤ β. If these conditions are not satisfies, J user aborts. Otherwise, J user defines the membership certificate as cert i = (id i , d i , s i ). The membership secret sec i is defined to be sec i = z i ∈ Z 4m . J GM stores transcript i = (v i , cert i , i, upk[i], sig i ) in the database St trans of joining transcripts.

Sign(Y, cert i , sec i , M ): To sign M ∈ {0, 1} * using cert i = (id i , d i , s i ), where

d i = [d T i,1 | d T i,2
] T ∈ Z 2m and s i ∈ Z 2m , as well as the membership secret sec i = z i ∈ Z 4m , the group member U i generates a one-time signature key pair (VK, SK) ← G(n) and conducts the following steps.

1. Compute G 0 = H 0 (VK) ∈ Z n×2m q and use it as an IBE public key to encrypt bin(v i ) ∈ {0, 1} 2m , where

v i = F • z i ∈ Z 4n
q is the syndrome of

sec i = z i ∈ Z 4m for the matrix F. Namely, compute c vi ∈ Z m q × Z 2m q as c vi = (c 1 , c 2 ) = B T • e 0 + x 1 , G T 0 • e 0 + x 2 + bin(v i ) • q/2 (8)
for randomly chosen e 0 ← χ n , x 1 ← χ m , x 2 ← χ 2m . Notice that, as in the construction of [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], the columns of G 0 can be interpreted as public keys for the multi-bit version of the dual Regev encryption scheme. 2. Run the protocol in Section 5.5 so as to prove the knowledge of identifier

id i = id i [1] . . . id i [ ] ∈ {0, 1} , vectors s i ∈ Z 2m , d i,1 , d i,2 ∈ Z m , z i ∈ Z 4m with infinity norm bound β; e 0 ∈ Z n , x 1 ∈ Z m , x 2 ∈ Z 2m with infinity norm bound B and bin(v i ) ∈ {0, 1} 2m , w i ∈ {0, 1} m
, that satisfy (8) as well as

A • d i,1 + A 0 • d i,2 + j=1 (id i [j] • d i,2 ) • A j -D • w i = u ∈ Z n q (9)
and

H 2n×m • w i = D 0 • bin(v i ) + D 1 • s i ∈ Z 2n q ( 10
)
F • z i = H 4n×2m • bin(v i ) ∈ Z 4n q . ( 11
)
The protocol is repeated t = ω(log n) times in parallel to achieve negligible soundness error, and then made non-interactive using the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] as a triple

π K = ({Comm K,j } t j=1 , Chall K , {Resp K,j } t j=1 ), where Chall K = H(M, VK, c vi , {Comm K,j } t j=1 ) ∈ {1, 2, 3} t 4. Compute a one-time signature sig = S(SK, (c vi , π K )).
Output the signature that consists of

Σ = VK, c vi , π K , sig . (12)
Verify(Y, M, Σ): Parse Σ as in [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF]. Then, return 1 if and only if:

(i) V(VK, (c vi , c si , c id , π K ), sig) = 1;
(ii) The proof of knowledge π K properly verifies.

Otherwise, return 0. Open(Y, S OA , M, Σ): Parse S OA as T B ∈ Z m×m and Σ as in [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF].

1. Compute G 0 = H 0 (VK) ∈ Z n×2m q . Then, using T B to compute a smallnorm matrix E 0,VK ∈ Z m×2m such that B • E 0,VK = G 0 mod q. 2. Using E 0,VK , decrypt c vi to obtain a string bin(v) ∈ {0, 1} 2m (i.e., by computing (c 2 -E T 0,VK • c 1 )/(q/2) ). 3. Determine if the bin(v) ∈ {0, 1} 2m obtained at step 2 corresponds to a vector v = H 4n×2m • bin(v) mod q that appears in a record transcript i = (v, cert i , i, upk[i], sig i ) of the database St trans for some i. If so, output the corresponding i (and, optionally, upk[i]). Otherwise, output ⊥.

We remark that the scheme readily extends to provide a mechanism whereby the opening authority can efficiently prove that signatures were correctly opened at each opening operation. The difference between the dynamic group signature models suggested by Kiayias and Yung [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] and Bellare et al. [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] is that, in the latter, the opening authority (OA) must be able to convince a judge that the Open algorithm was run correctly. Here, such a mechanism can be realized using the techniques of public-key encryption with non-interactive opening [START_REF] Damgård | Non-interactive proofs for integer multiplication[END_REF][START_REF] Damgård | Public-key encryption with non-interactive opening[END_REF]. Namely, since bin(v i ) is encrypted using an IBE scheme for the identity VK, the OA can simply reveal the decryption matrix E 0,VK , that satisfies B • E 0,VK = G 0 mod q (which corresponds to the verification of a GPV signature) and allows the verifier to perform step 2 of the opening algorithm himself. The resulting construction is easily seen to satisfy the notion of opening soundness of Sakai et al. [START_REF] Sakai | On the security of dynamic group signatures: Preventing signature hijacking[END_REF].

Security Analysis

Due to the fact that the number of public matrices {A j } j=0 is only logarithmic in N gs = 2 instead of being linear in the security parameter λ, the proof of security against misidentification attacks (as defined in Appendix A) cannot rely on the security of our signature scheme in a modular manner. The reason is that, at each run of the Join protocol, the group manager maintains a state and, instead of choosing the -bit identifier id uniformly in {0, 1} , it chooses an identifier that has not been used yet. Since λ (given that N gs = 2 is polynomial in λ), we thus have to prove security from scratch. However, the strategy of the reduction is exactly the same as in the security proof of the signature scheme. Theorem 4. The scheme is secure against misidentification attacks under the SIS assumption. (The proof is available in Appendix C.1.) Theorem 5. The scheme is secure against framing attacks under the SIS assumption. (The proof is given in Appendix C.2.) Theorem 6. Suppose that Π OTS is a strongly unforgeable one-time signature. In the random oracle model, the scheme provides CCA-anonymity under the LWE q,α assumption. Namely for any PPT adversary A with advantage ε, there exists an algorithm B solving the LWE q,α problem with advantage at most 2 -Ω(n) smaller. (The proof is given in Appendix C.3.)

Supporting Zero-Knowledge Argument Systems

This section provides a general framework that allows obtaining zero-knowledge arguments of knowledge for the majority of relations appearing in lattice-based cryptography. Since lattice-based cryptosystems are built upon the hardness of the SIS and LWE problems, the relations among objects of the schemes are typically represented by modular linear equations. Thanks to the linearity property, we can often unify the given equations into just one equation of the form:

P • x = v mod q, (13)
where (P, v) are public and x is a secret vector (or matrix) that possesses some constraints to be proven in zero-knowledge, e.g., its smallness (like a SIS solution, an LWE noise) or a special arrangement of its entries. Starting from this high-level observation, we look for a tool that handles these constraints well.

Stern's protocol [START_REF] Stern | A new paradigm for public key identification[END_REF], originally proposed in the context of code-based cryptography, appears to be well-suited for our purpose. Stern's main idea is simple, yet elegant: To prove that a binary vector x has the fixed-Hamming-weight constraint, simply send the verifier a random permutation π(x) which should guarantee that the constraint is satisfied while leaking no additional information about x. Ling et al. [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF] developed this idea to handle the smallness constraint, via a technique called Decomposition-Extension. This technique decomposes a vector with small infinity norm B ≥ 1 into log 2 B + 1 vectors with infinity norm 1, and then, extends these vectors into elements of sets that are closed under permutations. Several subsequent works [START_REF] Langlois | Lattice-based group signature scheme with verifier-local revocation[END_REF] [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][61] employed Stern's idea and Ling et al.'s technique in different contexts, but did not address the applicability and flexibility of the protocol in an abstract, generalized manner.

In Section 5.1, we abstract Stern's protocol to capture many relations that naturally appear in lattice-based cryptography. In particular, we demonstrate that the argument systems used in Sections 5.3, 5.4 and 5.5 can all be derived from this abstract protocol. Our strategy might be of wide interest, since it yields a blueprint for proving many other intricate relations in a simple manner.

Abstracting Stern's Protocol

Let D, L, q ≥ 2 be positive integers 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. ( 14
)
We aim to construct a sZKAoK for the following abstract relation:

R abstract = (M, c), x ∈ Z D×L q × Z D q × VALID : M • x = c 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 ( 14) 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 M • y = M • r + c mod q.

The interactive protocol between P(M, c, x) and V(M, c), 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.

1. 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(π, M • r; ρ1), C2 = COM(Tπ(r); ρ2), C3 = COM(Tπ(x + r); ρ3). 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 8. 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 (M, 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 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 M • x = c mod q.

The proof of Lemma 8 employs standard simulation and extraction techniques for Stern-type protocols [54][62]. We defer it to Appendix D.

Vector Decompositions and Extensions

Our constructions in the next subsections employ the Decomposition-Extension technique for Stern-type protocols, introduced by Ling et al. [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF]. We formalize their technique as follows.

-Define, for any positive integer B, the number δ B := log 2 B + 1 and the sequence B 1 , . . . , B δ B , where

B j = B+2 j-1 2 j for all j ∈ [1, δ B ].
As noted in [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF], this sequence satisfies δ 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:

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

K m,B = K m,B 0 m×2mδ B ∈ Z m×3mδ B .
-For any positive integer i, 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}.

Lemma 9 (Decomposition-Extension). Let m, B be positive integers. Then, there exists an efficient algorithm DecExt m,B that on input vector

v ∈ [-B, B] m , outputs vector v ∈ B 3mδ B such that K m,B • v = v. Proof. Let v = (v 1 , . . . , v m ), where v i ∈ [-B, B] for all i ∈ [1, 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 K m,B • v = v. By appending 2mδ B suitable coordinates to v , one can obtain a vector v ∈ B 3mδ B such that K m,B • v = v.
Additionally, for any positive integer i, let B 2i be the set of all vectors in {0, 1} 2i having exactly i coordinates equal to 1. We denote by Ext 2i (•) the algorithm that on input vector w ∈ {0, 1} i , outputs vector ŵ ∈ B 2i : it simply appends i suitable coordinates to w.

Proving the Consistency of Commitments

The argument system used in our protocol for signing a committed value in Section 3.3 can be summarized as follows.

Common Input: Matrices

{D k ∈ Z 2n×2m q } N k=0 ; B ∈ Z n×m q ; G 1 ∈ Z n×2m q ; vectors c m ∈ Z 2n q ; {c k,1 ∈ Z m q } N k=1 ; {c k,2 ∈ Z 2m q } N k=1 ; c s ,1 ∈ Z m q ; c s ,2 ∈ Z 2m q .
Prover's Input:

{m k ∈ {0, 1} 2m } N k=1 ; s ∈ [-(p -1), (p -1)] 2m ; {s k,0 ∈ [-B, B] n , e k,1 ∈ [-B, B] m ; e k,2 ∈ [-B, B] 2m } N k=1 ; s 0 ∈ [-B, B] n , e 0,1 ∈ [-B, B] m ; e 0,2 ∈ [-B, B] 2m .
Prover's Goal: Convince the verifier in ZK that:

       c m = D 0 • s + N k=1 D k • m k mod q; c s ,1 = B T • s 0 + e 0,1 mod q; c s ,2 = G T 1 • s 0 + e 0,2 + q/p • s mod q; ∀k ∈ [N ] : c k,1 = B T • s k,0 + e k,1 ; c k,2 = G T 1 • s k,0 + e k,2 + q/2 • m k . (15)
We will show that the above argument system can be obtained from the one in Section 5.1. We proceed in 2 steps.

Step 1: Transforming the linear equations in (15) into a unified equation of the form M • x = c mod q, where x has infinity norm 1, and belongs to a "speciallydesigned" set VALID.

To do so, we first form the following vectors and matrices:

                                                   x 1 = s T 0 e T 0,1 e T 0,2 s T 1,0 e T 1,1 e T 1,2 . . . s T N,0 e T N,1 e T N,2 T ∈ [-B, B] (n+3m)(N +1) ; x 2 = m T 1 . . . m T N T ∈ {0, 1} 2mN ; x 3 = s ∈ [-(p -1), (p -1)] 2m c = c T m c T s ,1 c T s ,2 c T 1,1 c T 1,2 . . . c T N,1 c T N,2 T ∈ Z 2n+3m(N +1) q ; D = [D 1 | . . . |D N ] ∈ Z 2n×2mN q ; P 1 = B G 1 I 3m ; Q 2 = 0 q 2 I 2m ; Q p = 0 q p I 2m M 1 =         0 P 1 P 1 . . . P 1         ; M 2 =          D 0 Q p 0          ; M 3 =         D 0 Q 2 . . . Q 2         .
We then observe that (15) can be rewritten as:

M 1 • x 1 + M 2 • x 2 + M 3 • x 3 = c ∈ Z D q , (16)
where D = 2n + 3m(N + 1). Now we employ the Decomposition-Extension technique from Section 5.2 to convert [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] into the form M • x = c mod q. Specifically, if we let:

               DecExt (n+3m)(N +1),B (x 1 ) → x1 ∈ B 3(n+3m)(N +1)δ B ; M 1 = M 1 • K (n+3m)(N +1),B ∈ Z D×3(n+3m)(N +1)δ B q ; Ext 2mN (x 2 ) → x2 ∈ B 2(2mN ) ; M 2 = M 2 |0 D×2mN ] ∈ Z D×4mN q ; DecExt 2m,p-1 (x 3 ) → x3 ∈ B 3(2m)δp-1 ; M 3 = M 3 • K 2m,p-1 ∈ Z D×6mδp-1 q , L = 3(n + 3m)(N + 1)δ B + 4mN + 6mδ p-1 , and M = M 1 |M 2 |M 3 ∈ Z D×L q
, and x = x 1 x 2 x 3 , then we will obtain the desired equation:

M • x = c mod q.
Define VALID as the set of all vectors t ∈ {-1, 0, 1} L of the form t = t 1 t 2 t 3 , where t 1 ∈ B 3(n+3m)(N +1)δ B , t 2 ∈ B 2(2mN ) , and t 3 ∈ B 3(2mδp-1) . Note that x ∈ VALID.

Step 2: Specifying the set S and permutations of L elements {T π : π ∈ S} for which the equivalence ( 14) holds.

-Define S := S 3(n+3m)(N +1)δ B × S 4mN × S 6mδp-1 .

-For π = (π 1 , π 2 , π 3 ) ∈ S, and for w = w 1 w 2 w 3 ∈ Z L q , where w 1 ∈ Z

3(n+3m)(N +1)δ B q , w 2 ∈ Z 4mN q , w 3 ∈ Z 6mδp-1 q
, we define:

T π = π 1 (w 1 ) π 2 (w 2 ) π 3 (w 3 )
By inspection, it can be seen that the property ( 14) is satisfied, as desired. As a result, we can obtain the required argument system by running the protocol in Section 5.1 with common input (P, v) and prover's input x.

Proving the Possession of a Signature on a Committed Value

We now describe how to derive the protocol for proving the possession of a signature on a committed value, that is used in Section 3.3.

Common Input: Matrices

A, {A j } j=0 , D ∈ Z n×m q ; {D k ∈ Z 2n×2m q } N k=0 ; B ∈ Z n×m q ; G 1 ∈ Z n×2m q ; G 0 ∈ Z n× q ; vectors c τ,1 , {c k,1 } N k=1 , c v1,1 , c v2,1 , c s,1 ∈ Z m q ; c τ,2 ∈ Z q ; {c k,2 } N k=1 , c s,2 ∈ Z 2m q ; c v1,2 , c v2,2 ∈ Z m q ; u ∈ Z n q . Prover's Input: τ ∈ {0, 1} ; v 1 , v 2 ∈ [-β, β] m ; s ∈ [-(p -1), (p -1)] 2m ; m = (m T 1 . . . m T N ) T ∈ ({0, 1} 2m ) N ; {s k,0 } N k=1 , s v1 , s v2 , s 0 , s τ ∈ [-B, B] n ; {e k,1 } N k=1 , e v1,1 , e v2,1 , e 0,1 , e τ,1 ∈ [-B, B] m ; {e k,2 } N k=1 , e 0,2 ∈ [-B, B] 2m ; e v1,2 , e v2,2 ∈ [-B, B] m ; e τ,2 ∈ [-B, B] .
Prover's Goal: Convince the verifier in ZK that: [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF] and that

A•v 1 + A 0 •v 2 + i=1 A i •τ [i]v 2 -D•bin(D 0 •s + N k=1 D i •m k ) = u mod q,
               ∀k ∈ [N ] : c k,1 = B T • s k,0 + e k,1 ; c k,2 = G T 1 • s k,0 + e k,2 + q/2 • m k ; c v1,1 = B T • s v1 + e v1,1 mod q; c v1,2 = G T 1 • s v1 + e v1,2 + q p • v 1 mod q; c v2,1 = B T • s v2 + e v2,1 mod q; c v2,2 = G T 1 • s v2 + e v2,2 + q p • v 2 mod q; c s,1 = B T • s 0 + e 0,1 mod q; c s,2 = G T 1 • s 0 + e 0,2 + q/p • s mod q; c τ,1 = B T • s τ + e τ,1 mod q; c τ,2 = G T 0 • s τ + e τ,2 + q/2 • τ mod q. ( 18
)
We proceed in 2 steps.

Step 1: Transforming the linear equations in ( 17) and 18 into a unified equation of the form M • x = c mod q, where x has infinity norm 1, and belongs to a "specially-designed" set VALID.

Note that, if we let y = bin(D 0 •s 17) can be equivalently written as:

+ N k=1 D i •m k ) ∈ {0, 1} m , then (
A 0 •v 1 + A 0 0 •v 2 + i=1 A i 0 •τ [i]v 2 + 0 D 0 • s + -D H 2n×m • y + 0 D 1 | . . . |D N • m = u 0 2n mod q.
Next, we use basic linear algebra to combine this equation and ( 18) into:

F•v 1 +F 0 •v 2 + i=1 F i •τ [i]v 2 + M 1 •τ +M 2 • y m + M 3 •s = c mod q, ( 19
)
where matrices F, F 0 , F 1 , . . . ,

F ∈ Z D×m q , M 1 ∈ Z D× q , M 2 ∈ Z D×(m+2mN ) q , M 3 ∈ Z D×2m q
and vector c ∈ Z D q are built from the public input, for D = + 3n + 8m + 3mN . Now we further transform ( 19) using the Decomposition-Extension technique. Specifically, we form the following:

                       DecExt m,β (v 1 ) → v1 ∈ B 3mδ β ; DecExt m,β (v 2 ) → v2 ∈ B 3mδ β ; F = F • K m,β |F 0 • K m,β |F 1 • K m,β | . . . |F • K m,β |0 D×3mδ β ∈ Z D×3mδ β (2 +2) q ; Ext 2 (τ ) → τ = (τ [1], . . . , τ [ ], . . . , τ [2 ]) ∈ B 2 ; M 1 = [M 1 |0 D× ] ∈ Z D×2 q ; Ext 2(m+2mN ) y m → t ∈ B 2(m+2mN ) ; M 2 = [M 2 |0 D×(m+2mN ) ] ∈ Z D×2(m+2mN ) q ; DecExt 2m,p-1 (s) → ŝ ∈ B 3(2mδp-1) ; M 3 = M 3 • K 2m,B ∈ Z D×6mδp-1 q , Now, let L = 3mδ β (2 + 2) + 2 + 2(m + 2mN ) + 6mδ p-1 , and construct matrix M = F |M 1 |M 2 |M 3 ∈ Z D×L q and vector x = v 1 v 2 τ [1]v 2 . . . τ [ ]v 2 . . . τ [2 ]v 2 τ t ŝ ,
then we will obtain the equation M • x = c mod q. Before going to Step 2, we define VALID as the set of all vectors w ∈ {-1, 0, 1} L having the form:

w = w 1 w 2 g 1 w 2 . . . g 2 w 2 g w 3 w 4 for some w 1 , w 2 ∈ B 3mδ β , g = (g 1 , . . . , g 2 ) ∈ B 2 , w 3 ∈ B 2(m+2mN )
, and w 4 ∈ B 3(2mδp-1) . It can be checked that the constructed above vector x is an element of VALID.

Step 2: Specifying the set S and permutations of L elements {T π : π ∈ S} for which the equivalence (14) holds.

-Define S = S 3mδ β × S 3mδ β × S 2 × S 2(m+2mN ) × S 6mδp-1 .

-For π = (φ, ψ, γ, ρ, η) ∈ S and for z = ẑ z z 1 . . . z 2 z z z ∈ Z L q , where ŵ, w, w 1 , . . . ,

w 2 ∈ Z 3mδ β q , w ∈ Z 2 q , ẅ ∈ Z 2(m+2mN ) q , w ∈ Z 6mδp-1 q
, we define:

T π (z) = φ(ẑ) ψ(z) ψ(z γ(1) ) . . . ψ(z γ(2 ) ) γ(z) ρ(z) η(z)
as the permutation that transforms z as follows:

1. It rearranges the order of the 2 blocks z 1 , . . . , z 2 according to γ.

2. It then permutes block ẑ according to φ, blocks z, {z i } 2 i=1 according to ψ, block z according to γ, block z according to ρ, and block z according to η.

It can be check that the equivalence ( 14) holds. Therefore, we can obtain a sZKAoK for the given relation by running the protocol in Section 5.1.

The Underlying ZKAoK for the Group Signature Scheme

The argument system upon which our group signature scheme is built can be summarized as follows.

Common Input: Matrices

A, A 0 , A 1 , . . . , A , B ∈ Z n×m q , D 0 , D 1 ∈ Z 2n×2m q , F ∈ Z 4n×4m q , H 2n×m ∈ Z 2n×m q , H 4n×2m ∈ Z 4n×2m q , G 0 ∈ Z n×2m q ; vectors u ∈ Z n q , c 1 ∈ Z m q , c 2 ∈ Z 2m q . Prover's Input: z ∈ [-β, β] 4m , y ∈ {0, 1} 2m , w ∈ {0, 1} m , d 1 , d 2 ∈ [-β, β] m , s ∈ [-β, β] 2m , id = (id[1], . . . , id[ ]) T ∈ {0, 1} , e 0 ∈ [-B, B] n , e 1 ∈ [-B, B] m , e 2 ∈ [-B, B] 2m . Prover's Goal: Convince the verifier in ZK that      F • z = H 4n×2m • y mod q; H 2n×m • w = D 0 • y + D 1 • s mod q; A • d 1 + A 0 • d 2 + j=1 A j • (id[j] • d 2 ) -D • w = u mod q; c 1 = B T • e 0 + e 1 mod q; c 2 = G T 0 • e 0 + e 2 + q/2 • y mod q.
Using the same strategy as in Sections 5.3 and 5.4, we can derive a sZKAoK for the above relation from the protocol given in Section 5.1. As the transformations are very similar to the ones in Section 5.4, we will only sketch main points below.

In the first step, we unify the given equations to an equation of the form:

V •   d 1 s z   + V 0 • d 2 + j=1 V j (id[j]d 2 ) + M 1 • w y + M 2 •   e 0 e 1 e 2   = c mod q,
where matrices V, V 0 , . . . , V , M 1 , M 2 and vector c are constructed from the public input. We then perform the Decomposition-Extension technique for the secret vectors

x 1 = (d 1 s z ) ∈ [-β, β] 7m , d 2 ∈ [-β, β] m ; x 2 ∈ {0, 1} 3m ; and x 3 = (e 0 e 1 e 2 ) ∈ [-B, B] n+3m
. This allows us to obtain a unified equation P • x = c mod q, and to define the sets VALID, S, and permutations {T π : π ∈ S} so that the equivalence ( 14) holds, in a similar manner as in Section 5.4.

introduced by Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] in 2003 and was extended to dynamic groups by Bellare, Shi and Zhang (BSZ) in 2005 [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF].

In the setting of dynamic groups, the syntax of group signatures includes an interactive protocol which allows users to register as new members of the group at any time. The syntax and the security model are those defined by Kiayias and Yung [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF]. Like the very similar BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], the Kiayias-Yung (KY) model assumes an interactive join protocol whereby a prospective user becomes a group member by interacting with the group manager. This protocol provides the user with a membership certificate, cert i , and a membership secret, sec i .

We denote by N ∈ Poly(n) the maximal number of group members.

Definition 4 (Dynamic Group Signature). A dynamic group signature scheme consists of the following algorithms or protocols.

Setup(1 n , N ): given a security parameter n and a maximal number of group members N ∈ N, this algorithm is run by a trusted party to generate a group public key Y, the group manager's private key S GM and the opening authority's private key S OA . Each key is given to the appropriate authority while Y is made public. The algorithm also initializes a public state St comprising a set data structure St users = ∅ and a string data structure St trans = .

In the following, all algorithms have access to the public parameters Y. Join: is an interactive protocol between the group manager GM and a user U i where the latter becomes a group member. The protocol involves two interactive Turing machines J user and J GM that both take Y as input. Each membership certificate contains a unique tag that identifies the user.

The correctness requirement basically captures that, if all parties honestly run the protocols, all algorithms are correct with respect to their specification described as above.

The Kiayias-Yung model [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] considers three security notions: the security against misidentification attacks requires that, even if the adversary can introduce users under its control in the group, it cannot produce a signature that traces outside the set of dishonest users. The notion of security against framing attacks implies that honest users can never be accused of having signed messages that they did not sign, even if the whole system conspired against them. And finaly the anonymity property is also formalized by granting the adversary access to a signature opening oracle as in the models of [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF].

Correctness for Dynamic Group Signatures. Following the Kiayias-Yung terminology [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF], we say that a public state St is valid if it can be reached from St = (∅, ε) by a Turing machine having oracle access to J GM . Also, a state St is said to extend another state St if it is within reach from St.

Moreover, as in [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF], when we write cert i Y sec i , it means that there exists coin tosses for J GM and J user such that, for some valid public state St , the execution of the interactive protocol [J user (n, Y), J GM (n, St , Y, S GM )]( ) provides J user with i, sec i , cert i .

Definition 5 (Correctness).

A dynamic group signature scheme is correct if the following conditions are all satisfied:

(1) In a valid state St, |St users | = |St trans | always holds and two distinct entries of St trans always contain certificates with distinct tag. (2) If [J user (n, Y), J GM (n, St, Y, S GM )] is run by two honest parties following the protocol and at the end i, cert i , sec i is obtained by J user , then it holds that cert i Y sec i . (3) For each i, cert i , sec i such that cert i Y sec i , satisfying condition 2, it always holds that:

Verify Sign(Y, cert i , sec i , M ), M, Y = 1 (4) For any outcome i, cert i , sec i of the interaction [J user (., .), J GM (., St, ., .)] for some valid state St, if σ = Sign(Y, cert i , sec i , M ), then

Open(M, σ, S OA , Y, St ) = i.
We formalize security properties via experiments where the adversary interacts with a stateful interface I that maintains the following variables:

state I : is a data structure representing the state of the interface as the adversary invokes the various oracles available in the attack games. It is initialized as state I = (St, Y, S GM , S OA ) ← Setup(n, N ). It includes the (initially empty) set St users of group members and a dynamically growing database St trans storing the transcripts of previously executed join protocols. n = |St users | < N denotes the current cardinality of the group.

-Sigs: is a database of signatures created by the signing oracle. Each entry consists of a triple (i, M, σ) indicating that message M was signed by user i. -U a : is the set of users that were introduced by the adversary in the system in an execution of the join protocol. -U b : is the set of honest users that the adversary, acting as a dishonest group manager, introduced in the system. For these users, the adversary obtains the transcript of the join protocol but not the user's membership secret.

When mounting attacks, adversaries will be granted access to the following oracles:

-Q pub , Q keyGM and Q keyOA : when these oracles are invoked, the interface looks up state I and returns the group public key Y, the GM's private key S GM and the opening authority's private key S OA respectively. -Q a-join : allows the adversary to introduce users under his control in the group. On behalf of the GM, the interface runs J GM in interaction with the J user -executing adversary who plays the role of the prospective user in the join protocol. -Q sig : given a message M , an index i, the interface checks whether the private area of state I contains a certificate cert i and a membership secret sec i . If no such elements (cert i , sec i ) exist or if i ∈ U b , the interface returns ⊥. Otherwise, it outputs a signature σ on behalf of user i and also sets Sigs ← Sigs||(i, M, σ). -Q open : when this oracle is invoked on input of a valid pair (M, σ), the interface runs algorithm Open using the current state St. When S is a set of pairs of the form (M, σ), Q ¬S open denotes a restricted oracle that only applies the opening algorithm to pairs (M, σ) which are not in S.

-Q read and Q write : are used by the adversary to read and write the content of state I . Namely, at each invocation, Q read outputs the whole state I but the public/private keys and the private part of state I where membership secrets are stored after Q b-join -queries. By using Q write , the adversary can modify state I at will as long as it does not remove or alter elements of St users , St trans or invalidate the public state St: for example, the adversary is allowed to create dummy users as long as he/she does not re-use already existing certificate tags.

Using this formalism, we can now properly define the three announced security properties.

Security Against Misidentification Attacks. In a misidentification attack, the adversary can corrupt the opening authority using the Q keyOA oracle. Moreover, he/she can also introduce malicious users in the group via Q a-join -queries. His/her purpose is to come up with a valid signature σ . He/she succeeds if the produced signature σ does not open to any adversarially-controlled. Definition 6. A dynamic group signature scheme is secure against misidentification attacks if, for any PPT adversary A involved in the experiment hereunder, we have the advantage of A to be:

Adv mis-id A (n) = Pr Exp mis-id A (n) = 1 ∈ negl (n) Algorithm 1: Experiment Exp mis-id A (n) 1 stateI = (St, Y, S GM , S OA ) ← Setup(n, N ); 2 (M , σ ) ← A(Q pub , Q a-join , Q read , Q keyOA ); 3 if Verify(σ , M , Y) = 0 then 4 return 0; 5 i = Open(M , σ , S OA , Y, St ); 6 if i ∈ U a then 7 return 1; 8 return 0;
Non-Frameability. Framing attacks consider the situation where the entire system, including the group manager and the opening authority, is colluding against some honest user. The adversary can corrupt the group manager as well as the opening authority (via oracles Q keyGM and Q keyOA , respectively). He/she is also allowed to introduce honest group members (via Q b-join -queries), observe the system while these users sign messages and create dummy users using Q write . The adversary eventually aims at framing an honest group member.

Definition 7. A dynamic group signature scheme is secure against framing attacks if, for any PPT adversary A involved in the experiment below, it holds that:

Adv fra A (n) = Pr Exp fra A (n) = 1 ∈ negl (n)
Full Anonymity. The notion of anonymity is formalized by means of a game involving a two-stage adversary. The first stage is called play stage and allows the adversary A to modify state I via Q write -queries and open arbitrary signatures by probing Q open . When the play stage ends, A chooses a message M as well as two pairs (sec 0 , cert 0 ) and (sec 1 , cert 1 ), consisting of a valid membership certificate and a corresponding membership secret. Then, the challenger flips a coin d ← {0, 1} and computes a challenge signature σ using (sec d , cert d ). The adversary is given σ with the task of eventually guessing the bit d ∈ {0, 1}. Before doing so, he/she is allowed further oracle queries throughout the second stage, called guess stage, but is restricted not to query Q open for (M , σ ).

B.1 The Rényi Divergence

Instead of the classical statistical distance we sometime use the Rényi divergence, which is a measurement of the distance between two distributions. Its use in security proofs for lattice-based systems was first considered by Bai et al. [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF].

Definition 9 (Rényi divergence). For any two discrete distributions P and Q such that Supp(P ) ⊆ Supp(Q), and a ∈]1, +∞[, we define the Rényi divergence of order a by:

R a (P ||Q) =   x∈Supp(P ) P (x) a Q(x) a-1   1 a-1
We define the Rényi divergences of orders 1 and +∞ by:

R 1 (P ||Q) = exp   x∈Supp(P ) P (x) log P (x) Q(x)   and R ∞ (P ||Q) = max x∈Supp(P ) P (x) Q(x) .
The divergence R 1 is the (exponential) of the Kullback-Leibler divergence.

We will focus on the following properties of the Rényi divergence, the proofs can be found in [START_REF] Langlois | GGHLite: More efficient multilinear maps from ideal lattices[END_REF]. denote the conditional distribution of Y 2 given that Y 1 = y 1 . Then we have:

• R a (P ||Q) = P a (P 1 ||Q 1 ) • R a (P 2 ||Q 2 ) if Y B and Y 2 are independent; • R a (P ||Q) ≤ R ∞ (P 1 ||Q 1 ) • max y1∈X R a P 2|1 (•|y 1 )||Q 2|1 (•|y 1 ) . Probability Preservation: Let A ⊆ Supp(Q) be an arbitrary event. If a ∈ ]1, +∞[, then Q(A) ≥ P (A) a a-1 /R a (P ||Q).
Further we have:

Q(A) ≥ P (A)/R ∞ (P ||Q)
Weak Triangle Inequality: Let P 1 , P 2 , P 3 be three distributions with Supp(P 1 ) ⊆ Supp(P 2 ) ⊆ Supp(P 3 ). Then we have:

R a (P 1 ||P 3 ) ≤ R a (P 1 ||P 2 ) • R ∞ (P 2 ||P 3 ), R ∞ (P 1 ||P 2 ) a a-1 • R a (P 2 ||P 3 ) if a ∈]1, +∞[.
In our proofs, we mainly use the probability preservation to bound the probabilities during hybrid games where the two distribution are not statistically indistinguishable in the attacker point of view.

B.2 Proof of Lemma 6

Proof. Let A be a PPT adversary that can mount a Type I attack with nonnegligible success probability ε. We construct a PPT algorithm B that uses A to break the SIS m,q,β assumption. It takes as input Ā ∈ Z n×m q and computes v ∈ Λ ⊥ q ( Ā) with 0 < v ≤ β . Algorithm B first chooses the -bit strings τ (1) , . . . , τ (Q) ← U ({0, 1} ) to be used in signing queries. As in [START_REF] Hohenberger | Short and stateless signatures from the RSA assumption[END_REF], it guesses the shortest prefix such that the string τ contained in A's forgery differs from all prefixes of τ (1) , . . . , τ (Q) . To this end, B chooses i † ← U ({1, . . . , Q}) and t † ← U ({1, . . . , }) so that, with probability 1/(Q • ), the longest common prefix between τ and one of the

{τ (i) } Q i=1 is the string τ [1] . . . τ [t † -1] = τ (i † ) [1] . . . τ (i † ) [t † -1] ∈ {0, 1} t † -1 comprised of the first (t † -1)-th bits of τ ∈ {0, 1} . We define τ † ∈ {0, 1} t † as the t † -bit string τ † = τ [1] . . . τ [t † ]. By construction, with probability 1/(Q • ), we have τ † ∈ {τ (1) |t † , . . . , τ (Q) |t † }, where τ (i)
|t † denotes the t † -th prefix of τ (i) for each i ∈ {1, . . . , Q}.

Then, B runs TrapGen(1 n , 1 m , q) to obtain C ∈ Z n×m q and a basis T C of Λ ⊥ q (C) with T C ≤ O( √ n log q). Then, it picks + 1 matrices Q 0 , . . . , Q ∈ Z m×m , where each matrix Q i has its columns sampled independently from D Z m ,σ . The reduction B defines the matrices {A j } j=0 as

     A 0 = Ā • Q 0 + ( t † j=1 τ [j]) • C A j = Ā • Q j + (-1) τ [j] • C, for j ∈ [j, t † ] A j = Ā • Q j , for j ∈ [t † + 1, ]
It also sets A = Ā. We note that we have

A τ (i) = Ā A 0 + j=1 τ (i) [j]A j = Ā Ā • (Q 0 + j=1 τ (i) [j]Q j ) + ( t † j=1 τ [j] + (-1) τ [j] τ (i) [j]) • C = Ā Ā • (Q 0 + j=1 τ (i) [j]Q j ) + h τ (i) • C where h τ (i) ∈ [1, t † ] ⊂ [1,
] stands for the Hamming distance between τ (i)

|t † and τ † |t † . Note that, with probability 1/(Q• ) and since q > , we have h τ (i) = 0 mod q whenever τ (i)

|t † = τ |t † .
Next, B picks a random short matrix R ← Z m×m which has its columns independently sampled from D Z m ,σ and computes

D = Ā • R.
Finally, B samples short vectors e u ∈ D Z m ,σ1 and computes the vector u ∈ Z n q as u = Ā • e u ∈ Z n q . The public key

P K := A, {A j } j=0 , {D k } N k=0 , D, u
each i ∈ {1, . . . , Q} from the signing oracle. At the end of the game, the adversary outputs a forgery sig = (τ , v , s ) on a message Msg = (m 1 , . . . , m N ). By hypothesis, the adversary's advantage is ε = Pr[W 0 ]. We assume w.l.o.g. that the random -bit strings τ (1) , . . . , τ (Q) are chosen at the very beginning of the game. Since (Msg , sig ) is a Type II forgery, there exists an index i ∈ {1, . . . , Q} such that τ = τ (i ) .

Game 1: This game is identical to Game 0 with the difference that the reduction aborts the experiment in the unlikely event that, in the adversary's forgery sig = (τ , v , s ), τ coincides with more than one of the random -bit strings τ (1) , . . . , τ (Q) used by the challenger. If we call F 1 the latter event, we have Pr[F 1 ] < Q 2 /2 since we are guaranteed to have ¬F 1 as long as no two τ (i) , τ (i ) collide. Given that Game 1 is identical to Game 0 until F 1 occurs, we have

| Pr[W 1 ] -Pr[W 0 ]| ≤ Pr[F 1 ] < Q 2 /2 .
Game 2: This game is like Game 1 with the following difference. At the outset of the game, the challenger B chooses a random index i † ← U ({1, . . . , Q}) as a guess that A's forgery will recycle the -bit string τ (i † ) ∈ {0, 1} of the i †th signing query. When A outputs its Type II forgery sig = (τ , v , s ), the challenger aborts in the event that τ (i † ) = τ (i.e., i † = i ). Since the choice of i † in {1, . . . , Q} is independent of A's view, we have Pr

[W 2 ] = Pr[W 1 ]/Q.
Game 3: In this game, we modify the key generation phase and the way to answer signing queries. First, the challenger B randomly picks h 0 , h 1 , . . . , h ∈ Z q subject to the constraints

h 0 + j=1 τ (i † ) [j] • h j = 0 mod q h 0 + j=1 τ (i) [j] • h j = 0 mod q i ∈ {1, . . . , Q} \ {i † }
It runs (C, T C ) ← TrapGen(1 n , 1 m , q), (D 0 , T D0 ) ← TrapGen(1 2n , 1 2m , q) so as to obtain statistically random matrices C ∈ Z n×m q , D 0 ∈ Z 2n×2m q with trapdoors T C ∈ Z m×m , T D0 ∈ Z 2m×2m consisting of short bases of Λ ⊥ q (C) and Λ ⊥ q (D 0 ), respectively. Then, B chooses a uniformly random D ← U (Z n×m q ) and re-randomizes it using short matrices S, S 0 , S 1 , . . . , S ← Z m×m , which are obtained by sampling their columns from the distribution D Z m ,σ . Namely, from

D ∈ Z n×m q , B defines A = D • S A 0 = D • S 0 + h 0 • C (20) A j = D • S j + h j • C ∀j ∈ {1, . . . , }
In addition, B picks random matrices D 1 , . . . , D N ← U (Z 2n×2m q ) and a random vector c M ← U (Z 2n q ). It samples short vectors v 1 , v 2 ← D Z m ,σ and computes

u ∈ Z n q as u = A τ (i † ) • v 1 v 2 -D • bin(c M ) mod q, where A τ (i † ) = A A 0 + j=1 τ (i † ) [j] • A j = D • S D • (S 0 + j=1 τ (i † ) [j] • S j ) .
The adversary's signing queries are then answered as follows.

-At the i-th signing query (m

(i) 1 , . . . , m (i)
N ), whenever i = i † , we have

A τ (i) = A A 0 + j=1 τ (i) [j] • A j = A D • (S 0 + j=1 τ (i) [j] • S j ) + h τ (i) • C ∈ Z n×2m q , with h τ (i) = h 0 + j=1 τ (i) [j] • h j = 0.
This implies that B can use the trapdoor T C ∈ Z m×m to generate a signature. To this end, B first samples a discrete Gaussian vector s (i) ← D Z 2m ,σ1 and computes u M ∈ Z n q as

u M = u + D • bin( N k=1 D k • m (i) k + D 0 • s (i) ) mod q.
Then, using T C ∈ Z m×m , it samples a short vector

v (i) ∈ Z 2m in D u M Λ ⊥ (A τ (i) ),σ such that (τ (i) , v (i) , s (i) ) satisfies (2).
-At the i † -th signing query (m

(i † ) 1 , . . . , m (i † ) N ), we have A τ (i † ) = A A 0 + j=1 τ (i † ) [j] • A j = D • S D • (S 0 + j=1 τ (i † ) [j] • S j ) ∈ Z n×2m q (21)
due to the constraint h 0 + j=1 τ (i † ) [j] • h j = 0 mod q. To answer the query, B uses the trapdoor T D0 ∈ Z 2m×2m of Λ ⊥ q (D 0 ) to sample a short vector

s (i † ) ∈ D Λ c M q (D0),σ1
, where

c M = c M - N k=1 D k • m (i † ) k ∈ Z 2n
q . The obtained vector s (i † ) ∈ Z 2m thus verifies

D 0 • s (i † ) = c M - N k=1 D k • m (i † ) k mod q, (22)
and A receives sig

(i † ) = (τ (i † ) , v (i † ) , s (i † ) ), where v (i † ) = (v T 1 | v T 2 ) T . By construction, the returned signature sig (i † ) satisfies A τ (i † ) • v 1 v 2 = u + D • bin D 0 • s (i † ) + N k=1 D k • m (i † ) k mod q,
and the distribution of (τ

(i † ) , v (i † ) , s (i † )
) is statistically the same as in Game 2.

We conclude that Pr[W 2 ] is negligibly far apart from Pr[W 3 ] since, by the Leftover Hash Lemma (see [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]Lemma 13]), the public key P K in Game 3 is statistically close to its distribution in Game 2.

In Game 3, we claim that the challenger B can use A to solve the SIS problem by finding a short vector of Λ ⊥ q (D) with probability Pr[W 3 ]. Indeed, with probability Pr[W 3 ], the adversary outputs a valid signature sig = (τ

(i † ) , v , s ) on a message Msg = (m 1 , . . . , m N ) with v ≤ σ √ 2m and s ≤ σ 1 √ 2m. If we parse v ∈ Z 2m as (v 1 T | v 2 T ) T with v 1 , v 2 ∈ Z m , we have the equality A τ (i † ) • v 1 v 2 = u + D • bin(D 0 • s + N k=1 D k • m k ) mod q. ( 23
)
Due to the way u ∈ Z n q was defined at the outset of the game, B also knows short vectors

v (i † ) = (v T 1 | v T 2 ) T ∈ Z 2m such that A τ (i † ) • v 1 v 2 = u + D • bin(c M ) mod q. ( 24
)
Relation [START_REF] Brakerski | A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model[END_REF] 24) from ( 23), we get

implies that c M = D 0 • s + N k=1 D k • m k mod q by hypothesis. It follows that bin(c M ) -bin(D 0 • s + N k=1 D k • m k ) is a non-zero vector in {-1, 0, 1} m . Subtracting (
A τ (i † ) • v 1 -v 1 v 2 -v 1 = D • bin(c M ) -bin(D 0 • s + N k=1 D k • m k ) mod q,
which implies

D • S D • (S 0 + j=1 τ (i † ) [j] • S j ) • v 1 -v 1 v 2 -v 2 = D • bin(c M ) -bin(D 0 • s + N k=1 D k • m k ) mod q. ( 25
)
The above implies that the vector

w = S • (v 1 -v 1 ) + (S 0 + j=1 τ (i † ) [j] • S j ) • (v 2 -v 2 ) + bin D 0 • s + N k=1 D k • m k -bin(c M )
is a short integer vector of Λ ⊥ q (D). Indeed, its norm can be bounded as w ≤ β = √ 2( + 2)σ 2 m 3/2 + m 1/2 . We argue that it is non-zero with overwhelming probability. We already observed that bin(D 0 • s

+ N k=1 D k • m k ) -bin(c M ) is a
non-zero vector of {-1, 0, 1} m , which rules out the event that (v 1 , v 2 ) = (v 1 , v 2 ). Hence, we can only have w = 0 m when the equality

S • (v 1 -v 1 ) + (S 0 + j=1 τ (i † ) [j] • S j ) • (v 2 -v 2 ) = bin(c M ) -bin D 0 • s + N k=1 D k • m k (26)
holds over Z. However, as long as either v 1 = v 1 or v 2 = v 2 , the left-hand-side member of ( 26) is information theoretically unpredictable since the columns of matrices S and {S j } j=0 are statistically hidden in the view of A. Indeed, conditionally on the public key, each column of S and {S j } j=0 has at least n bits of min-entropy, as shown by, e.g., [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]Lemma 2.7].

B.4 Proof of Theorem 2

Proof. The proof is very similar to the proof of Theorem 1 and we will only explain the changes.

Assuming that an adversary A can prove possession of a signature on a message (m 1 , . . . , m N ) which has not been blindly signed by the issuer, we outline an algorithm B that solves a SIS instance ( Ā, β), where Ā =

[ Ā1 | Ā2 ] ∈ U (Z n×2m q ) with Ā1 , Ā2 ∈ U (Z n×m q ).
At the outset of the game, B generates the common parameters par by choosing B ∈ R Z n×m q and defining G

0 = B • E 0 ∈ Z n× q , G 1 = B • E 1 ∈ Z n×2m q
. The short Gaussian matrices E 0 ∈ Z m× and E 1 ∈ Z m×2m are retained for later use. Also, B flips a coin coin ∈ {0, 1, 2} as a guess for the kind of attack that A will mount. If coin = 0, B expects a Type I forgery, where A's forgery involves a new τ ∈ {0, 1} that was never used by the signing oracle. If coin = 1, B expects A to recycle a tag τ involved in some signing query in its forgery. Namely, if coin = 1, B expects an attack which is either a Type II forgery or a Type III forgery. If coin = 2, B rather bets that A will break the soundness of the interactive argument systems used in the signature issuing protocol or the Prove protocol. Depending on the value of coin ∈ {0, 1, 2}, B generates the issuer's public key P K and simulates A's view in different ways.

• If coin = 0, B undertakes to find a short non-zero vector of Λ ⊥ q ( Ā1 ), which in turn yields a short non-zero vector of Λ ⊥ q ( Ā). To this end, it defines A = Ā1 and generates P K by computing {A j } j=0 as re-randomizations of A ∈ Z n×m q as in the proof of Lemma 6. This implies that B can always answer signing queries using the trapdoor T C ∈ Z m×m of the matrix C without even knowing the messages hidden in the commitments c m and {c k } N k=1 , c s . When the adversary generates a proof of possession of its own at the end of the game, B uses the matrices E 0 ∈ Z m× and E 1 ∈ Z m×2m as an extraction trapdoor to extract a plain message-signature pair (m 1 , . . . , m N ), (τ , v , s ) from the ciphertexts {c k } N k=1 (c v1 , c v 2 ), c τ , c s produced by A as part of its forgery. If the extracted τ is not a new tag, then B aborts. Otherwise, it can solve the given SIS instance exactly as in the proof of Lemma 6.

• If coin = 1, the proof proceeds as in the proof of Lemma 7 with one difference in Game 3. This difference is that Game 3 is no longer statistically indistinguishable from Game 2: instead, we rely on an argument based on the Rényi divergence. In Game 3, B generates P K exactly as in the proof of Lemma 7. This implies that B takes a guess i † ← U ({1, . . . , Q}) with the hope that A will choose to recycle the tag τ (i † ) of the i † -th signing query (i.e., τ = τ (i † ) ). As in the proof of Lemma 7, B defines D = Ā1 ∈ Z n×m q and A = Ā1 • S for a small-norm matrix S ∈ Z m×m with Gaussian entries. It also "programs" the matrices {A j } j=0 in such a way that the trapdoor precisely vanishes at the i † -th signing query: in other words, the sum

A 0 + j=1 τ (i) [j]A j = Ā1 • (S 0 + j=1 τ (i) [j] • S j ) + (h 0 + j=1 τ (i) [j] • h j ) • C
does not depend on the matrix C ∈ Z n×m q (of which a trapdoor T C ∈ Z m×m is known to B) when τ (i) = τ (i † ) , but it does for all other tags τ (i) = τ (i † ) . In the setup phase, B also sets up a random matrix D 0 ∈ U (Z 2n×2m q ) which it obtains by choosing A ← U (Z n×2m q ) to define

D 0 = Ā A ∈ Z 2n×2m q . (27)
Then, it computes c M = D 0 • s 0 ∈ Z 2n q for a short Gaussian vector s 0 ← D Z 2m ,σ0 , which will be used in the i † -th query. Next, it samples short vectors v 1 , v 2 ← D Z m ,σ to define

u = A τ (i † ) • v 1 v 2 -D • bin(c M ) ∈ Z n q .
In addition, B picks extra small-norm matrices R 1 , . . . , R N ← Z 2m×2m whose columns are sampled from D Z m ,σ , which are used to define randomizations of D 0 by computing D k = D 0 • R k for each k ∈ {1, . . . , N }. The adversary is given public parameters par := {B, G 0 , G 1 , CK}, where CK = {D k } N k=0 , and the public key P K := A, {A j } j=0 , D, u .

Using T C , B can perfectly emulate the signing oracle at all queries, except the i † -th query where the vector s (i † ) chosen by B is sampled from a distribution that departs from D Z 2m ,σ0 . At the i † -th query, B uses the extraction trapdoor

E 1 ∈ Z m×2m to obtain s (i † ) ∈ Z 2m and {m k } N k=1
-which form a valid opening of c m unless the soundness of the proof system is broken (note that the latter case is addressed by the situation coin = 3) -from the ciphertexts c (i † ) s and {c k } N k=1 sent by A at step 1 of the signing protocol. Then, B computes the vector s (i † ) as

s (i † ) = s 0 - N k=1 R k • m (i † ) k -s (i † ) ∈ Z 2m , (28)
• If coin = 2, B faithfully generates par and P K, but it retains the extraction trapdoor (E 0 , E 1 ) associated with the dual Regev public keys (G 0 , G 1 ). Note that A can break the soundness of the proof system by either: (i) Generating ciphertexts {c k } N k=1 and c s that do not encrypt an opening of c m in the signature issuing protocol; (ii) Generating ciphertexts {c k } N k=1 , c τ , c v1 , c v2 and c s that do not encrypt a valid signature in the Prove protocol. In either case, the reduction B is able to detect the event by decrypting dual Regev ciphertext using (E 0 , E 1 ) and create a breach in the soundness of the argument system.

It it easy to see that, since coin ∈ {0, 1, 2} is chosen independently of A's view, it turns out to be correct with probability 1/3. As a consequence, if A's advantage is non-negligible, so is B's.

B.5 Proof of Theorem 3

Proof. The proof is rather straightforward and consists of a sequence of three games.

Game 0: This is the real game. Namely, the adversary is given common public parameters par and comes up with a public key P K of its own. The adversary can run oblivious signing protocols with honest users. At each query, the adversary chooses a user index i and triggers an execution of the signing protocol with the challenger emulating the honest users. At some point, the adversary chooses some user index i for which the execution of the signing protocol ended successfully. At this point, the challenger B runs the real Prove protocol on behalf of user i. At the end of the game, the adversary outputs a bit b ∈ {0, 1}. We define W 0 to be the event that b = 1.

Game 1: This game is identical to Game 0 with the difference that, at each execution of the Prove protocol, the challenger runs the zero-knowledge simulator of the interactive proof system. The latter simulator uses either a trapdoor hidden in the common reference string (if Damgård's technique [START_REF] Damgård | Efficient concurrent zero-knowledge in the auxiliary string model[END_REF] is used) or proceeds by programming the random oracle which allows implementing the Fiat-Shamir heuristic. In either case, the statistical zero-knowledge property ensures that the adversary cannot distinguish Game 1 from Game 0 and | Pr

[W 1 ] -Pr[W 0 ]| ∈ negl(λ).
Game 2: This game is like Game 1 except that, at each execution of the Prove protocol, the ciphertexts {c k } N k=1 , c s , c τ , and c v1 , c v2 encrypt random messages instead of the actual witnesses. The semantic security of the dual Regev cryptosystem ensures that, under the LWE assumption, the adversary is unable to see the difference. Hence, we have

| Pr[W 2 ] -Pr[W 1 ]| ≤ Adv LWE B (λ).
In Game 2, it is easy that the adversary is interacting with a simulator that emulates the user in the Prove protocol without using the any message-signature pair. We thus conclude that, under the LWE assumption, A's view cannot distinguish a real proof of signature possession from a simulated proof produced without any witness.

As part of the generation of Y, the vector u ∈ Z n q is obtained by picking short discrete Gaussian vectors d i ,1 , d i ,2 ← D Z m ,σ and computing

u = [A | A 0 + j=1 id † [j]A j ] • d i ,1 d i ,2 -D • bin(c M ), (33)
where c M ← U (Z 2n q ) is a randomly chosen vector. Observe that, since A is statistically uniform over Z n×m q and d i ,1 ← D Z m ,σ , the distribution of u is statistically close to U (Z n q ).

• If coin = 2, B picks Ā ← U (Z n×2m q
) and a random matrix Q ← Z 2m×2m whose columns are sampled from D Z 2m ,σ . These are used to define

D 0 = Ā Ā ∈ Z 2n×2m q , and D 1 = D 0 • Q mod q, which is statistically close to U (Z 2n×2m q
). All other components of Y are obtained by faithfully running the setup algoritm.

For each value of coin ∈ {0, 1, 2}, the group public key

Y = A, {A j } j=0 , B, D, D 0 , D 1 , F, u, OT S, H, H 0
has a distribution which is statistically close to that of the real scheme and Y is given to A.

Queries. The reduction B starts interacting with the adversary A and the way it handles A's queries to the Q a-join oracle depends on the value of the bit coin ∈ {0, 1, 2}.

• If coin = 0, answers Q a-join -queries as follows. When A triggers an execution of the joining protocol, it chooses a syndrome v i ∈ Z n q . To answer the query, B chooses a fresh -bit identifier id i ∈ {0, 1} such that id i = id † . If A also provides a correct signature sig i such that Verify upk[i] (v i , sig i ) = 1, B samples s i ← D Z 2m ,σ and uses the trapdoor T C to compute a short vector

d i = [d T i,1 | d T i,2 ] T ∈ Z 2m such that A idi • d i,1 d i,2 = u + D • bin D 0 • bin(v i ) + D 1 • s i , (34)
where A idi ∈ Z n×2m q is the matrix in [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF]. Note that B is able to compute such a vector using the SampleRight algorithm of [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] (since the Hamming distance h idi between id i and id is non-zero). The membership certificate cert i = (id i , d i , s i ) is then returned to A.

• If coin = 1, algorithm B responds each Q a-join -query depending on the index i ∈ {1, . . . , Q a } of the query. Specifically, we distinguish two cases.

-If i = i , B proceeds as in the previous case. Namely, it recalls the -bit identifier id i ∈ {0, 1} (for which id i = id † ) that was chosen in the setup phase and samples a short vector s i ← D Z 2m ,σ . If A also provides a correct signature sig i such that Verify upk[i] (v i , sig i ) = 1, generates a membership certificate cert i for A as in the case coin = 0. Note that

A idi = Ā • S Ā • (S 0 + j=1 id i [j]S j ) + h idi C = Ā • S Ā + h idi • C (35)
Since h idi = 0, B can use the trapdoor T C ∈ Z m×m of Λ ⊥ q (C) to compute a short vector

d i = [d T i,1 | d T i,2 ] T ∈ Z 2m such that A idi • d i,1 d i,2 = u + D • bin D 0 • (bin(v i ) + D 1 • s i ,
where v i ∈ Z 4n q is the syndrome chosen by A at step 1 of the joining protocol. -If i = i , B undertakes to generate a membership certificate cert i for the -bit identifier id † ∈ {0, 1} that was chosen at the outset of the game. To this end, B has to compute cert i without using the trapdoor T C since the matrix A id † does no longer depend on C in [START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF]. This can be done by recalling the vector d i ,1 , d i ,2 ∈ Z m and c M ∈ Z 2n q that were used to define u ∈ Z n q in (33) and using T D1 . If A provides a correct signature sig i such that Verify upk[i ] (v i , sig i ) = 1, B uses the trapdoor T D1 of Λ ⊥ q (D 1 ) to sample a short vector s i ∈ Z 2m of D Λ c i q (D1),σ , where c i = c M -D 0 • bin(v i ) mod q, satisfying D 1 • s i = c M -D 0 • bin(v i ) mod q, before returning cert i = (id † , d i = [d T i ,1 | d T i ,2 ] T , s i ) to A. From the definition of u ∈ Z n q (33), it is easy to see that cert i = (id † , d i , s i ) forms a valid membership certificate for any membership secret z i ∈ Z 4m corresponding to the syndrome v i = F • z i mod q.

Regardless of the value of coin, queries to the random oracle H are handled by returning a uniformly chosen value in {1, 2, 3} t . For each κ ≤ Q H , we let r κ denote the answer to the κ-th H-query. Of course, if the adversary makes a given query more than once, then B consistently returns the previously defined value. Queries to the random oracle H 0 are answered in the usual way, by returning a uniformly random value in the appropriate range.

Forgery. When A halts, it outputs a signature Σ = VK , c vi , π K , sig on some message M . At this point, B uses the trapdoor T B to decrypt c vi and obtain an m-bit string bin(v ) ∈ {0, 1} m .

If we parse the proof of knowledge π K as ({Comm K,j } t j=1 , Chall K , {Resp K,j } t j=1 ), with high probability, A must have invoked the random oracle H on the input (M , VK , c vi , {Comm K,j } t j=1 ). Otherwise, the probability that Chall K = H(M , VK , c vi , {Comm K,j } t j=1 ) is negligible (at most 3 -t ). It comes that, with Assuming that fail does not occur, B can solve the problem instance as follows.

• If coin = 0, we have id = id † and B knows a short vector e u ∈ Z m such that u = Ā1 • e u mod q. Hence, it can obtain a short integer vector

h = d 1 + Q 0 + i=1 id † [i]Q i • d 2 -Q D • bin(v ) -e u ∈ Z m
such that Ā1 • h = 0 m mod q. Moreover, we have h = 0 m w.h.p. since the syndrome u ∈ Z n q statistically hides e u ∈ Z m in Λ u q ( Ā1 ). Finally, the norm of h is at most h 2 ≤ ( + 1)σ 2 m 3/2 + σm 1/2 (m + 2). This implies that (h T | 0 m ) T is a short non-zero vector of Λ ⊥ q ( Ā) and solves the initial SIS instance. • If coin = 1, the extracted witnesses (d 1 , d 2 , s , id ) and the decrypted bin(v ) satisfy id = id † ,

w = bin(D 0 • bin(v ) + D 1 • s ) = bin(D 0 • bin(v i ) + D 1 • s i ) = w i
(since ¬fail implies that the collision (30) did not occur if coin = 1) and

A A 0 A 1 . . . A -D •          d 1 d 2 id † [1]d 2 . . . id † [ ]d 2 w          = u mod q. (36)
Since B already knew short vectors (d i ,1 , d i ,2 , w i ) ∈ Z m × Z m × Z m such that

A A 0 A 1 . . . A -D •           d i ,1 d i ,2 id † [1]d i ,2 . . . id † [ ]d i ,2 w i           = u mod q, (37)
by subtracting (37) from [START_REF] Chase | Algebraic macs and keyed-verification anonymous credentials[END_REF], we find that

h = S • (d 1 -d i ,1 ) + (S 0 + j=1 id † [j]S j ) • (d 2 -d i ,2 ) + (w -w i ) ( 38
)
is a small-norm vector h ∈ Z m satisfying Ā1 • h = 0 mod q. We claim that h = 0 with high probability. Indeed, we know that w = w i if ¬fail occurs. This implies that the last term of ( 38) is non-zero, which rules out that (d 1 , d 2 ) = (d i ,1 , d i ,2 ). Since the columns of S and {S j } j=0 have a lot of entropy conditionally on Y, this implies that we can only have h = 0 m with negligible probability. Furthermore, the norm of h can be bounded by h 2 ≤ 4σ 2 m 3/2 ( + 2) + 2m 1/2 , so that (h T | 0 m ) T solves the original SIS instance.

• If coin = 2, B is done as well since the collision (30) directly provides a vector

h = bin(v ) -bin(v i ) + Q • (s -s i ) ∈ Z 2m
of Λ ⊥ q (D 0 ) (which is also in the lattice Λ ⊥ q ( Ā) by construction) and has norm h 2 ≤ 2(σ 2 (2m) 3/2 + (2m) 1/2 ). Moreover, h ∈ Z 2m is non-zero with overwhelming probability given that bin(v ) = bin(v i ) and the large amount of entropy retained by the columns Q ∈ Z 2m×2m given D 1 = D 0 • Q.

C.2 Proof of Theorem 5

Proof. Let us assume that a PPT adversary A can create a forgery (M , Σ ) that opens to some honest user i ∈ U b who did not sign M . In the random oracle model, we give a reduction B that uses A to solve an instance of the SIS 4n,4m,q,β problem: B takes as input Ā ∈ Z 4n×4m q and finds a non-zero short vector w ∈ Λ ⊥ q ( Ā). Algorithm B generates the group public key Y by faithfully running the real setup algorithm with the sole difference that, at step 2 of Setup, B defines F = Ā ∈ Z 4n×4m q . However, the distribution of Y is as in the real scheme. . Next, B recalls the vector z i ∈ Z 4m that was chosen to define the syndrome v i = F • z i at step 1 of the Join protocol as well as the identifier id i ∈ {0, 1} and the short vectors (d i,1 , d i,2 , s i ) that were supplied by A in an earlier Q b-join -query. It faithfully computes a signature by IBEencrypting bin(v i ) ∈ {0, 1} 2m and using (d i,1 , d i,2 , s i , z i , s i , id i ) to compute a -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.

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: 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); M • yc = M • r 3 mod q.

         t x ∈ VALID; C 1 = COM(
Let x = yr 3 , then we have T π2 (x ) = t x ∈ VALID which implies that x ∈ VALID. Furthermore, we have M • x = M • (y -r 3 ) = c mod q.

This concludes the proof.

2 .

 2 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, M • yc; ρ1), C3 = COM(Tπ 2 (y); ρ3). -Ch = 3: Check that C1 = COM(π3, M • r3; ρ1), C2 = COM(Tπ 3 (r3); ρ2).

Fig. 1 :

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

Lemma 10 (

 10 [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF] Le. 2.7]). Let a ∈[1, +∞]. Let P and Q denote distributions with Supp(P ) ⊆ Supp(Q). Then the following properties hold: Log. Positivity: R a (P ||Q) ≥ R a (P ||P ) = 1 Data Processing Inequality: R a (P f ||Q f ) ≤ R a (P ||Q) for any function f , where P f denotes the distribution of f (y) induced by sampling y ← P (resp. y ← Q) Multiplicativity: Assume P and Q are two distributions of a pair of random variables (Y 1 , Y 2 ). For i ∈ {1, 2}, let P i (resp. Q i ) denote the marginal distribution of Y i under P (resp. Q), and let P 2|1 (•|y 1 ) (resp. Q 2|1 (•|y 1 ))

  As a result of having generated Y itself, B knows S GM = T A and S OA = T B . The adversary B is run on input of the group public key Y := A, {A j } j=0 , B, D, D 0 , D 1 , F = Ā, u, Π OTS , H, H 0 ) . If A chooses to corrupt the group manager or the opening authority during the game, B is able to reveal S GM = T A and S OA = T B . Then, B starts interacting with A as follows. -Q keyGM -queries: If A decides to corrupt the group manager, B hands the secret key S GM = T A to A. -Q b-join -queries: At any time A can act as a corrupted group manager and introduce a new honest user i in the group by invoking the Q b-join oracle. At each Q b-join -query, B faithfully runs J user on behalf of the honest user in an execution of Join protocol. -Q pub -queries: These can be answered as in the real game, by having the simulator return Y. -Q sig -queries: When the adversary A requests user i ∈ U b to sign a message M , B first generates a one-time key pair (VK, SK) ← G(n) to compute G 0 = H 0 (VK) ∈ Z n×2m q

π 2 ,

 2 M • yc; ρ 1 ) = COM(π 3 , M • 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 ).

  Sign(cert i , sec i , M ): given a membership certificate cert i , a membership secret sec i and a message M , this probabilistic algorithm outputs a signature σ. Verify(σ, M ): given a signature σ, a message M and a group public key Y, this deterministic algorithm returns either 0 or 1. Open(S OA , M, σ): takes as input a message M , a valid signature σ w.r.t. Y , the opening authority's private key S OA and the public state St. It outputs i ∈ St users ∪ {⊥}, which is the identity of a group member or a symbol indicating an opening failure.

The execution, denoted as [J user (n, Y), J GM (n, St, Y, S GM )], ends with user U i obtaining a membership secret sec i , that no one else knows, and a membership certificate cert i . If the protocol is successful, the group manager updates the public state St by setting St users := St users ∪ {i} as well as St trans := St trans || i, transcript i .

  If this protocol successfully ends, the interface increments n, updates St by inserting the new user n in both sets St users and U a . It also sets St trans := St trans || n, transcript n . -Q b-join : allows the adversary, acting as a corrupted group manager, to introduce new honest group members of his/her choice. The interface triggers an execution of [J user , J GM ] and runs J user in interaction with the adversary who runs J GM . If the protocol successfully completes, the interface increments n, adds user n to St users and U b and sets St trans := St trans || n, transcript n . It stores the membership certificate cert n and the membership secret sec n in a private part of state I .

By "dynamic setting", we refer to a scenario where new group members can register at any time but, analogously to[START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF][START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF], we do not consider the orthogonal problem of user recovation here.

Note that each signature still requires the user to prove knowledge of his secret key. However, this is not a problem in concurrent settings as the proof of knowledge is made non-interactive via the Fiat-Shamir heuristic.

Acknowledgements

We thank Damien Stehlé for useful discussions. 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). San Ling, Khoa Nguyen and Huaxiong Wang were supported by the "Singapore Ministry of Education under Research Grant MOE2013-T2-1-041".

A Model for Group Signatures with Dynamic Groups

In this appendix the definition of group signatures, and the security requirements are presented, based on the Kiayias and Yung [START_REF] Kiayias | Secure scalable group signature with dynamic joins and separable authorities[END_REF] model.

Informally, a group signature is a scheme that allows a group member to attest that a message was provided by a member of a group without being altered during the process and preserving the anonymity of the users. This primitive was Algorithm 2: Experiment Exp fra A (n) One can wonder why the revocation is not in the dynamic group signature scheme description, the reason is only pragmatic. It is a different problem to build a scheme that allows to revoke a group member than a scheme that allows inserting a group member [START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF], and it has to be done in a case-by-case fashion.

B Deferred Proofs for the Signature with Efficient Protocols

In the security proof of the signature with efficient protocols, we make use of the Rényi divergence in a similar way to [START_REF] Bai | Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance[END_REF] in the proof of Theorem 2.

is given to A.

At the i-th signing query Msg (i) = (m

N ) ∈ ({0, 1} m ) N , B can use the trapdoor T C ∈ Z m×m to generate a signature. To do this, B first samples s (i) ← D Z 2m ,σ1 and computes a vector u M ∈ Z m q as

Using T C ∈ Z m×m , B can then sample a short vector

) satisfies the verification equation ( 2).

When A halts, it outputs a valid signature sig = (τ

At this point, B aborts and declares failure if it was unfortunate in its choice of i † ∈ {1, . . . , Q} and t † ∈ {1, . . . , }. Otherwise, with probability 1/(Q • ), B correctly guessed i † ∈ {1, . . . , Q} and t † ∈ {1, . . . , }, in which case it can solve the given SIS instance as follows.

If

which implies that the vector

. Moreover, with overwhelming probability, this vector is non-zero since, in A's view, the distribution of e u ∈ Z m is D Λ u q ( Ā),σ1 , which ensures that e u is statistically hidden by the syndrome u = Ā • e u . Finally, the norm of w is smaller than β = m 3/2 σ 2 ( + 3) + m 1/2 σ 1 which yields a valid solution of the given SIS m,q,β instance with overwhelming probability.

B.3 Proof of Lemma 7

Proof. We prove the result using a sequence of games. For each i, we denote by W i the event that the adversary wins by outputting a Type II forgery in Game i.

Game 0: This is the real game where, at the i-th signing query

) and allows returning

) satisfies the verification equation of the signature scheme. Moreover, we argue that, with noticeable probability, the integer vector s (i † ) = s (i † ) + s (i † ) will be accepted by the verification algorithm since the Rényi divergence between the simulated distribution of s (i † ) and its distribution in the real game will be sufficiently small. Indeed, its distribution is now that of a Gaussian vector D Z 2m ,σ0,z † centered in

. By choosing the standard deviation σ 0 to be at least σ 0 > N σ(2m) 3/2 + σ(2m) 1/2 , the Rényi divergence between the simulated distribution of s (i † ) (in Game 3) and its real distribution (which is the one of Game 2) can be kept constant: we have

This ensures that, with noticeable probability, (τ (i † ) , v (i † ) , s (i † ) ) will pass the verification test and lead A to eventually output a valid forgery. So, the success probability of A in Game 3 remains noticeable as [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF] implies

When W 3 occurs in Game 3, B uses the matrices (E 0 , E 1 ) to extract a plain message-signature pair (m 1 , . . . , m N ), (τ , v , s ) from the extractable commitments {c k } N k=1 (c v1 , c v2 ), c τ , c s generated by A. At this point, two cases can be distinguished. First, if c M = N k=1 D k • m k + D 0 • s mod q, then algorithm B can find a short vector of Λ ⊥ q ( Ā1 ) = Λ ⊥ q (D) exactly as in the proof of Lemma 7. In the event that

which belongs to Λ ⊥ q (D 0 ) and has norm w 2 ≤ N σ(2m) 3/2 +4σ 1 m 3/2 . Moreover, it is non-zero with overwhelming probability. Indeed, there exists at least one

Let us assume w.l.o.g. that they differ in their first two bits where m (i † ) k contains a 0 and m k contains a 1 (recall that each bit b is encoded as ( b, b) in both messages). This implies that s (i † ) (as computed in [START_REF] Camenisch | Formal treatment of privacy-enhancing credential systems[END_REF]) does not depend on the first column of R k but w does. Hence, given that the columns of R k have at least n bits of min-entropy conditionally on

Due to the definition of D 0 ∈ Z 2n×2m q in (27), we finally note that w ∈ Z 2m is also a short non-zero vector of Λ ⊥ q ( Ā).

C Security Proofs for the Dynamic Group Signature

C.1 Proof of Theorem 4

Proof. We prove that any adversary A with non-negligible success probability implies an algorithm B solving the SIS problem in the random oracle model.

Let A be such a PPT adversary. we build a PPT algorithm B that uses A to solve SIS m,q,β : Specifically, B takes as input Ā = Ā1 | Ā2 ∈ Z n×2m q , where Ā1 , Ā2 ∈ Z n×m q , and finds w ∈ Λ ⊥ q ( Ā) with 0 < w ≤ β. Initialization. Algorithm B first chooses a random bit coin ← U ({0, 1, 2}) as a guess for the kind of misidentification attack that A will mount. Also, B chooses a random -bit string id † ← U ({0, 1} ). In addition,

Looking ahead, coin = 0 corresponds to the case where, after repeated executions of A, the knowledge extractor of the proof system reveals witnesses containing a new identifier id ∈ {0, 1} that does not belong to any user in U a . In this case, B will be able to exploit A's forgery when id = id † . The case coin = 1 corresponds to B's expectation that the knowledge extractor will obtain the identifier id = id † of a group member in U a (i.e., a group member that was legitimately introduced at the i -th Q a-join -query, for some i ∈ {1, . . . , Q a }, where the identifier id † is used by Q a-join ), but bin(v ) ∈ {0, 1} 2m (which is encrypted in in c vi as part of the forgery Σ ) and the extracted

for which user i obtained a membership certificate at the i -th Q a-join -query. When coin = 1, the choice of i corresponds to a guess that the knowledge extractor will reveal an -bit identifier that coincides with the identifier id † assigned to the user introduced at the i -th Q a-join -query. The last case coin = 2 corresponds to B's expectation that decrypting c vi (which is part of Σ ) and running the knowledge extractor on A will uncover vectors bin(v

but (bin(v ), s ) = (bin(v i ), s i ), where v i ∈ Z 4n q and s i ∈ Z 2m are the vectors involved in the i -th Q a-join -query.

Depending on coin ∈ {0, 1, 2}, the group public key Y is generated using different methods.

• If coin = 0, algorithm B first randomly chooses id † ← U ({0, 1} ) as a guess for the -bit string that will be revealed by the knowledge extractor of the proof system after repeated executions of the adversary A. Then, it runs

) at random and also faithfully generates the GPV master key pair (B, T B ) as in Step 3 of the real setup algorithm. The group public key Y = A, {A j } j=0 , B, D, D 0 , D 1 , F, u, OT S, H, H 0 is finally given to A.

Note that, for each id = id † , we have

where h id ∈ [1, ] denotes the Hamming distance between the identifiers id and id † . Since q > , we have h idj = 0 mod q whenever id j = id † , so that algorithm B is able to compute (see [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]Se. 4.2], using the basis T C of Λ ⊥ q (C) and the refined GPVSample of Lemma 2) a basis T id of Λ ⊥ q (A id ) with T id ≤ Ω(m √ n log q). In contrast, algorithm B lacks a trapdoor for A id † as the latter only depends on A and {Q k } k=0 . Observe that, since the columns of the matrices {Q k } k=0 are sampled from D Z m ,σ , the matrices A 0 , . . . , A are within statistical distance 2 -Ω(m) of U (Z n×m q ).

\{i }, id i will be embedded in the membership certificate returned in the i-th Q a-join -query. Let also id † = id i be the -bit identifier that will be used in the i -th query. The reduction B picks random h 0 , h 1 , . . . , h ∈ Z q under the constraints

) and rerandomizes D = Ā1 ∈ Z n×m q using Gaussian matrices S, S 0 , S 1 , . . . , S ← Z m×m whose columns are sampled from the distribution D Z m ,σ . Namely, from D = Ā1 , B defines

probability at least ε := -3 -t , the tuple (M , VK , c vi , {Comm K,j } t j=1 ) coincides with the κ -th random oracle query for some κ ≤ Q H .

At this stage, the reduction B runs the adversary A up to 32 • Q H /( -3 -t ) times with the same random tape and input as in the initial run. All queries are answered as previously with one difference in the treatment of random oracle queries. Namely, the first κ -1 random oracle queries -which are identical to those of the first execution since A is run with the same random tape as before -receive the same answers Chall 1 , . . . , Chall κ -1 as in the first run. This implies that the κ -th query will involve exactly the same tuple (M , VK , c vi , {Comm K,j } t j=1 ) as in the first run. However, from the κ -th query onwards, A obtains fresh random oracle values Chall κ , . . . , Chall Q H at each new execution. The Improved Forking Lemma of Brickell et al. [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] guarantees that, with probability at least 1/2, B can obtain a 3-fork involving the same tuple (M , VK , c vi , {Comm K,j } t j=1 ) with pairwise distinct answers Chall

κ ∈ {1, 2, 3} t . 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 Chall From the corresponding responses (Resp K,j (1) , Resp K,j (2) , Resp K,j

), B is able

At this point, B aborts and declares failure in the following situations:

-coin = 0 but id ∈ {0, 1} is recycled from some output of the Q a-join oracle.

-coin = 0 and id = id † .

-coin = 1 but id ∈ {0, 1} never appeared in a membership certificate returned by the Q a-join oracle. -coin = 1 and id ∈ {0, 1} belongs to some user in U a , but this user is not the one introduced at the i -th Q a-join -query (i.e., i = i † and id = id † ). -coin = 1 and the knowledge extractor revealed vectors bin(v ) ∈ {0, 1} 2m and s ∈ Z 2m satisfying the collision [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF], where bin(v i ) and s i are the vectors involved in the i -th Q a-join query. -coin = 2 and the knowledge extraction yields vectors bin(v ) ∈ {0, 1} 2m and s ∈ Z 2m such that the collision (30) does not occur.

We call fail the event that one of the above situations occurs. Given that the choices of coin ← U ({0, 1, 2}) and i ← U ([1, Q a ]) are completely independent of A's view, the choice of coin is correct with probability 1/3. If coin = 0, B's choice of id † ← U ({0, 1} ) is correct with probability 1/(N gs -Q a ) ≥ 1/N gs and, when coin = 1, B's correctly guesses i ∈ [1, Q a ] with probability 1/Q a . We find

witness indistinguishable proof π K = ({Comm K,j } t j=1 , Chall K , {Resp K,j } t j=1 ). Finally, B computes a one-time signature sig = S(SK, (c vi , π K )) and returns the signature Σ = VK, c vi , π K , sig to A.

When A halts, it outputs a signature Σ = VK , c v , π K , sig for some message M , which opens to i ∈ U b although user i did not sign the message M at any time. Since (M , Σ ) supposedly frames user i , the opening of Σ must reveal the m-bit string bin(v i ) ∈ {0, 1} m . We note that the reduction B has recollection of a short vector

chose when running J user on behalf of user i when this user was introduced in the group. Hence, B would be able to solve its given SIS instance if it had another short vector z ∈ Z 4m satisfying v i = F • z mod q. To compute such a vector, B proceeds by replaying the adversary A sufficiently many times and applying the Improved Forking Lemma of Brickell et al. [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF].

If we parse π K as ({Comm K,j } t j=1 , Chall K , {Resp K,j } t j=1 ), with high probability, A must have queried H on the input (M , VK , c v , {Comm K,j } t j=1 ). Otherwise, we would only have

) with negligible probability 3 -t . It comes that, with probability at least ε := ε -3 -t , the tuple (M , VK , c v , {Comm K,j } t j=1 ) was the input of the κ -th random oracle query for some index κ ≤ Q H .

At this point, the reduction B runs the adversary A up to 32 • Q H /(ε -3 -t ) times with the same random tape and input as in the first run. All queries are answered as previously with one difference in the way to handle H-queries. Namely, the first κ -1 H-queries -which are the same as in the first execution since A is run with the same random tape -obtain the same answers Chall 1 , . . . , Chall κ -1 as in the original run. This implies that the κ -th query will also involve exactly the same tuple (M , VK , c v , {Comm K,j } t j=1 ) as in the original run. From the κ -th query forward, however, the adversary A obtains fresh random oracle outputs Chall κ , . . . , Chall Q H at each new execution. The Improved Forking Lemma et al. [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] ensures that, with probability > 1/2, B obtains a 3-fork involving the tuple (M , VK , c v , {Comm K,j } t j=1 ) of the initial run and with pairwise distinct answers Chall

κ ∈ {1, 2, 3} t . Since the forgeries of the 3-fork all correspond to the tuple (M , VK , c v , {Comm K,j } t j=1 ), they open to the same m-bit string bin(v i ) ∈ {0, 1} m and which is uniquely determined by c v . In turn, this implies that the three forgeries all reveal the same bin(v i ) at the second step of Open. With probability 1 -(7/9) t it can be shown that there exists j ∈ {1, . . . , t} such that the j-th bits of Chall

κ ,j ) = (1, 2, 3). From the corresponding responses (Resp K,j (1) , Resp K,j (2) , Resp K,j

), B is able to extract a short vector z ∈ Z 4m

Due to the statistical witness indistinguishability of the Stern-like proof of knowledge which is used to generate signature, with overwhelming probability, we have z = z i . Indeed, from the adversary's view, the distribution of z i is D Λ v i q (F),σ , which means that it has at least n bits of min-entropy. Hence, the difference h = zz i ∈ Z 4m is a suitably short non-zero vector of Λ ⊥ q ( Ā).

C.3 Proof of Theorem 6

Proof. We will proceed as in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF]: we will prove the anonymity through an hybrid argument using a sequence of indistinguishable games. The first game Game 0 is the real experiment and the last one will be such that Adv A (Game 6) = 0

Game 0: This is the real CCA-anonymity game. The challenger runs algorithm Setup(1 λ , 1 Ngs ) to obtain (Y, S OA , S GM ) and then gives Y and S GM to the attacker A. Using the secret key S OA , the challenger is able to answer all the signatures opening queries. In the challenge phase, A sends a message M together with two pairs (sec 0 , cert 0 ), (sec 1 , cert 1 ), where Game 1: In this experiment, we slightly modify Game 0: at the outset of the game, the challenger generates the one-time signature key pair (VK , SK ). During the game, if A requests the opening of a valid signature Σ = (VK, c vi , π K , sig) where VK = VK , the challenger returns a random bit and abort. However, this event F 1 would contradict the strong unforgeability of the one-time signature Π OTS . Indeed, before the challenge phase VK is independent of A's view and the probability that VK shows up in A's queries is negligible. Moreover, after seeing the challenge signature Σ , if A comes up with a valid signature Σ = (VK, c vi , π K , sig) such that VK = VK , then sig is a forged one-time signature, which defeats the strong unforgeability of Π OTS . Therefore the probability Pr[F 1 ] that the challenger aborts in this experiment is negligible. From here on, we thus assume that A's opening queries for valid signatures do not include VK .

Game 2: In this game, we program the random oracle H 0 in the following way: at the beginning of the game, we choose a uniformly random matrix G 0 ∈ Z n×2m q and set H 0 (VK ) = G 0 . From the attacker's point of view, the distribution of G 0 is statistically close to the one in the real attack game, as in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. As for other queries, for each fresh H 0 -queries on VK, the challenger samples small-norm matrices E 0,VK ← D 2m Z m ,σ and programs the oracle such that H 0 (VK) = B • E 0,VK mod q. The chosen matrices E 0,VK are retained for later use. Note that the values of H 0 (VK) are statistically close to the uniform. For any query involving a previously queried VK, the challenger consistently returns the previously stored images. The view of the attacker remains the same as in Game 1, as in the security proof of the GPV IBE [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF].

Game 3: Here, we will change the behaviour of the opening algorithm. Namely, at each fresh oracle query, we still store the matrices E 0,VK ∈ Z m×2m q and, at the beginning of the game, the challenger samples an uniformly random B ∈ Z n×m q . When the adversary queries the opening of a signature Σ = (VK, c vi , π K , sig), B recalls the small-norm matrices E 0,VK which were defined when A first queried H 0 (VK). These matrices are used as "decryption matrices" to open Σ for the corresponding G 0 = H 0 (VK) ∈ Z n×2m q . Similarly to the security proof [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], the distribution of G 0 is statistically close to the uniform, implying that Game 2 and Game 3 are statistically indistinguishable.

Game 4: Instead of faithfully generating the NIZKPoK π K , the challenger simulates the proof without using the witness (note that this is possible since the HVZK property of the underlying proof system is preserved under parallel repetitions). This is done by running the simulator for the underlying interactive protocol for each j ∈ 1, . . . , t, and then programming the random oracle H accordingly. The challenge signature Σ = (VK , c vi , π K , sig ) is statistically close to the challenge signature of the previous game, because the proof system is statistically zero-knowledge. Consequently, Game 3 and Game 4 are indistinguishable. Game 5: In this game, we change the generation of the ciphertext c vi in the challenge phase. Instead of using the real encryption algorithm of the GPV IBE to compute c vi , we return truly random ciphertexts. In other words, we let

where v i b = F•z i b , and where z 1 ← U (Z m q ), z 2 ← U (Z 2m q ) are uniformly random. The hardness of the decisional LWE q,α problem implies that c vi in Game 4 and Game 5 are computationally indistinguishable. If A can distinguish between these two games, it can distinguish

which would break the decisional LWE q,α assumption. Therefore, Game 4 and Game 5 are computationally indistinguishable. Game G (6) : Finally we make a conceptual modification on the previous game. Namely we sample uniformly random z 1 ← U (Z m q ), z 2 ← U (Z 2m q ) and assign

Clearly, the distribution of c vi has not changed since Game 5. Since Game 6 does no longer depend on the challenger's bit b ∈ {0, 1}, the result follows.

D Proof of Lemma 8

We first restate Lemma 8.

Lemma 11. 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 (M, 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 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 M • x = c mod q.

Proof. Note that, by construction, the protocol is perfectly complete: 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 M • x = c 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 C 1 = COM(π, M • 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, where C 1 = COM(π, M • 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, while C 1 = COM(π, M • (x + r) -c; ρ 1 ), Receiving a challenge Ch from V, it responds as follows: