Shweta Agrawal

Benoît Libert

Damien Stehlé

Fully Secure Functional Encryption for Inner Products, from Standard Assumptions

Keywords: Functional encryption, adaptive security, standard assumptions, DDH, LWE, extended LWE, composite residuosity

Functional encryption is a modern public-key paradigm where a master secret key can be used to derive sub-keys SKF associated with certain functions F in such a way that the decryption operation reveals F (M ), if M is the encrypted message, and nothing else. Recently, Abdalla et al. gave simple and efficient realizations of the primitive for the computation of linear functions on encrypted data: given an encryption of a vector y over some specified base ring, a secret key SKx for the vector x allows computing x, y . Their technique surprisingly allows for instantiations under standard assumptions, like the hardness of the Decision Diffie-Hellman (DDH) and Learning-with-Errors (LWE) problems. Their constructions, however, are only proved secure against selective adversaries, which have to declare the challenge messages M0 and M1 at the outset of the game. In this paper, we provide constructions that provably achieve security against more realistic adaptive attacks (where the messages M0 and M1 may be chosen in the challenge phase, based on the previously collected information) for the same inner product functionality. Our constructions are obtained from hash proof systems endowed with homomorphic properties over the key space. They are (almost) as efficient as those of Abdalla et al. and rely on the same hardness assumptions. In addition, we obtain a solution based on Paillier's composite residuosity assumption, which was an open problem even in the case of selective adversaries. We also propose LWE-based schemes that allow evaluation of inner products modulo a prime p, as opposed to the schemes of Abdalla et al. that are restricted to evaluations of integer inner products of short integer vectors. We finally propose a solution based on Paillier's composite residuosity assumption that enables evaluation of inner products modulo an RSA integer N = p • q. We demonstrate that the functionality of inner products over a prime field is powerful and can be used to construct bounded collusion FE for all circuits.

Introduction

Functional encryption (FE) [START_REF] Sahai | Fuzzy identity-based encryption[END_REF][START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF] is a generalization of public-key encryption, which overcomes the all-or-nothing, user-based access to data that is inherent to public key encryption and enables fine grained, role-based access that makes it very desirable for modern applications. A bit more formally, given an encryption enc(X) and a key corresponding to a function F , the key holder only learns F (X) and nothing else. Apart from its theoretical appeal, the concept of FE also finds numerous applications. In cloud computing platforms, users can store encrypted data on a remote server and subsequently provide the server with a key SK F which allows it to compute the function F of the underlying data without learning anything else.

In some cases, the message X = (IND, M ) consists of an index IND (which can be thought of as a set of descriptive attributes) and a message M , which is sometimes called "payload". One distinguishes FE systems with public index, where IND is publicly revealed by the ciphertext but M is hidden, from those with private index, where IND and M are both hidden. Public index FE is popularly referred to as attribute based encryption.

A Brief History of FE. The birth of Functional Encryption can be traced back to Identity Based Encryption [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF][START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] which can be seen as the first nontrivial generalization of Public Key Encryption. However, it was the work of Sahai and Waters [START_REF] Sahai | Fuzzy identity-based encryption[END_REF] that coined the term Attribute Based Encryption, and the subsequent, natural unification of all these primitives under the umbrella of Functional Encryption took place only relatively recently [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF][START_REF] O'neill | Definitional issues in functional encryption[END_REF]. Constructions of public index FE have matured from specialized -equality testing [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF][START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], keyword search [START_REF] Boneh | Public key encryption with keyword search[END_REF][START_REF] Abdalla | Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions[END_REF][START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF], boolean formulae [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF], inner product predicates [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF], regular languages [START_REF] Waters | Functional encryption for regular languages[END_REF] -to general polynomial-size circuits [START_REF] Garg | Attribute-based encryption for circuits from multilinear maps[END_REF][START_REF] Gorbunov | Attribute-based encryption for circuits[END_REF][START_REF] Boneh | Fully key-homomorphic encryption, arithmetic ABE and compact garbled circuits[END_REF] and even Turing machines [START_REF] Goldwasser | How to run Turing machines on encrypted data[END_REF]. The journey of private index FE has been significantly more difficult, with inner product predicate constructions [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF][START_REF] Agrawal | Functional encryption for inner product predicates from learning with errors[END_REF] being the state of the art for a long time until the recent elegant generalization to polynomial-size circuits [START_REF] Gorbunov | Predicate encryption for circuits from LWE[END_REF].

However, although private index FE comes closer than ever before to the goal of general FE, it falls frustratingly short. This is because all known constructions of private index FE only achieve weak attribute hiding, which severely restricts the function keys that the adversary can request in the security game -the adversary may request keys for functions f i that do not decrypt the challenge ciphertext (IND * , M * ), i.e., f i (IND * ) = 0 holds for all i. The most general notion of FE -private index, strongly attribute hiding -has been built for the restricted case of bounded collusions [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF][START_REF] Goldwasser | Reusable garbled circuits and succinct functional encryption[END_REF] or using the brilliant, but ill-understood3 machinery of multi-linear maps [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] and indistinguishability obfuscation [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF]. These constructions provide FE for general polynomial-size circuits and Turing machines [START_REF] Goldwasser | How to run Turing machines on encrypted data[END_REF], but, perhaps surprisingly, there has been little effort to build the general notion of FE ground-up, starting from smaller functionalities.

This appears as a gaping hole that begs to be filled. Often, from the practical standpoint, efficient constructions for a smaller range of functionalities, such as linear functions or polynomials, are extremely relevant, and such an endeavour will also help us understand the fundamental barriers that thwart our attempts for general FE. This motivates the question:

Can we build FE for restricted classes of functions, satisfying standard security definitions, under well-understood assumptions?

In 2015, Abdalla, Bourse, De Caro and Pointcheval [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] considered the question of building FE for linear functions. Here, a ciphertext C encrypts a vector y ∈ D over some ring D, a secret key for the vector x ∈ D allows computing x, y and nothing else about y. Note that this is quite different from the inner product predicate functionality of [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF][START_REF] Agrawal | Functional encryption for inner product predicates from learning with errors[END_REF]: the former computes the actual value of the inner product while the latter tests whether the inner product is zero or not, and reveals a hidden bit M if so. Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] showed, surprisingly, that this functionality allows for very simple and efficient realizations under standard assumptions like the Decision Diffie-Hellman (DDH) and Learning-with-Errors (LWE) assumptions [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. The instantiation from DDH was especially unexpected since DDH is not known to easily lend itself to the design of such primitives. 4What enables this surprising result is that the functionality itself is rather limited -note that with queries, the adversary can reconstruct the entire message vector. Due to this, the scheme need not provide collusion resistance, which posits that no collection of secret keys for functions F 1 , . . . , F q should make it possible to decrypt a ciphertext that no individual such key can decrypt. Collusion resistance is usually the chief obstacle in proving security of FE schemes. On the contrary, for linear FE constructions, if two adversaries combine their keys, they do get a valid new key, but this key gives them a plaintext which could anyway be computed by their individual plaintexts. Hence, collusion is permitted by the functionality itself, and constructions can be much simpler. As we shall see below, linear FE is already very useful and yields many interesting applications, as we discuss in Appendix B.

More recently, Bishop, Jain and Kowalczyk [START_REF] Bishop | Function-hiding inner product encryption[END_REF] considered the same functionality as Abdalla et al. in the secret-key setting with the motivation of achieving function privacy.

While [START_REF] Bishop | Function-hiding inner product encryption[END_REF] considers adaptive adversaries, their construction requires bilinear maps and does not operate over standard DDH-hard groups. In the public-key setting, Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] only proved their schemes to be secure against selective adversaries, that have to declare the challenge messages M 0 , M 1 of the semantic security game upfront, before seeing the master public key mpk. Selective security is usually too weak a notion for practical applications and is often seen as a stepping stone to proving full adaptive security. Historically, most flavors of functional encryption have been first realized for selective adversaries [START_REF] Boneh | Efficient selective-id secure identity-based encryption without random oracles[END_REF][START_REF] Sahai | Fuzzy identity-based encryption[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF][START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF][START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] before being upgraded to attain full security. Boneh and Boyen [START_REF] Boneh | Efficient selective identity-based encryption without random oracles[END_REF] observed that a standard complexity leveraging argument can be used to argue that a selectively-secure system is also adaptively secure. However, this argument is not satisfactory in general as the reduction incurs an exponential security loss in the message length. Quite recently, Ananth, Brakerski, Segev and Vaikuntanathan [START_REF] Ananth | The trojan method in functional encryption: From selective to adaptive security, generically[END_REF] described a generic method of building adaptively secure functional encryption systems from selectively secure ones. However their transformation is based on the existence of a sufficiently expressive selectively secure FE scheme, where sufficiently expressive roughly means capable of evaluating a weak PRF. Since no such scheme from standard assumptions is known, their transformation does not apply to our case, and in any case would significantly increase the complexity of the construction, even if it did.

Our Results. In this paper, we describe fully secure functional encryption systems for the evaluation of inner products on encrypted data. We propose schemes that evaluate inner products of integer vectors, based on DDH, LWE and the Composite Residuosity hardness assumptions. Our DDH-based and LWEbased constructions for integer inner products are of efficiency comparable to those of Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] and rely on the same standard assumptions. Note that a system based on Paillier's composite residuosity assumption was an open problem even for the case of selective adversaries, which we resolve in this work.

Additionally, we propose schemes that evaluate inner products modulo a prime p or a composite N = pq, based on the LWE and Composite Residuosity hardness assumptions. In contrast, the constructions of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] must restrict the ring D to the ring of integers, which is a significant drawback. Indeed, although their DDH-based realization allows evaluating x, y mod p when the latter value is sufficiently small, their security proof restricts the functionality to the computation of x, y ∈ Z.

The functionality of inner products over a prime field is powerful: we show that it can be bootstrapped all the way to yield a conceptually simple construction for bounded collusion FE for all circuits. The only known construction for general FE handling bounded collusions is by Gorbunov, Vaikuntanathan and Wee [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]. Our construction is conceptually simpler, albeit a bit more inefficient. Also, since it requires the inner product functionality over a prime field, it can only be instantiated with our LWE-based scheme for now.

Overview of techniques

We briefly summarize our techniques below.

Fully secure linear FE: hash proof systems. Our DDH-based construction and its security proof implicitly build on hash proof systems [START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF]. It involves public parameters comprised of group elements g, h, {h i = g si • h ti } i=1 , where g, h generate a cyclic group G of prime order q, and the master secret key is msk = (s, t) ∈ Z q ×Z q . On input of a vector y = (y 1 , . . . , y ) ∈ Z q , the encryption algorithm computes (g r , h r , {g yi • h r i } i=1 ) in such a way that a secret key of the form SK x = ( s, x , t, x ) allows computing g y,x in the same way as in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF]. Despite its simplicity and its efficiency (only one more group element than in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] is needed in the ciphertext), we show that the above system can be proved fully secure using arguments -akin to those of Cramer and Shoup [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF] -which consider what the adversary knows about the master secret key (s, t) ∈ Z q × Z q in the information theoretic sense. The security proof is arguably simpler than its counterpart in the selective case [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF]. As in all security proofs based on hash proof systems, it uses the fact that the secret key is known to the reduction at any time, which makes it simpler to handle secret key queries without knowing the adversary's target messages y 0 , y 1 ∈ Z q in advance.

While our DDH-based realization only enables efficient decryption when the inner product x, y is contained in a sufficiently small interval, we show how to eliminate this restriction using Paillier's cryptosystem in the same way as in [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF][START_REF] Bresson | A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications[END_REF]. We thus obtain the first solution based on the Composite Residuosity assumption, which was previously an open problem (even in the case of selective security).

