Benoît Libert

San Ling

Fabrice Mouhartem

Khoa Nguyen

Huaxiong Wang

Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption

Keywords: Lattices, zero-knowledge proofs, group encryption, anonymity

Group encryption (GE) is the natural encryption analogue of group signatures in that it allows verifiably encrypting messages for some anonymous member of a group while providing evidence that the receiver is a properly certified group member. Should the need arise, an opening authority is capable of identifying the receiver of any ciphertext. As introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), GE is motivated by applications in the context of oblivious retriever storage systems, anonymous third parties and hierarchical group signatures. This paper provides the first realization of group encryption under lattice assumptions. Our construction is proved secure in the standard model (assuming interaction in the proving phase) under the Learning-With-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a crucial component of our system, we describe a new zero-knowledge argument system allowing to demonstrate that a given ciphertext is a valid encryption under some hidden but certified public key, which incurs to prove quadratic statements about LWE relations. Specifically, our protocol allows arguing knowledge of witnesses consisting of X ∈ Z m×n q , s ∈ Z n q and a small-norm e ∈ Z m which underlie a public vector b = X • s + e ∈ Z m q while simultaneously proving that the matrix X ∈ Z m×n q has been correctly certified. We believe our proof system to be useful in other applications involving zero-knowledge proofs in the lattice setting.

Introduction

Since the pioneering work of Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and Gentry, Peikert and Vaikuntanathan (GPV) [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], lattice-based cryptography has been an extremely active research area. Not only do lattices enable powerful functionalities (e.g., [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF][START_REF] Gorbunov | Predicate encryption for circuits from LWE[END_REF]) that have no viable realizations under discrete-logarithm or factoring-related assumptions, they also offer a number of advantages over conventional number-theoretic techniques, like simpler arithmetic operations, their conjectured resistance to quantum attacks or a better asymptotic efficiency.

The design of numerous cryptographic protocols crucially relies on zeroknowledge proofs [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF] to prove properties about encrypted or committed values so as to enforce honest behavior on behalf of participants or protect the privacy of users. In the lattice settings, efficient zero-knowledge proofs are non-trivial to construct due to the limited amount of algebraic structure. While natural methods of proving knowledge of secret keys [START_REF] Micciancio | Statistical zero-knowledge proofs with efficient provers: Lattice problems and more[END_REF][START_REF] Lyubashevsky | Lattice-based identification schemes secure under active attacks[END_REF][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] are available, they are only known to work for specific languages. When it comes to proving circuit satisfiability, the best known methods are designed for the LPN setting [START_REF] Jain | Commitments and efficient zeroknowledge proofs from learning parity with noise[END_REF] or take advantage of the extra structure available in the ring LWE setting [START_REF] Xie | Zero knowledge proofs from Ring-LWE[END_REF][START_REF] Benhamouda | Efficient zeroknowledge proofs for commitments from learning with errors over rings[END_REF]. Hence, these methods are not known to readily carry over to standard (i.e., non-ideal) lattices. In the standard model, the problem is even trickier as we do not have a lattice-based counterpart of Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] and efficient non-interactive proof systems are only available for specific problems [START_REF] Peikert | Non-interactive statistical zero-knowledge proofs for lattice problems[END_REF].

The difficulty of designing efficient zero-knowledge proofs for lattice-related languages makes it highly non-trivial to adapt privacy-preserving cryptographic primitives in the lattice setting. In spite of these technical hurdles, a recent body of work successfully designed anonymity-enabling mechanisms like ring signatures [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Aguilar-Melchor | Adapting lyubashevsky's signature schemes to the ring signature setting[END_REF], blind signatures [START_REF] Rückert | Lattice-based blind signatures[END_REF], group signatures [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF][START_REF] Laguillaumie | Lattice-based group signatures with logarithmic signature size[END_REF][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][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] or, more recently, signature schemes with companion zero-knowledge protocols [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. A common feature of all these works is that the zero-knowledge layer of the proposed protocols only deals with linear equations, where witnesses are only multiplied by public values.

In this paper, motivated by the design of advanced privacy-preserving protocols in the lattice setting, we construct zero-knowledge arguments for non-linear statements among witnesses consisting of vectors and matrices. For suitable parameters q, n, m ∈ Z, we consider zero-knowledge argument systems whereby a prover can demonstrate knowledge of secret matrices X ∈ Z m×n q and vectors s ∈ Z n q , e ∈ Z m such that: (i) e ∈ Z m has small norm; (ii) A public vector b ∈ Z n q equals b = X • s + e mod q; (iii) The underlying pair (X, s) satisfies additional algebraic relations: for instance, it should be possible to prove possession of a signature on some representation of the matrix X. In particular, our zero-knowledge argument makes it possible to prove that a given ciphertext is a well-formed LWE-based encryption with respect to some hidden, but certified public key. This protocol comes in handy in the design of group encryption schemes [START_REF] Kiayias | Group encryption[END_REF], where such languages naturally arise. In this paper, we thus construct the first construction of group encryption under lattice assumptions.

Group Encryption. As suggested by Kiayias, Tsiounis and Yung [START_REF] Kiayias | Group encryption[END_REF], group encryption (GE) is the encryption analogue of group signatures [START_REF] Chaum | Group signatures[END_REF], which allow users to anonymously sign messages on behalf of an entire group they belong to. While group signatures aim at hiding the source of some message within a crowd administered by some group manager, group encryption rather seeks to hide its destination within a group of legitimate receivers. In both cases, a verifier should be convinced that the anonymous signer/receiver indeed belongs to a purported population. In order to keep users accountable for their actions, an opening authority (OA) is further empowered with some information allowing it to un-anonymize signatures/ciphertexts. Kiayias, Tsiounis and Yung [START_REF] Kiayias | Group encryption[END_REF] formalized GE schemes as a primitive allowing the sender to generate publicly verifiable guarantees that: (1) The ciphertext is well-formed and intended for some registered group member who will be able to decrypt; [START_REF] Aguilar-Melchor | Adapting lyubashevsky's signature schemes to the ring signature setting[END_REF] the opening authority will be able identify the receiver if necessary; [START_REF] Aimani | Toward practical group encryption[END_REF] The plaintext satisfies certain properties such as being a witness for some public relation or the private key that underlies a given public key. In the model of Kiayias et al. [START_REF] Kiayias | Group encryption[END_REF], the message secrecy and anonymity properties are required to withstand active adversaries, which are granted access to decryption oracles in all security experiments.

As a natural application, group encryption allows a firewall to filter all incoming encrypted emails except those intended for some certified organization member and the content of which is additionally guaranteed to satisfy certain requirements, like the absence of malware.

GE schemes are also motivated by natural privacy applications such as anonymous trusted third parties, key recovery mechanisms or oblivious retriever storage systems. In optimistic protocols, GE allows verifiably encrypting messages to anonymous trusted third parties which mostly remain off-line and only come into play to sort out conflicts. In order to protect privacy-sensitive information such as users' citizenship, group encryption makes it possible to hide the identity of users' preferred trusted third parties within a set of properly certified trustees.

In cloud storage services, GE enables privacy-preserving asynchronous transfers of encrypted datasets. Namely, it allows users to archive encrypted datasets on remote servers while convincing those servers that the data is indeed intended for some anonymous certified client who paid a subscription to the storage provider. Moreover, a judge should be able to identify the archive's recipient in case a misbehaving server is found guilty of hosting suspicious transaction records or any other illegal content.

As pointed out by Kiayias et al. [START_REF] Kiayias | Group encryption[END_REF], group encryption also implies a form of hierarchical group signatures [START_REF] Trolin | Hierarchical group signatures[END_REF], where signatures can only be opened by a set of eligible trustees operating in a very specific manner determiner by the signer. Related work. Kiayias, Tsiounis and Yung (KTY) [START_REF] Kiayias | Group encryption[END_REF] formalized the notion of group encryption and provided a modular design using zero-knowledge proofs, digital signatures, anonymous CCA-secure public-key encryption and commitment schemes. They also gave an efficient instantiation using Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] and Camenisch-Lysyanskaya signatures [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF].

Cathalo, Libert and Yung [START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF] designed a non-interactive system in the standard model under non-interactive pairing-related assumptions. El Aimani and Joye [START_REF] Aimani | Toward practical group encryption[END_REF] suggested various efficiency improvements with both interactive and non-interactive proofs.

Libert et al. [START_REF] Libert | Traceable group encryption[END_REF] empowered the GE primitive with a refined traceability mechanism akin to that of traceable signatures [START_REF] Kiayias | Traceable signatures[END_REF]. Namely, by releasing a user-specific trapdoor, the opening authority can allow anyone to publicly trace ciphertexts encrypted for this specific group member without affecting the privacy of other users. Back in 2010, Izabachène, Pointcheval and Vergnaud [START_REF] Izabachène | Mediated traceable anonymous encryption[END_REF] considered the problem of eliminating subliminal channels in a different form of traceable group encryption.

As a matter of fact, all existing realizations of group encryption or similar primitives rely on traditional number theoretic assumptions like the hardness of factoring or computing discrete logarithms. In particular, all of them are vulnerable to quantum attacks. For the sake of not putting all one's eggs in the same basket, it is highly desirable to have instantiations based on alternative, quantum-resistant foundations.

Our results and techniques. We put forth the first lattice-based realization of the group encryption primitive and prove its security under the Learning-With-Errors (LWE) [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and Short-Integer-Solution (SIS) [START_REF] Ajtai | Generating hard instances of the short basis problem[END_REF] assumptions. As in the original design of Kiayias, Tsiounis and Yung [START_REF] Kiayias | Group encryption[END_REF], the security analysis of our scheme stands in the standard model if we avail ourselves of interaction between the prover and the verifier. In the random oracle model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF], the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] readily provides a non-interactive solution based on the same hardness assumptions.

As a core ingredient of our GE scheme, we develop a new technique allowing to prove that a given ciphertext is a valid LWE-based encryption under some hidden but certified public key. Via a novel extension of Stern-like zeroknowledge arguments [START_REF] Stern | A new paradigm for public key identification[END_REF][START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] in the lattice setting, we provide a method of proving quadratic relations between a secret certified matrix and a secret vector occurring in LWE-related languages. We believe our zero-knowledge arguments to be of independent interest as they find applications in other protocols involving zero-knowledge proofs in lattice-based cryptography.

It was shown by Kiayias et al. [START_REF] Kiayias | Group encryption[END_REF] that, in order to design a GE scheme, three ingredients are necessary: we need digital signatures, anonymous (i.e., keyprivate [START_REF] Bellare | Key-privacy in public-key encryption[END_REF]) public-key encryption and zero-knowledge proofs. While the first two ingredients are available in lattice-based cryptography, suitable zero-knowledge proof systems are currently lacking. The underlying proof system should allow the sender to prove that the ciphertext is well-formed and is decryptable by some certified group member without betraying the latter's identity. Such statements typically involve equations of the form b = X • s + e mod q, for which given integers n, m, q and vector b ∈ Z m q , the prover has to demonstrate possession of a certified matrix X ∈ Z m×n q , vector s ∈ Z n q and small-norm error vector e ∈ Z m satisfying the equation. Existing mechanisms of proving relations appearing in lattice-based cryptosystems belong to two main classes. The first one, which uses "rejection sampling" techniques for Schnorr-like protocols [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF], was introduced by Lyubashevsky [START_REF] Lyubashevsky | Lattice-based identification schemes secure under active attacks[END_REF]. The second class, which was initiated by Ling et al. [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF], appeals to "decomposition-extension-permutation" techniques in lattice-based extensions [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] of Stern's protocol [START_REF] Stern | A new paradigm for public key identification[END_REF]. These techniques mainly deal with linear equations, where each term is a product of a public matrix with a secret vector, which possibly satisfies some additional constraints (e.g., smallness) to be proven. Here, we are presented with quadratic equations where some terms X • s are products of two secret witnesses X ∈ Z m×n q and s ∈ Z n q which are involved in other equations. Proving such quadratic equations thus requires new ideas.

To overcome the above hurdle, we employ a divide-and-conquer strategy.

First, we consider the binary representations of X and s, and view the product X • s as a bunch of bit-wise products {x i • s j } i,j . Now, although these bit-wise products still admit a quadratic nature, but to prove that each of them is wellformed, it suffices to demonstrate in zero-knowledge that x i • s j belongs to the set

B = {0 • 0, 0 • 1, 1 • 0, 1 • 1} of cardinality 4.
This can be done with a Stern-like sub-protocol, using the following extending-then-permuting technique. We first extend x i • s j to vector ext(x i , s j )

def = (x i • s j , x i • s j , x i • s j , x i • s j ) ∈ {0, 1} 4
whose entries are elements of B (here, c denotes the bit 1 -c). We then employ a special permutation, determined by two random bits b x and b s , to the entries of ext(x i , s j ), such that the permuted vector is exactly the correct extension ext(x i ⊕ b x , s j ⊕ b s ), where ⊕ denotes the addition modulo 2. Seeing that a permutation of ext(x i , s j ) has entries in the set B, the verifier should be convinced that x i •s j ∈ B. Meanwhile, the bits b x and b s act as one-time pads that perfectly hide x i and s j . Furthermore, to prove that the same bits x i and s j are involved in other equations, we establish similar extending-then-permuting mechanisms for their other appearances, and use the same one-time pads b x and b s , respectively, as those places.