LWE-based fully secure linear FE. Our LWE-based construction builds on the dual Regev encryption scheme from Gentry, Peikert and Vaikuntanathan [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. Its security analysis requires more work. The master public key contains a random matrix A ∈ Z m×n q . For simplicity, we restrict ourselves to plaintext vectors and secret key vectors with binary coordinates. Each vector coordinate i ∈ {1, . . . , } requires a master public key component u T i = z T i • A ∈ Z n q , for a small norm vector z i ∈ Z m made of Gaussian entries which will be part of the master secret key msk = {z i } i=1 . Each {u i } i=1 can be seen as a syndrome in the GPV trapdoor function for which vector z i is a pre-image. Our security analysis will rely on the fact that each GPV syndrome has a large number of pre-images and, conditionally on u i ∈ Z n q , each z i retains a large amount of entropy. In the security proof, this will allow us to apply arguments similar to those of hash proof systems [START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF] when we will generate the challenge ciphertext using {z i } i=1 . More precisely, when the first part c 0 ∈ Z m q of the ciphertext is a random vector instead of an actual LWE sample c 0 = A • s + e 0 , the action of {z i } i=1 on c 0 ∈ Z m q produces vectors that appear statistically uniform to any legitimate adversary. In order to properly simulate the challenge ciphertext using the master secret key {z i } i=1 , we use a variant of the extended LWE assumption [START_REF] O'neill | Bi-deniable public-key encryption[END_REF] (eLWE) so as to have the (hint) values { z i , e 0 } i=1 at disposal. One difficulty is that the reductions from LWE to eLWE proved in [START_REF] Alperin-Sheriff | Circular and KDM security for identity-based encryption[END_REF] and [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] handle a single hint vector z. Fortunately, we extend the techniques of Brakerski et al. [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] using the gadget matrix from [START_REF] Ling | Hardness of k-LWE and Applications in Traitor Tracing[END_REF] to obtain a reduction from LWE to the multi-hint variant of eLWE that we use in the security proof. More specifically, we prove that the multi-hint variant of eLWE remains at least as hard as LWE when the adversary obtains as many as n/2 hints, where n is the dimension of the LWE secret.

Evaluation inner products modulo p. Our construction from the DDH assumption natively supports the computation of inner products modulo a prime p as long as the remainder x, y mod p falls in a polynomial-size interval. Under the Paillier and LWE assumptions, we first show how to compute integer inner products x, y ∈ Z. In a second step, we upgrade our Paillier and LWEbased systems so as to compute inner products modulo a composite N = pq and a prime p, respectively, without leaking the actual value x, y over Z.

Hiding anything but the remainder modulo N or p requires additional techniques. In the context of LWE-based FE, this is achieved by using an LWE modulus of the form q = p • p and multiplying plaintexts by p , so that an inner product modulo q over the ciphertext space natively translates into an inner product modulo p for the underlying plaintexts.

The latter plaintext/ciphertext manipulations do not solve another difficulty which arises from the discrepancy between the base rings of the master key and the secret key vectors: indeed, the master key consists of integer vectors, whereas the secret keys are defined modulo an integer. When the adversary queries a secret key vector x ∈ Z p (or Z N ), it gets the corresponding combination modulo p of the master key components. By making appropriate vector queries that are linearly dependent modulo p (and hence valid), an attacker could learn a combination of the master key components which is singular modulo p but invertible over the field of rational numbers: it would then obtain the whole master key! However, note that as long as the adversary only queries secret keys for -1 independent vectors over Z p (or Z N ), there is no reason not to reveal more than -1 secret keys overall. In order to make sure that the adversary only obtains redundant information by making more than -1 queries, we assume that a trusted authority keeps track of all vectors x for which secret keys were previously given out (more formally, the key generation algorithm is stateful).

Compiling Linear FE to Bounded Collusion General FE. We provide a conceptually simpler way to build q-query Functional Encryption for all circuits. The only known construction for this functionality was suggested by Gorbunov et al. in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]. At a high level, the q-query construction by Gorbunov et al. is built in several layers, as follows:

1. They start with a single key FE scheme for all circuits, which was provided by [START_REF] Sahai | Worry-free encryption: Functional encryption with public keys[END_REF]. 2. The single FE scheme is compiled into a q-query scheme for NC 1 circuits. This is the most non-trivial part of the construction. They run N copies of the single key scheme, where N = O(q 4 ). To encrypt, they encrypt the views of some N -party MPC protocol computing some functionality related to C, à la "MPC in the head". For the MPC protocol, they use the BGW [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF] semi-honest MPC protocol without degree reduction and exploit the fact that this protocol is completely non-interactive when used to compute bounded degree functions. The key generator provides the decryptor with a subset of the single query FE keys, where the subsets are guaranteed to have small pairwise intersections. This subset of keys enables the decryptor to recover sufficiently many shares of C(x) which enables her to compute C(x) via polynomial interpolation. However, an attacker with q keys only learns a share x i in the clear if two subsets of keys intersect, and due to small pairwise intersections, this does not occur often enough for him learn sufficiently many shares of x, hence, by the guarantees of secret sharing, input x remains hidden. 3. Finally, they bootstrap the q-query FE for NC 1 to a q-query FE for all circuits using computational randomized encodings [START_REF] Applebaum | Computationally private randomizing polynomials and their applications[END_REF]. They must additionally use cover-free sets to ensure that fresh randomness is used for each randomized encoding.

Our construction replaces steps 1 and 2 with a inner product modulo p FE scheme, and then uses step 3 as in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]. Thus, the construction of single key FE in step 1 by Sahai and Seyalioglu, and the nontrivial "MPC in the head" of step 2 can both be replaced by the simple abstraction of an inner product FE scheme. For step 3, observe that the bootstrapping theorem of [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF] provides a method to bootstrap an FE for NC 1 that handles q queries to an FE for all polynomial-size circuits that is also secure against q queries. The bootstrapping relies on the result of Applebaum et al. [START_REF] Applebaum | Computationally private randomizing polynomials and their applications[END_REF]Theorem 4.11] which states that every polynomial time computable function f admits a perfectly correct computational randomized encoding of degree 3. In more detail, let C be a family of polynomial-size circuits. Let C ∈ C and let x be some input. Let C(x, R) be a randomized encoding of C that is computable by a constant depth circuit with respect to inputs x and R.

Then consider a new family of circuits G defined by:

G C,∆ (x, R 1 , . . . , R S ) = C x; ⊕ a∈∆ R a : C ∈ C, ∆ ⊆ [S] ,
for some sufficiently large S (quadratic in the number of queries q). As observed in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF], circuit G C,∆ (•, •) is computable by a constant degree polynomial (one for each output bit). Given an FE scheme for G, one may construct a scheme for C by having the decryptor first recover the output of G C,∆ (x, R 1 , . . . , R S ) and then applying the decoder for the randomized encoding to recover C(x). However, to support q queries the decryptor must compute q randomized encodings, each of which needs fresh randomness. This is handled by hardcoding S random elements in the ciphertext and using random subsets ∆ ⊆ [S] (which are cover-free with overwhelming probability) to compute fresh randomness ⊕ a∈∆ R a for every query. The authors then conclude that bounded query FE for NC 1 suffices to construct a bounded query FE scheme for all circuits.

We observe that the ingredient required to bootstrap is not FE for the entire circuit class NC 1 but rather only the particular circuit class G as described above. This circuit class, being computable by degree 3 polynomials, may be supported by a linear FE scheme, via linearization of the degree 3 polynomials! To illustrate, let us consider FE secure only for a single key. Then, the functionality that the initial FE must support is exactly the randomized encoding of [START_REF] Applebaum | Computationally private randomizing polynomials and their applications[END_REF], which, indeed, is in NC 0 . Now, to support q queries, we must ensure that each key uses a fresh piece of randomness, and this is provided using a cover-free set family S as in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF] -the key generator picks a random subset ∆ ⊆ [S] and sums up its elements to obtain i.i.d. randomness for the key being requested. To obtain a random element in this manner, addition over the integers does not suffice, we must take addition modulo p. Here, our inner product modulo p construction comes to our rescue! Putting it together, the encryptor encrypts all degree 3 monomials in the inputs R 1 , . . . , R S and x 1 , . . . , x . Note that this ciphertext is polynomial in size. Now, for a given circuit C, the keygen algorithm samples some ∆ ⊆ [S] and computes the symbolic degree 3 polynomials which must be released to the decryptor. It then provides the linear FE keys to compute the same. By correctness and security of Linear FE as well as the randomizing polynomial construction, the decryptor learns C(x) and nothing else. The final notion of security that we obtain is non-adaptive simulation based security NA-SIM [START_REF] O'neill | Definitional issues in functional encryption[END_REF][START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF], i.e. (poly, poly, 0) SIM security, where the adversary can request a polynomial number of pre-challenge keys, ask for polynomially sized challenge ciphertexts but may not request post-challenge keys. For more details, we refer the reader to Section 6. We note that the construction of [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF] also achieves the stronger AD-SIM security, but for a scheme that supports only a single ciphertext and bounded number of keys. The bound on the number of ciphertexts is necessary due to a lower bound by [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF]. The notion of single ciphertext, bounded key FE appears to be quite restrictive, hence we do not study AD-SIM security here.

We note that subsequent to our work, Agrawal and Rosen [START_REF] Agrawal | Online-offline functional encryption for bounded collusions[END_REF] used our adaptively secure mod p inner products FE scheme in a more sophisticated manner than we do here, to achieve ciphertext size that improves upon the construction of [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF].

Background

In this section, we recall the hardness assumptions underlying the security of the schemes we will describe. The functionality and security definitions of functional and non-interactive controlled functional encryption schemes are given in Appendix A.

Our first scheme relies on the standard DDH assumption in ordinary (i.e., non-pairing-friendly) cyclic groups.

Definition 1. In a cyclic group G of prime order q, the Decision Diffie-Hellman (DDH) problem is to distinguish the distributions

D 0 = {(g, g a , g b , g ab ) | g ← G, a, b ← Z q }, D 1 = {(g, g a , g b , g c ) | g ← G, a, b, c ← Z q }.
A variant of our first scheme relies on Paillier's composite residuosity assumption.

Definition 2 ([50]

). Let N = pq, for prime numbers p, q. The Decision Composite Residuosity (DCR) problem is to distinguish the distributions

D 0 := {z = z N 0 mod N 2 | z 0 ← Z * N } and D 1 := {z ← Z * N 2 }.
Our third construction builds on the Learning-With-Errors (LWE) problem, which is known to be at least as hard as certain standard lattice problems in the worst case [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]. Definition 3. Let q, α, m be functions of a parameter n. For a secret s ∈ Z n q , the distribution A q,α,s over Z n q × Z q is obtained by sampling a ← Z n q and an e ← D Z,αq , and returning (a, a, s + e) ∈ Z n+1 q . The Learning With Errors problem LWE q,α,m is as follows: For s ← Z n q , the goal is to distinguish between the distributions:

D 0 (s) := U (Z m×(n+1) q ) and D 1 (s) := (A q,α,s ) m .
We say that a PPT algorithm A solves LWE q,α if it distinguishes D 0 (s) and D 1 (s) with non-negligible advantage (over the random coins of A and the randomness of the samples), with non-negligible probability over the randomness of s.

3 Fully secure functional encryption for inner products from DDH

In this section, we show that an adaptation of the DDH-based construction of Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] provides full security under the standard DDH assumption. Like [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], the scheme computes inner products over Z as long as they land in a sufficiently small interval.

In comparison with the solution of Abdalla et al., we only introduce one more group element in the ciphertext and all operations are just as efficient as in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF]. Our scheme is obtained by modifying [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] in the same way as Damgård's encryption scheme [START_REF] Damgård | Towards practical public key systems secure against chosen ciphertext attacks[END_REF] was obtained from the Elgamal cryptosystem. The original DDH-based system of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] encrypts a vector y = (y 1 , . . . , y ) ∈ Z q by computing (g r , {g yi • h r i } i=1 ), where {h i = g si } i=1 are part of the master public key and sk x = i=1 s i • x i mod q is the secret key associated with the vector x = (x 1 , . . . , x ) ∈ Z q . Here, we encrypt y in the fashion of Damgård's Elgamal, by computing (g r , h r , {g yi • h r i } i=1 ). The decryption algorithm uses secret keys of the form sk x = ( i=1 s i • x i , i=1 t i • x i ), where h i = g si • h ti for each i and s = (s 1 , . . . , s ) ∈ Z q and t = (t 1 , . . . , t ) ∈ Z q are part of the master key msk.

The scheme and its security proof also build on ideas from the Cramer-Shoup cryptosystem [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF][START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF]. Analogously to the bounded-collusion-resistant IBE schemes of Goldwasser et al. [START_REF] Goldwasser | Bounded-collusion IBE from key homomorphism[END_REF], the construction can be seen as an applying a hash proof system [START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF] with homomorphic properties over the key space. It also bears similarities with the broadcast encryption system of Dodis and Fazio [START_REF] Dodis | Public key trace and revoke scheme secure against adaptive chosen ciphertext attack[END_REF] in the way to use hash proof systems to achieve adaptive security.

Setup(1 λ , 1 ): Choose a cyclic group G of prime order q > 2 λ with generators g, h ← G. Then, for each i ∈ {1, . . . , }, sample s i , t i ← Z q and compute h i = g si • h ti . Define msk := {(s i , t i )} i=1 and mpk := G, g, h, {h i } i=1 .
Keygen(msk, x): To generate a key for the vector

x = (x 1 , . . . , x ) ∈ Z q , compute sk x = (s x , t x ) = ( i=1 s i • x i , i=1 t i • x i ) = ( s, x , t, x
). Encrypt(mpk, y): To encrypt a vector y = (y 1 , . . . , y ) ∈ Z q , sample r ← Z q and compute

C = g r , D = h r , {E i = g yi • h r i } i=1 . Return C y = (C, D, E 1 , . . . , E ). Decrypt(mpk, sk x , C y ): Given sk x = (s x , t x ), compute E x = ( i=1 E xi i )/(C sx • D tx ).
Then, compute and output log g (E x ).

The decryption algorithm requires to compute a discrete logarithm. This is in general too expensive. Like in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], this can be circumvented by imposing that the computed inner product lies in an interval {0, . . . , L}, for some polynomially bounded integer L. Then, computing the required discrete logarithm may be performed in time O(L 1/2 ) using Pollard's kangaroo method [START_REF] Pollard | Kangaroos, monopoly and discrete logarithms[END_REF]. As reported in [START_REF] Bernstein | Computing small discrete logarithms faster[END_REF], this can be reduced to O(L 1/3 ) operations by precomputing a table of size O(L 1/3 ). Note that even though the functionality is limited (decryption may not be performed efficiently for all key vectors and for all message vectors), while proving security we will let the adversary query any key vector in Z q .

Before proceeding with the security proof, we would like to clarify that, although the scheme of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] only decrypts values in a polynomial-size space, the usual complexity leveraging argument does not prove it fully secure via a polynomial reduction. Indeed, when is polynomial in λ, having the inner product y, x in a small interval does not mean that original vector y ∈ Z q lives in a polynomial-size universe. In Section 5, we show how to eliminate the small-interval restriction using Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF].

The security analysis uses similar arguments to those of Cramer and Shoup [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF][START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF] in that it exploits the fact that mpk does not reveal too much information about the master secret key. At some step, the challenge ciphertext is generated using msk instead of the public key and, as long as msk retains a sufficient amount of entropy from the adversary's view, it will perfectly hide which vector among y 0 , y 1 is actually encrypted. The reason why we can prove adaptive security is the fact that, as usual in security proofs relying on hash proof systems [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF][START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF], the reduction knows the master secret key at any time. It can thus correctly answer all secret key queries without knowing the challenge messages y 0 , y 1 beforehand.

The DDH-based scheme can easily be generalized so as to rely on weaker variants of DDH, like the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF] or the Matrix DDH assumption [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF].

Theorem 1. The scheme provides full security under the DDH assumption. (The proof is given in Appendix E).

Full security under the LWE assumption

We describe two LWE-based schemes: the first one for integer inner products of short integer vectors, the second one for inner products over a prime field Z p .

In both cases, the security relies on the hardness of a variant of the extended-LWE problem. The extended-LWE problem introduced by O'Neill, Peikert and Waters [START_REF] O'neill | Bi-deniable public-key encryption[END_REF] and further investigated in [START_REF] Alperin-Sheriff | Circular and KDM security for identity-based encryption[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]. At a high level, the extended-LWE problem can be seen as LWE α,q with a fixed number m of samples, for which some extra information on the LWE noises is provided: the adversary is provided a given linear combination of the noise terms. More concretely, the problem is to distinguish between the distributions

A, A • s + e, z, e, z
and A, u, z, e, z ,

where A ← Z m×n q , s ← Z n q , u ← Z m q , e ← D m Z,αq
, and z is sampled from a specified distribution. Note that in [START_REF] O'neill | Bi-deniable public-key encryption[END_REF], a noise was added to the term e, z . The LWE to extended-LWE reductions from [START_REF] Alperin-Sheriff | Circular and KDM security for identity-based encryption[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] do not require such an extra noise term.

We will use a variant of extended-LWE for which multiple hints (z i , e, z i ) are given, for the same noise vector e.

Definition 4 (Multi-hint extended-LWE). Let q, m, t be integers, α be a real and τ be a distribution over Z t×m , all of them functions of a parameter n. The multi-hint extended-LWE problem mheLWE q,α,m,t,τ is to distinguish between the distributions of the tuples

A, A • s + e, Z, Z • e and A, u, Z, Z • e , where A ← Z m×n q , s ← Z n q , u ← Z m q , e ← D m
Z,αq , and Z ← τ . A reduction from LWE to mheLWE is presented in Subsection 4.3.

Integer inner products of short integer vectors

In the description hereunder, we consider the message space P = {0, . . . , P -1} , for some integer P and where ∈ poly(n) denotes the dimension of vectors to encrypt. Secret keys are associated with vectors in V = {0, . . . , V -1} for some integer V . As in the DDH case, inner products are evaluated over Z. However, unlike our DDH-based construction, we can efficiently decrypt without confining inner product values within a small interval: here the inner product between the plaintext and key vectors belongs to {0, . . . , K -1} with K = P V , and it is possible to set parameters so that the scheme is secure under standard hardness assumptions while K is more than polynomial in the security parameter. We compute ciphertexts using a prime modulus q, with q significantly larger than K.

Setup(1 n , 1 , P, V ): Set integers m, q ≥ 2, real α ∈ (0, 1) and distribution τ over Z ×m as explained below. Set

K = P V . Sample A ← Z m×n q and Z ← τ . Compute U = Z • A ∈ Z ×n q
. Define mpk := (A, U, K, P, V ) and msk := Z. Keygen(msk, x): Given a vector x ∈ V, compute and return the secret key z x := x T • Z ∈ Z m . Encrypt(mpk, y): To encrypt a vector y ∈ P, sample s ← Z n q , e 0 ← D m Z,αq and e 1 ← D Z,αq and compute

c 0 = A • s + e 0 ∈ Z m q , c 1 = U • s + e 1 + q K • y ∈ Z q .
Then, return C := (c 0 , c 1 ). Decrypt(mpk, x, z x , C): Given a ciphertext C := (c 0 , c 1 ) and a secret key z x for x ∈ V, compute µ = x, c 1 -z x , c 0 mod q and output the value

µ ∈ {-K + 1, . . . , K -1} that minimizes | q K • µ -µ |.
Setting the parameters. Let B τ be such that with probability ≥ 1 -n -ω (1) , each row of sample from τ has norm ≤ B τ . As explained just below, correctness may be ensured by setting

α -1 ≥ K 2 B τ ω( log n) and q ≥ α -1 ω( log n).
The choice of τ is driven by the reduction from LWE to mheLWE (as summarized in Theorem 4), and more precisely from Lemma 4 (another constraint arises from the use of Lemma 10 at the end of the security proof). We

may choose τ = D ×m/2 Z,σ1 × (D Z m/2 ,σ2,δ1 × . . . × D Z m/2 ,σ2,δ )
, where δ i ∈ Z denotes the ith canonical vector, and the standard deviation parameters satisfy

σ 1 = Θ( √ n log m max( √ m, K)) and σ 2 = Θ(n 7/2 m 1/2 max(m, K 2 ) log 5/2 m).
To ensure security based on LWE q,α ,m in dimension ≥ c • n for some c ∈ (0, 1) via Theorems 2 and 4 below, one may further impose that ≤ (1 -c) • n and m = Θ(n log q), to obtain α = Ω(α/(n 6 K log 2 q log 5/2 n)). Note that LWE q,α ,m enjoys reductions from lattice problems when q ≥ Ω( √ n/α ). Combining the security and correctness requirements, we may choose α = 1/((n log q) O(1) • K 2 ) and q = Ω( √ n/α ), resulting in LWE parameters that make LWE resist all known attacks running in time 2 λ , as long as n ≥ Ω(λ log K).

Decryption correctness. To show the correctness of the scheme, we first observe that, modulo q:

µ = x, c 1 -z x , c 0 = q/K • x, y + x, e 1 -z x , e 0 .
Below, we show that the magnitude of the term x, e 1) . Thanks to the choices of α and q, the latter upper bound is ≤ q/K /4, which suffices to guarantee decryption correctness.

1 -z x , e 0 is ≤ V B τ αqω( √ log n) with probability ≥ 1 -n -ω(
Note that e 1 is an integer Gaussian vector of dimension and standard deviation αq ≥ ω( √ log n), and that x ≤ √ V . As a result, we have 1) . Similarly, as z x ≤ V B τ , we obtain that | z x , e 0 | ≤ V B τ αqω( √ log n) holds with probability 1 -n -ω (1) .

that | x, e 1 | ≤ √ V αqω( √ log n) holds with probability 1 -n -ω(
Full security. In order to prove adaptive security of the scheme, we use the multi-hint extended-LWE from Definition 4. Before we provide the formal proof, we provide some intuition.

Intuition. Here we describe some challenges in proving adaptive security for our LWE construction. To begin we describe the approach used by Abdalla et. al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] in showing selective security for a similar construction. In the selective game, the adversary must announce the challenge vectors y 0 , y 1 at the outset of the game. By definition of an admissible adversary, every query x i made must satisfy the property that x i , (y 0 -y 1 ) = 0 (over Z) for all i. For ease of exposition, consider challenge messages y 0 , y 1 that only differ in the last co-ordinate. Then, the simulator knows at the very beginning of the game, the subspace within which all queries must lie. Since the secret key is structured as (x i ) T Z, it suffices for the simulator to pick all but the final column of Z in order to answer all legitimate key requests. It can set the public parameters by constructing all except one row of U using its choice of Z, and receiving the final u from the LWE oracle. Now the challenge ciphertext can be embedded along this dimension to argue security.

In the adaptive game however, the simulator cannot know in advance which subspace the adversary's queries will lie in, hence it must pick the entire master secret key Z to answer key requests. Given that the simulator has no secrets, it is unclear how it may leverage the adversary. To handle this, our approach is to carefully analyze the entropy loss that occurs in the master secret Z via that keys seen by the adversary. We show that despite seeing linear relations involving Z, there is enough residual entropy left in the master secret so that the challenge ciphertext created using this appears uniform to the adversary.

To the best of our knowledge, this proof technique has not been used in prior constructions of LWE based FE systems, which mostly rely on a "punctured trapdoor" approach. This approach roughly provides the simulator with a trapdoor that can be used to answer key requests but vanishes w.h.p for the challenge. Our simulator does not use trapdoors, but relies on an argument about entropy leakage as described above. We now proceed with the formal proof.

Theorem 2. Assume that ≤ n O (1) , m ≥ 4n log 2 q, q > K 2 and τ is as described above. Then the functional encryption scheme above is fully secure, under the mheLWE q,α,m, ,τ hardness assumption.

Proof. The proof proceeds with a sequence of games that starts with the real game and ends with a game in which the adversary's advantage is negligible. For each i, we call S i the event that the adversary wins in Game i.

Game 0: This is the genuine full security game. Namely: the adversary A is given the master public key mpk; in the challenge phase, adversary A comes up with two distinct vectors y 0 , y 1 ∈ P and receives an encryption C of y β for β ← {0, 1} sampled by the challenger; when A halts, it outputs β ∈ {0, 1} and S 0 is the event that β = β. Note that any vector x ∈ V queried by A to the secret key extraction oracle must satisfy x, y 0 = x, y 1 over Z if A is a legitimate adversary.

Game 1: We modify the generation of C = (c 0 , c 1 ) in the challenge phase. Namely, at the outset of the game, the challenger picks s ← Z n q , e 0 ← D m Z,αq (which may be chosen ahead of time) as well as Z ← τ . The master public key mpk is computed by setting U = Z • A mod q. In the challenge phase, the challenger picks a random bit β ← {0, 1} and encrypts y β by computing (modulo q)

c 0 = A • s + e 0 , c 1 = Z • c 0 -Z • e 0 + e 1 + q/K • y β ,
with e 1 ← D Z,αq . As the distribution of C is the same as in Game 0, we have

Pr[S 1 ] = Pr[S 0 ].
Game 2: We modify again the generation of C = (c 0 , c 1 ) in the challenge phase. Namely, the challenger picks u ← Z m q , sets c 0 = u and computes c 1 using c 0 , Z and e 0 as in Game 1.

Under the mheLWE hardness assumption with t = , this modification has no noticeable effect on the behavior of A. Below, we prove that Pr[S 2 ] ≈ 1/2, which completes the proof of the theorem. Let x i ∈ V be the vectors corresponding to the secret key queries made by A. As A is a legitimate adversary, we have x i , y 0 = x i , y 1 over Z for each secret key query x i . Let g = 0 be the gcd of the coefficients of y 1 -y 0 and define y = (y 1 , . . . , y ) = 1 g (y 1 -y 0 ). We have that x i , y = 0 (over Z) for all i. Consider the lattice {x ∈ Z : x, y = 0}: all the queries x i must belong to that lattice. Without loss of generality, we assume the n 0 first entries of y are zero (for some n 0 ), and all remaining entries are non-zero. Further, the rows of the following matrix form a basis of a full-dimensional sublattice:

X top =        I n0 -y n0+2 y n0+1 -y n0+3 y n0+2 . . . . . . -y y -1        ∈ Z ( -1)× . (4.1)
We may assume that through the secret key queries, the adversary learns exactly X top Z, as all the queried vectors x i can be obtained as rational combinations of the rows of X top .

Let X bot = y T ∈ Z 1× . Consider the matrix X ∈ Z × q obtained by putting X top on top of X bot . We claim that X is invertible modulo q. To see this, observe that