Having settled the problem of proving quadratic relations, we are able to realize the desired zero-knowledge layer by combining our proof system with the techniques of [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. These help us demonstrate possession of a signature on the user's public key while proving that this key is encrypted under the OA's public key. Since users' public keys consist of a matrix B U ∈ Z n×m q , we actually encrypt a hash value of this matrix under the OA's public key while the sender proves knowledge of a signature on the binary decomposition of B U . By using a suitable lattice-based hash function [START_REF] Goldreich | Collision-Free Hashing from Lattice Problems[END_REF], the Stern-like protocols of [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] make it possible to prove that the hashed matrix encrypted under the OA's public key coincides with the one for which the sender knows a certificate and which served as a public key to encrypt the actual plaintext.

The last issue to sort out is to determine the appropriate encryption schemes to work with in the two public-key encryption components. The CCA2-secure cryptosystem implied by the Agrawal-Boneh-Boyen (ABB) identity-based encryption (IBE) scheme [1] via the CHK transformation [START_REF] Canetti | Chosen-ciphertext security from identitybased encryption[END_REF] is a natural choice as it is one of the most efficient LWE-based candidates in the standard model. For technical reasons, we chose to use a variant of the ABB cryptosystem based on the trapdoor mechanism of Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] because it allows dispensing with zero-knowledge proofs of public key validity. Indeed, the Kiayias-Tsiounis-Yung model [START_REF] Kiayias | Group encryption[END_REF] mandates that certified public keys be valid public keys (for which an underlying private key exists). This requirement is easier to handle using Micciancio-Peikert trapdoors [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] since, unlike GPV trapdoors [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], they are guaranteed to exist for any public matrix.

Background and Definitions

Lattices

In our notations, all vectors are denoted in bold lower-case letters while bold upper-case letters will be used for matrices. If b ∈ R n , its Euclidean norm and infinity norm will be denoted by b and b ∞ respectively. The Euclidean norm of matrix B ∈ R m×n with columns (b i ) i≤n is denoted by B = max i≤n b i . If B is full column-rank, we let B denote its Gram-Schmidt orthogonalization.