XX T =           I n0 y 2 n0+1 + y 2 n0+2 -y n0+1 • y n0+3 -y n0+1 • y n0+3 y 2 n0+2 + y 2 n0+3 . . . . . . . . . . . . -y -2 • y y 2 -1 + y 2 y 2          
It can be proved by induction that its determinant is

det(XX T ) = ( -1 k=n0+2 y 2 k ) • y 4 .
As each of the y k 's is small and non-zero, they are all non-zero modulo prime q.

Similarly, the integer ( k=n0+1 y 2 k ) is non-zero and < P 2 < q. This shows that (det X) 2 = 0 mod q, which implies that X is invertible modulo q.

In Game 2, we have c 1 = Z(ue 0 ) + e 1 + q/K • y β . We write:

c 1 = X -1 • X • (Z(u -e 0 ) + e 1 + q/K • y β ) mod q.
We will show that the distribution of X • c 1 mod q is (almost) independent of β. As X is (almost) independent of β and invertible over Z q , this implies that the distribution of c 1 is (almost) independent of β and Pr[S 2 ] ≈ 1/2.

The first -1 entries of X • c 1 do not depend on β because, by construction of X top , we have X top • y 0 = X top • y 1 mod q.

It remains to prove that the last entry of X • c 1 mod q is (almost) independent of β. For this, we show that the residual distribution of X bot Z given the tuple (A, ZA, X top , X top Z) has high min-entropy. Using (a variant of) the leftover hash lemma with randomness X bot Z and seed ue 0 , we will then conclude that given (A, ZA, X top , X top Z), the pair (u -e 0 , X bot Z(ue 0 )) is close to uniform. Hence the pair (u, X bot Z(ue 0 )) statistically hides q/K • y β in c 1 .

Write A = (A T 1 |A T 2 ) T with A 1 , A 2 ∈ Z (m/2)×n q . Similarly, write Z = (Z 1 |Z 2 ) with Z 1 , Z 2 ∈ Z ×(m/2) q
. Recall that by construction, every entry of Z 1 is independently sampled from a zero-centered integer Gaussian of standard deviation parameter

σ 1 = Θ( √ n log m max( √ m, K)).
Further, every entry of Z 2 is independently sampled from a (not zero-centered) integer Gaussian of standard deviation parameter σ 2 that is larger than σ 1 .

Lemma 1. Conditioned on (A, ZA, X top , X top Z), the min-entropy of X bot Z is ≥ n log q + 2λ.
Proof. We first consider the distribution of X bot Z conditioned on (X top , X top Z). Note that in X top Z and X bot Z, matrices X top and X bot act in parallel on the columns of Z. We can hence restrict ourselves to the distribution of X bot z i conditioned on (X top , X top z i ), with z i sampled from D Z ,σi,ci (with

σ i ∈ {σ 1 , σ 2 } and c i ∈ {0, 1} ). Let b i = X top z i ∈ Z -1 and fix z i ∈ Z arbitrary such that b i = X top z i . The distribution of z i given (X top , X top z i ) is z i + D Λ,σi,ci-z i , with Λ = {x ∈ Z : X top x = 0}.
By construction of X, we have that Λ = Zy. As a result, the conditional distribution of X bot z i is y, z i + D y 2 Z, y σi, y,ci-z i .

As σ 1 and σ 2 are sufficiently large, we can apply Lemma 7. After conditioning with respect to (X top , X top Z), each entry of X bot Z has min-entropy ≥ log(4/3). As these are independent, we have that

H ∞ (X bot Z|X top , X top Z) ≥ m log(4/3).
Now, we aim at further conditioning with respect to (A, ZA). As X is invertible modulo q, conditioning with respect to (A, ZA) is the same as conditioning with respect to (A, XZA). In particular, we can omit the conditioning with respect to X top ZA, as we already know A and X top Z. As a result, conditioning with respect to (A, ZA) is the same as conditioning with respect to (A, X bot ZA).

Using the observation above, we obtain that the min-entropy of X bot Z conditioned on(A, ZA, X top , X top Z) is ≥ m log(4/3) -n log q. The result then follows from the parameter settings.

Thanks to Lemmas 1 and 11, given (A, ZA, X top , X top Z), the pair (ue 0 , X bot Z(u-e 0 )) is within statistical distance 2 -λ from the uniform distribution over Z m q × Z q . This completes the proof.

Inner products modulo a prime p

We now modify the LWE-based scheme above so that it enables secure functional encryption for inner products modulo prime p. The plaintext and key vectors now belong to Z p . Note that the prior scheme evaluates inner products over the integers and is insecure if ported as is to the modulo p setting. To see this, consider the following simple attack in which the adversary requests a single key x so that integer inner product with the challenge messages y 0 and y 1 are different by a multiple of p. Since the functionality posits that the inner product evaluations only agree modulo p, this is an admissible query. However, since decryption is performed over Z q with q much larger than p, the adversary can easily distinguish. To prevent this attack, we scale the encrypted message by a factor of q/p (instead of q/K as in the previous scheme): decryption modulo q forces arithmetic modulo p on the underlying plaintext.

A related difficulty in adapting the previous LWE-based scheme to modular inner products is the distribution of the noise component after inner product evaluation. Ciphertexts are manipulated modulo q, which internally manipulates plaintexts modulo p. If implemented naively, the carries of the plaintext computations may spill outside of the plaintext slots and bias the noise components of the ciphertexts. This may result in distinguishing attacks. To handle this, we take q a multiple of p. This adds some technical complications, as Z q is hence not a field anymore.

A different attack is that the adversary may request keys for vectors that are linearly dependent modulo p but linearly independent over the integers. Note that with such queries, the attacker can recover the master secret key. To prevent this attack, we modify the scheme in that the authority is now stateful and keeps a record of all key queries made so far, so that it can make sure that key queries that are linearly dependent modulo p remain so modulo q. We also take q a power of p to simplify the implementation of this idea.

We note that for our application to bounded query FE for all circuits, all queries will be linearly independent modulo p, hence we will not require a stateful keygen. For details, see Section 6.

We now describe our scheme for inner products modulo p.

Setup(1 n , 1 , p): Set integers m, q = p k for some integer k, real α ∈ (0, 1) and distribution τ over Z ×m as explained below. Sample A ← Z m×n q and Z ← τ . Compute U = Z • A ∈ Z ×n q . Define mpk := (A, U) and msk := Z. Keygen(msk, x, st): Given a vector x ∈ Z p , and an internal state st, compute the secret key z x as follows. Recall that Keygen is a stateful algorithm with empty initial State st. At any point in the scheme execution, State st contains at most tuples (x i , x i , z i ) where the x i 's are (a subset of the) key queries that have been made so far, and the (x i , z i )'s are the corresponding secret keys. If x is linearly independent from the x i 's modulo p,

set x = x ∈ Z (with coefficients in [0, p)), z x = x T • Z ∈ Z m and add (x, x, z x ) to st. If x = i k i x i mod p for some k i 's in [0, p), then set x = i k i x i ∈ Z and z x = i k i z i ∈ Z m .
In both cases, return (x, z x ). Encrypt(mpk, y): To encrypt a vector y ∈ Z p , sample s ← Z n q , e 0 ← D m Z,αq and e 1 ← D Z,αq and compute

c 0 = A • s + e 0 ∈ Z m q , c 1 = U • s + e 1 + p k-1 • y ∈ Z q .
Then, return C := (c 0 , c 1 ). Decrypt(mpk, (x, z x ), C): Given C := (c 0 , c 1 ) and a secret key (x, z x ) for x ∈ Z p , compute µ = x, c 1 -z x , c 0 mod q and output the value

µ ∈ Z p that minimizes |p k-1 • µ -µ |.
Decryption correctness. Correctness derives from the following observation:

µ = x, c 1 -z x , c 0 = p k-1 • ( x, y mod p) + x, e 1 -z x , e 0 mod q.
By adapting the proof of the first LWE-based scheme, we can show that the magnitude of the term x, e 1 -z x , e 0 is ≤ 2 p 2 B τ αqω( √ log n) with probability ≥ 1 -n -ω (1) . This follows from the bound z x ≤ x ≤ 2 p 2 B τ .

Setting the parameters. The main difference with the previous LWE-based scheme with respect to parameter conditions is the choice of q of the form q = p k instead of q prime. As explained just above, correctness may be ensured by setting

α -1 ≥ 2 p 3 B τ ω( log n) and q ≥ α -1 ω( log n).
The choice of τ is driven by Lemma 2 below (the proof requires that σ 1 is large) and the reduction from LWE to mheLWE (as summarized in Theorem 4), and more precisely from Lemma 4. We may choose τ = D ×m/2 Z,σ1

× (D Z m/2 ,σ2,δ1 × . . . × D Z m/2 ,σ2,δ )
, where δ i ∈ Z denotes the ith canonical vector, and the standard deviation parameters satisfy

σ 1 = Θ( √ n log m max( √ m, K )) and σ 2 = Θ(n 7/2 m 1/2 max(m, K 2 ) log 5/2 m), with K = ( √ p) .
To ensure security based on LWE q,α ,m in dimension ≥ c • n for some c ∈ (0, 1) via Theorems 2 and 4 below, one may further impose that ≤ (1 -c) • n and m = Θ(n log q), to obtain α = Ω(α/(n 6 K log 2 q log 5/2 n)). Remember that LWE q,α ,m enjoys reductions from lattice problems when q ≥ Ω( √ n/α ). Note that the parameter conditions make the scheme efficiency degrade quickly when increases, as K is exponential in . Assume that p ≤ n O(1) and = Ω(log n). Then σ 1 , σ 2 , 1/α, 1/α and q can all be set as 2 O( ) . To maintain security against all 2 o(λ) attacks, one may set n = Θ( λ).

Theorem 3. Assume that ≤ n O (1) , m ≥ 4n log 2 q and τ is as described above. Then the stateful functional encryption scheme above is fully secure, under the mheLWE q,α,m, ,τ hardness assumption.

Proof. The sequence of games in the proof of Theorem 2 can be adapted to the modified scheme. The main difficulty is to show that in the adapted version of the last game, the winning probability is close to 1/2. Let us recall that game in details.

Game 2 : At the outset of the game, the challenger picks s ← Z n q , e 0 ← D m Z,αq as well as Z ← τ . The master public key mpk is computed by setting U = Z•A mod q and is provided to the adversary. In the challenge phase, adversary A comes up with two distinct vectors y 0 , y 1 ∈ Z p . The challenger picks a random bit β ← {0, 1}, u ← Z m q and encrypts y β by computing (modulo q)

c 0 = u, c 1 = Z • c 0 -Z • e 0 + e 1 + p k-1 • y β ,
with e 1 ← D Z,αq . Note that any vector x ∈ Z p queried by A to the secret key extraction oracle must satisfy x, y 0 = x, y 1 mod p if A is a legitimate adversary. Adversary A is then given a secret key (x, z x ) as in the real scheme.

When A halts, it outputs β ∈ {0, 1} and wins in the event that β = β.

Define y = y 1 -y 0 ∈ Z p . Let x i ∈ Z p be the vectors corresponding to the secret key queries made by A. As A is a legitimate adversary, we have x i , y = 0 mod p for each secret key query x i .

We consider the view of the adversary after it has made exactly j key queries that are linearly independent modulo p, for each j from 0 up to -1. In fact, counter j may stop increasing before reaching -1, but without loss of generality, we may assume that it eventually reaches -1. We are to show by induction that for any j, the view of the adversary is almost independent of β. In particular, for all j < -1, this implies that the (j + 1)th linearly independent key query is almost (statistically) independent of β. It also implies, for j = -1, that the adversary's view through Game 2 is almost independent of β, which is exactly what we are aiming for. In what follows, we take j ∈ {0, . . . , -1}, and assume that state st is independent from β. We also assume that the jth private key query occurs after the challenge phase since the adversary's view is trivially independent of β before the generation of the challenge ciphertext.

At this stage, the state st contains exactly j tuples (x i , x i , z i ), where the vectors {x i } j i=1 form a Z p -basis of a subspace of the ( -1)-dimensional vector space y ⊥ := {x ∈ Z p : x, y = 0 mod p}. From y, we deterministically extend {x i } j i=1 into a basis of y ⊥ that is statistically independent of β. A way to interpret this is to imagine that the challenger makes dummy private key queries {x i } -1 i=j+1 for itself so as to get a full basis of y ⊥ and creates the corresponding {x i } -1 i=j+1 in Z . We define X top ∈ Z ( -1)× as the matrix whose ith row is x i for all i, including the genuine and dummy keys. Through the secret key queries, the adversary learns at most X top Z ∈ Z ( -1)×m .

Let x ∈ Z p be a vector that does not belong to y ⊥ , and X bot ∈ Z 1× be the canonical lift of (x ) T over the integers. Consider the matrix X ∈ Z × obtained by putting X top on top of X bot . By construction, the matrix X is invertible modulo p, and hence modulo q = p k . Also, by induction and construction, the matrix X ∈ Z × is statistically independent of β ∈ {0, 1}.