When S is a finite set, we denote by U (S) the uniform distribution over S and by x ← D the action of sampling x according to the distribution D.

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 ([6, 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 in [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 ([14, 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 ([5, 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 rely on a basis delegation algorithm [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF] which extends a trapdoor for A ∈ Z n×m q into a trapdoor of any B ∈ Z n×m q whose left n × m submatrix is A. Lemma 4 ([17,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 .

Like [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 use a technique due to Agrawal, Boneh and Boyen [1] that realizes a punctured trapdoor mechanism [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF]. Analogously to [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], we will use such a mechanism in the real scheme and not only in the proof.

Lemma 5 ([1, Th. 19]

). There exists a PPT algorithm SampleRight that takes as inputs matrices

A ∈ Z n×m q , 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 a short vector b ∈ Z m+ m such that A A • R + C • b = u mod q and with distribution statistically close to D L,σ where L denotes the shifted lattice

Λ u q [A | A • R + C] .

Computational Problems

The security of our schemes provably relies 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 n,m,q,β is as follows: Given A ← U (Z n×m q ), find x ∈ Λ ⊥ q (A) with 0 < x ≤ β.

If q ≥ √ nβ and m, β ≤ poly(n), then SIS n,m,q,β is at least as hard as standard worst-case lattice problem SIVP γ with γ = O(β √ n) (see, e.g., [24, Se. 9]).

Definition 3. Let n, m ≥ 1, q ≥ 2, and let χ be a probability distribution on Z. For s ∈ Z n q , let A s,χ be the distribution obtained by sampling a ← U (Z n q ) and e ← χ, and outputting (a, a T • s + e) ∈ Z n q × Z q . The Learning With Errors problem LWE n,q,χ asks to distinguish m samples chosen according to A s,χ (for s ← U (Z n q )) and m samples chosen according to U (Z n q × Z q ).

If q is a prime power, B ≥ √ nω(log n), γ = O(nq/B), then there exists an efficient sampleable B-bounded distribution χ (i.e., χ outputs samples with norm at most B with overwhelming probability) such that LWE n,q,χ is as least as hard as SIVP γ (see, e.g., [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]).

Syntax and Definitions of Group Encryption

We use the syntax and the security model of Kiayias, Tsiounis and Yung [START_REF] Kiayias | Group encryption[END_REF]. The group encryption (GE) primitive involves a sender, a verifier, a group manager (GM) that manages the group of receivers and an opening authority (OA) which is capable of identitying ciphertexts' recipients. In the syntax of [START_REF] Kiayias | Group encryption[END_REF], a GE scheme is specified by the description of a relation R as well as a tuple GE = SETUP, JOIN, G r , R, sample R , ENC, DEC, OPEN, P, V of algorithms or protocols. In details, SETUP is a set of initialization procedures that all take (implicitly or explicitly) a security parameter 1 λ as input. We call them SETUP init (1 λ ), SETUP GM (param) and SETUP OA (param). The first one of these procedures generates a set of public parameters param (like the KTY construction [START_REF] Kiayias | Group encryption[END_REF], we rely on a common reference string even when using interaction between provers and verifiers). The latter two procedures are used to produce key pairs (pk GM , sk GM ), (pk OA , sk OA ) for the GM and the OA. In the following, param is incorporated in the inputs of all algorithms although we sometimes omit to explicitly write it.

JOIN = (J user , J GM ) is an interactive protocol between the GM and the prospective user. After the execution of JOIN, the GM stores the public key pk and its certificate cert pk in a public directory database. As in [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF], we will restrict this protocol to have minimal interaction and consist of only two messages: the first one is the user's public key pk sent by J user to J GM and the latter's response is a certificate cert pk for pk that makes the user's group membership effective. We do not require the user to prove knowledge of his private key sk or anything else about it. In our construction, valid keys will be publicly recognizable and users will not have to prove their validity. By avoiding proofs of knowledge of private keys, the security proof never has to rewind the adversary to extract those private keys, which allows supporting concurrent joins as advocated by Kiayias and Yung [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF]. If applications demand it, it is possible to add proofs of knowledge of private keys in a modular way but our security proofs do not require rewinding the adversary in executions of JOIN.

Algorithm sample R allows sampling pairs (x, w) ∈ R (made of a public value x and a witness w) using keys (pk R , sk R ) produced by G r (1 λ ) which samples public/secret parameters for the relation R. Depending on the relation, sk R may be the empty string (as in the scheme [START_REF] Kiayias | Group encryption[END_REF] and ours which both involve publicly samplable relations). The testing procedure R(x, w) uses pk R to return 1 whenever (x, w) ∈ R. To encrypt a witness w such that (x, w) ∈ R for some public x, the sender fetches the pair (pk, cert pk ) from database and runs the randomized encryption algorithm. The latter takes as input w, a label L, the receiver's pair (pk, cert pk ) as well as public keys pk GM and pk OA . Its output is a ciphertext Ψ ← ENC(pk GM , pk OA , pk, cert pk , w, L). On input of the same elements, the certificate cert pk , the ciphertext Ψ and the random coins coins Ψ that were used to produce Ψ , the non-interactive algorithm P generates a proof π Ψ that there exists a certified receiver whose public key was registered in database and who is able to decrypt Ψ and obtain a witness w such that (x, w) ∈ R. The verification algorithm V takes as input Ψ , pk GM , pk OA , π Ψ and the description of R and outputs 0 or 1. Given Ψ , L and the receiver's private key sk, the output of DEC is either a witness w such that (x, w) ∈ R or a rejection symbol ⊥. Finally, OPEN takes as input a ciphertext/label pair (Ψ, L) and the OA's secret key sk OA and returns a receiver's public key pk.

The model of [START_REF] Kiayias | Group encryption[END_REF] considers four properties termed correctness, message se-curity, anonymity and soundness. In the security definitions, stateful oracles capture the adversary's interaction with the system. In the soundness game, the KTY model requires that pk belongs to the language of valid public keys. Here, we are implicitly assuming that the space of valid public keys is dense (all matrices are valid keys, as is the case in our scheme).

In the upcoming definitions, we sometimes use the notation output A |output B ← A(input A ), B(input B ) (common-input) to denote the execution of a protocol between A and B obtaining their own outputs from their respective inputs.

Correctness. The correctness property requires that the following experiment returns 1 with overwhelming probability.

Experiment Expt correctness (λ) param ← SETUP init (1 λ ); (pk R , sk R ) ← G r (λ); (x, w) ← sample R (pk R , sk R ); (pk GM , sk GM ) ← SETUP GM (param); (pk OA , sk OA ) ← SETUP OA (param); pk, sk, cert pk |pk, cert pk ← J user , J GM (sk GM ) (pk GM ); Ψ ← ENC(pk GM , pk OA , pk, cert pk , w, L); π Ψ ← P(pk GM , pk OA , pk, cert, w, L, Ψ, coins Ψ ); If (w = DEC(sk, Ψ, L)) ∨ (pk = OPEN(sk OA , Ψ, L)) ∨(V(Ψ, L, π Ψ , pk GM , pk OA ) = 0) then return 0 else return 1;
Message Secrecy. The message secrecy property is defined by an experiment where the adversary has access to oracles that may be stateful (and maintain a state across queries) or stateless:

-DEC(sk): is a stateless oracle for the user decryption function DEC. When this oracle is restricted not to decrypt a ciphertext-label pair (Ψ, L), we denote it by DEC ¬ Ψ,L . -CH b ror (λ, pk, w, L): is a real-or-random challenge oracle which is only called once. It returns (Ψ, coins Ψ ) such that Ψ ← ENC(pk GM , pk OA , pk, cert pk , w, L) if b = 1 whereas, if b = 0, Ψ ← ENC(pk GM , pk OA , pk, cert pk , w , L) encrypts a random plaintext of length O(λ) uniformly sampled in the plaintext space. In both cases, coins Ψ denote the random coins used to generate Ψ . -PROVE b P,P (pk GM , pk OA , pk, cert pk , pk R , x, w, Ψ, L, coins Ψ ): is a stateful oracle that can be invoked a polynomial number times. If b = 1, it replies by running the real prover P on the inputs to create an actual proof π Ψ . If b = 0, the oracle runs a simulator P that uses the same inputs as P except witness w, coins Ψ and generates a simulated proof.

These oracles are used in an experiment where the adversary controls the GM, the OA and all members except the honest receiver. The adversary A embodies the dishonest GM that certifies the honest receiver in an execution of JOIN. It is granted access to an oracle DEC which decrypts on behalf of that receiver. In the challenge phase, it transmits a state information aux to itself and invokes the challenge oracle for a label and a pair (x, w) ∈ R of its choice. After the challenge phase, it can also query the PROVE oracle many times and finally attempts to guess the challenger's bit b.

As pointed out in [START_REF] Kiayias | Group encryption[END_REF][START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF], designing an efficient simulator P (for executing PROVE b P,P (.) when b = 0) is part of the security proof.

Definition 4. A GE scheme satisfies message security if, for any PPT adversary A, the experiment below returns 1 with probability at most 1/2 + negl(λ).

Experiment Expt sec A (λ) param ← SETUP init (1 λ ); (aux, pk GM , pk OA ) ← A(param); pk, sk, cert pk |aux ← J user , A(aux) (pk GM ); (aux, x, w, L, pk R ) ← A DEC(sk,.) (aux); If (x, w) ∈ R then return 0; b ← {0, 1}; (Ψ, coins Ψ ) ← CH b ror (λ, pk, w, L); b ← A PROVE b P,P (pk GM ,pk OA ,pk,cert pk ,pk R ,x,w,Ψ,L,coins Ψ ),DEC ¬ Ψ,L (sk,.) (aux, Ψ ); If b = b then return 1 else return 0;
Anonymity. In the experiment modeling the anonymity property, the adversary controls the entire system except the opening authority and two well-behaved users. The challenger thus introduces two honest users' public keys pk 0 , pk 1 in database and thus obtains certificate for both pk 0 , pk 1 from the adversariallycontrolled GM. For a pair (x, w) ∈ R of its choice, the adversary obtains an encryption of w under pk b for some b ∈ {0, 1} chosen by the challenger. The adversary is provided with decryption oracles w.r.t. both keys pk 0 , pk 1 . In addition, it has the following oracles at disposal:

-CH b anon (pk GM , pk OA , pk 0 , pk 1 , w, L): is a challenge oracle that is only queried once by the adversary. It returns a pair (Ψ, coins Ψ ) consisting of a ciphertext Ψ ← ENC(pk GM , pk OA , pk b , cert pk b , w, L) and the coin tosses coins Ψ that were used to generate Ψ .

-USER(pk GM ): is a stateful oracle that obtains certificates from the adversary by simulating two executions of J user to introduce two honest users in the group. It uses a string keys where the outputs (pk 0 , sk 0 , cert pk 0 ), (pk 1 , sk 1 , cert pk 1 ) of honest users are written as long as the adversariallysupplied certificates {cert pk d } 1 d=0 are valid w.r.t. pk GM (i.e., invalid certificates are ignored by the oracle and no entry is introduced in keys for them).

-OPEN(sk OA , .): is a stateless oracle that simulates the opening algorithm and, on input of a GE ciphertext, returns the receiver's public key.

The reason why the USER oracle is needed is that both honest users' public keys pk 0 , pk 1 must have been properly certified by the adversarially-controlled GM before the challenge phase because the adversary subsequently obtains proofs generated using (pk b , cert pk b ). Definition 5. A GE scheme satisfies anonymity if, for any PPT adversary A, the experiment below returns 1 with a probability not exceeding 1/2 + negl(λ).

Experiment Expt anon

A (λ) param ← SETUP init (1 λ ); (pk OA , sk OA ) ← SETUP OA (param);
(aux, pk GM ) ← A(param, pk OA ); aux ← A USER(pk GM ),OPEN(sk OA ,.) (aux); If keys = (pk 0 , sk 0 , cert pk 0 , pk 1 , sk 1 , cert pk 1 )(aux) then return 0; (aux, x, w, L, pk R ) ← A OPEN(sk OA ,.),DEC(sk0,.),DEC(sk1,.) (aux);

If (x, w) ∈ R then return 0; b ← {0, 1}; (Ψ, coins Ψ ) ← CH b anon (pk GM , pk OA , pk 0 , pk 1 , w, L); b ← A P(pk GM ,pk OA ,pk b ,cert pk b ,x,w,Ψ,L,coins Ψ , OPEN ¬ Ψ,L (sk OA ,.),DEC ¬ Ψ,L (sk0,.),DEC ¬ Ψ,L (sk1,.)) (aux, Ψ ); If b = b then return 1 else return 0;
Soundness. Here, the adversary creates the group of receivers by interacting with the honest GM. Its goal is to produce a ciphertext Ψ and a convincing proof that Ψ is valid w.r.t. a relation R of its choice but either: (1) The opening of Ψ reveals a receiver's public key pk that does not belong to any group member;

(2) The output pk of OPEN is not a valid public key (i.e., pk ∈ PK, where PK is the language of valid public keys); (3) The ciphertext C is not in the space C x,L,pk R ,pk GM ,pk OA ,pk of valid ciphertexts. This notion is formalized by a game where the adversary is given access to a user registration oracle REG(sk GM , .) that simulates J GM . This oracle maintains a list database where registered public keys and their certificates are stored. Definition 6. A GE scheme is sound if, for any PPT adversary A, the experiment below returns 1 with negligible probability.

Experiment Expt soundness A (λ) param ← SETUP init (1 λ ); (pk OA , sk OA ) ← SETUP OA (param); (pk GM , sk GM ) ← SETUP GM (param); (pk R , x, Ψ, π Ψ , L, aux) ← A REG(sk GM ,.) (param, pk GM , pk OA , sk OA ); If V(Ψ, L, π Ψ , pk GM , pk OA ) = 0 return 0; pk ← OPEN(sk OA , Ψ, L); If (pk ∈ database) ∨ (pk ∈ PK) ∨ (Ψ ∈ C x,L,pk R ,pk GM ,pk OA ,pk )
then return 1 else return 0;

The model of Kiayias et al. [START_REF] Kiayias | Group encryption[END_REF] requires that pk belongs to the language of valid public keys, so that the adversary is considered to defeat the soundness property when (Ψ, L) opens to a key outside the language (i.e., pk ∈ PK). In our scheme, we will assume that the space of valid public keys is dense in that all matrices of a given dimension are valid public keys, which have an underlying private key. We nevertheless use the same definition as [START_REF] Kiayias | Group encryption[END_REF] in order to emphasize that we are not relaxing the model in any way.

Warm-up: Decompositions, Extensions, Permutations

This section introduces the notations and techniques that will be used throughout the paper. Part of the covered material appeared (in slightly different forms) in recent works [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Ezerman | A provably secure group signature scheme from code-based assumptions[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] on Stern-like protocols [START_REF] Stern | A new paradigm for public key identification[END_REF]. The techniques that will be employed for handling quadratic relations (double-bit extension ext(•, •), expansion expand ⊗ (•, •) of matrix-vector product and the associated permuting mechanisms) are novel contributions of this paper.

Decompositions

For any B ∈ Z + , define the number δ B := log 2 B + 1 = log 2 (B + 1) and the sequence B 1 , . . . , B δ B , where

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

δ B j=1 B j = B and any integer v ∈ [0, B] can be decom- posed into a binary vector idec B (v) = (v (1) , . . . , v (δ B ) ) ∈ {0, 1} δ B such that δ B j=1 B j • v (j) = v.
We describe this decomposition procedure in a deterministic manner:

1. v := v 2. For j = 1 to δ B do: (i) If v ≥ B j then v (j) := 1, else v (j) := 0; (ii) v := v -B j • v (j) . 3. Output idec B (v) = (v (1) , . . . , v (δ B ) ) .
Next, for any positive integers m, B, we define the decomposition matrix:

H m,B :=      B 1 . . . B δ B B 1 . . . B δ B . . . B 1 . . . B δ B      ∈ Z m×mδ B , (1)
and the following injective functions:

(i) vdec m,B : [0, B] m → {0, 1} mδ B that maps vector v = (v 1 , . . . , v m ) to vector idec B (v 1 ) . . . idec B (v m ) . Note that H m,B • vdec m,B (v) = v. (ii) vdec m,B : [-B, B] m → {-1, 0, 1} mδ B that maps vector w = (w 1 , . . . , w m ) to vector σ(w 1 ) • idec B (w 1 ) . . . σ(w m ) • idec B (w m )
, where for each

i = 1, . . . , m: σ(w i ) = 0 if w i = 0; σ(w i ) = -1 if w i < 0; σ(w i ) = 1 if w i > 0. Note that H m,B • vdec m,B (w) = w.
We also define the following matrix decomposition procedure. For positive integers n, m, q, define the injective function mdec n,m,q : Z m×n q → {0, 1} mnδq-1 that maps matrix

X = [x 1 | . . . |x n ] ∈ Z m×n q , where x 1 , . . . , x n ∈ Z m q , to vector mdec n,m,q (X) = vdec m,q-1 (x 1 ) . . . vdec m,q-1 (x n ) = (x 1,1 , . . . , x 1,mk , x 2,1 , . . . , x 2,mk , . . . , x n,1 , x n,mk ) ∈ {0, 1} nmδq-1 ,
where, for each (i, j) ∈ [n] × [mδ q-1 ], x i,j ∈ {0, 1} denotes the j-th bit of the decomposition of the i-th column of X.

Looking ahead, when proving knowledge of witnesses (X, s) ∈ Z m×n q × Z n q satisfying b = X • s + e mod q, we will have to consider terms of the form x i,j • s i,t , where s = (s 1 , . . . , s n ) ∈ Z n q and (s i,1 , . . . , s i,δq-1 ) = idec q-1 (s i ) for each i ∈ [n].

Extensions and Permutations

We now introduce the extensions and permutations which will be essential for proving quadratic relations.

-For each c ∈ {0, 1}, denote by c the bit 1 -c ∈ {0, 1}.

-For c 1 , c 2 ∈ {0, 1}, define the vector

ext(c 1 , c 2 ) = (c 1 • c 2 , c 1 • c 2 , c 1 • c 2 , c 1 • c 2 ) ∈ {0, 1} 4 . -For b 1 , b 2 ∈ {0, 1}, define the permutation T b1,b2 that transforms vector v = (v 0,0 , v 0,1 , v 1,0 , v 1,1 ) ∈ Z 4 q to vector (v b1,b2 , v b1,b2 , v b1,b2 , v b1,b2
) . Note that, for all c 1 , c 2 , b 1 , b 2 ∈ {0, 1}, we have the following:

z = ext(c 1 , c 2 ) ⇐⇒ T b1,b2 (z) = ext(c 1 ⊕ b 1 , c 2 ⊕ b 2 ), (2)
where ⊕ denotes the bit-wise addition modulo 2. Now, for positive integers n, m, k, and for vectors That is, expand ⊗ (x, s 0 ) is obtained by applying ext to all pairs of the form (x i,j , s i,t ) for (i, j, t)

x = (x 1,1 , . . . , x 1,mk , x 2,1 , . . . , x 2,mk , . . . , x n,1 , x n,mk ) ∈ {0, 1} nmk and s 0 = (s 1,1 , . . . , s 1,k , s 2,1 , . . . , s 2,k , . . . , s n,1 , . . . , s n,k ) ∈ {0, 1} nk , we define the vector expand ⊗ (x, s 0 ) ∈ {0, 1} 4nmk 2 as expand ⊗ (x, s 0 ) = ext (x 1,1 , s 1,1 ) ext (x 1,1 , s 1,2 ) . . . ext (x 1,1 , s 1,k ) ext (x 1,2 , s 1,1 ) ext (x 1,2 , s 1,2 ) . . . ext (x 1,2 , s 1,k ) . . . ext (x 1,mk , s 1,1 ) ext (x 1,mk , s 1,2 ) . . . ext (x 1,mk , s 1,k ) ext (x
∈ [n] × [mk] × [k]. Now, for b = (b 1,1 , . . . , b 1,mk , b 2,1 , . . . , b 2,mk , . . . , b n,1 , b n,mk ) ∈ {0, 1} nmk and d = (d 1,1 , . . . , d 1,k , d 2,1 , . . . , d 2,k , . . . , d n,1 , . . . , d n,k ) ∈ {0, 1} nk , we define the permutation P b,d that transforms vector v = (v 1,1,1 . . . v 1,1,k ) (v 1,2,1 . . . v 1,2,k ) . . . (v 1,mk,1 . . . v 1,mk,k ) (v 2,1,1 . . . v 2,1,k ) (v 2,2,1 . . . v 2,2,k ) . . . (v 2,mk,1 . . . v 2,mk,k ) (v n,1,1 . . . v n,1,k ) (v n,2,1 . . . v n,2,k ) . . . (v n,mk,1 . . . v n,mk,k ) ∈ Z 4nmk 2 ,
consisting of nmk 2 blocks of length 4, to the vector P b,d (v) of the form

(w 1,1,1 . . . w 1,1,k ) (w 1,2,1 . . . w 1,2,k ) . . . (w 1,mk,1 . . . w 1,mk,k ) (w 2,1,1 . . . w 2,1,k ) (w 2,2,1 . . . w 2,2,k ) . . . (w 2,mk,1 . . . w 2,mk,k ) (w n,1,1 . . . w n,1,k ) (w n,2,1 . . . w n,2,k ) . . . (w n,mk,1 . . . w n,mk,k ) ,
where for each (i, j, t)

∈ [n] × [mk] × [k]: w i,j,t = T bi,j ,di,t (v i,j,t ).
Observe that, for all b ∈ {0, 1} nmk , d ∈ {0, 1} nk , we have:

z = expand ⊗ (x, s 0 ) ⇐⇒ P b,d (z) = expand ⊗ (x ⊕ b, s 0 ⊕ d). (3)
Next, we recall the notations, extensions and permutations used in previous Stern-like protocols [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Ezerman | A provably secure group signature scheme from code-based assumptions[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] for proving linear relations.

For any positive integer t, denote by S t the symmetric group of all permutations of t elements, by B 2t the set of all vectors in {0, 1} 2t having Hamming weight t, and by B 3t the set of all vectors in {-1, 0, 1} 3t having exactly t coordinates equal to j, for each j ∈ {-1, 0, 1}. Note that for any φ ∈ S 2t and ψ ∈ S 3t , we have the following equivalences:

x ∈ B 2t ⇐⇒ φ(x) ∈ B 2t and y ∈ B 3t ⇐⇒ ψ(y) ∈ B 3t . (4)
The following extending procedures are defined for any positive integers t.

-ExtendTwo t : {0, 1} t → B 2t . On input vector x with Hamming weight w, it outputs x = (x 1 t-w 0 w ) . -ExtendThree t : {-1, 0, 1} t → B 3t . On input vector y containing n j coordinates equal to j for j ∈ {-1, 0, 1}, output y = (y 1 t-n1 0 t-n0 (-1) t-n-1 ).

We also use the following encodings and permutations to achieve fine-grained control over coordinates of binary witness-vectors.

-For any positive integer t, define the function encode t that encodes vector x = (x 1 , . . . , x t ) ∈ {0, 1} t to vector encode t (x) = (x 1 , x 1 , . . . , xt , x t ) ∈ {0, 1} 2t . -For any positive integer t and any vector c = (c 1 , . . . , c t ) ∈ {0, 1} t , define the permutation

F (t) c that transforms vector v = (v (0) 1 , v (1)
1 , . . . , v

(0) t , v (1)
t ) ∈ Z 2t into vector F (t) c (v) = (v (c1) 1 , v (c1) 1 , . . . , v (ct) t , v (ct) t ) .
Note that the following equivalence holds for all t, c:

y = encode t (x) ⇐⇒ F (t) c (y) = encode t (x ⊕ c). (5)
To close this warm-up section, we remark that the equivalences observed in (3), ( 4) and (5) will play crucial roles in our zero-knowledge layer.

Proving the LWE Relation With Hidden Matrices

Let n, m, q, β be positive integers where β q, and let k = δ q-1 = log 2 q . We identify Z q as the set {0, 1, . . . , q -1}. We consider a zero-knowledge argument system allowing prover P to convince verifier V on input b ∈ Z m q that P knows secret matrix X ∈ Z m×n q , and vectors

s ∈ Z n q , e ∈ [-β, β] m such that: b = X • s + e mod q. (6)
Moreover, the argument system should be readily extended to proving that X and s satisfy additional conditions, such as:

-The bits representing X are certified by an authority, and the prover also knows that secret signature-certificate. -The (secret) hash of X is correctly encrypted to a given ciphertext.

-The LWE secret s is involved in other linear equations.

Let q 1 , . . . , q k ∈ Z q be the sequence of integers obtained by decomposing q -1 using the technique recalled in Section 3.1, and define the row vector g = (q 1 , . . . , q k ). Let

X = [x 1 | . . . |x n ] ∈ Z m×n q and s = (s 1 , . . . , s n ) . For each index i ∈ [n], let us consider vdec m,q-1 (x i ) = (x i,1 , . . . , x i,mk ) ∈ {0, 1} mk . Let vdec n,q-1 (s) = (s 1,1 , . . . , s 1,k , s 2,1 , . . . , s 2,k , . . . , s n,1 , . . . s n,k ) ∈ {0, 1} nk and ob- serve that s i = g • idec q-1 (s i ) = g • (s i,1 , . . . , s i,k ) for each i ∈ [n].
We have:

X • s = n i=1 x i • s i = n i=1 H m,q-1 • vdec m,q-1 (x i ) • s i = H m,q-1 • n i=1 (x i,1 • s i , . . . , x i,mk • s i ) mod q.
Observe that, for each i ∈ [n] and each j ∈ [mk], we have

x i,j • s i = x i,j • g • (s i,1 , . . . , s i,k ) = (q 1 , . . . , q k ) • (x i,j • s i,1 , . . . , x i,j • s i,k ) .
We now extend vector (q 1 , q 2 , . . . , q k ) to g = (0, 0, 0, q 1 , 0, 0, 0, q 2 , . . . , 0, 0, 0, q k ) ∈ Z 4k q . For all (i, j) ∈ [n] × [mk], we have:

x i,j • s i = g • (ext (x i,j , s i,1 ) . . . ext (x i,j , s i,k )) .
Let us define the matrices

Q 0 := I mk ⊗ g =      g g . . . g      ∈ Z mk×4mk 2 q , (7)
and

Q = [ n times Q 0 | . . . |Q 0 ] ∈ Z mk×4nmk 2 q
. For each i ∈ [n], define

y i = ( ext (x i,1 , s i,1 ) . . . ext (x i,1 , s i,k )) ext (x i,2 , s i,1 . . . ext (x i,2 , s i,k ) . . . ext (x i,mk , s i,1 . . . ext (x i,mk , s i,k )) ∈ {0, 1} 4mk 2 .
Then, for all i ∈ [n], we have:

(x i,1 • s i , . . . , x i,mk • s i ) = Q 0 • y i . Now, we note that (y 1 . . . y n ) = expand ⊗ (mdec n,m,q (X), vdec n,q-1 (s)),
and

n i=1 (x i,1 • s i , . . . , x i,mk • s i ) = n i=1 Q 0 • y i = Q • expand ⊗ (mdec n,m,q (X), vdec n,q-1 (s)). ( 8
)
Letting

Q = H m,q-1 • Q ∈ Z m×4nmk 2 q
and left-multiplying ( 8) by H m,q-1 , we obtain the equation:

X • s = Q • expand ⊗ mdec n,m,q (X), vdec n,q-1 (s) mod q.
This means that the task of proving knowledge of (X, s, e) ∈ Z m×n q

× Z n q × [-β, β] m such that b = X • s + e mod q boils down to proving knowledge of z ∈ {0, 1} 4nmk 2 , x ∈ {0, 1} nmk , s 0 ∈ {0, 1} nk and a short e ∈ Z m such that b = Q • z + I m • e mod q and z = expand ⊗ (x, s 0 ).
As the knowledge of small-norm e can easily be proved with Stern-like protocol (e.g., [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF]), the challenging part is to prove in ZK the constraint of z = expand ⊗ (x, s 0 ). To this end, we will use the following permuting technique inspired by the equivalence of equation ( 3). We sample uniformly random d x ∈ {0, 1} nmk and d s ∈ {0, 1} nk , send x = x⊕d x and s = s 0 ⊕d s to the verifier, and let the latter check that P dx,ds (z) = expand ⊗ (x , s ). This will be sufficient to convince the verifier that the original vector z satisfies the required constraint. The crucial point is that no additional information about x and s 0 is leaked, since these binary vectors are perfectly hidden under the "one-time pad" d x and d s , respectively. In the framework of Stern's protocol, the idea of using "one-time-pad" permutations further allows us to prove that x and s 0 satisfy additional conditions, i.e., they appear in other equations. This is done by first setting up an equivalence similar to (3) in the places where these objects appear, and then, using the same "one-time pad" for each of them in all appearances. We will explain in detail how this technique can be realized in the next subsection.

The Main Zero-Knowledge Argument System

The zero-knowledge argument of knowledge used in our group encryption scheme (Section 5) will involve a system of 10 modular equations:

           v 1 = M 1,1 • w 1 + M 1,2 • w 2 + . . . + M 1,15 • w 15 mod q, v 2 = M 2,1 • w 1 + M 2,2 • w 2 + . . . + M 2,
where {M i,j } (i,j)∈ [START_REF] Benhamouda | Efficient zeroknowledge proofs for commitments from learning with errors over rings[END_REF]× [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF] , {v i } i∈ [START_REF] Benhamouda | Efficient zeroknowledge proofs for commitments from learning with errors over rings[END_REF] are public matrices and vectors (which are possibly zero). Our goal is to prove knowledge of vectors w 1 , . . . , w 15 , such that (9) holds, and that these vectors have the following constraints.

1. w 1 ∈ {0, 1} n mk , w 2 ∈ {0, 1} nk and w 3 = expand ⊗ (w 1 , w 2 ) ∈ {0, 1} 4n mk 2 .

(Note that these vectors are obtained via the techniques of Section 4.1.) 2. w 4 , w 5 , w 6 , w 7 are {0, 1} vectors. 3. Vectors w 8 , . . . , w 14 have bounded infinity norms. 4. Vector w 15 has the form

d 1 d 2 τ [1] • d 2 . . . τ [ ] • d 2 , for some vectors d 1 , d 2 ∈ [-β, β] m and τ = (τ [1], . . . , τ [ ]) ∈ {0, 1} .
Towards achieving the goal, we employ a 4-step strategy.

1. The first step transforms all the secret vectors with infinity norm larger than 1 into vectors with infinity norm 1. This is done with the decomposition technique of Section 3.1. 2. The norm-1 vectors is then encoded or extended into vectors whose constraints are invariant under random permutations. This is done with the techniques described at the end of Section 3.2. The public matrices {M i,j } i,j are transformed accordingly to preserve the equations. 3. The third step unifies all the equations into one of the form M•x = v mod q, where x is a concatenation of the newly obtained witness-vectors. 4. In the final step, we run a Stern-like protocol to prove the unified equation M • x = v mod q, where a composed permutation is employed to prove the constraints of vector x.

Our strategy subsumes the central ideas underlying recent works on Sternlike protocols [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] for lattice-based relations: preprocessing secret witnessvectors to make them provable-in-zero-knowledge with random permutations, unifying them into just one vector for the sake of convenience, and then running Stern's protocol in a classical manner.

The first step is applicable to vectors w 8 , . . . , w 14 and w 15 . Suppose that w i has dimension m i and infinity norm bound β i , for i ∈ [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]. Then we compute vector w i = vdec mi,βi (w i ) ∈ {-1, 0, 1} miδ β i . Note that H mi,βi • w i = w i . To decompose w 15 , we compute d j = vdec m,β (d j ) ∈ {-1, 0, 1} mδ β , for j = 1, 2. The second step performs the following encodings and extensions.

-Encode w 1 and w 2 : Let w 1 = encode n mk (w 1 ) and w 2 = encode nk (w 2 ).

Note that to prove knowledge of w 1 and w 2 , we will employ the "one-time pad" permuting technique implied by ( 5). The same one-time pads are used to prove that w 3 = expand ⊗ (w 1 , w 2 ), as discussed in Section 4.1. -Extend vectors w 4 , . . . , w 7 , w 8 , . . . , w 14 and d 1 , d 2 , τ .

For i ∈ [START_REF] Ajtai | Generating hard instances of the short basis problem[END_REF][START_REF] Bellare | Key-privacy in public-key encryption[END_REF], suppose that the binary vector w i has dimension m i . Then we extend it to w i = ExtendTwo mi (w i ) ∈ B 2mi . For i ∈ [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF], we extend w i to w i = ExtendThree miδ β i (w i ) ∈ B 3miδ β i . It follows from (4) that, the knowledge of vectors {w i } 14 i=4 can be proved in zero-knowledge using random permutations.

Meanwhile, we need a more sophisticated treatment for the components of vector w 15 . For j = 1, 2, we let d j = ExtendThree mδ β (d j ) ∈ B 3mδ β . We also extend

τ to τ = ExtendTwo (τ ) = (τ [1], . . . , τ [ ], τ [ + 1], . . . , τ [2 ]) ∈ B 2 .
Then we form the vector:

w 15 = (d 1 ) (d 2 ) τ [1](d 2 ) . . . τ [ ](d 2 ) . . . τ [2 ](d 2 )
.

Next, we define CorMix as the set of all vectors in {-1, 0, 1} (2 +2)3mδ β , that have the form

z 1 z 2 ρ[1]z 2 . . . ρ[2 ]z 2 for some z 1 , z 2 ∈ B 3mδ β and ρ ∈ B 2 .
Clearly, w 15 ∈ CorMix. Furthermore, as shown in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF], this set is closed under a special composition of 3 permutations φ 1 ∈ S 3mδ β , φ 2 ∈ S 3mδ β , φ 3 ∈ S 2 , which we denote by T φ1,φ2,φ3 . That is, we have the equivalence:

w 15 ∈ CorMix ⇐⇒ T φ1,φ2,φ3 (w 15 ) ∈ CorMix. (10)
-As we have changed the dimensions of the witness-vectors, we also have to transform the public matrices {M i,j } i,j accordingly to preserve the equations. In short, this can be done through right-multiplying by the decomposition matrices (if needed), and then inserting zero-columns at suitable positions. We denote the transformed public matrices by {M i,j } i,j .

At the end of the second step, we are presented with the following system of equations, which is equivalent to [START_REF] Benhamouda | Better zero-knowledge proofs for lattice encryption and their application to group signatures[END_REF]. (11)

           v 1 = M 1,1 • w 1 + M 1,2 • w 2 + . . . + M 1,15 • w 15 mod q, v 2 = M 2,1 • w 1 + M 2,2 • w 2 + . . . + M 2,
The third step involves only basic linear algebra. Let

M =       M 1,1 M 1,2 . . . M 1,15 M 2,
      ; x =       w 1 w 2 . . . w 15       ; v =       v 1 v 2 . . . v 10       , then we obtain the unified equation M • x = v mod q.
Given the above preparations, we now comes to the final step where we formally present our protocol. Let D be the dimension of vector x. Denote by VALID the set of all vectors in {-1, 0, 1} D , that have the form z = (z 1 . . . z 15 ) , where:

1. z 1 = encode n mk (y 1 ), z 2 = encode nk (y 2 ) and z 3 = expand ⊗ (y 1 , y 2 ), for some y 1 ∈ {0, 1} n mk and y 2 ∈ {0, 1} nk . 2. For i ∈ [START_REF] Ajtai | Generating hard instances of the short basis problem[END_REF][START_REF] Bellare | Key-privacy in public-key encryption[END_REF], vector z i ∈ B 2mi . For i ∈ [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF], vector z i ∈ B 3miδ β i .

Vector z 15 ∈ CorMix.

It can be seen that our vector x is an element of this tailored set VALID. By construction, the task of proving knowledge of vectors w 1 , . . . , w 15 that have the required constraints, and that satisfy system (9) has boiled down to proving the possession of vector x ∈ VALID such that M • x = v mod q. We will fulfill this task with a Stern-like zero-knowledge protocol, in which we hide x from the verifier's view by a random permutation and a random masking vector.

Let us determine the type of permutations to be applied for x. Let

S = {0, 1} n mk × {0, 1} nk × S 2m4 × . . . × S 2m7 × S 3m8δ β 8 × . . . . . . × S 3m14δ β 14 × (S 3mδ β ) 2 × S 2 .
We associate each element π = (b 1 , b 2 , φ 4 , . . . , φ 14 , φ 1 15 , φ 2 15 , φ 3 15 ) ∈ S with the permutation Γ π that transforms vector z = (z 1 . . . z 15 ) ∈ Z D , where the length of block z i equals to that of w i for all i ∈ [15], into vector

Γ π (z) = F (n mk) b1 (z 1 ) F (nk) b2 (z 2 ) P b1,b2 (z 3 ) φ 4 (z 4 ) . . . . . . φ 14 (z 14 ) T φ 1 15 ,φ 2 15 ,φ 3
15 (z 15 ) . It is implied by the equivalences given in (3), ( 5), ( 4) and ( 10) that the following holds for all π ∈ S:

x ∈ VALID ⇐⇒ Γ π (x) ∈ VALID.
Additionally, if x ∈ VALID and π is uniformly random in S, then Γ π (x) is uniformly random in VALID. In the framework of Stern's protocol, these facts allow us to prove in zero-knowledge the knowledge of x ∈ VALID.

Furthermore, proving that equation M • x = v mod q holds can be done by sampling a uniformly random masking vector r x ∈ Z D q , and demonstrating to the verifier that M

• (x + r x ) -v = M • r x mod q.
The interaction between prover P and verifier V is described in Figure 1. Prior to the interaction, both parties obtain matrix M and vector v from the public input, while P construct witness-vector x from his secret input, as described above. The protocol employs the statistically hiding and computationally binding string commitment scheme COM from [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF].

The properties of the given protocol are summarized in Theorem 1. The proof of the theorem employs standard simulation and extraction techniques for Stern-like protocols [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF], and is deferred to Appendix B.

Theorem 1. The protocol in Figure 1 is a statistical ZKAoK with perfect completeness, soundness error 2/3, and communication cost O(D log q). Namely:

-There exists a polynomial-time simulator that, on input (M, v), outputs an accepted transcript which is statistically close to that produced by the real prover.

1. Commitment: Prover samples rx ← U (Z D q ), π ← U (S) and randomness ρ1, ρ2, ρ3 for COM. Then he sends CMT = C1, C2, C3 to the verifier, where C1 = COM(π, M • rx; ρ1), C2 = COM(Γπ(rx); ρ2), C3 = COM(Γπ(x + rx); ρ3).

Challenge:

The verifier sends a challenge Ch ← U ({1, 2, 3}) to the prover. 3. Response: Depending on Ch, the prover sends RSP computed as follows:

-Ch = 1: Let tx = Γπ(x), tr = Γπ(rx), and RSP = (tx, tr, ρ2, ρ3).

-Ch = 2: Let π2 = π, y2 = x + rx, and RSP = (π2, y2, ρ1, ρ3).

-Ch = 3: Let π3 = π, y3 = r, and RSP = (π3, y3, ρ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 • y2 -v; ρ1), C3 = COM(Γπ 2 (y2); ρ3). -Ch = 3: Check that C1 = COM(π3, M • y3; ρ1), C2 = COM(Γπ 3 (y3); ρ2).
In each case, the verifier outputs 1 if and only if all the conditions hold. -There exists a polynomial-time 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 = v mod q.

Note that, given vector x outputted by the extractor, one can efficiently compute 15 vectors satisfying the conditions described at the beginning of this subsection, simply by "backtracking" the transformations conducted by our first 3 steps. In the group encryption scheme presented next, the constructed ZKAoK will be invoked by algorithm P, V , while its simulator and extractor will come in handy in the proofs of Theorems 2, 3, and 4.

Our Lattice-Based Group Encryption Scheme

To build a GE scheme using our zero-knowledge argument system, we need to choose a specific key-private CCA2-secure encryption scheme. The first idea is to use the CCA2-secure public-key cryptosystem which is implied by the Agrawal-Boneh-Boyen identity-based encryption (IBE) scheme [1] (which is recalled in Appendix A.2) via the Canetti-Halevi-Katz (CHK) transformation [START_REF] Canetti | Chosen-ciphertext security from identitybased encryption[END_REF]. The ABB scheme is a natural choice since it has pseudo-random ciphertexts (which implies the key-privacy [START_REF] Bellare | Key-privacy in public-key encryption[END_REF] when the CHK paradigm is applied) and provides one of the most efficient CCA2 cryptosystem based on the hardness of LWE in the standard model. One difficulty is that the Kiayias-Tsiounis-Yung model [START_REF] Kiayias | Group encryption[END_REF] requires that certified public keys be valid public keys (i.e., which have a matching secret key). When new group members join the system and request a certificate for their public key B U ∈ Z n× m q , a direct use of the ABB/CHK technique would incur of proof of existence of a GPV trapdoor [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] corresponding to B U (i.e., a small-norm matrix T B U ∈ Z m× m s.t. B•T B U = 0 n mod q). While the techniques of Peikert and Vaikuntanathan [START_REF] Peikert | Non-interactive statistical zero-knowledge proofs for lattice problems[END_REF] would provide a solution to this problem (as they allow proving that T B U ∈ Z m× m has full-rank), we found it simpler to rely on the trapdoor mechanism of Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF].

If we assume public parameters containing a random matrix Ā ∈ Z n×m q , each user's public key can consist of a matrix

B U = Ā•T U ∈ Z n× m q
, where T U ∈ Z m× m is a small-norm matrix whose calms are sampled from a discrete Gaussian distribution. Note that, if Ā ∈ Z n×m q is uniformly distributed, then [24, Lemma 5.1] ensures that, with overwhelming probability, any matrix B U ∈ Z n× m q has an underlying small-norm matrix satisfying B U = Ā • T U mod q. This simplifies the joining procedure by eliminating the need for proofs of public key validity.

In the encryption algorithm, the sender computes a dual Regev encryption [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] of the witness w ∈ {0, 1} m using a matrix

[ Ā | B U + FRD(VK) • G] ∈ Z n×(m+ m) q such that: (i) VK ∈ Z n
q is the verification key of a one-time signature; (ii) FRD : Z n q → Z n×n q is the full-rank difference3 function of [1]; (iii)

G = I n ⊗ [1|2| . . . |2 k-1 ] ∈ Z n× m q
is the gadget matrix of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. Given that G has a publicly known trapdoor allowing to sample short vectors in Λ ⊥ q (G), the user can use his private key T U ∈ Z m× m to decrypt by running the SampleRight algorithm of Lemma 5.

Having encrypted the witness w ∈ {0, 1} m by running the ABB encryption algorithm, the sender proceeds by encrypting a hash value of B U ∈ Z n× m q under the public key B OA = Ā•T OA ∈ Z n× m q of the opening authority. The latter hash value is obtained as a bit-wise decomposition of F • mdec n,m,q (B U ) ∈ Z 2n q , where F ∈ Z 2n×n m log q q is a random public matrix and mdec n,m,q (B U ) ∈ {0, 1} n m log q denotes an entry-wise binary decomposition of the matrix B U ∈ Z n× m q . By combining our new argument for quadratic relations and the extensions of Stern's protocol suggested in [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF], we are able to prove that some component of the ciphertext is of the form c = B U • s + e ∈ Z m q , for some s ∈ Z n q and a small-norm e ∈ Z m while also arguing possession of a signature on the binary decomposition mdec n,m,q (B U ) ∈ {0, 1} n m log q of B U . For this purpose, we use a variant of a signature scheme due to Böhl et al.'s signature [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] which was recently proposed by Libert, Ling, Mouhartem, Nguyen and Wang [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] (and of which a description is given in Appendix A.1). At the same time, the prover P can also argue that a hash value of mdec n,m,q (B U ) is properly encrypted under the OA's public key using the ABB encryption scheme.

Description of the Scheme

Our GE scheme allows encrypting witnesses for the Inhomogeneous SIS relation R ISIS (n, m, q, 1), which consists of pairs

((A R , u R ), w) ∈ (Z n×m q × Z n q ) × {0, 1} m satisfying u R = A R • w mod q.
This relation is in the same spirit as the one of Kiayias, Tsiounis and Yung [START_REF] Kiayias | Group encryption[END_REF], who consider the verifiable encryption of discrete logarithms. While the construction of [START_REF] Kiayias | Group encryption[END_REF] allow verifiably encrypting discrete-logarithm-type secret keys under the public key of some anonymous TTP, our construction makes it possible to encrypt GPV-type secret keys [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF].

SETUP init (1 λ ): This algorithm performs the following:

1. Choose integers n = O(λ), prime q = O(n 4 ), and let k = log 2 q , m = nk and m = 2 m = 2nk. Choose a B-bounded distribution χ over Z for some B = √ nω(log n). 2. Choose a Gaussian parameter σ = Ω( √ n log q log n). Let β = σω(log n) be the upper bound of samples from D Z,σ . 3. Select integers = (λ) which determines the maximum expected group size 2 , and κ = ω(log λ) (the number of protocol repetitions). 4. Select a strongly unforgeable one-time signature OT S = (Gen, Sig, Ver).

We assume that the verification keys live in Z n q . 5. Select public parameters COM par for a statistically-hiding commitment scheme like [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]. This commitment will serve as a building block for the zero-knowledge argument system used in P, V . 6. Let FRD : Z n q → Z n×n q be the full-rank difference mapping from [1]. 7. Pick a random matrix F ← Z 2n×n mk q , which will be used to hash users' public keys from

Z n× m q to Z n q . 8. Let G ∈ Z n× m q be the gadget matrix G = I n ⊗ 1 2 . . . 2 k-1 of [44]. Pick matrices Ā, U ← U (Z n×m q ) and V ← U (Z n×m q
). Looking ahead, U will be used to encrypt for the receiver while V will be used to encrypt the user's public key under the OA's public key. As for Ā, it will be used in two instances of the ABB encryption scheme [1].

Output param = λ, n, q, k, m, B, χ, σ, β, , κ, OT S, COM par , FRD, Ā, G, F, U, V .

G r , sample R : Algorithm G r (1 λ , 1 n , 1 m ) proceeds by sampling a random matrix A R ← U (Z n×m q
) and outputting (pk R , sk R ) = (A R , ε). On input of a public key pk R = A R ∈ Z n×m q for the relation R ISIS , algorithm sample R picks w ← U ({0, 1} m ) and outputs a pair ((A R , u R ), w), where u R = A R •w ∈ Z n q . SETUP GM (param): The GM generates (sk GM , pk GM ) ← Keygen( 1 λ ,q,n,m,,σ) as a key pair for the SIS-based signature scheme of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] (as recalled in Appendix A.1). This key pair consists of sk GM := T A and

pk GM := A, A 0 , . . . , A ∈ Z n×m q , D 0 , D 1 ∈ Z n×m q , D ∈ Z n× m q , u ∈ Z n q . ( 12
)
SETUP OA (param): The OA samples a small-norm matrix

T OA ← D m Z m ,σ in Z m× m to obtain a statistically uniform B OA = Ā • T OA ∈ Z n× m q
. The OA's key pair consists of (sk OA , pk OA ) = (T OA , B OA ).

JOIN:

The prospective user U and the GM interact in the following protocol.

a. Sample s oa ← U (Z n q ), R oa ← D m× m Z,σ , x oa ← χ m , y oa ← χ m . Set z oa = R oa • y oa ∈ Z m. b. Compute        c (1) oa = Ā • s oa + y oa mod q; c (2) oa = (B OA + H VK • G) • s oa + z oa mod q; c (3) oa = V • s oa + x oa + vdec n,q-1 (h U ) • q 2 , (16)
and let c oa = c

(1)

oa , c (2)
oa , c

∈ Z m q × Z m q × Z m q . 5. Compute a one-time signature Σ = Sig(SK, (c rec , c oa , L)).

Output the ciphertext

Ψ = (VK, c rec , c oa , Σ). (17)
and the state information coins Ψ = s rec , R rec , x rec , y rec , s oa , R oa , x oa , y oa .

DEC(sk U , Ψ, L) : The decryption algorithm proceeds as follows:

1. If Ver VK, Σ, (c rec , c oa , L) = 0, return ⊥. Otherwise, parse the secret key sk U as T U ∈ Z m× m and the ciphertext Ψ as in [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF]. Define the matrix

B VK = B U + FRD(VK) • G ∈ Z n× m q . 2. Decrypt c rec using a decryption key for the tag VK ∈ Z n . Namely, a. Define B U,VK = [ Ā|B VK ] = [ Ā| Ā • T U + FRD(VK) • G] ∈ Z n×(m+ m) q
. Using T U and the publicly known trapdoor T G of G, compute a small-norm matrix E VK ∈ Z (m+ m)×m such that B U,VK •E VK = U mod q by running the SampleRight algorithm of Lemma 5. b. Compute

w = c (3) rec -E VK • c (1) rec c (2) rec / q 2 ∈ Z m
and return the obtained w ∈ {0, 1} m .

OPEN(sk OA , Ψ, L) : The opening algorithm proceeds as follows:

1. If Ver VK, Σ, (c rec , c oa ), L = 0, then return ⊥. Otherwise, parse sk OA as T OA ∈ Z m× m and the ciphertext Ψ as in [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF]. 2. Decrypt c oa using a decryption key for the tag VK ∈ Z n q in the same way as in the decryption algorithm. That is, do the following: a. Define the matrix

B OA,VK = [ Ā|B OA + FRD(VK) • G] ∈ Z n×(m+ m) q . Use T OA to compute a small-norm E OA,VK ∈ Z (m+ m)×m satisfying B OA,VK • E OA,VK = V mod q. b. Compute h = c (3) oa -E OA,VK • c (1) oa c (2) oa / q 2 ∈ {0, 1} m and h U = H 2n,q-1 • h ∈ Z 2n q .
3. Look up database to find a public key pk U = B U ∈ Z n× m q that hashes to h U ∈ Z 2n q (i.e., such that h U = F • mdec n, m,q (B U )). If more than one such key exists, return ⊥. If only one key pk U = B U ∈ Z n× m q satisfies h U = F • mdec n, m,q (B U ), return that key pk U . In any other situation, return ⊥. P, V : The common input consists of param and pk GM as specified above, as well as

(A R , u R ) ∈ Z n×m q × Z n q , pk OA = B OA ∈ Z n× m q
, and a ciphertext Ψ as in [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF]. Both parties compute B OA,VK = [ Ā|B OA + FRD(VK) • G] as specified above. The prover's secret input consists of a witness w ∈ {0, 1} m ,

pk U = B U , cert U = (τ, d, r) ∈ {0, 1} × Z 2m × Z m ,
and the random coins coins Ψ = s rec , R rec , x rec , y rec , s oa , R oa , x oa , y oa used to generate Ψ. The prover's goal is to convince the verifier in zero-knowledge that his secret input satisfies the following:

1. A R • w = u R mod q. 2. h M = F • mdec n,m,q (M) mod q.
3. Conditions ( 13) and ( 14) hold. 4. Vectors x rec , y rec , x oa , y oa have infinity norms bounded by B, and vectors z rec , z oa have infinity norms bounded by βmB. 5. Equations in ( 15) and ( 16) hold.

To this end P conducts the following steps.

1. Decompose the matrix B U ∈ Z n× m q into b U = mdec n, m,q (B U ) ∈ {0, 1} n mk and the vectors s rec , s oa ∈ Z n q into s 0,rec = vdec n,q-1 (s rec ) ∈ {0, 1} nk and s 0,oa = vdec n,q-1 (s oa ) ∈ {0, 1} nk . Combine the first two binary vectors into

z Ψ = expand ⊗ (b U , s 0,rec ) ∈ {0, 1} 4n mk 2 . Define Q = H m,q-1 • [ n times Q 0 | . . . |Q 0 ] ∈ Z m×4n mk 2 q , where Q 0 = I mk ⊗ g ∈ Z mk×4 mk 2 q
is the matrix defined as in [START_REF] Bellare | Key-privacy in public-key encryption[END_REF].

Generate a zero-knowledge argument of knowledge of

           τ ∈ {0, 1} , d = [d 1 |d 2 ] ∈ [-β, β] 2m , r ∈ [-β, β] m t U ∈ {0, 1} m , w U ∈ {0, 1} m b U ∈ {0, 1} n mk , s 0,rec ∈ {0, 1} nk , z Ψ = expand ⊗ (b U , s 0,rec ) x rec , y rec ∈ [-B, B] m , z rec ∈ [-βmB, βmB] m, w ∈ {0, 1} m , s 0,oa ∈ {0, 1} nk , x oa , y oa ∈ [-B, B] m , z oa ∈ [-βmB, βmB]
m such that the following system of 10 equations holds:

                                                                         u = [A|A 0 |A 1 | . . . |A ] •         d 1 d 2 τ [1] • d 2 . . . τ [ ] • d 2         + (-D) • w U mod q, 0 = H n,q-1 • w U + (-D 0 ) • r + (-D 1 ) • t U mod q, 0 = H 2n,q-1 • t U + (-F) • b U mod q, c (1)
rec = ( Ā • H n,q-1 ) • s 0,rec + I m • y rec mod q, c (2)
rec = Q • z Ψ + (G • H VK • H n,q-1 ) • s 0,rec + I m • z rec mod q, c (3)
rec = (U • H n,q-1 ) • s 0,rec + I m • x rec + ( q 2 • I m ) • w mod q, u R = A R • w mod q, c (1)
oa = ( Ā • H n,q-1 ) • s 0,oa + I m • y oa mod q, c (2)
oa = [(B OA + H VK • G) • H n,q-1 ] • s 0,oa + I m • z oa mod q, c (3)
oa = (V • H n,q-1 ) • s 0,oa + I m • x oa + ( q 2 • I m ) • t U mod q. (18)
Let

w 1 = b U , w 2 = s 0,rec , w 3 = z Ψ = expand ⊗ (b U , s 0,rec ), w 4 = w U , w 5 = t U , w 6
= s 0,oa , w 7 = w, w 8 = x rec , w 9 = y rec , w 10 = z rec , w 11 = r, w 12 = x oa , w 13 = y oa , w 14 = z oa and

w 15 = d 1 d 2 τ [1]• d 2 . . . τ [ ]• d 2 .
Then system (18) can be rewritten as:

           v 1 = M 1,1 • w 1 + M 1,2 • w 2 + . . . + M 1,15 • w 15 mod q, v 2 = M 2,1 • w 1 + M 2,2 • w 2 + . . . + M 2,
where {M i,j } (i,j)∈[10]× [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF] , {v i } i∈ [START_REF] Benhamouda | Efficient zeroknowledge proofs for commitments from learning with errors over rings[END_REF] are public matrices and vectors (which are possibly zero).

The argument system is obtained by invoking the protocol from Section 4.2. The protocol is repeated κ times to make the soundness error negligibly small.

Efficiency and Correctness

Efficiency. It can be seen that the given group encryption scheme can be implemented in polynomial time. We now will evaluate the bit-sizes of keys and ciphertext, as well as the communication cost of the protocol P, V .

-The public key of GM, as in [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF], has bit-size O( n 2 log 2 q) = O( λ 2 ).

-The public keys of OA and each user both have bit-size n m log 2 q = O(λ 2 ).

-The secret key of each party in the scheme is a trapdoor of bit-size O(λ 2 ).

The user's certificate cert U has bit-size O(λ). -The ciphertext Ψ consists of VK ∈ Z n q , two ABB ciphertexts of total size 2(2m+ m) log 2 q and a one-time signature Σ. Thus, its bit-size is O(λ)+ Σ .

-The communication cost of the protocol P, V is largely dominated by the bit-size of the witness

z Ψ = expand ⊗ (b U , s 0,rec ) ∈ {0, 1} 4n mk 2 . The total cost is κ • O(n 2 log 4 q) = O(λ 2 ) bits.
Correctness. The given group encryption scheme is correct with overwhelming probability. We first remark that the scheme parameters are set up so that the two instances of the ABB identity-based encryption [1] are correct. Indeed, during the decryption procedure of DEC(sk U , Ψ, L), we have:

c (3) rec -E VK • c (1) rec c (2) rec = x rec -E VK • y rec z rec + w • q 2 .
Note that x rec ∞ and y rec ∞ are bounded by B, and

z rec ∞ = R rec •y rec ∞ ≤ βmB = O(n 2
). Furthermore, the entries of the discrete Gaussian matrix E VK are bounded by O( √ n). Hence, the error term x rec -E VK • y rec z rec is bounded by O(n 3.5 ) which is much smaller than q/4 = O(n 4 ). As a result, the decryption algorithm returns w with overwhelming probability. The correctness of algorithm OPEN(sk OA , Ψ, L) also follows from a similar argument. Finally, we note that if a certified group user honestly follows all the prescribed algorithms, then he should be able to compute valid witness-vectors to be used in the protocol P, V , and he should be accepted by the verifier, thanks to the perfect completeness of the argument system in Section 4.2.

Security

Our scheme is proven secure under the SIS and LWE assumptions using classical reduction techniques. The security results are explicited in the following theorems, for which some proofs have been deferred to Appendix C. Theorem 2. The scheme provides anonymity if the LWE assumption holds and if OT S is a strongly unforgeable one-time signature. (The proof is given in Appendix C.1.) Theorem 3. The scheme provides message secrecy assuming that the LWE assumption holds and that OT S is a strongly unforgeable one-time signature. (The proof is presented in Appendix C.2.) Theorem 4. The scheme provides soundness under the SIS assumption. Proof. To prove the result, we observe that, in order to break the soundness property, the adversary must come up with a relation pk R = (A R , u R ) ∈ Z n×m q × Z n q , a ciphertext Ψ = (VK , c rec , c oa , Σ ), a label L and produce a convincing proof π Ψ such that either a. c oa does not decrypt to a string h ∈ {0, 1} m such that h U = H 2n,q-1 • h ∈ Z 2n q coincides with h U = F•mdec n,m,q (B U ) for some pk U = B U ∈ Z n× m q appearing in database. b. c oa opens to a certified public key pk U = B U ∈ Z n× m q , which belongs to database (and for which a certificate was issued), but B U is outside the language PK of valid public keys. This case is immediately ruled out by the density of the public key space. Namely, all matrices B U ∈ Z n× m q are potentially valid public keys as there always exist a small-norm matrix T U ∈ Z m× m such that B U = Ā • T U mod q. c. c oa opens to a certified key pk U = B U for which Ψ = (VK , c rec , c oa , Σ ) is not a valid encryption of w ∈ {0, 1} m such that u R = A R • w mod q. d. The opening algorithm fails to uniquely identify the receiver. This occurs if c oa decrypts to a string h ∈ {0, 1} m such that h U = H 2n,q-1 • h ∈ Z 2n q corresponds to at least two distinct public keys B U,0 , B U,1 ∈ Z n× m q which satisfy h U = F • mdec n, m,q (B U,0 ) mod q = F • mdec n, m,q (B U,1 ) mod q.

Since mdec n, m,q (.) : Z m×n q → {0, 1} n mk is an injective function, the above equality necessarily implies a collision for the SIS-based hash function built upon F ∈ Z 2n×n mk q : namely, mdec n, m,q (B U,0 ) -mdec n, m,q (B U,1 ) ∈ {-1, 0, 1} n mk is a short non-zero vector of Λ ⊥ q (F). Having shown that cases b and d cannot occur if the SIS assumption holds, we only need to consider cases a and c. The computational soundness of the argument system ensures that, by replaying the soundness adversary a sufficient number of times, the knowledge extractor will be able to extract either: (i) A breach in the computational soundness of the argument system and thus the binding property of the commitment scheme COM (which relies on the SIS assumption with the commitment scheme of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]). Note that this situation covers case (c.) above. (ii) A set of witnesses [START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF]. Given that witnesses τ ∈ {0, 1} , d ∈ [-β, β] 2m , r ∈ [-β, β] m and t U ∈ {0, 1} m satisfy [START_REF] Cathalo | Group encryption: Non-interactive realization in the standard model[END_REF], it comes that (τ, d, r) form a valid signature for the message t U ∈ {0, 1} m . At this point, case a implies that no matrix B U ∈ Z n× m q of database decomposes to a string h U ∈ {0, 1} n mk such that t U = vdec n,q-1 (F • h U mod q) was signed by the reduction during an execution of JOIN. This implies that the pair t U , (τ, d, r) forms a forgery for the SISbased signature scheme of Appendix A.1. The reduction is straightforward and omitted.

           τ ∈ {0, 1} , d = [d 1 |d 2 ] ∈ [-β, β] 2m , r ∈ [-β, β] m t U ∈ {0, 1} m , w U ∈ {0, 1} m b U ∈ {0, 1} n mk , s 0,rec ∈ {0, 1} nk , z Ψ ∈ {0, 1} 4n mk 2 x rec , y rec ∈ [-B, B] m , z rec ∈ [-βmB, βmB] m, w ∈ {0, 1} m , s oa ∈ {0, 1} nk , x oa , y oa ∈ [-B, B] m , z oa ∈ [-βmB, βmB] m satisfying relations
Output the signature sig = (τ, v, r) ∈ {0, 1} × Z 2m × Z m . Verify P K, m, sig : Given P K, m ∈ {0, 1} m and sig = (τ, v, r) ∈ {0, 1} ×

Z 2m × Z m , return 1 if v < σ √ 2m, r < σ √ m and
A τ • v = u + D • vdec n,q-1 (D 0 • r + D 1 • m) mod q. (21)
Like [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], the scheme of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] was proved secure under the SIS assumption and shown to easily interact with Stern-like protocols when it comes to proving knowledge of a hidden message-signature pair. While such proofs would also be possible using Boyen's signature [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF], the number of public matrices {A j } j=0 in the public key can be reduced from Θ(n • log q) to Θ(λ) using the scheme of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF].

The above description uses a slightly different variant of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] where, at step 2 of the signing algorithm, a different binary decomposition of c M is used to compute u M : while [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] uses the standard binary decomposition, we use a non-unique encoding based on the vdec function for convenience. However, the security proof of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] goes through with this encoding since the function vdec n,q-1 (.) is injective. Lemma 6 ([38,Th. 1]). The above signature scheme is unforgeable under chosen-message attacks if the SIS assumption holds. Our proofs rely on the semantic security of the scheme against selective adversaries (IND-sID-CPA) but also on the stronger property of ciphertext pseudorandomness. Informally, this notions demands that the adversary be unable to distinguish an encryption of a message of its choice from a random element of the ciphertext space C. Notice that this property implies IND-sID-CPA security. We first restate Theorem 1.

Theorem 6. The protocol in Figure 1 is a statistical ZKAoK with perfect completeness, soundness error 2/3, and communication cost O(D log q). In particular:

-There exists an efficient simulator that, on input (M, v), outputs an accepted transcript which is statistically close to that produced by the real prover. -There exists an efficient knowledge extractor that, on input a commitment CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs x ∈ VALID such that M • x = v mod q.

Proof. It can be checked that the protocol has perfect completeness: If an honest prover follows the protocol, then he always gets accepted by the verifier. It is also easy to see that the communication cost is bounded by O(D log q). We now prove that the protocol is a statistical zero-knowledge argument of knowledge.

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} as 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 D q such that M • x = v mod q. Next, it samples r x ← U (Z D 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 x ; ρ 1 ), C 2 = COM(Γ π (r x ); ρ 2 ), C 3 = COM(Γ π (x + r x ); ρ 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 x , ρ 1 , ρ 3 . -If Ch = 3: Send RSP = π, r x , ρ 1 , ρ 2 . Case Ch = 2: SIM samples x ← U (VALID), r x ← U (Z D 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 x ; ρ 1 ), C 2 = COM(Γ π (r x ); ρ 2 ), C 3 = COM(Γ π (x + r x ); ρ 3 ).
Receiving a challenge Ch from V, the simulator responds as follows:

C Security Proofs for the Group Encryption Scheme Proof. We consider a sequence of games where the first game is the real experiment of definition 5 while, in the final game, the adversary A is essentially an adversary against the anonymity of the Agrawal-Boneh-Boyen IBE scheme [1]. In Game i, we call W i the event that the challenger outputs 1.

Game 1: The challenger B generates public parameters param, which include matrices Ā, U, V ∈ Z n×m q and F ∈ Z 2n×n mk q . The opening authority's public key pk OA = B OA ∈ Z n× m q is given to A who generates a group manager's public key pk GM of its own. By invoking the USER oracle, A registers two distinct receivers' public keys pk U,0 = B U,0 ∈ Z n× m q , pk U,1 = B U,1 ∈ Z n× m q chosen by the challenger. It also makes a number of opening queries and decryption queries, which the challenger handles using sk OA = T OA and sk U,0 = T U,0 , sk U,1 = T U,1 , respectively. After a while, the adversary outputs (

(A R , u R ), w, L) such that u R = A R • w mod q, with A R ∈ Z n×m p , u R ∈ Z n
q and w ∈ {0, 1} m . In return, A obtains, as a challenge, a group encryption Ψ = (VK , c rec , c oa , Σ ). of the witness w under pk U,b = B U,b , for some random bit b ← U ({0, 1}) of the challenger's choice. Then, the adversary obtains proofs π Ψ for Ψ and makes further opening and decryption queries under the natural restrictions of Definition 5. When the adversary A halts, it outputs a bit b ∈ {0, 1} and the challenger outputs 1 if and only if b = b.

Game 2: This game is like Game 1 except the challenger aborts in the event that the adversary A queries the opening of a ciphertext Ψ = (VK, c rec , c oa , Σ) such that VK = VK and σ is valid (we assume w.l.o.g. that VK is generated ahead of time). If this event occurs, the adversary A is necessarily able to break the strong unforgeability of OT S (note that, if the query occurs before the challenge phase, it means that A has forged a signature without seeing a signature at all). There thus exist a one-time signature forger B such that |Pr

[W 2 ] -Pr[W 1 ]| ≤ Adv ots B (λ)
, which means that Game 2 is identical to Game 1 so long as OT S is a strongly unforgeable one-time signature.

Game 3: In this game, we modify the generation of proofs π Ψ : instead of generating proofs using the real witnesses, we appeal to the zero-knowledge simulator of the argument system of Section 4.2 at each invocation of P after the challenge phase. Note that, since we assume public parameters generated by a trusted party, the statistical ZK simulator is allowed to use a trapdoor embedded in param to generate simulated proofs (using, e.g., Damgård's technique [START_REF] Damgård | Efficient concurrent zero-knowledge in the auxiliary string model[END_REF]). The statistical zero-knowledge property of the argument system ensures that A's view remains statistically close to that of Game 2: we have

|Pr[W 3 ] -Pr[W 2 ]| ≤ negl(λ).
Game 4: We now modify the generation of the challenge ciphertext Ψ . In this game, the challenger computes the ciphertext c oa as an ABB encryption under the identity VK of a random m-bit string instead of a decomposition

vdec n,q-1 (h U,b ) ∈ {0, 1} m of h U,b = F • mdec n, m,q (B U,b ) ∈ Z 2n
q . Since the random encryption coins s oa , R oa , x oa , y oa are no longer used to generate proofs π Ψ , we can show that any noticeable change in A's output distribution implies a selective adversary against the ABB IBE, as established by Lemma At the outset of the game, the reduction B generates a one-time signature key pair (VK , SK ) and declares VK as the target identity to its challenger for the selective security game, and obtains in return the IBE public parameters

PP = Ā, B, V ∈ Z n×m q × Z n× m q × Z n×m q .
Next, the reduction runs the appropriate steps of the actual SETUP init algorithm to obtain COM par , F ∈ Z 2n×n mk q and U ∈ Z n×m q . Namely, B samples F ← U (Z 2m×n mk q ) and U ← U (Z n×m q ) like in the SETUP init algorithm and sends param = λ, n, q, k, m, B, χ, σ, β, , κ, OT S, COM par , FRD, Ā, G, F, U, V along with pk OA = B ∈ Z n× m q to the adversary A. In return, the adversary A chooses pk GM , which allows it to enroll two users for whom B faithfully generates (pk U,i , sk U,i ) i∈{0,1} . Knowing both private keys {sk U,i = T U,i } i∈{0,1} , B is able to perfectly simulate the DEC(•) oracle.

Open Queries. To answer opening queries for ciphertexts Ψ = (VK, c rec , c OA , Σ) and labels L, B first checks that Ver(VK, Σ, (c rec , c OA , L)) = 1. If this test fails, B returns ⊥. Otherwise, B queries its IBE challenger to obtain a IBE private key T OA,VK ∈ Z (m+ m)×m for identity VK = VK . The IBE challenger's response allows B to decrypt c OA and figure out the identity of the receiver by looking up database. The result of the opening operation is then returned to A.

After a number of queries, A decides to move to the challenge phase and sends a challenge query (A R , u R ), w , L such that u R = A R • w mod q. The reduction handles this query by requesting a challenge ciphertext for the IBE security game with the messages m 0 = vdec n,q-1 (h U,b ), for some random bit b ← U ({0, 1}) and m 1 ← U ({0, 1} m ). In return, B obtains a challenge ciphertext c OA under identity VK , which is embedded in A's challenge ciphertext.

To answer decryption queries (Ψ = (VK, c rec , c OA , Σ), L), for any query pertaining to pk U,b , the reduction invokes its ROR challenger to obtain an IBE private key for the identity VK = VK and uses the result to decrypt c rec . For any decryption query involving pk U,1-b , the reduction can faithfully run the actual decryption algorithm using its trapdoor T 1-b . Open queries are answered using T OA as in the real Open algorithm.

When the adversary A decides to do so, it queries a challenge for a triple ((A R , u R ), w, L) of its choice subject to the constraint u R = A R • w. At this point, B queries a challenge to its own challenger for the message w and obtains a ciphertext c, which is embedded in Ψ = (VK , c, c OA , Σ ) while c OA and Σ are generated as in Game 3 (in particular, c OA encrypts a random string instead of a hash value of pk U,b ). After the challenge phase, all queries to the proving oracle P are replied by returning a simulated ZK argument as in Game 3.

When Proof. We proceed via a sequence of games. The first one corresponds to the experiment of Definition 4 when the challenger's bit b is 1 and the adversary obtains an actual encryption of the witness w ∈ {0, 1} m and real proofs at each invocation of the PROVE(.) oracle. In the last game, the adversary A is given an encryption of some random plaintext whereas PROVE(.) returns simulated zero-knowledge arguments which are generated a simulator P that does not use any witness. In Game i, W i stands for the event that the adversary A outputs the bit b = 1.

Game 1: This is the real game, where the challenger feeds A with public parameters param containing Ā, U, V ∈ Z n×m q and F ∈ Z 2n×n mk q . The adversary produces public keys pk OA = B OA ∈ Z n× m q and pk GM = (A, {A i } i=0 , D 0 , D 1 , D, u) on behalf of the opening authority and the group manager which are both under its control. The challenger and A run an execution of the JOIN protocol which allows A to register and certify the public key pk U = B U ∈ Z n× m q of some honest receiver chosen by the challenger. Then, the adversary A makes a polynomial number of decryption queries which the challenger faithfully handles using the private key sk U = T U ∈ Z m× m for which B U • T U = 0 n× m. At some point, the adversary A outputs a triple ((A R , u R ), w, L) such that u R = A R • w mod q, with A R ∈ Z n×m p , u R ∈ Z n q and w ∈ {0, 1} m . At this point, the challenger generates a challenge ciphertext Ψ = (VK , c rec , c oa , Σ ) consisting of a group encryption of the real witness w under pk U = B U . Then, the adversary obtains a polynomial number of proofs π Ψ related to the challenge ciphertext Ψ and 40 is granted further access to the decryption oracle under the obvious restrictions. When A halts, it outputs a bit b ∈ {0, 1}.

Game 2: In this game, we modify the DEC(.) oracle and have the challenger reject any ciphertext of the form Ψ = (VK, c rec , c oa , Σ) such that VK = VK (note that VK can be generated at the outset of the game w.l.o.g.). Clearly Game 2 is identical to Game 1 until the event that the challenger rejects a ciphertext that would not have been rejected in Game 1. This can only occur if A is able to break the strong unforgeability of the one-time signature OT S. As in the proof of Theorem 2, we have |Pr[W 2 ] -Pr[W 1 ]| ≤ Adv ots (λ), which is negligible if OT S is strongly unforgeable.

Game 3: We now modify the generation of proofs π Ψ . Instead of generating them using the witnesses used in the generation of Ψ , we rely on the zeroknowledge simulator of the argument system of Section 4.2 at each invocation of PROVE b P,P after the challenge phase (note that, since we assume trusted public parameters, the simulator can use techniques [START_REF] Damgård | Efficient concurrent zero-knowledge in the auxiliary string model[END_REF] to achieve statistically perfect simulation without increasing the number of rounds). The statistical ZK property of the argument system ensures that this change will remain unnoticed, even in the view of an all powerful adversary: we have |Pr[W 3 ]-Pr[W 2 ]| ∈ negl(λ). From now onwards, the random coins coins Ψ = s rec , R rec , x rec , y rec , s oa , R oa , x oa , y oa are no longer used by the PROVE oracle. At the very beginning of the IND-sID-CPA game, the reduction B generates a one-time signature key pair (SK , VK ) and hands VK to its selective security

  15 • w 15 mod q, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 10 = M 10,1 • w 1 + M 10,2 • w 2 + . . . + M 10,15 • w 15 mod q,

  15 • w 15 mod q, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 10 = M 10,1 • w 1 + M 10,2 • w 2 + . . . + M 10,15 • w 15 mod q.

Fig. 1 :

 1 Fig. 1: Our zero-knowledge argument of knowledge.

  15 • w 15 mod q, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 10 = M 10,1 • w 1 + M 10,2 • w 2 + . . . + M 10,15 • w 15 mod q,

A. 2

 2 The Agrawal-Boneh-Boyen IBE Scheme Identity-Based Encryption. An IBE scheme is a tuple of efficient algorithms (Setup, Extract PP , Encrypt PP , Decrypt PP ) such that Setup(1 λ ): On security parameter λ, this algorithm outputs public parameters PP and a master secret key msk. Extract PP (msk, ID): Takes as input a master secret key msk and an identity ID and outputs a secret key sk ID . Encrypt PP (ID, M ): Given an identity ID and a message M , it outputs a ciphertext C. Decrypt PP (sk ID , C): Given a secret key sk ID and a ciphertext C, outputs either a decryption error symbol ⊥, or a message M . Correctness requires that, for any pair (PP, msk) ← Setup(1 λ ), any ID and any message M , we have Decrypt PP Extract PP (msk, ID), Encrypt PP (ID, M ) = M.

Definition 7 .= 1 -1 2 |

 712 An IBE scheme has pseudo-random-ciphertexts if no PPT adversary A with access to private key extraction oracle Extract PP (msk, •) has nonnegligible advantage Adv ROR A (λ) = | Pr Expt ROR A in this game: B Proof of Theorem 1

C. 1

 1 Anonymity (Proof of Theorem 2)

  A ends, it outputs a bit b ∈ {0, 1}. If b = b, the reduction outputs Real. Otherwise, it outputs Random. Indeed, if the ROR challenger is playing the real game, we are exactly in Game 4: we have Pr[b = b|Real] = Pr[W 4 ]. Otherwise, the challenge ciphertext Ψ is completely independent of b ∈ {0, 1} so that we can only have b = b with probability Pr[b = b|Random] = 1/2. It follows that Adv ROR B (λ) ≥ | Pr[W 4 ] -1/2|. C.2 Message Secrecy (Proof of Theorem 3)

Game 4 :

 4 In the generation of Ψ , we set c rec as an encryption of a random element of Z m p . Since the random encryption coins s rec , R rec , x rec , y rec are not used in Game 3, Lemma 9 gives a simple reduction showing that any significant change in A's behavior would imply a selective adversary against the ABB identity-based encryption scheme. The result of[1] tells us that, under the LWE assumption, Game 4 is computationally indistinguishable from Game 3 in the adversary's view: we have |Pr[W 4 ] -Pr[W 3 ]| ≤ Adv LWE (λ).

Game 5 :

 5 We bring a last modification to the DEC(.) oracle and now refrain from applying the rejection rule of Game 2. If OT S is strongly unforgeable, the distance |Pr[W 5 ] -Pr[W 4 ]| ≤ Adv ots (λ) must be negligible. In the last game, the oracle PROVE(.) does not need to know any witness. It thus mirrors the experiment of Definition 4 where the challenger's bit is b = 0. Putting everything altogether, we get |Pr[W 5 ] -Pr[W 1 ]| ∈ negl(λ), which yields the claimed result. Lemma 9. Any PPT adversary that can distinguish Game 4 from Game 3 implies a selective adversary against the ABB IBE scheme. Proof. Let us assume a PPT adversary A such that ε = Pr[W 4 ] -Pr[W 3 ] is noticeable. We use A to construct a PPT adversary B that breaks the IND-sID-CPA security of the ABB scheme, which would contradict the LWE assumption, as established in [1, Th. 23].

  7, which would contradict the LWE assumption. The result of Agrawal et al. [1, Theorem 23] (recalled in Theorem 5) indeed implies |Pr[W 4 ] -Pr[W 3 ]| ≤ Adv LWE (λ). In Game 4, we can show that, if the adversary A has noticeable advantage in the anonymity game, we can break the anonymity of the ABB IBE system, as shown in the proof of Lemma 8. From the result of [1, Theorem 23], we deduce that |Pr[W 4 ] -1/2| ≤ Adv LWE (λ), which implies the announced result. Lemma 7. Any PPT adversary such that Pr[W 4 ] is noticeably different from Pr[W 3 ] implies a selective adversary against the ABB IBE scheme. Proof. Let A be a PPT adversary for which |Pr[W 4 ] -Pr[W 3 ]| = ε is nonnegligible. We use A to build a selective adversary against the ABB IBE system.

The Supporting Zero-Knowledge LayerIn this section, we first demonstrate how to prove in zero-knowledge that a given vector b is a correct LWE evaluation, i.e., b = X • s + e mod q, where the hidden matrix X and vector s may satisfy additional conditions. This sub-protocol, which we believe will have other applications, is one of the major challenges in our road towards the design of lattice-based group encryption. We then plug this building block into the big picture, and construct the supporting zero-knowledge argument of knowledge (ZKAoK) for our group encryption scheme (Section

5).

This means that, for any two distinct one-time verification keys VK, VK ∈ Z n q , the difference FRD(VK) -FRD(VK ) ∈ Z n×n q is invertible over Zq.

Acknowledgements

We thank Damien Stehlé for useful discussions and the reviewers for useful comments. 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". Huaxiong Wang was also supported by NTU under Tier 1 grant RG143/14.

q

. The prospective user defines his key pair as (pk U , sk U ) = (B U , T U ) and sends pk U = B U to the GM. 2. Upon receiving a public key pk U = B U ∈ Z n× m q from the user, the GM certifies pk U via the following steps: a. Compute h U = F•mdec n, m,q (B U ) ∈ Z 2n q as a hash value of the public key pk U = B U ∈ Z n× m q . b. Use the trapdoor sk GM = T A to generate a signature

satisfying

where τ = τ [1] . . . τ [ ] ∈ {0, 1} , as in the scheme of Section A.1. U verifies that cert U is tuple of the form [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF] satisfying [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] and returns ⊥ if it is not the case. The GM stores (pk U , cert U ) in the user database database and returns the certificate cert U to the new user U.

ENC(pk GM , pk OA , pk U , cert U , w, L): To encrypt a witness w ∈ {0, 1} m such that ((A R , u R ), w) ∈ R ISIS (n, m, q, 1) (i.e., A R • w = u R mod q), parse pk GM as in [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF], pk OA as B OA ∈ Z n× m q , pk U as B U ∈ Z n× m q and cert U as in [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF].

1. Generate a one-time key-pair (SK, VK) ← Gen(1 λ ), where VK ∈ Z n q . 2. Compute a full-rank-difference hash H VK = FRD(VK) ∈ Z n×n q of the one-time verification key VK ∈ Z n q . 3. Encrypt the witness w ∈ {0, 1} m under U's public key B U ∈ Z n× m q using the tag VK by taking the following steps: a. Sample

and let c rec = c

(1)

rec , c

rec ∈ Z m q ×Z m q ×Z m q , which forms an ABB ciphertext [1] for the tag VK ∈ Z n q . 4. Encrypt the decomposition vdec n,q-1 (h U ) ∈ {0, 1} m of the hashed pk U under the OA's public key B OA ∈ Z n× m q w.r.t. the tag VK ∈ Z n q . Namely, conduct the following steps:

A Building Blocks

A.1 Signatures Supporting Zero-Knowledge Proofs

We use a signature scheme proposed by Libert, Ling, Mouhartem, Nguyen and Wang [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] who extended the Böhl et al. signature [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] (which is itself built upon Boyen's signature [START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF]) into a signature scheme compatible with zero-knowledge proofs. While the scheme was designed to sign messages comprised of multiple blocks, we only use the single-block version here.

Keygen(1 λ , q, n, m, , σ): This algorithm takes as input a security parameter λ > 0 as well as the following parameters: n = O(λ); a prime modulus q = O(n 4 ); dimension m = 2n log q ; an integer = poly(λ); and Gaussian parameters σ = Ω( √ n log q log n). It defines the message space as {0, 1} m .

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/2 q ), D 0 , D 1 ← U (Z n×m 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

Sign SK, m : To sign a message m ∈ {0, 1} m , 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

The ABB System. Agrawal, Boneh and Boyen described [1] a compact IBE scheme in the standard model which allows encrypting multi-bit messages.

Setup(1 λ ): Given a security parameter λ, choose parameters q, n, σ, α and define k = log q , m = nk, m = 2 m and choose a noise distribution χ for LWE.

be the full-rank difference mapping from [1]. Output PP = Ā, B, U and msk = T Ā. Extract PP (msk, ID): Given msk = T Ā and an identity ID ∈ Z n q , do as follows: 1. Define the matrix

, use T A to compute a delegated basis T ID for the lattice Λ ⊥ (B A,ID ). 3. Use T ID to sample a small-norm matrix E ID ∈ Z (m+ m)×m satisfying the equality

Encrypt PP (ID, m): Given an identity ID and a message m ∈ {0, 1} m , 1. Compute the matrix

Decrypt PP (sk ID , c):

Theorem 5 ([1, Th. 23]). The ABB IBE scheme has pseudo-random ciphertexts if the LWE n,q,χ assumption holds.

-

-If Ch = 2: Output ⊥ and abort.

-

Case Ch = 3: SIM samples x ← U (VALID), r x ← U (Z D 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(Γ π (r x ); ρ 2 ), C 3 = COM(Γ π (x +r x ); ρ 3 ) as in the previous two cases, while

Receiving a challenge Ch from V, it responds as follows:

-If Ch = 1: Send RSP computed as in the case (Ch = 2, Ch = 1).

-If Ch = 2: Send RSP computed as in the case (Ch = 1, Ch = 2).

-If Ch = 3: Output ⊥ and abort.

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

3 ), RSP 3 = (π 3 , y 3 , ρ

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:

This concludes the proof.

Namely, Ψ = (VK , c rec , c OA , Σ ) is obtained by computing c rec as an ABB encryption of the witness w using the matrix B U,b ∈ Z n× m q as in ( 15) and Σ = Sign(SK , (c rec , c OA , L )). All queries to the proving oracle P are replied by returning a simulated ZK argument as in Game 3.

When A halts, it outputs a bit b ∈ {0, 1}. If b = b , B returns the bit 0 as a guess that the selective security challenger encrypted m 0 = vdec n,q-1 (h U,b ). Otherwise, B outputs 1 meaning that the IBE challenger chose to encrypt m 1 , which was chosen independently of the value of b ∈ {0, 1}. If we call Random (resp. Real) the event that the IBE challenger chooses to encrypt m 1 (resp. m 0 ), we can assess the advantage of the reduction B as

which proves the result. Lemma 8. In Game 4, the adversary's advantage is negligible assuming that the ABB IBE has pseudo-random ciphertexts.

Proof. Let us assume the existence of a PPT adversary A with non negligible advantage ε in Game 4. From A, we construct a selective adversary B that can distinguish ABB ciphertexts from random elements of the ciphertext space with non-negligible advantage in the game described in Definition 7.

First, B generates (SK , VK ) via the key generation algorithm of the onetime-signature OTS and hands VK to its pseudo-randomness challenger. In return, B receives

from its real-or-random (ROR) challenger.

Our reduction uses PP to compute public parameters for our GE scheme. To this end, it samples F ← U (Z 2n×n mk q ), V ← U (Z n×m q ) as in the real SETUP init algorithm. The reduction B also computes B OA = Ā • T OA mod q, where the small-norm matrix T OA is sampled from D m× m Z,σ , and sends A the parameters

where Ā is taken from PP, along with pk OA = B OA . The rest of the keys are generated as in Game 4.

The reduction B then tosses a coin b ← U ({0, 1}). When the adversary A triggers an execution of the join protocol, B generates the public keys (pk i ) i∈{0,1} by defining pk U,b = B using the matrix B ∈ Z n× m q supplied by the ROR challenger as part of PP and generates (pk

Z m ,σ of its own. The two public keys (pk U,i ) i∈{0,1} are then certified by the adversarially-controlled GM. Notice that in the adversary's view, both public keys pk U,b and pk U,1-b are identically distributed. challenger as the target identity under which the challenge ciphertext will later be computed. In response, B receives the public parameters

The reduction then runs the missing steps of the actual Setup init algorithm: namely, B samples F ← U (Z 2m×n mk q ), V ← U (Z n×m q ) and generates COM par before sending the common public parameters param = λ, n, q, k, m, B, χ, σ, β, , κ, OT S, COM par , FRD, Ā, G, F, U, V to the adversary A.

At this point, the adversary A chooses the public keys pk OA = B OA ∈ Z n× m q and pk GM = (A, {A i } i=0 , D 0 , D 1 , D, u) on behalf of the opening authority and the group manager. It also starts an execution of the joining protocol in which the reduction B defines pk U = B ∈ Z n× m q as the honest receiver's public key, where B ∈ Z n× m q is taken from the public parameters PP supplied by its IBE challenger. Note that pk = B ∈ Z n× m q is distributed as a real key in A's view. This public key is certified by A which controls the GM.

In the next stage, A makes a number of decryption queries for ciphertexts of the form Ψ = (VK, c rec , c OA , Σ). To answer these, the reduction invokes its IBE challenger so as to obtain an IBE private key E VK ∈ Z (m+ m)×m for the identity VK = VK . The resulting E VK is used it to IBE-decrypt c rec and return the corresponding witness w to A .

At some point, the adversary A queries a challenge ciphertext by outputting a triple ((A R , u R ), w, L) such that w ∈ {0, 1} m satisfies u R = A R • w mod q. Then, the reduction B requests a challenge ciphertext c rec to its IBE challenger by sending it the messages m 1 = w ∈ {0, 1} m and m 0 ← U ({0, 1} m ). The resulting ciphertext c rec is embedded in Ψ = (VK , c rec , c OA , Σ ) by faithfully computing c OA and Σ as in the actual Enc algorithm.

After the challenge phase, A keeps sending decryption queries for ciphertexts Ψ containing one-time verification keys VK = VK and these decryption queries are answered as before. In addition, A is granted access to the stateful oracle PROVE b P,P . Recall that, from Game 3 onwards, all these queries are answered by returning simulated zero-knowledge arguments. Eventually A outputs a bit b ∈ {0, 1} which is also returned by B to its own challenger.

If the IBE challenger provides a challenge c rec that encrypts a random message (i.e., by encrypting m 0 ), then we are exactly in the setting of Game 4. In the even that c rec rather encrypts m 1 = w ∈ {0, 1} m , A's view is exactly the same as in Game 3. If we denote by Random (resp. Real) the event that the IBE challenger chooses to encrypt m 0 (resp. m 1 ), the advantage of the reduction B as an IND-sID-CPA adversary is