In Game 2 , we have c 1 = Z(ue 0 ) + e 1 + p k-1 • y β . We write:

c 1 = X -1 • X • Z(u -e 0 ) + e 1 + p k-1 • y β mod q.
We will show that the distribution of X • c 1 mod q is (almost) independent of β. As the matrix X is independent of β ∈ {0, 1} and invertible over Z q , this implies that the distribution of c 1 is statistically independent of β (recall that X is information-theoretically known to A, which means that, if c 1 carries any noticeable information on β, so does X • c 1 mod q). This ensures that the winning probability in Game 2 is negligibly far from 1/2. First, the first -1 entries of X • c 1 do not depend on β because we have the equality

p k-1 • X top • y 0 = p k-1 • X top • y 1 mod q, by construction of X top .
It remains to prove that the last entry of X • c 1 mod q is (almost) independent of β. The proof of the following lemma is adapted from that of Lemma 1.

Lemma 2. Conditioned on (A, ZA, X top , X top Z), the min-entropy of X bot Z mod p is ≥ n log q + 2λ.

Proof. We first consider the distribution of X bot Z conditioned on (X top , X top Z). Note that in X top Z and X bot Z, matrices X top and X bot act in parallel on the columns of Z. We can hence restrict ourselves to the distribution of X bot z i conditioned on (X top , X top z i ), with z i sampled from D Z ,σi,ci (with

σ i ∈ {σ 1 , σ 2 } and c i ∈ {0, 1} ). Let b i = X top z i ∈ Z -1 and fix z i ∈ Z arbitrary such that b i = X top z i . The distribution of z i given (X top , X top z i ) is z i + D Λ,σi,ci-z i , with Λ = {x ∈ Z : X top x = 0}. Note that Λ is a 1-dimensional lattice in Z .
We can write Λ = y • Z, for some y ∈ Z . Note that there exists α ∈ Z p \ {0} such that y = α • y mod p: otherwise, the vector y /p would belong to Λ \ y • Z, contradicting the definition of y . Further, we have y = det Λ ≤ det Λ , where Λ is the lattice spanned by the rows of X top (see, e.g., [START_REF] Nguyen | Merkle-Hellman revisited: A cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations[END_REF], for properties on orthogonal lattices). Hadamard's bound implies that y ≤ ( √ p) -1 . By Lemma 8, the fact that σ 1 , σ 2 ≥ √ n( √ p) implies that the distribution (D Λ,σi,-z i mod pΛ) is within 2 -Ω(n) statistical distance from the uniform distribution over Λ/pΛ yZ p . We conclude that the distribution of (X bot z i mod p) conditioned on (X top , X top Z) is within exponentially small statistical distance from the uniform distribution over Z p (here, we use the facts that p is prime and that X bot y = 0 mod p, by construction of X bot ). We hence have:

H ∞ (X bot Z|X top , X top Z) ≥ m log(4/3).
Now, we aim at further conditioning with respect to (A, ZA). As X is invertible modulo p and hence modulo q, conditioning with respect to (A, ZA) is the same as conditioning with respect to (A, XZA). As in the integer case, we deduce that conditioning with respect to (A, ZA) is the same as conditioning with respect to (A, X bot ZA). We obtain that the min-entropy of X bot Z mod p conditioned on(A, ZA, X top , X top Z) is ≥ m log(4/3) -n log q. The result then follows from the parameter settings.

Thanks to Lemmas 2 and 11, given (A, ZA, X top , X top Z), the pair (ue 0 , X bot Z(u-e 0 )) is within statistical distance 2 -λ from the uniform distribution over Z m q ×Z q . We then conclude that the pair (u, X bot Z(u-e 0 )) (as e 0 is known). This completes the security proof.

Hardness of multi-hint extended-LWE

In this section, we prove the following theorem, which shows that for some parameters, the mheLWE problem is no easier than the LWE problem. Theorem 4. Let n ≥ 100, q ≥ 2, t < n and m with m = Ω(n log n) and m ≤ n O (1) . There exists ξ ≤ O(n 4 m 2 log 5/2 n) and a distribution τ over Z t×m such that the following statements hold:

• There is a reduction from LWE q,α,m in dimension n -t to mheLWE q,αξ,m,t,τ that reduces the advantage by at most 2 Ω(t-n) , • It is possible to sample from τ in time polynomial in n,

• Each entry of matrix τ is an independent discrete Gaussian τ i,j = D Z,σi,j ,ci,j for some c i,j ∈ {0, 1} and σ i,j ≥ Ω( √ mn log m), rows of G, and let U ∈ Z m×(m-t) denote the matrix formed by the right m -t columns of U. By construction, we have ZU = 0. We define A = U • A mod q.

We sample f ← D αq(ξ 2 I-U U T ) 1/2 (thanks to Lemma 4 and the choice of ξ, the matrix ξ 2 I -U U T is positive definite). We sample e from {0} Finally, the reduction calls the mheLWE oracle on input (A , b + c, Z, h), and outputs the reply.

Correctness is obtained by showing that distribution A t q,{0},s × A m-t q,α,s is mapped to the mheLWE "LWE" distribution and that the uniform distribution is mapped to the mheLWE "uniform" distribution, up to 2 -Ω(n) statistical distances (we do not discuss these tiny statistical discrepancies below). The proof is identical to the reduction analysis in the proof of [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]Le. 4.7].

Theorem 4 is obtained by combining Lemmas 3, 4 and 5.

Constructions Based on Paillier

In this section, we show how to remove the main limitation of our DDH-based system which is its somewhat expensive decryption algorithm. To this end, we use Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] and the property that, for an RSA modulus N = pq, the multiplicative group Z * N 2 contains a subgroup of order N (generated by (N + 1)) in which the discrete logarithm problem is easy. We also rely on the observation [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF][START_REF] Bresson | A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications[END_REF] that combining the Paillier and Elgamal encryption schemes makes it possible to decrypt without knowing the factorization of N = pq.

Computing Inner Products over Z

In the following scheme, key vectors x and message vectors y are assumed to be of bounded norm x ∞ ≤ X and y ∞ ≤ Y , respectively. The bounds X and Y are chosen so that X • Y < N , where N is the composite modulus of Paillier's cryptosystem. Decryption allows to recover x, y mod N , which is exactly x, y over the integers, thanks to the norm bounds. We thus assume X, Y < (N/ ) 1/2 . Setup(1 λ , 1 , X, Y ): Choose safe prime numbers p = 2p + 1, q = 2q + 1 with sufficiently large primes p , q > 2 l(λ) , for some polynomial l (so that factoring is 2 λ -hard), and compute N = pq > XY . Then, sample g ← Z * N 2 and compute g = g 2N mod N 2 , which generates the subgroup of (2N )th residues in Z * N 2 with overwhelming probability. Then, sample an integer vector s = (s 1 , . . . , s ) T ← D Z ,σ with discrete Gaussian entries of standard deviation σ > √ λ • N 5/2 and compute h i = g si mod N 2 . Define

mpk := N, g, {h i } i=1 , Y
and msk := ({s i } i=1 , X). The prime numbers p, p , q, q are no longer needed.

Keygen(msk, x):

To generate a key for the vector x = (x 1 , . . . , x ) ∈ Z with x ≤ X, compute sk x = i=1 s i • x i over Z. Encrypt(mpk, y): To encrypt a vector y = (y 1 , . . . , y ) ∈ Z with y ≤ Y , sample r ← {0, . . . , N/4 } and compute

C 0 = g r mod N 2 , C i = (1 + y i N ) • h r i mod N 2 , ∀i ∈ {1, . . . , }. Return C y = (C 0 , C 1 , . . . , C ) ∈ Z +1 N 2 . Decrypt(mpk, sk x , C y ): Given sk x ∈ Z, compute C x = i=1 C xi i • C -skx 0 mod N 2 .
Then, compute and output log

(1+N ) (C x ) = Cx-1 mod N 2 N .
As in previous constructions (including those of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF]), our security proof requires inner products to be evaluated over Z, although the decryptor technically computes x, y mod N . The reason is that, since secret keys are computed over the integers, our security proof only goes through if the adversary is restricted to only obtain secret keys for vectors x such that x, y 0 = x, y 1 over Z. Theorem 5. The scheme provides full security under the DCR assumption. (The proof is available in Appendix F).

A Construction for Inner Products over Z N

Here, we show that our first scheme can be adapted in order to compute the inner product y, x mod N instead of computing it over Z. To do this, a first difficulty is that, as in our LWE-based system, private keys are computed over the integers and the adversary may query private keys for vectors that are linearly dependent over Z N but independent over Z . This problem is addressed as previously, by having the authority keep track of all previously revealed private keys. As in our LWE-based construction over Z p , we also need to increase the size of private keys (by a factor ≈ ) because we have to use a different information-theoretic argument in the last step of the security proof.

Specifically, in the proof of Theorem 5, we only had to consider the conditional distribution of s, y 0 -y 1 mod N , where y 0 , y 1 ∈ Z are the two adversariallychosen vectors and s ∈ Z is the master key. Here, we need to make sure that, conditionally on the adversary's view, reducing all coordinates the secret key s ∈ Z modulo N induces a statistically uniform distribution over Z N . One of the reasons is that we are no longer guaranteed that y 0 -y 1 , y 0 -y 1 = 0 mod N .

Setup(1 λ , 1 ): Choose safe prime numbers p = 2p +1, q = 2q +1 with sufficiently large primes p , q > 2 l(λ) , for some polynomial l, and compute N = pq.

Then, sample g ← Z * N 2 and compute g = g 2N mod N 2 , which generates the subgroup of (2N )th residues in Z * N 2 with overwhelming probability. Then, sample an integer vector s = (s 1 , . . . , s ) T ← D Z ,σ with discrete Gaussian entries of standard deviation σ > √ λ( √ N ) +1 and compute h i = g si mod N 2 . Define mpk := N, g, {h i } i=1 and msk := {s i } i=1 . Keygen(msk, x, st): To generate the jth secret key sk x for a vector x ∈ Z N using the master secret key msk and an (initially empty) internal state st, a stateful algorithm is used. At any time, st contains at most tuples (x i , x i , z xi ) where the (x i , z xi )'s are the previously revealed secret keys and the x i are the corresponding vectors.

-If x is linearly independent from the x i 's modulo

N , set x = x ∈ Z (with coefficients in [0, N )), z x = s, x ∈ Z and add (x, x, z x ) to st. -If x = i k i x i mod N for some coefficients {k i } i≤j-1 in Z N , then compute x = i k i • x i ∈ Z and z x = i k i • z xi ∈ Z m .
In either case, return sk x = (x, z x ). Encrypt(mpk, y): To encrypt a vector y = (y 1 , . . . , y ) ∈ Z N , sample r ← {0, . . . , N/4 } and compute

C 0 = g r mod N 2 , C i = (1 + y i N ) • h r i mod N 2 , ∀i ∈ {1, . . . , }. Return C y = (C 0 , C 1 , . . . , C ) ∈ Z +1 N 2 . Decrypt(mpk, sk x , C y ): Given sk x = (x, z x ) ∈ Z × Z with x = (x 1 , . . . , x ), compute C x = i=1 C xi i • C -zx 0 mod N 2 .
Then, compute and output log

(1+N ) (C x ) = Cx-1 mod N 2 N .
From a security standpoint, the following result is proved in Appendix G.

Theorem 6. The above stateful scheme provides full security under the DCR assumption.

Bootstrapping Linear FE to Efficient Bounded FE for all circuits

In this section, we describe how to compile our Linear FE scheme, denoted by LinFE which computes linear functions modulo p (for us p = 2), into a bounded collusion FE scheme for all circuits, denoted by BddFE. The underlying scheme LinFE is assumed to be AD-IND secure, which, by [START_REF] O'neill | Definitional issues in functional encryption[END_REF], is equivalent to non-adaptive simulation secure NA-SIM, since linear functions are "preimage sampleable". We refer the reader to [START_REF] O'neill | Definitional issues in functional encryption[END_REF] for more details.

Let C be a family of polynomial-size circuits. Let C ∈ C and let x be some input. Let C(x, R) be a randomized encoding of C that is computable by a constant depth circuit with respect to inputs x and R (see [START_REF] Applebaum | Computationally private randomizing polynomials and their applications[END_REF]). Then consider a new family of circuits G defined by:

G C,∆ (x, R 1 , . . . , R S ) = C x; ⊕ a∈∆ R a : C ∈ C, ∆ ⊆ [S] ,
for some S to be chosen below. As observed in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]Section 6], circuit G C,∆ (•, •) is computable by a constant degree polynomial (one for each output bit). Given an FE scheme for G, one may construct a scheme for C by having the decryptor first recover the output of G C,∆ (x, R 1 , . . . , R S ) and then applying the decoder for the randomized encoding to recover C(x).

Note that to support q queries the decryptor must compute q randomized encodings, each of which needs fresh randomness. As shown above, this is handled by hardcoding sufficiently many random elements in the ciphertext and taking a random subset sum of these to generate fresh random bits for each query. As in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF], the parameters are chosen so that the subsets form a cover-free system, so that every random subset yields fresh randomness (with overwhelming probability).

In more details, we let the set S, v, m be parameters to the construction. Let ∆ i for i ∈ [q] be a uniformly random subset of S of size v. To support q queries, we identify the set ∆ i ⊆ S with query i. If v = O(λ) and S = O(λ • q 2 ) then the sets ∆ i are cover-free with high probability. For details, we refer the reader to [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]Section 5]. We now proceed to describe our construction. Let L ( + S • m) 3 , where m ∈ poly(λ) is the size of the random input in the randomized encoding and is the length of the messages to be encrypted.

BddFE.Setup(1 λ , 1 ): Upon input the security parameter λ and the message space M = {0, 1} , invoke (mpk, msk) = LinFE.Setup(1 λ , 1 L ) and output it.

BddFE.KeyGen(msk, C): Upon input the master secret key and a circuit C, do: 1. Sample a uniformly random subset ∆ ⊆ S of size v.

2. Express C(x) by G C,∆ (x, R 1 , . . . , R S ), which in turn can be expressed as a sequence of degree 3 polynomials P 1 , . . . , P k , where k ∈ poly(λ). 3. Linearize each polynomial P i and let P i be its vector of coefficients. Note that the ordering of the coefficients can be arbitrary but should be public.

4. Output BddFE.SK C = {SK i = LinFE.KeyGen(LinFE.msk, P i )} i∈[k] .
BddFE.Enc(x, mpk): Upon input the public key and the plaintext x, do:

1. Sample R 1 , . . . , R S ← {0, 1} m .
2. Compute all symbolic monomials of degree 3 in the variables x 1 , . . . , x and R i,

j for i ∈ [S], j ∈ [m].
The number of such monomials is L = ( + S • m) 3 . Arrange them according to the public ordering and denote the resulting vector by y.

3. Output CT x = LinFE.Enc(LinFE.mpk, y). BddFE.Dec(mpk, CT x , SK C ): Upon input a ciphertext CT x for vector x, and a secret key

SK C = {SK i } i∈[k] for circuit C, do the following: 1. Compute G C,∆ (x, R 1 , . . . , R S ) = {P i (Y)} i∈[k] = {LinFE.Dec(CT x , SK i )} i∈[k] .
2. Run the decoder for the randomized encoding to recover C(x) from G C,∆ (x, R 1 , . . . , R S ).

Correctness follows from the correctness of LinFE and the correctness of randomized encodings.

Security. The definition for q-NA-SIM security is provided in Appendix A. We proceed to describe our simulator Bdd.Sim. Let RE.Sim be the simulator guaranteed by the security of randomized encodings and LinFE.Sim be the simulator guaranteed by the security of the LinFE scheme.

Simulator Bdd.Sim {C i , C i (x), SK i } i∈[q * ] : The simulator Bdd.Sim receives the secret key queries C i , the corresponding (honestly generated) secret keys SK i and the values C i (x) for i ∈ [q * ] where q * ≤ q, and must simulate the ciphertext CT x . It proceeds as follows:

1. Sample ∆ 1 , . . . , ∆ q ⊆ S, of size v each. 2. For each i ∈ [q * ], invoke RE.Sim(C i (x)) to learn G Ci (x, Ri ) for some Ri chosen by the simulator. Interpret Ri = ⊕R a a∈∆i and G Ci,∆i (x, R 1 , . . . , R S ) = G Ci (x, Ri ) = P 1 (Y), . . . , P k (Y) .

Let CT

x = LinFE.Sim {G Ci,∆i , G Ci,∆i (x, R 1 , . . . , R S ), SK i } i∈[q * ]
and output it.

The correctness of Bdd.Sim follows from the correctness of RE.Sim and LinFE.Sim.

A last remaining technicality is that the most general version of our construction for FE for inner product modulo p is stateful. This is because a general adversary against LinFE may request keys that are linearly dependent modulo p but linearly independent over the integers, thus learning new linear relations in the master secret. This forces the simulator (and hence the key generator) to maintain a state.

However, in our application, we can make do with a stateless variant, since all the queries will be linearly independent over Z 2 . To see this, note that in the above application of LinFE, each query is randomized by a unique random set ∆ i . Recall that by cover-freeness, the element ⊕ a∈∆i R a must contain at least one fresh random element, say R * , which is not contained by ∪ j =i ∆ j . Stated a bit differently, if we consider the query vectors of size L, then cover-freeness implies that no query vector lies within the linear span of the remaining queries made by the adversary. For any query Q, there is at least one position j ∈ [L] so that this position is nonzero in the L vector representing Q but zero for all other vectors. Hence the query vectors are linearly independent over Z 2 , for which case, our construction of Section 4.2 is stateless.

Definition 8 (Indistinguishability-based security). A functional encryption scheme FE = (Setup, Keygen, Encrypt, Decrypt) provides semantic security under chosen-plaintext attacks (or IND-CPA security) if no PPT adversary has non-negligible advantage in the following game, where q 1 ≤ q ∈ poly(λ):

1. The challenger runs (mpk, msk) ← Setup(1 λ ) and the master public key mpk is given to the adversary A. 2. The adversary adaptively makes secret key queries to the challenger. At each query, adversary A chooses a key K ∈ K and obtains sk K ← Keygen(msk, K). 3. Adversary A chooses distinct messages Y 0 , Y 1 subject to the restriction that, if {K i } q1 i=1 denotes the set of secret key queries made by A at Stage 2, it holds that F (K i , Y 0 ) = F (K i , Y 1 ) for each i ∈ {1, . . . , q 1 }. Then, the challenger flips a fair coin β ← {0, 1} and computes C ← Encrypt(mpk, Y β ) which is sent as a challenge to A. 4. Adversary A makes further secret key queries for arbitrary keys K ∈ K.

However, it is required that F (K, Y 0 ) = F (K, Y 1 ) at each query K ∈ {K q1+1 , . . . , K q }. 5. Adversary A eventually outputs a bit β ← {0, 1} and wins if β = β.

The adversary's advantage is defined to be Adv

A (λ) := | Pr[β = β] -1/2|
, where the probability is taken over all coin tosses. Definition 8 captures adaptive security in that the adversary is allowed to choose the messages Y 0 , Y 1 at Stage 3. In [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], Abdalla et al. considered a weaker security notion, called selective security, where the adversary has to declare the messages Y 0 , Y 1 at the very beginning of the game, before even seeing mpk (note that, in this scenario, the adversary can receive the challenge ciphertext at the same time as the public key). In this work, our goal will be to meet the strictly stronger requirements of adaptive security.

Simulation-Based Security for Bounded Collusions In this section, we define simulation based security for bounded collusions, as in [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]Defn 3.1].

Definition 9 (q-NA-SIM-and q-AD-SIM-Security).

Let F be a functional encryption scheme for a circuit family C. For every p.p.t. adversary A = (A 1 , A 2 ) and a p.p.t. simulator Sim, consider the following two experiments:

Exp real F ,A (1 λ ): Exp ideal F ,Sim (1 λ ): 1: (MPK, MSK) ← FE.Setup(1 λ ) 2: (x, st) ←A FE.Keygen(MSK,•) 1 (MPK) 3: CT ← FE.Enc(MPK, x) 4: α ← A O(MSK,•) 2
(MPK, CT, st) 5: Output (x, α)

1: MPK ← FE.Setup(1 λ ) 2: (x, st)←A FE.Keygen(MSK,•) 1 (MPK) Let V (C i , C i (x), SK i ) i∈[q] 3: CT, st ← Sim(MPK, V, 1 |x| ) 4: α ← A O (MSK,st ,•) 2 (MPK, CT, st) 5: Output (x, α)
Above, C i denote the queries made by the adversary. We distinguish between two cases of the above experiment:

1. The adaptive experiment, where:

the oracle O(MSK, •) = FE.Keygen(MSK, •) and the oracle O (MSK, st , •) is the simulator, namely Sim Ux(MSK,st ,•) (•) and U x (C) = C(x) for any C ∈ C. The simulator algorithm is stateful in that after each invocation, it updates the state st which is carried over to its next invocation. We call a stateful simulator algorithm Sim admissible if, on each input C, Sim makes just a single query to its oracle U x (•) on C itself. The functional encryption scheme F is then said to be q query simulationsecure for one message against adaptive adversaries (q-AD-SIM-secure, for short) if there is an admissible stateful p.p.t. simulator Sim such that for every p.p.t. adversary A = (A 1 , A 2 ) that makes at most q queries, the following two distributions are computationally indistinguishable:

Exp real F ,A (1 λ ) λ∈N c ≈ Exp ideal F ,Sim (1 λ ) λ∈N 2.
The non-adaptive experiment, where the oracles O(MSK, •) and O (MSK, st, •) are both the "empty oracles" that return nothing. The functional encryption scheme F is then said to be q query simulationsecure for one message against non-adaptive adversaries (q-NA-SIM-secure, for short) if there is an admissible stateful p.p.t. simulator Sim such that for every p.p.t. adversary A = (A 1 , A 2 ) that makes at most q queries, the two distributions above are computationally indistinguishable.

B Practical applications of Linear FE

On the practical front, Linear FE is already quite useful even when used directly. As pointed out by Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], the inner product functionality suffices for the computation of linear functions (e.g., sums or averages) over encrypted data.

As mentioned in the earlier work of Katz, Sahai and Waters [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF], inner products also enable the evaluation of polynomials over encrypted data. To do this, we can simply encode a message M as a vector y = (1, M, . . . , M d ) ∈ D d+1 and a degree- , the inner product functionality also allows for the computation of Hamming weights using secret keys sk x for the all-one vector x = (1, . . . , 1). More generally, inner products make it possible to compute the Hamming distance between an encrypted n-bit vector y = (y 1 , . . . , y n ) ∈ {0, 1} n and another binary vector x = (x 1 , . . . , x n ) ∈ {0, 1} n embedded in the key, which can be useful in biometric applications. To this end, we can simply encode y and

d polynomial P [X] = d i=0 p i X i is
x as vectors Y = (Y 1 , . . . , Y 2n ) ∈ {-1, 1} 2n and X = (X 1 , . . . , X 2n ) ∈ {-1, 1} 2n such that X 2i = Y 2i = 1 and Y 2i+1 = (-1) yi , X 2i+1 = -(-1) xi for each i ∈ {1, . . . , n}. By doing so, the integer X, Y = n i=1 (1 -(-1) xi+yi
) is exactly twice the Hamming distance between x and y.

C Background on lattices

Let Λ be a non-zero lattice. We recall that the smoothing parameter of Λ is defined as η ε (Λ) = min(s > 0 :

b∈ Λ Exp(-π b 2 /s 2 ) ≤ 1 + ε), where Λ = { b ∈ span R (Λ) : bT • Λ ⊆ Z} refers to the dual of Λ.

For a matrix A ∈ Z m×n q for some integers m, n, q, we define the lattice Λ ⊥ (A) = {x ∈ Z m : x T • A = 0 mod q}.

Lemma 6 (Adapted from [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]Le. 2.3 & 2.4]). Let n, m, q be positive integers, and ε, δ > 0. Assume that q = p k for p prime and k ≥ 1. Assume further that m ≥ max n + log(3 + 4/(δε)) log p , n log q + log(2 + 2/(δε)) log 2 .

Then η ε (Λ ⊥ (A)) ≤ 2 ln(2m(1 + 2/(δε)))/π, except with probability ≤ δ over the uniform choice of A ∈ Z m×n q .

Let Λ ⊆ R n be a lattice, σ > 0 and c ∈ R n . We define the lattice Gaussian distribution of support Λ, standard deviation parameter σ and center c as:

∀b ∈ Λ : D Λ,σ,c (b) = Exp(-π b -c 2 /σ 2 ) x∈Λ Exp(-π x -c 2 /σ 2 )
.

Given uniform samples, the reduction outputs uniform samples up to statistical distance 2 -n+t+1 . Given samples from A q,α,s , the reduction outputs t samples from A q,{0},s and the remaining samples from A q,α,s up to statistical distance 2 -n+t+1 , with s = R -1 • (s |s) T mod q. This proves correctness since R induces a bijection on Z n q . Leftover hash lemma. We will use the following variant of the leftover hash lemma.

Lemma 11 (Particular case of [45, Le. 2.3]). Let q = p k for p prime and k ≥ 1. Let m ≥ n ≥ 1. Take X a distribution over Z m . Let D 0 be the uniform distribution over Z n×m q ×Z n q and D 1 be the distribution of (A, A•x) ∈ Z n×m q ×Z n q , where by sampling A ← Z n×m q and x ← X . Then

∆(D 0 , D 1 ) ≤ 1 2 k i=1 p i•n • Pr i ,
where Pr i is the collision probability of two independent samples from X mod p i .

As an illustration, if the distribution (X mod p) is within statistical distance ε from the uniform distribution over Z m p , then

∆(D 0 , D 1 ) ≤ (ε + p -m )q n .

E Proof of Theorem 1

Proof. The proof uses a sequence of games that begins with the real game and ends with a game where the adversary has no advantage at all. For each i, we denote by S i the event that the adversary wins in Game i.

Game 0: This is the real game. In this game, the adversary A is given mpk. In the challenge phase, A chooses two distinct vectors y 0 , y 1 ∈ Z q and obtains an encryption of y β = (y β,1 , . . . , y β, ), for some random β ← {0, 1}. At the end of the game, A outputs β ∈ {0, 1} and we denote by S 0 the event that β = β. For any vector x ∈ Z q submitted to the secret key extraction oracle, it must be the case that x, y 0 = x, y 1 mod q.

Game 1: We modify the generation of the challenge C y β = (C, D, E 1 , . . . , E ). Namely, the challenger B first computes

C = g r and D = h r , (E.1)
for a randomly sampled r ← Z q . Then, it uses msk := {(s i , t i )} i=1 to compute In Game 2, we claim that the challenge ciphertext C y β = (C, D, E 1 , . . . , E ) perfectly hides β ∈ {0, 1}, so that Pr[S 2 ] = 1/2. To see this, we first remark that, for each i ∈ {1, . . . , }, we have

E i = g y β,i • C si • D ti . (E.
g y β,i • C si • D ti = g y β,i +ω•r •ti • h r i ,
where ω = log g (h), which means that an unbounded adversary can only infer

z β = y β,1 + ω • r • t 1 , . . . , y β, + ω • r • t = y β + ω • r • t ∈ Z q from C y β = (C, D, E 1 , . . . , E ).
To prove that z β does not reveal any information about β ∈ {0, 1} to any legitimate adversary, we define y = y 0 -y 1 mod q and deterministically generate a Z q -basis X top ∈ Z ( -1)× q of the ( -1)-dimensional subspace y ⊥ = {x ∈ Z q | x, y = 0 mod q}.

Let y ∈ Z q be a vector outside the subspace y ⊥ which we also choose in a deterministic manner. We define the invertible matrix

X = X top y T ∈ Z × q
Since the rows of X are deterministically generated from y ∈ Z q , they are known to A and it suffices to prove that X • z β ∈ Z q is information-theoretically independent of β ∈ {0, 1} to prove that z β does not reveal anything about β either. The first ( -1) rows of X • z β ∈ Z q are clearly independent of β since X top • y 0 = X top • y 1 mod q by construction. We are thus left with the last row, which is the inner product y , y β + ω • r • y , t mod q. Let (s 0 , t 0 ) ∈ Z q × Z q denote an arbitrary pair of vectors satisfying (h 1 , . . . , h ) = g s0 • h t0 and sk xi = ( s 0 , x i , t 0 , x i ) for all private key queries {x i } -1 i=1 . Since all queries involve vectors x i in y ⊥ , the joint distribution of the secret vectors (s, t)

∈ Z q × Z q is {(s 0 -ω • µ • y mod q, t 0 + µ • y mod q) | µ ∈ Z q } in the adversary's view. The conditional distribution of ω • r • y , t mod q is thus {ω • r • ( y , t 0 + µ • y , y ) mod q | µ ∈ Z q },
which is nothing but the uniform distribution over Z q since y , y = 0 mod q by construction. Since r = 0 with overwhelming probability, this means that the term ω • r • y , t mod q perfectly hides y , y β in the inner product y , z β modulo q.

F Proof of Theorem 5

Proof. The proof uses a sequence of games that begins with a game where the adversary is given a real encryption of y β , for some random bit β ∈ {0, 1}, and ends with a game where β ∈ {0, 1} is statistically independent of the adversary's view. For each i, we denote by S i the event that the adversary wins in Game i.

Game 0: This is the actual security game. The adversary A is given the master public key mpk = N, g, {h i } i=1 , Y , where h i = g si mod N 2 and s = (s 1 , . . . , s ) T ← D Z,σ is a discrete Gaussian vector. In the challenge phase, A chooses two vectors y 0 = (y 0,1 , . . . , y 0, ), y 1 = (y 1,1 , . . . , y 1, ) ∈ Z of norms ≤ Y and obtains an encryption of y β , for some random β ∈ {0, 1}. At the end of the game, A outputs β ∈ {0, 1} and we denote by S 0 the event that β = β. For any vector x ∈ Z submitted by the adversary to the secret key extraction oracle, we must have the equality x, y 0 = x, y 1 over Z. Game 2: We modify again the generation of C y β = (C 0 , C 1 , . . . , C ) in the challenge phase. Namely, instead of computing C 0 by first choosing a random N th residue z in Z * N 2 , the challenger rather samples z ← Z * N 2 at random, computes C 0 as in as in (F.1) (so that C 0 is a square in Z * N 2 but not a N th residue, except with negligible probablity) and sets

C i = (1 + N ) y β,i • C si 0 mod N 2 , ∀i ∈ {1, . . . , }.
Under the DCR assumption, this modification is not noticeable to A, which implies that | Pr[S 2 ] -Pr[S 1 ]| ≤ Adv DCR B (λ). Game 3: We modify the generation of C 0 in the challenge ciphertext. Instead of choosing it uniformly in QR N 2 , the challenger picks a z ← Z * N and r z ← {1, . . . , N/4 } and computes

C 0 = (1 + N ) az • g rz mod N 2 .
which is the lattice Λ = Z • y ∩ (p q • Z) = (p q ) • Z • y. Conditionally on {h i } i=1 and X top • s, the distribution of s, y is thus s 0 , y + D (p q ) y 2 •Z, y σ,-c , where c = s 0 , y ∈ Z. We consider the distribution obtained by reducing the distribution D (p q ) y 2 •Z, y σ,-c over Λ 0 = (p q ) y 2 • Z modulo the sublattice Λ 0 = (p q ) y 2 • (N Z). By Lemma 8, given that |(p q ) y 2 • N | < N 2 y 2 , gcd(p q y 2 , N ) = 1 and y < √ N , choosing σ > √ λ • N 5/2 suffices to ensure that s, y mod N is within distance 2 -λ from the uniform distribution over Λ 0 /Λ 0 Z N when {h i } i=1 and X top • s ∈ Z -1 are given. Since a z is invertible in Z N with all but negligible probability, the term y β , y mod N is thus statistically hidden in the right-hand-side member of (F.3).

When counting probabilities, we find that A's advantage in the real game can be bounded as | Pr[S 0 ] -1/2| ≤ Adv DCR B (λ) + 2 -λ+1 , which is thus negligible if the DCR assumption holds.

G Proof of Theorem 6

Proof. The proof proceeds similarly to the proof of Theorem 5 and uses the same sequence of games. The only modification is in the argument to argue that the adversary's view is independent of β ∈ {0, 1} in the final game.

For each i, we denote by S i the event that the adversary wins in Game i. We first recall the final game of the sequence: Game 3 : At the beginning of the game, the challenger sets g = g 2N mod N 2 , where g ← Z * N 2 , and picks s = (s 1 , . . . , s ) T ← D Z ,σ before defining the public parameters h i = g si mod N 2 for each i ∈ {1, . . . , }. The master public key mpk = (N, g, {h i } i=1 ) is given to the adversary A. In the challenge phase, A chooses two distinct vectors y 0 , y 1 ∈ Z N . The challenger flips a random coin β ← {0, 1} and encrypts y β by choosing a z ← Z N , r z ← {0, . . . , N/4 } and setting C 0 = (1 + N ) az • g rz mod N 2 , C i = (1 + N ) y β,i +az•si • h rz i mod N 2 ∀i ∈ {1, . . . , }.

Note that any vector x ∈ Z N queried by A to the private key generation oracle must satisfy x, y 0 = x, y 1 mod N . At each query, the adversary A is given a secret key (x, z x ) exactly as in the real scheme. When A halts, it outputs β ∈ {0, 1} and wins in the event that β = β.

Let us define y = y 1 -y 0 ∈ Z N and let x i ∈ Z p be the vectors corresponding to the secret key queries made by A. Since A is a legitimate adversary, we know that x i , y = 0 mod N for each secret key query x i ∈ Z N . Note that x i , y = 0 mod p and x i , y = 0 mod q. We may further assume that y is non-zero both modulo p and modulo q (otherwise, the reduction has found a non-trivial factor of N ).

We have to show that A's view is statistically independent of β ∈ {0, 1} in Game 3 . To this end, we use a similar analysis to that of Theorem 3. In particular, we cannot use the same matrix X top as in (4.1) since, if we define X to be the matrix formed by that matrix X top and y T , we cannot guarantee that the determinant of XX T is not a multiple of N . One option would be to define X as the × matrix formed by the Z N -independent private key queries and y T . One difficulty is that such an X may not be invertible (we may have y, y = 0 mod N ). Further, after the challenge phase, we cannot immediately rule out that the queried vectors x i somehow depend on β ∈ {0, 1}. To avoid a circularity, we use an inductive argument as in the proof of Theorem 3.

For each j from 0 to -1, we consider the adversary's view after exactly j private key queries for linearly independent vectors over Z N . Since A's view is trivially independent of β ∈ {0, 1} before the challenge phase, we only need to worry about post-challenge queries and we assume that the challenge ciphertext has been generated when the jth query occurs. By induction, we will show that, for any j ∈ {1, . . . , -1}, the view of the adversary remains statistically independent of β after the first j queries. In particular, the (j + 1)th linearly independent private key query will be statistically independent of β as well. It will also ensure that, for j = -1, A's view will remain statistically independent of β in Game 3 , which is exactly what we have to show.

Our induction hypothesis thus considers a counter value j ∈ {0, . . . , -1} and assumes that, at this point st, is independent of β. At this stage, st contains j tuples (x i , x i , z i ). These x i 's generate subspaces of both y ⊥p := {x ∈ Z p : x, y = 0 mod p} and y ⊥q := {x ∈ Z q : x, y = 0 mod q}. We deterministically extend the {x i } j i=1 into {x i } -1 i=1 so as to have a basis of both y ⊥ p and y ⊥ q which is statistically independent of β. This is achieved by linear algebra modulo N , and, if any Gaussian elimination step fails because Z/N Z is not a field, the reduction succeeds as it has found a factor of N . This extension of {x i } j i=1 into {x i } -1 i=1 can be seen as having the challenger making dummy private key queries for itself and creating the corresponding x i 's in Z so as to get a full basis of both y ⊥p and y ⊥q . Note that we may assume that the challenger knows y as we only need to apply the inductive argument to post-challenge queries.

We define X top ∈ Z ( -1)× as the matrix whose ith row is x i , for all i ∈ {1, . . . , -1} (including the genuine and dummy private key queries). Via private key queries, the information obtained by the adversary amounts to a subset of the coordinates of X top • s ∈ Z ( -1) .

Let x ∈ Z N be a vector outside y ⊥p and y ⊥q which is chosen as a deterministic function of {x i } j i=1 and y and let X bot ∈ Z 1× be the canonical lift of (x ) T over the integers. By construction of X bot ∈ Z 1× , we have X bot • y = 0 mod N . Now, let us define the matrix

X = X top X bot ∈ Z × .

  t × D m-t αq and define b = U • (b + e ) + f . We then sample c ← D Z m -b , √ 2αξq , and define h = Z(f + c).

  encoded as a vector x = (p 0 , p 1 , . . . , p d ) ∈ D d+1 for which the key SK x is generated. Using a similar encoding, we can also evaluate multivariate polynomials of the form P [X 1 , . . . , X d ] = d i=1 (X i -I i ) of small degree d = O(log ). By encoding -bit messages M = M [1] . . . M [ ] as vectors y = (M [1], . . . , M [ ])

2 )Game 2 :

 22 It can be observed that C y β = (C, D, E 1 , . . . , E ) has the same distribution as in Game 0. We hence have Pr[S 1 ] = Pr[S 0 ]. In this game, we modify again the generation of C y β = (C, D, E 1 , . . . , E ) in the challenge phase. Namely, instead of computing the pair (C, D) as in (E.1), the challenger B samples r, r ← Z q and sets C = g r and D = h r+r . The ciphertext components (E 1 , . . . , E ) are still computed as per (E.2). Under the DDH assumption, this modification should not significantly affect A's view and we have | Pr[S 2 ] -Pr[S 1 ]| ≤ Adv DDH B (λ).

Game 1 :

 1 We modify the generation of the challenge C y β = (C 0 , C 1 , . . . , C ). Namely, the challenger B first chooses z = z N 0 mod N 2 , for a randomly drawn z 0 ← Z * N and computesC 0 = z 2 mod N 2 . (F.1)Then, it uses msk := ({s i } i=1 , X) to computeC i = (1 + N ) y β,i • C si 0 mod N 2 , ∀i ∈ {1, . . . , }.The ciphertext C y β has almost the same distribution as in Game 1 as C 0 is now perfectly (instead of statistically) uniform in the subgroup of (2N )th residues. We have | Pr[S 1 ] -Pr[S 0 ]| ≤ 2 -λ .

Indeed, the two candidate multi-linear maps[START_REF] Garg | Candidate multilinear maps from ideal lattices and applications[END_REF][START_REF] Coron | Practical multilinear maps over the integers[END_REF] put forth in 2013 were recently found to be insecure[22,

42].

And indeed, this unsuitability partially manifests itself in the limitation of message/function space of the aforementioned construction: message/function vectors must be short integer vectors, and the inner product is evaluated over the integers.

Boneh, Sahai and Waters[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF] pinpointed shortcomings of indistinguishabilitybased definitions in the case of general functionalities, where they may fail to rule out intuitively insecure systems. Boneh et al.[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF] proposed strong simulationbased definitions, but these have been shown to be impossible to realize in the standard model[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF][START_REF] Agrawal | Functional encryption: New perspectives and lower bounds[END_REF].On the positive side, O'Neill[START_REF] O'neill | Definitional issues in functional encryption[END_REF] showed that indistinguishability-based security is equivalent to non-adaptive simulation based security (defined below) for a class of functions called preimage sampleable functions, which includes inner products. De Caro et al.[START_REF] Caro | On the achievability of simulation-based security for functional encryption[END_REF] gave a general method of constructing FE schemes that achieve a meaningful definition of simulation-based security from systems that are only proved secure in the sense of indistinguishability-based definitions. Also, note that the impossibility of achieving adaptive simulationbased security for IBE, exhibited by[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF] can be easily adapted to show that adaptive simulation-based security (AD-SIM) is also impossible to achieve for the inner product functionality. Thus, adaptive indistinguishability appears to be the strongest adaptive notion of security that may still be achievable, and for a wide range of practically interesting specific functionalities this notion is believed to suffice. In the following, we will aim at full security in the sense of Definition 8.

Acknowledgements. We thank Fabrice Benhamouda, Florian Bourse, Hoeteck Wee and Shota Yamada for helpful discussions. This work has been supported in part by ERC Starting Grant ERC-2013-StG-335086-LATTAC. Part of this work was also 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).

• With probability ≥ 1 -n -ω (1) , all rows from a sample from τ have norms ≤ ξ.

Our reduction from LWE to mheLWE proceeds as the reduction from LWE to extended-LWE from [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF], using the matrix gadget from [START_REF] Ling | Hardness of k-LWE and Applications in Traitor Tracing[END_REF] to handle the multiple hints. We first reduce LWE to the following variant of LWE in which the first samples are noise-free. This problem generalizes the first-is-errorless LWE problem from [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF].

Definition 5 (First-are-errorless LWE). Let q, α, m, t be functions of a parameter n. The first-are-errorless LWE problem faeLWE q,α,m,t is defined as follows: For s ← Z n q , the goal is to distinguish between the following two scenarios. In the first, all m samples are uniform over Z n q × Z q . In the second, the first t samples are from A q,{0},s (where {0} denotes the distribution that is deterministically zero) and the rest are from A q,α,s . Lemma 3. For any n > t, m, q ≥ 2, and α ∈ (0, 1), there is an efficient reduction from LWE q,α,m in dimension n -t to faeLWE q,α,m,t in dimension n that reduces the advantage by at most 2 -n+t+1 .

The proof, postponed to the appendices, is a direct adaptation of the one of [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]Le. 4.3].

In our reduction from faeLWE to mheLWE, we use the following gadget matrix from [START_REF] Ling | Hardness of k-LWE and Applications in Traitor Tracing[END_REF]Cor. 10]. It generalizes the matrix construction from [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]Claim 4.6].

There exists a probabilistic polynomial time algorithm that given n, m 1 , m 2 (in unary) and σ 1 , σ 2 as inputs, outputs G ∈ Z m×m such that:

Lemma 5. Let n, m 1 , m 2 , m, σ 1 , σ 2 , τ be as in Lemma 4, and ξ ≥ Ω( √ nm 2 σ 2 ).

Let q ≥ 2, t ≤ n, α ≥ Ω( √ n/q). Let τ t be the distribution obtained by keeping only the first t rows from a sample from τ . There is a (dimension-preserving) reduction from faeLWE q,α,m,t to mheLWE q,2αξ,m,t,τt that reduces the advantage by at most 2 -Ω(n) .

Proof. Let us first describe the reduction. Let (A, b) ∈ Z m q × Z q be the input, which is either sampled from the uniform distribution, or from distribution A t q,{0},s × A m-t q,α,s for some fixed s ← Z n q . Our objective is to distinguish between the two scenarios, using an mheLWE oracle. We compute G as in Lemma 4 and let U = G -1 . We let Z ∈ Z t×m denote the matrix formed by the top t

A Definitions for functional encryption

We now recall the syntax of Functional Encryption, as defined by Boneh, Sahai and Waters [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF], and their indistinguishability-based security definition.

Definition 6 ([18]

). A functionality F defined over (K, Y) is a function F : K × Y → Σ ∪ {⊥}, where K is a key space, Y is a message space and Σ is an output space, which does not contain the special symbol ⊥. Definition 7. A functional encryption (FE) scheme for a functionality F is a tuple FE = (Setup, Keygen,Encrypt, Decrypt) of algorithms with the following specifications:

Setup(1 λ ): Takes as input a security parameter 1 λ and outputs a master key pair (mpk, msk). Keygen(msk, K): Given the master secret key msk and a key (i.e., a function) K ∈ K, this algorithm outputs a key sk K . Encrypt(mpk, Y ): On input of a message Y ∈ Y and the master public key mpk, this randomized algorithm outputs a ciphertext C. Decrypt(mpk, sk K , C): Given the master public key mpk, a ciphertext C and a key sk K , this algorithm outputs v ∈ Σ ∪ {⊥}.

We require that, for all (mpk, msk) ← Setup(1 λ ), all keys K ∈ K and all messages Y ∈ Y, if sk K ← Keygen(msk, K) and C ← Encrypt(mpk, Y ), with overwhelming probability, we have Decrypt(mpk, sk

In some cases, we will also give a state st as input to algorithm Keygen, so that a stateful authority may reply to key queries in a way that depends on the queries that have been made so far. In that situation, algorithm Keygen may additionally update state st.

Indistinguishability-based security. From a security standpoint, what we expect from a FE scheme is that, given C ← Encrypt(mpk, Y ), the only thing revealed by a secret key sk K about the underlying Y is the function evaluation F (K, Y ). In the natural definition of indistinguishability-based security (see, e.g., [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF]), one asks that no efficient adversary be able to differentiate encryptions of Y 0 and Y 1 without obtaining secret keys sk K such that

We omit the subscript c when c = 0. To implement the primitives described in this work, we only need to be able sample from 1-dimensional lattice Gaussians. Such an efficient sampler is described in [START_REF] Ducas | Lattice signatures and bimodal gaussians[END_REF].

We make use of the following lemmas. ). Assume the rows of A ∈ Z m×n q generate Z n q and let ε ∈ (0, 1/2), c ∈ Z m and σ ≥ η ε (Λ ⊥ (A)). Then for e sampled from D Z m ,σ,c , the distribution of the syndrome e T • A mod q is within statistical distance 2ε of uniform over Z n q .

Note that if q = p k with p prime, then the rows of A ∈ Z m×n q generate Z n q if and only if they generate Z n p (once reduced modulo p). If A is sampled uniformly, this occurs with probability ≥ 1 -p -n when m ≥ 2n log 2 p.

Using the Lemmas 6 and 9, we obtain the following result, that we use in the proof of Theorem 2.

Lemma 10. Let n, m, q ≥ 2 be positive integers. Assume that q = p k for p prime and k ≥ 1. Assume further that m ≥ 2n log 2 q. Let σ ≥ Ω( √ n + log m) and c ∈ Z m . Then for A ∈ Z m×n q sampled uniformly and e ∈ Z m sampled from D Z m ,σ,c , the distribution of the pair (A, e T • A) is within statistical distance 2 -Ω(n) of uniform over Z m×n q × Z n q .

D Missing material from Section 4

Proof of Lemma 3. The reduction from LWE to faeLWE starts by sampling A ← Z t×n q . It aborts if it is not full-rank (modulo q): this happens with probability

Else, the reduction computes R ∈ Z n×n q which is invertible and whose top t × n submatrix is A . The reduction also samples s ← Z t q . The first t output samples are (a i , s i ) (for i ≤ t), where a i denote the ith row of A . The remaining samples are produced by taking a sample (a, b) ∈ Z n-t q × Z q from the given oracle, picking a fresh uniformly random d ∈ Z t q , and returning (R T • (d|a), b + s , d ).

The generation of {C i } i=1 remains unchanged. The statistical distance between the distribution of C 0 in Game 3 and Game 2 is smaller than 2 -λ . We have

In Game 3, we have C 0 = (1 + N ) az • g rz mod N 2 and we claim that

To prove this, we use a similar argument to the one in the proof of Theorem 2.

Namely, if we consider the vector y = (y 1 , . . . , y ) = 1 g (y 1 -y 0 ) ∈ Z , where g = gcd(y 0,1 -y 1,1 , . . . , y 0, -y 1, ), we know that any legal private key query x ∈ Z must be in the lattice {x ∈ Z : x, y = 0} for which the rows of the matrix X top ∈ Z ( -1)× defined in (4.1) form a basis. We also know that y 2 < N and we may assume that gcd( y 2 , N ) = 1 since the reduction would be able to compute a non-trivial factor of N otherwise. We may also assume that the information that the adversary can infer about s = (s 1 , . . . , s ) ∈ Z via private key queries is completely determined by

Since y 2 < N , the same arguments as in the proof of Theorem 2 ensure that the matrix X is invertible in Z N unless its determinant reveals a non-trivial factor of N . Recall that the challenge ciphertext (F.2) information-theoretically reveals

so that we have to show that z β is statistically independent of β ∈ {0, 1} conditionally on A's view. Since X ∈ Z × is invertible over Z N and does not depend on β ∈ {0, 1}, it suffices to show that X • z β ∈ Z N is statistically independent of β ∈ {0, 1}. Given that X top • (y 0 -y 1 ) = 0 (over the integers),

N is clearly independent of β ∈ {0, 1} and we only need to worry about the last row of X • z β ∈ Z N , which can be written

Let s 0 = (s 0,1 , . . . , s 0, ) ∈ Z denote an arbitrary vector satisfying

From A's view, the distribution of the master secret key s ∈ Z is s 0 + D Λ,σ,-s0 , where

By construction, this matrix X is invertible modulo N . Moreover, by induction and construction, it is statistically independent of β ∈ {0, 1}. In Game 3 , the challenge ciphertext information-theoretically reveals

and it thus suffices to prove that z β is almost independent of β ∈ {0, 1} conditionally on {h i = g si mod N 2 } i=1 and X top • s ∈ Z -1 . Since the rows of X are known to A in the information theoretic sense, it is sufficient to prove that X

N is necessarily independent of β ∈ {0, 1} and it suffices to consider the distribution of X bot • z β mod N . Let s 0 = (s 0,1 , . . . , s 0, ) T ∈ Z be an arbitrary vector satisfying the equalities h i = g s0,i mod N 2 and X top • s 0 = X top • s (over Z). Conditionally on the adversary's view, the distribution of s ∈ Z is s 0 + D Λ,σ,-s0 , where

which is a one-dimensional lattice in Z . We have

for some y ∈ Z . Note that, by the Chinese Remainder Theorem, there exists an invertible α ∈ Z * N such that y = α • y mod N as, if we had α = 0 mod p or α = 0 mod q, it would contradict the definition of y .

If we define Λ to be the lattice generated by the rows of X top ∈ Z ( -1)× , we have y = det(Λ/(p q )) ≤ det Λ and Hadamard's bound implies y ≤ ( √ N ) -1 . Since (p q )• y ≤ ( √ N ) , the smoothing parameter of the sublattice (N • Λ) must be bounded by ( √ N ) +1 . By choosing σ > √ λ( √ N ) +1 , we obtain that the distribution D Λ,σ,-s0 mod (N • Λ) is within 2 -λ distance from the uniform distribution over Λ/(N • Λ) which is isomorphic to y • Z N because gcd(p q , N ) = 1 and y = α•y mod N for some α ∈ Z * N . Since X bot •y = 0 mod p and X bot • y = 0 mod q, we find that X bot • s mod p and X bot • s mod q are statistically close to the uniform distribution over Z p and Z q , respectively.

Since gcd(a z , N ) = 1 with overwhelming probability, this implies that the product X bot • z β mod N does not carry any significant information about β, as claimed.

Putting the above altogether, the adversary's advantage in the initial game can be bounded as