Benoît Libert

Radu Ţiţiu

Multi-Client Functional Encryption for Linear Functions in the Standard Model from LWE

Keywords: Multi-client functional Encryption, inner product evaluation, LWE, standard model, decentralization

Multi-client functional encryption (MCFE) allows clients to encrypt ciphertexts (Ct,1, Ct,2, . . . , C t, ) under some label. Each client can encrypt his own data Xi for a label t using a private encryption key eki issued by a trusted authority in such a way that, as long as all Ct,i share the same label t, an evaluator endowed with a functional key dk f can evaluate f (X1, X2, . . . , X ) without learning anything else on the underlying plaintexts Xi. Functional decryption keys can be derived by the central authority using the master secret key. Under the Decision Diffie-Hellman assumption, Chotard et al. (Asiacrypt 2018) recently described an adaptively secure MCFE scheme for the evaluation of linear functions over the integers. They also gave a decentralized variant (DMCFE) of their scheme which does not rely on a centralized authority, but rather allows encryptors to issue functional secret keys in a distributed manner. While efficient, their constructions both rely on random oracles in their security analysis. In this paper, we build a standard-model MCFE scheme for the same functionality and prove it fully secure under adaptive corruptions. Our proof relies on the Learning-With-Errors (LWE) assumption and does not require the random oracle model. We also provide a decentralized variant of our scheme, which we prove secure in the static corruption setting (but for adaptively chosen messages) under the LWE assumption.

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 modern paradigm that overcomes the all-or-nothing nature of ordinary encryption schemes. In FE, the master secret key msk allows deriving a sub-key dk f associated with a specific function f . If a ciphertext C encrypts a message X under the master public key mpk, when dk f is used to decrypt C, the decryptor only obtains f (X) and nothing else about X. Functional encryption is an extremely general concept as it subsumes identity-based encryption [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Cocks | An identity based encryption scheme based on quadratic residues[END_REF], searchable encryption [START_REF] Boneh | Public key encryption with keyword search[END_REF], attribute-based encryption [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], broadcast encryption [START_REF] Fiat | Broadcast encryption[END_REF] and many others.

As formalized by Boneh, Sahai and Waters [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF], FE only allows evaluating a function f over data provided by a single sender whereas many natural applications require to compute over data coming from distinct distrustful parties. A straightforward solution to handle multiple senders is to distribute the generation of ciphertexts by means of a multi-party computation (MPC) protocol. Unfortunately, jointly generating a ciphertext incurs potentially costly interactions between the senders who should be online at the same time and have their data ready to be submitted. Ideally, the participants should be able to supply their input without interacting with one another and go off-line immediately after having sent their contribution. This motivates the concepts of multi-input [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] and multi-client [START_REF] Gordon | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] functional encryption, which support the evaluation of multivariate functions over data coming from distinct sources.

(Decentralized) Multi-Client FE

Multi-client functional encryption. As defined in [START_REF] Gordon | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF], multi-client functional encryption (MCFE) allows computing over input vectors (X 1 , . . . , X ) of which each coordinate X i may be sent by a different client. Each ciphertext C i is associated with a client index i and a tag t (also called "label"): on input of a vector of ciphertexts (C 1 = Encrypt(1, X 1 , t), . . . , C = Encrypt( , X , t)), where C i is generated by client i using a secret encryption key ek i for each i ∈ [ ], anyone holding a functional decryption key dk f for an -ary function can compute f (X 1 , . . . , X ) as long as all C i are labeled with the same tag t (which may be a time-specific information or a dataset name). No further information than f (X 1 , . . . , X ) is revealed about individual inputs X i and nothing can be inferred by combining ciphertexts generated for different tags. MCFE can thus be seen as a multi-party computation (MPC) where each ciphertext C i can be generated independently of others and no communication is needed between data providers.

Decentralized multi-client functional encryption. Most FE flavors involve a single central authority that should not only be trusted by all users, but also receives the burden of generating all functional secret keys. In decentralized FE systems [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF][START_REF] Chandran | Functional encryption: Decentralised and delegatable[END_REF], multiple authorities can operate independently without even being aware of one another.

Like its single-client counterpart, multi-client FE requires a trusted entity, which is assigned the task of generating a master key msk as well as handing out encryption keys ek i to all clients and functional decryption keys dk f to all decryptors. In some applications, clients may be reluctant to rely on a single point of trust. This motivates the design of a decentralized version of MCFE, as introduced by Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]. Decentralized multi-client functional encryption (DMCFE) obviates the need for a centralized authority by shifting the task of generating functional secret keys to the clients themselves. In a setup phase, the clients S 1 , . . . , S first generate public parameters by running an interactive protocol but no further interaction is needed among clients when it comes to generating functional secret keys later on. When a decryptor wishes to obtain a functional secret key for an -ary function f , it interacts with each client i independently so as to obtain partial functional decryption keys dk f,i . The decryptor can then fold {dk f,i } i=1 into a functional decryption key dk f for f . By doing so, each client has full control over his individual data and the functions for which secret keys are given out. Importantly, no interaction among senders is required beyond the setup phase, where public parameters are generated.

As a motivating example, Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] consider the use-case of a financial analyst that is interested in mining several companies' private data so as to better understand the dynamics of an economical sector. These companies have some incentives to collaborate, but they do not want their clients' data to be abused (in which case, they would risk heavy fines owing to the EU General Data Protection Regulation). After having interactively set up DMCFE parameters, each company can encrypt its own data with respect to a time-stamp. Then, the analyst can contact each company to obtain partial functional keys and reconstruct a key that only reveals a weighted aggregate of companies' private inputs provided they are labeled with the same time-stamp.

Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] described a DMCFE scheme that allows evaluating linear functions over encrypted data: namely, if (X 1 , . . . , X ) ∈ Z are the individual contributions sent by senders, a functional secret key dk f for the integer vector y = (y 1 , . . . , y ) ∈ Z allows computing i=1 y i • X i from {C i = Encrypt(i, X i , t)} i=1 , where C i is generated by the i-th sender. In the decentralized setting, each sender can also generate a partial functional secret key dk f,i for y = (y 1 , . . . , y ) ∈ Z using their secret encryption key ek i .

Our Contributions

The MCFE scheme of Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] was proved fully secure (as opposed to selectively secure) in the random oracle model under the standard Decision Diffie-Hellman assumption in groups without a bilinear maps. Its decentralized variant was proved secure under the Symmetric eXternal Diffie-Hellman (SXDH) assumption in groups endowed with an asymmetric bilinear map. While efficient, the schemes of [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] both require the random oracle model. Chotard et al. thus left open the problem of designing a (D)MCFE system under well-studied hardness assumptions without using random oracles: even in the centralized setting, the only known MCFE candidates in the standard model [START_REF] Gordon | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] rely on indistinguishability obfuscation. They also left open the problem of instantiating their schemes under the LWE assumption or any other assumption than DDH.

In this paper, we address both problems. For linear functions over the integers (i.e., the same functionality as [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]), we construct the first MCFE scheme in the standard model and prove it fully secure under the Learning-With-Errors assumption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] in the adaptive corruption setting (note that only static corruptions were considered in [START_REF] Gordon | Multi-input functional encryption[END_REF]Section 2.3]). This construction turns out to be the first standard-model realization of an MCFE system with labels -albeit for a restricted functionality -that does not require obfuscation. Next, we extend our centralized system to obtain the first labeled DMCFE scheme without random oracles. Like [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], our decentralized solution is only proved secure in the static corruption setting although we can handle adaptive corruptions in its centralized version. Both constructions are proved secure under the LWE assumption with sub-exponential approximation factors. Our security proofs stand in the standard model in the sense of the same security definitions as those considered in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF].

We leave it as an open problem to achieve security under an LWE assumption with polynomial approximation factor. Another natural open question is the feasibility of (D)MCFE beyond linear functions under standard assumptions.

Challenges and Techniques

We start from the observation that the DDH-based MCFE scheme of Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] can be interpreted as relying on (a variant of) the key-homomorphic pseudorandom function [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] of Naor, Pinkas and Reingold [START_REF] Naor | Distributed pseudo-random functions and KDCs[END_REF]. Namely, the scheme of [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] encrypts x i ∈ Z q for the tag t by computing [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] , where (s i , t i ) ∈ Z 2 q is the i-th sender's secret key and (H t,1 , H t,2 ) = H(t) ∈ G 2 is derived from a random oracle in a DDH-hard group G = g .

C i = g xi • H si t,1 • H ti t,
The security proof of [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] crucially exploits the entropy of the secret key (s i , t i ) in a hybrid argument over all encryption queries. To preserve this entropy, they need to prevent the encryption oracle from leaking too much about uncorrupted users' secret keys {(s i , t i )} i . For this purpose, they rely on the DDH assumption to modify the random oracle H : {0, 1} * → G 2 in such a way that, in all encryption queries but one, the hash value H(t) ∈ G 2 lives in a one-dimensional subspace. In order to transpose this technique in the standard model, we would need a programmable hash function [START_REF] Hofheinz | Programmable hash functions and their applications[END_REF] that ranges over a one-dimensional subspace of G 2 on polynomially-many inputs while mapping an extra input outside this subspace with noticeable probability. The results of Hanaoka et al. [START_REF] Hanaoka | On the impossibility of constructing efficient key encapsulation and programmable hash functions in prime order groups[END_REF] hint that such programmable hash functions are hardly instantiable in prime-order DDH groups. While the multi-linear setting [START_REF] Freire | Programmable hash functions in the multilinear setting[END_REF] allows bypassing the impossibility results of [START_REF] Hanaoka | On the impossibility of constructing efficient key encapsulation and programmable hash functions in prime order groups[END_REF], it is not known to enable standard assumptions.

A natural idea is to replace the random-oracle-based key-homomorphic PRF of [START_REF] Naor | Distributed pseudo-random functions and KDCs[END_REF] by an LWE-based key-homomorphic PRF [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF][START_REF] Banerjee | New and improved key-homomorphic pseudo-random functions[END_REF]. However, analogously to Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], 4 we aim at an MCFE system that can be proved secure in a game where the adversary is allowed to corrupt senders adaptively. In order to deal with the adaptive corruption of senders, we thus turn to the adaptively secure distributed PRF proposed by Libert, Stehlé and Titiu [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]. The latter can be seen as instantiating the programmable hash function of Freire et al. [START_REF] Freire | Programmable hash functions in the multilinear setting[END_REF] in the context of homomorphic encryption (FHE). Their PRF maps an input x to A(x) • s p , where5 s ∈ Z n is the secret key and A(x) ∈ Z n×m q is derived from public matrices using the Gentry-Sahai-Waters FHE [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF]. More precisely, the matrix A(x) is obtained as the product of GSW ciphertexts dictated by the output of an admissible hash function [START_REF] Boneh | Secure identity based encryption without random oracles[END_REF] applied to the PRF input. The security proof of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] uses the property that, with noticeable probability, the input-dependent matrix A(x) is a GSW encryption of 1 for the challenge input x : namely, A(x ) is a matrix of of the form A(x ) = A•R +G, where G ∈ Z n×m q is the gadget matrix of Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] and R ∈ Z m×m is a small-norm matrix. At the same time, all evaluation queries are associated with a matrix A(x) consisting of a GSW encryption of 0 (i.e., a matrix A(x) = A • R, for a small-norm R ∈ Z m×m ). Then, the proof of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] appeals to the lossy mode of LWE [START_REF] Goldwasser | Robustness of the Learning with Errors assumption[END_REF] and replaces the uniform matrix A ∈ Z m×n q by a lossy matrix of the form  • C + E, where E ∈ Z m×n is a short integer matrix with Gaussian entries, C ∈ Z n1×n q is random, and  ∈ Z n1×m q has rank n 1 n. In all evaluation queries, the smallness of s ∈ Z n then ensures that the values A(x) • s p always reveal the same information about s, which amounts to the product C • s ∈ Z n1 q . Since A(x ) depends on G for the challenge input x , the function A(x ) • s p is in fact an injective function of s, meaning that it has high min-entropy.

Our MCFE scheme relies on the lossy mode of LWE in a similar way to [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], except that we add a Gaussian noise instead of using the Learning-With-Rounding technique [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF]. The i-th sender uses his secret key s i ∈ Z n to encrypt a short integer vector as

x i ∈ Z n0 as C i = G 0 • x i + A(t) • s i + noise ∈ Z m
q , where A(t) ∈ Z n×m q is a tag-dependent matrix derived as a product of GSW ciphertexts indexed by the bits of t and G 0 ∈ Z n0×m q is a gadget matrix for which the lattice Λ ⊥ (G 0 ) has a short public basis. A functional secret key for the vector y = (y 1 , . . . , y ) consists of

dk y = i=1 y i • s i ∈ Z n and allows computing G 0 •( i=1 y i •x i )+small ∈ Z m q from i=1 y i •C i ∈ Z m q and eventually recovering the linear function i=1 y i • x i ∈ Z n0 of X = [x 1 | . . . | x ] ∈ Z n0× q .
At this point, adapting the security proof of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] is non-trivial. We cannot rely on the DPRF of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] in a modular way as it would require a DPRF where partial evaluations are themselves pseudorandom so long as the adversary does not obtain the underlying secret key shares: in our setting, a challenge ciphertext contains a bunch of partial evaluations (one for each message slot) rather than a threshold recombination of such evaluations. We emphasize that, in the LWE-based DPRF of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], partial evaluations are not proven pseudorandom: [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] only proves -via a deterministic randomness extraction argument -the pseudorandomness of the final PRF value obtained by combining partial evaluations. They cannot apply (and neither can we) a randomness extractor to individual partial DPRF evaluations as it would destroy their key homomorphic property. Instead of relying on the pseudorandomness of partial evaluations, we actually prove a milder indistinguishability property which suffices for our purposes.

The first step is to make sure that all encryption queries will involve a lossy matrix

A(t) = R t • Â • C + E t , for small-norm R t ∈ Z m×m and E t ∈ Z m×n , so that honest senders' ciphertexts are of the form C i = G 0 •x i +R t • Â •C•s i +noise and thus leak nothing about s i ∈ Z n beyond C • s i ∈ Z n1
q . The difficulty arises in the challenge queries (i, t , x 0,i , x 1,i ), where A(t ) ∈ Z n×m q is not a lossy matrix and we must find a way to replace

C i = G 0 • x 0,i + A(t ) • s i + noise by C i = G 0 • x 1,i + A(t )
• s i + noise without the adversary noticing. In [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF],

the proof relies on a deterministic randomness extraction6 argument to extract statistically uniform bits from A(x ) • s p , which has high min-entropy when A(x ) is of the form A • R + G. Here, we do not see how to apply deterministic extractors in the proof while preserving the functionality of the MCFE scheme.

Our solution is to program the public parameters in such a way that, with noticeable probability, the challenge ciphertexts are generated for a matrix A(t ) ∈ Z n×m q of the form

A(t ) = R • A + G 0 • V = R • Â • C + G 0 • V + noise, (1)
for a statistically random matrix V ∈ Z n0×n q included in the public parameters. In the proof, the simulator generates a statistically uniform matrix U = [ V C ], where C ∈ Z n1×n q is used to build the lossy matrix A = Â • C + E, together with a trapdoor T U for Λ ⊥ (U). (The idea of embedding a trapdoor in the LWE secret of a lossy matrix is borrowed from [START_REF] Libert | All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE[END_REF]). Using T U , the simulator can sample a short matrix T ∈ Z n×n0 satisfying U • T = In 0 0 mod q, allowing it to define an alternative secret key s i = s i +T•(x 0,i -x 1,i ) ∈ Z n . As long as s i is sampled from a Gaussian distribution with sufficiently large standard deviation, s i and s i are negligibly far apart in terms of statistical distance (note that, as in [START_REF] Wee | Dual system encryption via predicate encoding[END_REF][START_REF] Benhamouda | CCA-secure inner-product functional encryption from projective hash functions[END_REF], the simulator can guess x 0,i -x 1,i upfront without affecting the polynomial running time of the reduction since we are in the middle of a purely statistical argument). The alternative secret keys {s i } i=1 further satisfy i=1 y i • s i = i=1 y i • s i for all legal functional key queries y = (y 1 , . . . , y ) made by the adversary. The definition of s i finally ensures that C • s i = C • s i mod q, meaning that s i is compatible with all encryption queries for which A(t) is lossy. From (1), the condition V • T = I n0 mod q then implies that the challenge ciphertext can be interpreted as an encryption of x 1,i since

C i = G 0 • x 1,i + A(t ) • s i + noise is statistically close to C i = G 0 • x 0,i + A(t ) • s i + noise.
We insist that our construction and proof are not merely obtained by plugging the DPRF of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] into the high-level design principle of [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]. In particular, we do not rely on the pseudorandomness of partial PRF evaluations, but rather prove a milder indistinguishability property in some transition in our sequence of games. To do this, we need to modify the proof of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], by introducing a matrix V and embedding a trapdoor in the matrix U obtained by stacking up V and the secret matrix C of the lossy mode of LWE.

In order to build a DMCFE system, we proceed analogously to [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] and combine two instances of our centralized MCFE scheme. The first one is only used to generate partial functional secret keys whereas the second one is used exactly as in the centralized system. As in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], we first have the senders run an interactive protocol allowing them to jointly generate public parameters for the two MCFE instances. At the end of this protocol (which may involve costly MPC operations, but is only executed once), each sender holds an encryption key ek i = (s i , t i ) consisting of encryption keys for the two underlying instances. In order to have the i-th sender S i generate a partial functional secret key dk f,i for a vector y = (y 1 , . . . , y ) , we exploit the fact that our centralized scheme allows encrypting vectors. Namely, the decryptor obtains from S i an MCFE encryption of the vector y i • s i ∈ Z n under the encryption key t i of the first instance.

Related Work

Functional encryption was implicitly introduced by Sahai and Waters in [START_REF] Sahai | Fuzzy identity-based encryption[END_REF], where they also constructed a scheme for threshold functions. Constructions of FE for point functions (known as identity-based encryption) [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Cocks | An identity based encryption scheme based on quadratic residues[END_REF] existed already, but were not viewed through the lens of FE until later. Subsequent works saw constructions for several more advanced functionalities such as inner product functions [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], Boolean formulas [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF][START_REF] Lewko | Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption[END_REF][START_REF] Okamoto | Fully secure functional encryption with general relations from the decisional linear assumption[END_REF][START_REF] Waters | Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[END_REF][START_REF] Lewko | New proof methods for attribute-based encryption: Achieving full security through selective techniques[END_REF], membership checking [START_REF] Boneh | Conjunctive, subset, and range queries on encrypted data[END_REF] and even finite state automaton [START_REF] Waters | Functional encryption for regular languages[END_REF]. Recently, the landscape of functional encryption improved considerably. Gorbunov et al. [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF] and Garg et al. [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] provided the first constructions of attribute-based encryption for all circuits; Goldwasser et al. [START_REF] Goldwasser | Reusable garbled circuits and succinct functional encryption[END_REF] constructed succinct simulation-secure single-key FE scheme for all circuits and also obtained FE for Turing machines [START_REF] Goldwasser | How to run Turing machines on encrypted data[END_REF]. In a breakthrough result, Garg et al. [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] designed indistinguishability-secure multi-key FE schemes for all circuits. However, while the constructions of [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] rely on standard assumptions, the assumptions underlying the other constructions [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF][START_REF] Goldwasser | How to run Turing machines on encrypted data[END_REF] are still ill-understood and have not undergone much cryptanalytic effort. FE for simple circuits. 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 (a functionality dubbed IPFE for "inner product functional encryption"). 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. Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] described two constructions under the Decision Diffie-Hellman (DDH) and Learning-With-Errors (LWE) assumptions, respectively. On the downside, 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. Namely, in the security game, the adversary chooses two vectors x 0 , x 1 ∈ D and expects to receive an encryption of one of these in the challenge phase. Selective security forces the adversary to declare x 0 , x 1 before seeing the public key and before obtaining any private key. Agrawal, Libert and Stehlé subsequently upgraded the constructions of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] so as to prove security against adaptive adversaries, which may choose x 0 , x 1 after having seen the public key and obtained a number of private keys. Agrawal et al. [START_REF] Agrawal | Fully secure functional encryption for inner products from standard assumptions[END_REF] described several IPFE schemes under well-established assumptions which include the standard Decision Diffie-Hellman (DDH) assumption, the Decision Composite Residuosity (DCR) assumption and the LWE assumption. Under the DCR and LWE assumptions, the schemes of [START_REF] Agrawal | Fully secure functional encryption for inner products from standard assumptions[END_REF] can evaluate both inner products over the integers and modulo a prime or composite number. The IPFE constructions of [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products from standard assumptions[END_REF] served as building blocks for FE schemes handling general functionalities [START_REF] Agrawal | Functional encryption for bounded collusions, revisited[END_REF] in the bounded collusion setting [START_REF] Sahai | Worry-free encryption: Functional encryption with public keys[END_REF][START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF]. Quite recently, the IPFE functionality [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products from standard assumptions[END_REF] was extended into FE schemes supporting the evaluation of quadratic functions over encrypted data [START_REF] Lin | Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs[END_REF][START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF]. The schemes of [START_REF] Lin | Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs[END_REF][START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF] are only proved secure against selective adversaries and they can only compute functions which have their output confined in a small interval. For the time being, the only known FE schemes that support the evaluation of more general functions than quadratic polynomials either require fancy tools like obfuscation [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] , or are restricted to bounded collusions [START_REF] Gorbunov | Functional encryption with bounded collusions via multi-party computation[END_REF][START_REF] Agrawal | Functional encryption for bounded collusions, revisited[END_REF].

Multi-Input and Multi-Client Functional Encryption. Goldwasser et al. [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] introduced the concept of multi-input functional encryption (MIFE). MIFE and MCFE are both more interesting in the secret-key setting than in the public-key setting, where much more information inevitably leaks about the data (see, e.g., [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF][START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]). Similarly to MCFE, MIFE operates over input vectors (X 1 , . . . , X ) comprised of messages sent by distinct parties, but without assigning a tag to ciphertexts: each user i can encrypt X i as C i = Encrypt(X i ) in such a way that anyone equipped with a functional secret key dk f for an -argument function f can compute f (X 1 , . . . , X n ) given multiple ciphertexts {C i = Encrypt(X i )} i=1 . Brakerski et al. [START_REF] Brakerski | Multi-input functional encryption in the private-key setting: Stronger security from weaker assumptions[END_REF] gave a transformation for constructing adaptively secure general-purpose MIFE schemes for a constant n from any general-purpose privatekey single-input scheme. Like MCFE, MIFE for general functionalities necessarily rely on indistinguishability obfuscation or multilinear maps, so that instantiations under standard assumptions are currently lacking. Under the SXDH assumption, Abdalla et al. [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF] managed to construct a MIFE scheme for the inner product functionality. In their scheme, each input slot encrypts a vector x i ∈ Z m p while each functional secret key sk y corresponds to a vector y ∈ Z •m p , where is the total number of slots. On input of encrypted data X = (x 1 , . . . , x ) such that x i is encrypted by sender i in the i-th slot, their multi-input inner product functionality computes X, y using sk y . Function-hiding MIFE schemes were described in [START_REF] Datta | Full-hiding (unbounded) multi-input inner product functional encryption from the k-linear assumption[END_REF][START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF]. Abdalla et al. [START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF] notably gave a generic single-input to multiinput transformation, which yields MIFE constructions for the inner product functionality under the DDH, LWE and DCR assumptions.

Besides syntactical differences, MCFE departs from MIFE in the amount of information leaked about plaintexts. The MIFE model [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] allows any slot of any ciphertext to be combined with any other slot of any other ciphertext. As soon as senders encrypt more than one ciphertext per slot, a given functional secret key can thus compute a much larger number of values. As discussed in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], this feature incurs a much more important information leakage, especially when many functional secret keys are given out. In contrast, the multi-client setting only allows functional secret keys to operate over ciphertexts that share the same tag. As long as tags are single-use (e.g., a timestamp), this allows clients to retain a more accurate control over the information leaked about their data.

The first MCFE realization was proposed in [START_REF] Gordon | Multi-input functional encryption[END_REF][START_REF] Goldwasser | Multi-input functional encryption[END_REF] and relies on the DDH assumption and on indistinguishability obfuscation to handle general circuits. The notion of aggregator-oblivious encryption (AOE) [START_REF] Shi | Privacy-preserving aggregation of time-series data[END_REF][START_REF] Chan | Privacy-preserving stream aggregation with fault tolerance[END_REF][START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF][START_REF] Benhamouda | A framework for privacy-preserving aggregation of time-series data[END_REF] allows an untrusted aggregator to compute sums of encrypted values without learning anything else about individual inputs. As such, AOE can be seen as a form of MCFE with single-key security (namely, the only key revealed to the aggregator is for the vector (1, 1, . . . , 1) ) for the evaluation of inner products. So far, all non-interactive AOE constructions [START_REF] Shi | Privacy-preserving aggregation of time-series data[END_REF][START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF][START_REF] Benhamouda | A framework for privacy-preserving aggregation of time-series data[END_REF] rely on the random oracle model.

The first efficient MCFE scheme with multi-key security was described by Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] who also introduced the concept of decentralized MCFE. Their schemes both rely on DDH-like assumptions in the random oracle model. At the time of writing, we are not aware of any (D)MCFE construction based on a well-studied assumption in the standard model.

Decentralized Functional Encryption.

The first examples of decentralized FE schemes were given in the context of attribute-based encryption (ABE) [START_REF] Chase | Multi-authority attribute based encryption[END_REF][START_REF] Chase | Improving privacy and security in multi-authority attributebased encryption[END_REF]. Lewko and Waters [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF] gave the first ciphertext-policy ABE where users' attributes may be certified by completely independent authorities. Boneh and Zhandry [START_REF] Boneh | Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation[END_REF] suggested distributed broadcast encryption systems, which dispense with the need for an authority handing out keys to registered users. Chandran et al. [START_REF] Chandran | Functional encryption: Decentralised and delegatable[END_REF] considered decentralized general-purpose FE using obfuscation. The decentralization of multi-client FE was first considered by Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] in a model where all clients run an interactive protocol to generate public parameters, but eliminate any interaction beyond the setup phase.

Abdalla et al. [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] described generic transformations providing DMCFE schemes from any MCFE system satisfying extra properties. While applying their compilers to [START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF] yields DMCFE schemes in the standard model, the resulting ciphertexts are not labeled. Without labels, the functionality leaks much more information about encrypted messages for a given functional key since there is no restriction on the way slots from different ciphertexts can be combined together (any slot from any ciphertext can be combined with any other slot from any other ciphertext). In this paper, our goal is to support labels, which is significantly more challenging and was only achieved in the random oracle model so far.

Chotard et al. [START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] gave a technique to remove the restriction that forces the adversary to make challenge queries for all uncorrupted ciphertext slots. Their technique upgrades any MCFE scheme satisfying our definition (which is the definition introduced in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] and called "pos-IND" security in [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF]) so as to prove security under a stronger definition where the adversary can obtain incomplete ciphertexts. Their technique builds on a "secret-sharing layer" (SSL) primitive which is only known to exist assuming pairings and random oracles as their SSL scheme [29, Section 4.2] is implicitly based on the Boneh-Franklin IBE [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]. Abdalla et al. [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] suggested a different technique to handle incomplete ciphertexts without using pairings, but they either require random oracles or they do not support labels (except in a model with static corruptions and selective security).

Chotard et al. [START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] also showed how to transform the ROM-based scheme from [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] in such a way that users are allowed multiple encryption queries for each slot-label pair. Their technique is not generic and only works for their DDH-based construction (as they mention in Section 6.2). Finally, [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF][START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] both give generic compilers from MCFE to DMCFE. Abdalla et al. [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] obtain DMCFE under adaptive corruptions, but they need to start from an MCFE which computes inner products modulo an integer L (instead of inner products over Z). Hence, their compiler does not imply DMCFE from LWE in the standard model. As it turns out, neither [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF][START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] implies MCFE with labels in the standard model from LWE (nor any standard assumption), even for the security definition of [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]. In a concurrent and independent work [START_REF] Abdalla | From single-input to multi-client inner product functional encryption[END_REF], Abdalla et al. provide a solution to this problem via a generic construction of labeled MCFE from single-input IPFE schemes evaluating modular inner products. While their construction satisfies a stronger security notion than ours (which allows multiple encryption queries for the same slot-label pair), their scheme of [1, Section 3] requires longer ciphertext than ours as each slot takes a full IPFE ciphertext of linear size in if is the number of slots.

In their construction and in ours, handling incomplete ciphertexts expands partial ciphertexts by a factor O( ). In our most efficient schemes, we still need to assume that the adversary obtains challenge ciphertexts for all clients as in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]. In Appendix A, we show that a variant of the compiler of Abdalla et al. [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] allows proving security in the standard model, even when the adversary is allowed to obtain incomplete challenge ciphertexts. Our compiler relies on pseudorandom functions satisfying a specific security definition in the multi-instance setting. The concurrent work of Abdalla et al. [START_REF] Abdalla | From single-input to multi-client inner product functional encryption[END_REF] achieves a similar result using any PRF satisfying a standard security definition.

Background

Lattices

For any q ≥ 2, we let Z q denote the ring of integers modulo q. For a vector

x ∈ R n denote x = x 2 1 + x 2 2 + • • • x 2 n and x ∞ = max i |x i |. If M is a matrix over R, then M := sup x =0 Mx x and M ∞ := sup x =0 Mx ∞
x ∞ . For a finite set S, we let U (S) denote the uniform distribution over S. If X and Y are distributions over the same domain, then ∆(X, Y ) denotes their statistical distance. Let Σ ∈ R n×n be a symmetric positive-definite matrix, and c ∈ R n . We define the Gaussian function on R n by ρ Σ,c (x) = exp(-π(xc) Σ -1 (xc)) and if Σ = σ 2 • I n and c = 0 we denote it by ρ σ . For an n dimensional lattice Λ ⊂ R n and for any lattice vector x ∈ Λ the discrete gaussian is defined ρ (Λ) . For an n-dimensional lattice Λ, we define η ε (Λ) as the smallest r > 0 such that ρ 1/r ( Λ \ 0) ≤ ε with Λ denoting the dual of Λ, for any ε ∈ (0, 1). For

Λ,Σ,c (x) = ρ Σ,c ρ Σ,c
a matrix A ∈ Z n×m q , we define Λ ⊥ (A) = {x ∈ Z m : A • x = 0 mod q} and Λ(A) = A • Z n + qZ m . For an arbitrary vector u ∈ Z n q , we also define the shifted lattice Λ u (A) = {x ∈ Z m : A • x = u mod q}.

Definition 2.1 (LWE).

Let m ≥ n ≥ 1, q ≥ 2 and α ∈ (0, 1) be functions of a security parameter λ. The LWE problem consists in distinguishing between the distributions (A, As + e) and U (Z m×n q × Z m q ), where A ∼ U (Z m×n q ), s ∼ U (Z n q ) and e ∼ D Z m ,αq . For an algorithm A : Z m×n q × Z m q → {0, 1}, we define:

Adv LWE q,m,n,α (A) = |Pr[A(A, As + e) = 1] -Pr[A(A, u) = 1| ,
where the probabilities are over

A ∼ U (Z m×n q ), s ∼ U (Z n q ), u ∼ U (Z m q
) and e ∼ D Z m ,αq and the internal randomness of A. We say that LWE q,m,n,α is hard if, for any ppt algorithm A, the advantage Adv LWE q,m,n,α (A) is negligible.

Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] described a trapdoor mechanism for LWE. Their technique uses a "gadget" matrix G ∈ Z n×w q , with w = n log q, for which anyone can publicly sample short vectors x ∈ Z w such that G • x = 0.

Lemma 2.2 ([58, Section 5]). Let m ≥ 3n log q.

There exists a ppt algorithm GenTrap that outputs a statistically uniform matrix A ∈ Z n×m q , together with a trapdoor

T A ∈ Z m×m for Λ ⊥ (A), such that max j tj ≤ O( √ n log q)
, where tj are the corresponding Gram-Schmidt vectors.

It is known [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] that, for any u ∈ Z n q , a trapdoor for

A ∈ Z n×m q allows sampling from D Λ u (A),s•ω √ log m for s = O( √ n log q). Since η 2 -m Λ ⊥ (A) ≤ max j tj • ω( log m) ≤ s • ω( log m) for large enough s = O( √ n log q), the magnitude of a vector x sampled from D Λ u (A),s•ω √ log m , is bounded by x ≤ s √ m • ω( √ log m).
Remark 2.3. For m ≥ 3n log q, we can thus sample a statistically uniform matrix A from Z n×m q together with a trapdoor, which allows finding small solutions of

A • x = u mod q, with x ≤ s √ m • ω( √ log m) = O( √ mn log q) • ω( √ log m).
We sometimes rely on the so-called "noise flooding" technique via the next lemma.

Lemma 2.4 ([40, Lemma 3]).

Let y ∈ Z m . The statistical distance between D Z m ,σ and y

+ D Z m ,σ is at most ∆ (D Z m ,σ , y + D Z m ,σ ) ≤ m • y ∞ σ .

Lemma 2.5 ([36, Theorem 4.1]).

There is a ppt algorithm that, given a basis

B of an n-dimensional lattice Λ = L(B), a parameter s > B • ω( √ log n)
, and a center c ∈ R n , outputs a sample from a distribution statistically close to D Λ,s,c .

Admissible Hash Functions

Admissible hash functions were introduced by Boneh and Boyen [START_REF] Boneh | Secure identity based encryption without random oracles[END_REF] as a combinatorial tool for partitioning-based security proofs for which Freire et al. [START_REF] Freire | Programmable hash functions in the multilinear setting[END_REF] gave a simplified definition. Jager [START_REF] Jager | Verifiable random functions from weaker assumptions[END_REF] considered the following generalization in order to simplify the analysis of reductions under decisional assumption.

Definition 2.6 ([48]

). Let (λ), L(λ) ∈ N be functions of a security parameter λ ∈ N. Let AHF : {0, 1} → {0, 1} L be an efficiently computable function. For every K ∈ {0, 1, ⊥} L , let the partitioning function P K : {0, 1} → {0, 1} such that

P K (X) := 0 if ∀i ∈ [L] (AHF(X) i = K i ) ∨ (K i =⊥) 1 otherwise
We say that AHF is a balanced admissible hash function if there exists an efficient algorithm AdmSmp(1 λ , Q, δ) that takes as input Q ∈ poly(λ) and a non-negligible δ(λ) ∈ (0, 1] and outputs a key K ∈ {0, 1, ⊥} L such that, for all X (1) , . . . , X (Q) , X ∈ {0, 1} such that X ∈ {X (1) , . . . , X (Q) }, we have

γ max (λ) ≥ Pr K P K (X (1) ) = • • • = P K (X (Q) ) = 1 ∧ P K (X ) = 0 ≥ γ min (λ),
where γ max (λ) and γ min (λ) are functions such that

τ (λ) = γ min (λ) • δ(λ) - γ max (λ) -γ min (λ) 2 is a non-negligible function of λ.
Intuitively, the condition that τ (λ) be non-negligible requires γ min (λ) to be noticeable and the difference of γ max (λ) -γ min (λ) to be small. It is known [START_REF] Jager | Verifiable random functions from weaker assumptions[END_REF] that balanced admissible hash functions exist for , L = Θ(λ).

Theorem 2.7 ([48, Theorem 1]). Let (C ) ∈N be a family of codes

C : {0, 1} → {0, 1} L with minimal distance c • L for some constant c ∈ (0, 1/2).
Then, (C ) ∈N is a family of balanced admissible hash functions. Furthermore,

AdmSmp(1 λ , Q, δ) outputs a key K ∈ {0, 1, ⊥} L for which η = ln(2Q+Q/δ) -ln((1-c))
components are not ⊥ and

γ max = 2 -η , γ min = 1 -Q(1 -c) η • 2 -η , so that τ = (2δ -(2δ + 1) • Q • (1 -c) η )/2 η+1 is a non-negligible function of λ.

Lemma 2.8 ([50, Lemma 8],[6, Lemma 28]). Let

K ← AdmSmp(1 λ , Q, δ),
an input space X and the mapping γ that maps a (Q + 1)-uple (X , X 1 , . . . , X Q ) in X Q+1 to a probability value in [0, 1], given by:

γ(X , X 1 , . . . , X Q ) := Pr K P K (X (1) ) = • • • = P K (X (Q) ) = 1 ∧ P K (X ) = 0 .
We consider the following experiment where we first execute the PRF security game, in which the adversary eventually outputs a guess b ∈ {0, 1} of the challenger's bit b ∈ {0, 1} and wins with advantage ε. We denote by X ∈ X the challenge input and X 1 , . . . , X Q ∈ X the evaluation queries. At the end of the game, we flip a fair random coin b ← U ({0, 1}). If the condition

P K (X (1) ) = • • • = P K (X (Q) ) = 1 ∧ P K (X ) = 0 is satisfied we define b = b. Oth- erwise, we define b = b . Then, we have | Pr[b = b] -1/2| ≥ γ min • ε -γmax-γmin 2
, where γ min and γ max are the maximum and minimum of γ(X) for any X ∈ X Q+1 .

Randomness Extraction

The Leftover Hash Lemma was used by Agrawal et al. [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] to re-randomize matrices over Z q by multiplying them with small-norm matrices.

Lemma 2.9 ([6]

). Let integers m, n such that m > 2n • log q, for some prime q > 2. Let A, U ← U (Z n×m q ) and R ← U ({-1, 1} m×m ). The distributions (A, AR) and (A, U) are within 2 -Ω(n) statistical distance.

Multi-Client Functional Encryption

We recall the syntax of multi-client functional encryption as introduced in [START_REF] Gordon | Multi-input functional encryption[END_REF]. Definition 2.10. A multi-client functional encryption (MCFE) scheme for a message space M and tag space T is a tuple (Setup, Encrypt, DKeygen, Decrypt) of efficient algorithm with the following specifications:

Setup(cp,
f : M → R, if C t,i ← Encrypt(ek i , x i , t) for all i ∈ [ ] and dk f ← DKeygen(msk, f ), we have Decrypt dk f , t, C t = (C t,1 , . . . , C t, ) = f (x) with overwhelming probability.
We now recall the security definition given in [START_REF] Gordon | Multi-input functional encryption[END_REF] for an adaptively secure MCFE, and then we will give the definition that we use in this work. These two definitions are in fact equivalent.

Definition 2.11 (IND-sec).

For an MCFE scheme with senders, consider the following game between an adversary A and a challenger C. The game involves a set HS of honest senders (initialized to HS := [ ]) and a set CS (initialized to CS := ∅) of corrupted senders.

Initialization:

The challenger C chooses cp and runs (mpk, msk, {ek i } i=1 ) ← Setup(cp, 1 ). Then, it chooses a random bit b ← {0, 1} and gives the master public key mpk to the adversary Encryption queries: The adversary A can adaptively make encryption queries QEncrypt(i, x 0 , x 1 , t), to which the challenger replies with Encrypt(ek i , x b , t). For any given pair (i, t), only one query is allowed and subsequent queries involving the same (i, t) are ignored.

Functional decryption key queries: The adversary can adaptively obtain functional decryption keys by making queries of the form QDKeygen(f ).

The challenger returns dk f ← DKeygen(msk, f ). Corruption queries: For any user i ∈ HS, the adversary can adaptively make queries QCorrupt(i), to which the challenger replies with ek i and updates HS and CS by setting CS := CS ∪ {i} and HS := HS \ {i}. Finalize: The adversary makes its guess b ∈ {0, 1}; A wins the game if β = b, where β is defined to be β := b except in the following situations.

1. An encryption query QEncrypt(i, x 0 , x 1 , t) has been made for an index i ∈ CS with x 0 = x 1 . 2. For some label t, an encryption query QEncrypt(i, x 0 i , x 1 i , t) has been asked for i ∈ HS, but encryption queries QEncrypt(j, x 0 j , x 1 j , t) have not been asked for all j ∈ HS. 3. For a label t and some function f queried to QDKeygen, there exists a pair of vectors (x 0 , x 1 ) such that f (x 0 ) = f (x 1 ), where

-x 0 i = x 1 i for all i ∈ CS; -QEncrypt(i, x 0 i , x 1 i , t
) have been asked for all i ∈ HS. In any of the above cases, A's output is replaced by a random β ← U ({0, 1}).

An MCFE scheme provides IND security if, for any efficient adversary A, we have Adv

IND (A) := |Pr[β = 1 | b = 1] -Pr[β = 1 | b = 0]| ∈ negl(λ).
In the following, it will be convenient to work with the following security definition, which is equivalent to Definition 2.11. 3. For the challenge tag t , a challenge query CQEncrypt(i, x 0 i , x 1 i , t ) has been asked for some i ∈ HS, but challenge queries CQEncrypt(j, x 0 j , x 1 j , t ) have not been asked for all j ∈ HS. 4. For the challenge tag t and some function f queried to QDKeygen, there exists a pair of vectors (x 0 , x 1 ) such that f (x 0 ) = f (x 1 ), where -

Definition 2.12 (1-challenge IND-sec). For an MCFE scheme with senders, we consider the following game between an adversary

x 0 i = x 1 i for all i ∈ CS; -CQEncrypt(i, x 0 i , x 1 i , t
) have been asked for all i ∈ HS. If any of these events occurred, A's output is overwritten by β ← U ({0, 1}).

We say that an MCFE scheme provides 1Ch-IND security if, for any efficient adversary A, we have

Adv 1Ch-IND (A) := Pr[β = b] -1 2 ∈ negl(λ).
In Appendix B, we show that 1Ch-IND security implies IND security. We also note that condition 2 of "Finalize" could be:

2'. Both QEncrypt(i, x, t ) and CQEncrypt(i, x 0 i , x 1 i , t ) have been made for an index i and the challenge label t , such that

x 0 i = x 1 i
This allows the adversary to make both an encryption query QEncrypt(i, x, t ) and a challenge query CQEncrypt(i, x 0 i , x 1 i , t ) where x 0 i = x 1 i . In Proposition B.2 in Appendix, we show that replacing condition 2 by condition 2 does not make the adversary any stronger.

Our first construction is proven secure under Definition 2.12. Abdalla et al. [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] and Chotard et al. [START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] independently showed constructions that can be proven secure in the sense of a stronger definition which eliminates restriction 3 from the "Finalize" stage. In Appendix A, we show that a variant of the compiler of [2, Section 4.2] is secure in the standard model. Recently, Abdalla et al. [START_REF] Abdalla | From single-input to multi-client inner product functional encryption[END_REF] independently obtained a similar result. While their PRF-based compiler [START_REF] Abdalla | From single-input to multi-client inner product functional encryption[END_REF] can rely on any PRF, we obtain a tighter reduction using a specific PRF described in [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]. Chotard et al. [START_REF] Chotard | Multi-client functional encryption with repetition for inner product[END_REF] additionally show how to enable repetitions by allowing multiple encryption queries for the same pair (i, t). However, they need random oracles for this purpose.

Decentralized Multi-Client Functional Encryption

We use the same syntax as Chotard et al. [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF] with the difference that we explicitly assume common public parameters cp. As in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], we assume that each function f can be injectively encoded as a tag t f (called "label" in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]) taken as input by the partial functional key generation algorithm. Definition 2.13. For a message space M and tag space T , a decentralized multi-client functional encryption (DMCFE) scheme between senders {S i } i=1 and a functional decryptor FD is specified by the following components. For simplicity, we assume that mpk is included in all secret keys and encryption keys, as well as in (partial) functional decryption keys. We also assume that a description of f is included in (partial) functional decryption keys.

Setup(cp, 1 ) : This is an interactive protocol between the senders {S

i } i=1 ,
Correctness. For any λ ∈ N, any (mpk, 1. An encryption query QEncrypt(i, x 0 i , x 1 i , t) has been made for an index i ∈ CS with x 0 i = x 1 i . 2. For some label t, an encryption query QEncrypt(i, x 0 i , x 1 i , t) has been asked for i ∈ HS, but encryption queries QEncrypt(j, x 0 j , x 1 j , t) have not been asked for all j ∈ HS.

{sk i } i=1 , {ek i } i=1 ) ← Setup(cp,
3. For a tag t and some function f queried to QDKeygen(i, .) for all i ∈ HS, there exists a pair of vectors (x 0 , x 1 ) such that f (x 0 ) = f (x 1 ), where x 0 i = x 1 i for all i ∈ CS; -QEncrypt(i, x 0 i , x 1 i , t) have been asked for all i ∈ HS. If any of these events occurred, A's output is overwritten by β ← U ({0, 1}).

We say that a DMCFE scheme provides IND security if, for any efficient adversary A, we have Adv

IND (A) := |Pr[β = 1 | b = 1] -Pr[β = 1 | b = 0]| ∈ negl(λ).
The above definition captures adaptive corruptions in that the QCorrupt(•) oracle may be invoked at any time during the game. In the static corruption setting, all queries to QCorrupt(•) should be made at once before the initialization phase. In this case, the sets HS and CS are thus determined before the generation of (mpk, {sk i } i=1 , {ek i } i=1 ). We denote by sta-IND-sec the latter security game.

Our scheme of Section 4 will be proven secure under static corruptions. We insist that only corruptions are static: the encryption oracle can be queried on adaptively chosen messages (x 0 , x 1 ), which is stronger than the selective security game, where the challenge messages have to be declared upfront.

Our MCFE Scheme for Linear Functions

The scheme encrypts

x i ∈ Z n0 as a vector C t,i = G 0 • x i + A(τ ) • s i + e i ,
where G 0 is a gadget matrix; τ = AHF(t) ∈ {0, 1} L is an admissible hash of the tag t; and e i is a Gaussian noise. This is done in a way that a functional secret key s y = i=1 y i • s i ∈ Z n allows computing i=1 y i • x i from {C t,i } i=1 by using the public trapdoor of the lattice Λ ⊥ (G 0 ).

We derive A(τ ) from a set of 2L public matrices {A i,0 , A i,1 } L i=1 and an additional matrix V ∈ Z n0×n q . Like [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], our proof interprets each

A i,b ∈ Z n×m q as a GSW ciphertext A i,b = A•R i,b +µ i,b •G, where R i,b ∈ {-1, 1} m×m , µ i,b ∈ {0, 1} and G ∈ Z n×m q
is the gadget matrix of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. Then, we homomorphically compute

A(τ ) as an FHE ciphertext A • R τ + ( L i=1 µ i,τ [i] ) • G, for some small-norm R τ ∈ Z m×m , which is in turn multiplied by G -1 (V • G 0 ) in such a way that A(τ ) = A•R τ +( L i=1 µ i,τ [i] )•(V •G 0 ). Via a careful choice of {µ i,b } i∈[L],b∈{0,1}
, the properties of admissible hash functions imply that L i=1 µ i,x [i] vanishes in all encryption queries but evaluates to 1 on the challenge tag τ . In order to prevent the encryption oracle from leaking too much about s i ∈ Z n , we proceed as in [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] and replace the random A ∈ Z n×m q by a lossy matrix

A =  • C + E, where  ← U (Z n1×m q ), C ← U (Z n1×n q
) and for a small-norm E ∈ Z m×n . Our construction and proof depart from [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] in that we use an additional multiplication by G -1 (V • G 0 ) in order to introduce a matrix V ∈ Z n0×n q in the expression of A(τ ). In addition, unlike [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], we do not rely on a randomness extraction argument to exploit the entropy of A(τ ) • s i + e i in the challenge phase. Instead, we use a trapdoor for the matrix U = [ V C ] to "equivocate" the challenge ciphertexts and explain them as an encryption of x 1,i instead of x 0,i .

Another difference with [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] is that the product A(τ ) of GSW ciphertexts {A i,τ [i] } L i=1 is evaluated in a sequential manner 7 (as in the "right-spine" PRF construction of [START_REF] Banerjee | New and improved key-homomorphic pseudo-random functions[END_REF]) in order for the noise matrix R τ to retain small entries.

We note that, as was suggested by [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Section 4.3] in the context of distributed PRFs, a technique due to Yamada [START_REF] Yamada | Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques[END_REF] can be used to compute A(τ ) as a function of Θ(log 2 λ) (instead of Θ(λ))) public matrices. For simplicity, we chose to describe the scheme using public parameters containing a linear number of matrices here.

Description

In the following description, we assume public parameters

cp := λ, max , X, Y, n 0 , n 1 , n, m, α, α 1 , σ, t , L, q, AHF ,
consisting of a security parameter λ and the following quantities:

-(X, Y, max , n 0 , n 1 , n, m), which are all in poly(λ)

X = 1, n 1 = λ d , q = 2 λ d-1 , α = 2 - √ λ , α 1 = 2 -λ d-1 +d log λ , n 0 = o(λ d-2 ), n = O(λ 2d-1 ), σ = 2 λ d-1 -2λ and n 0 • max = O(λ d-2
) where d is a constant; for instance d = 3 works asymptotically. -The description of a tag space T = {0, 1} t , for some t ∈ poly(λ), such that tags may be arbitrary strings (e.g., time period numbers or dataset names). -The description of a balanced admissible hash function AHF : {0, 1} t → {0, 1} L , for a suitable L ∈ Θ(λ). -The message space will be M = [-X, X] n0 , for some n 0 ∈ poly(λ).

-Integers n, n 0 , n 1 , m ∈ poly(λ) satisfying the conditions m > 2n • log q and n > 3 • (n 0 + n 1 ) • log q . -A real α > 0 and a Gaussian parameter σ > 0, which specifies an interval

[-β, β] = [-σ √ n, σ √ n]
where the coordinates of users' secret keys will live (with probability exponentially close to 1).

Letting ∈ poly(λ), with ≤ max , be the number of users, our function space is the set of all functions f y : Z n0× → Z n0 indexed by an integer vector y ∈ Z of infinity norm y ∞ < Y .

We define G 0 ∈ Z n0×m q to be the gadget matrix

G 0 = [I n0 ⊗ (1, 2, 4, . . . , 2 log q ) | 0 n0 | . . . | 0 n0 ] ∈ Z n0×m q
where the product I n0 ⊗ (1, 2, 4, . . . , 2 log q ) is padded with m -n 0 • log q zero columns. We similarly denote by G ∈ Z n×m q the gadget matrix of rank n:

G = [I n ⊗ (1, 2, 4, . . . , 2 log q ) | 0 n | . . . | 0 n ] ∈ Z n×m q .
Our MCFE construction goes as follows.

7

In [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF], the multiplication of ciphertexts

{A i,τ [i] } L i=1 was computed in a parallel fashion A0 • L i=1 G -1 (A i,τ [i]
) because their initial proof required the matrices {A i,b } i,b to be generated in such a way that G -1 (A i,b ) was invertible over Zq.

Setup(cp, 1 ): On input of cp and a number of users , do the following.

Choose random matrices

A i,b ← U (Z n×m q ), for each i ∈ [L], b ∈ {0, 1}. 2. Choose a uniformly random matrix V ← U (Z n0×n q ). 3. For each i ∈ [ ], sample s i ← D Z n ,σ and define ek i = s i ∈ Z n .
Output the master secret key msk := {ek i } i=1 and the public parameters

mpk := cp, V, {A i,0 , A i,1 ∈ Z n×m q } L i=1 .
DKeygen(msk, f y ) : Given the master secret key msk := {ek i } i=1 and a linear function f y : Z n0× → Z n0 defined by an integer vector y = (y 1 , . . . , y ) ∈ Z which maps an input

X = [x 1 | . . . | x ] ∈ Z n0× to f y (X) = X • y ∈ Z n0
, parse each ek i as a vector s i ∈ Z n . Then, compute and output the functional secret key dk y := (y, s y ), where

s y = i=1 s i • y i ∈ Z n . Encrypt(ek i , x i , t) : Given ek i = s i ∈ Z n , x i ∈ [-X, X] n0 , and t ∈ {0, 1} t , 1. Compute τ = AHF(t) ∈ {0, 1} L and parse it as τ = τ [1] . . . τ [L]. 2. Define W = G 0 • V ∈ Z m×n q and compute A(τ ) = A L,τ [L] • G -1 A L-1,τ [L-1] • G -1 . . . A 2,τ [2] • G -1 A 1,τ [1] • G -1 (W ) ∈ Z n×m q . ( 2
)
3. Sample a noise vector e i ← D Z m ,αq . Then, compute and output

C t,i = G 0 • x i + A(τ ) • s i + e i ∈ Z m q .
Decrypt(dk y , t, C t ) : On input of a functional secret key dk y = (y, s y ) for a vector y = (y 1 , . . . , y ) ∈ [-Y, Y ] , a tag t ∈ {0, 1} t , and an -vector of ciphertexts C t = (C t,1 , . . . , C t, ) ∈ (Z m q ) , conduct the following steps.

1. Compute τ = AHF(t) ∈ {0, 1} L and parse it as

τ = τ [1] . . . τ [L]. 2. Compute A(τ ) ∈ Z n×m q as per (2). 3. Compute f t,y = i=1 y i • C t,i -A(τ ) • s y mod q.
4. Interpret f t,y ∈ Z m q as a vector of the form f t,y = G 0 • z + ẽ mod q, for some error vector ẽ ∈ [-B, B] m . Using the public trapdoor of Λ ⊥ (G 0 ), compute and output the underlying vector z

∈ [-• X • Y, • X • Y ] n0 .
The following lemma is proved in Appendix C.1.

Lemma 3.1 (Correctness). Assume that αq

= ω( √ log ), Y • • αq • log q < q/2 and • X • Y < q/2. Then, for any (mpk, msk, {ek i } i=1 ) ← Setup(cp, 1 λ ), any message X = [x 1 | • • • |x ] ∈ [-X, X] n0× , any y ∈ [-Y, Y ]
, any tag t ∈ {0, 1} t , algorithm Decrypt(dk y , t, C t ) outputs X • y ∈ Z n0 with probability exponentially close to 1, where C t,i ← Encrypt(ek i , x i , t) and dk y ← DKeygen(msk, f y ).

Security

We now prove the security of the scheme in the sense of Definition 2.12 (and thus Definition 2.11 modulo some loss of tightness in the reduction).

For the current parameters n 1 = λ d , q = 2 λ d-1 , and α 1 = 2 -λ d-1 +d log λ , α 1 q = Ω( √ n 1 ), we know from [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] that LWE q,n1,α1 is at least as hard as GapSVP γ , with γ = Õ(n 1 /α 1 ) = Õ(2 λ d-1 ). The best known algorithms [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF] for solving GapSVP γ run in 2 Õ( n 1 log γ ) , which for our parameters is 2 Õ(λ) .

Theorem 3.2. The above MCFE schemes provides adaptive security under the LWE q,m,n1,α1 assumption.

Proof. The proof considers a sequence of games. In each game, we denote by W i the event that b = b. For each i, the adversary's advantage function in Game i is

Adv i (A) := | Pr[b = b] -1/2| = 1 2 • | Pr[b = 1 | b = 1] -Pr[b = 1 | b = 0]|.
Game 0 : This is the real security game. We denote by t the tag of the challenge phase while t (1) , . . . , t (Q) are the tags involved in encryption queries. Namely, for each j ∈ [Q], t (j) stands for the j-th distinct tag involved in an encryption query. Since up to encryption queries (i, x i , t) are allowed for each tag t, the adversary can make a total of • Q encryption queries. The game begins with the challenger initially choosing encryption keys {ek i } i=1 by sampling

ek i = s i ← D Z n ,σ for each i ∈ [ ].
In addition, the challenger flips a fair coin b ← U ({0, 1}) which will determine the response to challenge queries. At each corruption query i ∈ [ ], the adversary obtains ek i and the challenger updates a set CS := CS ∪ {i}, which is initially empty. At each encryption query (i, x (j) i , t (j) ), the challenger samples e (j)

i ← D Z m ,αq and returns

C t,i = G 0 • x (j) i + A(τ (j) ) • s i + e (j) i ∈ Z m q ,
where τ (j) = AHF(t (j) ). In the challenge phase, the adversary A chooses a fresh tag t and two vectors of messages

X 0 = [x 0,1 | . . . | x 0, ] ∈ [-X, X] n0× and X 1 = [x 1,1 | . . . | x 1, ] ∈ [-X
, X] n0× subject to the constraint that, for any private key query y ∈ [-Y, Y ] made by A, we must have X 0 • y = X 1 • y over Z. In addition, the invariant that x 0,i = x 1,i for any i ∈ CS must be satisfied at any time during the game. In response to a challenge query (i, x 0,i , x 1,i , t ), the challenger generates a challenge ciphertext C t ,i , where Game 1 : This game is identical to Game 0 except for the following changes. First, the challenger runs K ← AdmSmp(1 λ , Q, δ) to generate a key K ∈ {0, 1, ⊥} L for a balanced admissible hash function AHF : {0, 1} t → {0, 1} L . When the adversary halts and outputs b ∈ {0, 1}, the challenger checks if the conditions

C t ,i = G 0 • x b,i + A(τ ) • s i + e i , (3)
P K (t (1) ) = • • • = P K (t (Q) ) = 1 ∧ P K (t ) = 0 (
| Pr[W 1 ] -1/2| ≥ γ min • Adv(A) - 1 2 • (γ max -γ min ) = τ,
where τ (λ) is a noticeable function.

Game 2 : In this game, we modify the generation of mpk in the following way. Initially, the challenger samples a uniformly random matrix

A ← U (Z n×m q ). Next, for each i ∈ [L], it samples R i,0 , R i,1 ← U ({-1, 1}) m×m and defines {A i,0 , A i,1 } L i=1
as follows for all i ∈ [L] and j ∈ {0, 1}:

A i,j := A • R i,j if (j = K i ) ∧ (K i =⊥) A • R i,j + G if (j = K i ) ∨ (K i =⊥) (5)
Since A ∈ Z n×m q was chosen uniformly, the Leftover Hash Lemma ensures that {A i,0 , A i,1 } L i=1 are statistically independent and uniformly distributed over

Z n×m q . It follows that | Pr[W 2 ] -Pr[W 1 ]| ≤ L • 2 -λ .
We note that, at each encryption query (i, x (j) i , t (j) ), the admissible hash function maps t (j) to τ (j) = AHF(t (j) ), which is itself mapped to a GSW encryption

A(τ (j) ) = A • R τ (j) + ( L i=1 µ i ) • W , (6)
of a product L i=1 µ i , for some small norm matrix R τ (j) ∈ Z m×m , where

µ i := 0 if (AHF(t (j) ) i = K i ) ∧ (K i =⊥) 1 if (AHF(t (j) ) i = K i ) ∨ (K i =⊥)
If conditions (4) are satisfied, at each encryption query (i, x (j) i , t (j) ), the admissible hash function ensures that τ (j) = AHF(t (j) ) satisfies

A(τ (j) ) = A • R τ (j) ∀j ∈ [Q], (7)
for some small norm R τ (j) ∈ Z m×m . Moreover, the challenge tag t is mapped to an L-bit string τ = AHF(t ) such that

A(τ ) = A • R τ + W = A • R τ + V • G 0 (8)
Game 3 : In this game, we modify the distribution of mpk and replace the uniform matrix A ∈ Z n×m q by a lossy matrix such that

A = Â • C + E ∈ Z m×n q , ( 9
)
where  ← U (Z n1×m q ), C ← U (Z n1×n q

) and E ← D Z m×n ,α1q , for n 1 n. The matrix (9) is thus "close" to a matrix  • C of much lower rank than n. Under the LWE assumption in dimension n 1 with error rate α 1 , this change should not significantly affect A's behavior and a straightforward reduction

B shows that | Pr[W 3 ] -Pr[W 2 ]| ≤ n • Adv LWEq,m,n 1 ,α 1 B (λ)
, where the factor n comes from the use of an LWE assumption with n secrets. Game 4 : In this game, we modify the encryption oracle. At each encryption query (i, x (j) i , t (j) ), the challenger generates the ciphertext by computing:

C t,i = G 0 • x (j) i + R τ (j) • Â • C • s i + e (j) i ∈ Z m q , ( 10
)
and for each challenge query (i, x 0,i , x 1,i , t ) the challenger replies with:

C t ,i = G 0 • x b,i + R τ • Â • C + G 0 • V • s i + e i ∈ Z m q (11) where e (j)
i ← D Z m ,αq and e i ← D Z m ,αq . The only difference between Game 3 and Game 4 is thus that the terms R τ

(j) • E • s i + e (j) i and R τ • E • s i + e i are
replaced by e (j) i and e i respectively, at each encryption or challenge query. However, the smudging lemma (Lemma 2.4) ensures that the two distributions are statistically close as long as α is sufficiently large with respect to α 1 and σ. Concretely, Lemma 3. [START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF], the challenger encrypts a linear combination of X 0 and X 1 . It initially chooses a uniformly random γ ← U (Z q ) and, at each challenge query (i, x 0,i , x 1,i , t ), computes C t ,i as

3 implies | Pr[W 4 ] -Pr[W 3 ]| ≤ • (Q + 1) • 2 -Ω(λ) .
C t ,i = G 0 • (1 -γ) • x b,i + γ • x 1-b,i + R τ • Â • C + G 0 • V • s i + e i ,
with e i ← D Z m ,αq , for all i ∈ [ ]. Lemma 3.4 shows that Game 4 and Game 5 are negligibly far part as

| Pr[W 5 ] -Pr[W 4 ]| ≤ 2 -Ω(λ) .
In Game 5 , we clearly have Pr[W 5 ] = 1/2 since the challenge ciphertexts (C t,1 , . . . , C t, ) reveal no information about b ∈ {0, 1}. Lemma 3.3. Let R τ ∈ Z m×m be as in equation [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]. Let E ← D Z m×n ,α1q and

s ← D Z n ,σ . If α 1 q = ω( √ log n), σ = ω( √ log n) and α ≥ 2 λ •L•m 4 •n 3/2 •α 1 •σ, we have the statistical distance upper bound ∆ D Z m ,αq , R τ • E • s + D Z m ,αq ≤ 2 -λ . (The proof is given in Appendix C.2.) Lemma 3.4. We have | Pr[W 5 ] -Pr[W 4 ]| ≤ 2 -Ω(λ) .
Proof. To prove the result, we resort to a technique of guessing in advance the difference X 1-b -X b , which was previously used in [START_REF] Wee | Dual system encryption via predicate encoding[END_REF][START_REF] Benhamouda | CCA-secure inner-product functional encryption from projective hash functions[END_REF] and can be seen as complexity leveraging with respect to a statistical argument. We consider the following variants of Game 4 and Game 5 , respectively.

We define Game 4 and Game 5 simultaneously by using an index k ∈ {4, 5}:

Game k : This game is like Game k with one difference in the setup phase. To generate mpk, the challenger B generates a statistically uniform U ∈ Z (n0+n1)×n q with a trapdoor T U for the lattice Λ ⊥ (U). Then, B parses U as

U = V C ∈ Z (n0+n1)×n q ,
where V ∈ Z n0×n q and C ∈ Z n1×n q are statistically independent and uniform over Z q . Next, it computes

A =  • C + E ∈ Z m×n q , where  ← U (Z n1×m q
) and E ← D Z m×n ,α1q . The obtained matrix A ∈ Z n×m q is then used to generate {A i,j } i∈[L],j∈{0,1} as per [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF]. The upper part

V ∈ Z n0×n q of U is included in mpk, the distribution of which is statistically close to that of Game k : we indeed have | Pr[W k ] -Pr[W k ]| ≤ 2 -Ω(λ) .
We do the same as above and define Game 4 and Game 5 simultaneously by using an index k ∈ {4, 5}: Game k : This game is identical to Game k with the following difference. At the outset of the game, the challenger randomly chooses ∆X ← U ([-2X, 2X] n0× ) as a guess for the difference X 1-b -X b between the challenge messages X 0 , X 1 . In the challenge phase, the challenger checks if ∆X = X 1-b -X b . If not, it aborts and replaces A's output b with a random bit b ← U ({0, 1}).

If the guess for X 1-b -X b was successful (we call Guess this event), the challenger proceeds exactly as it did in Game k .

Since the choice of ∆X ← U ([-2X, 2X] n0× ) is completely independent of A's view, we clearly have Pr[Guess] = 1/(4X) n0 . Since Game 4 is identical to Game 4 when Guess occurs, this implies Adv 4 (A) = (4X) n0 • Adv 4 (A). Indeed,

Adv 4 (A) := 1 2 • | Pr[b = 1 | b = 1, Guess] • Pr[Guess] + 1 2 • Pr[¬Guess] -Pr[b = 1 | b = 0, Guess] • Pr[Guess] - 1 2 • Pr[¬Guess]| = 1 2 • Pr[Guess] • | Pr[b = 1 | b = 1, Guess] -Pr[b = 1 | b = 0, Guess]| = Pr[Guess] • Adv 4 (A) = 1 (4X) n0 • Adv 4 (A)
and we can similarly show that Adv 5 (A) = (4X) n0 • Adv 5 (A).

Game 5 : This game is identical to Game 4 except that encryption keys {ek i } i=1 are replaced by alternative encryption keys {ek i } i=1 , which are generated as follows. After having sampled ek i = s i ← D Z n ,σ for all i ∈ [ ], the challenger B chooses γ ← U (Z q ) and uses the trapdoor T U for Λ ⊥ (U) to sample a small-norm matrix T ∈ Z n×n0 satisfying

U • T = γ • I n0 0 n1×n0 mod q, ( 12
)
so that V • T = γ • I n0 mod q and C • T = 0 n1×n0 mod q. For each i ∈ [ ], B then defines the alternative key ek i = s i of user i to be

s i = s i + T • ∆x i ∈ Z n ∀i ∈ [ ], ( 13
)
where ∆x i is the i-th column of ∆X (i.e., the guess for x 1-b,i -x b,i ). These modified encryption keys {ek i = s i } i=1 are used to answer all encryption queries and to generate the challenge ciphertext. At each corruption query i, the adversary is also given ek i instead of ek i .

We first claim that, conditionally on Guess, Game 5 is statistically close to Game 4 .

To see this, we first argue that trading {ek i } i=1 for {ek i } i=1 has no incidence on queries made by a legitimate adversary:

-We have C • s i = C • s i mod q, so that encryption queries obtain the same responses no matter which key set is used among {ek i } i=1 and {ek i } i=1 . -We have i=1 s i • y i = i=1 s i • y i so long as the adversary only obtains private keys for vectors y ∈ Z such that (X 0 -X 1 ) • y = 0 (over Z). -For any corrupted user i ∈ CS, it should be the case that x 0,i = x 1,i , meaning that s i = s i as long as Guess occurs.

This implies that Game 5 is identical to Game 4 , except that users' secret keys are defined via [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF] and thus have a slightly different distribution. Lemma 3.5 shows that the statistical distance between the distributions of {s i } i=1 and {s i } i=1 is at most 2 -λ • (4X) -n0 . This implies that Game 4 and Game 5 are statistically close assuming that Guess occurs. When Guess does not occur, both games output a random b ← U ({0, 1}), so that

| Pr[W 5 ] -Pr[W 4 ]| ≤ 2 -λ • (4X) -n0 .
We finally claim that, from the adversary's view Game 5 is identical to Game 5 . Indeed, our choice of T ensures that V • T = γ • I n0 mod q, so that we have

V • s i = V • s i + γ • (x 1-b,i -x b,i ) mod q. This implies C t ,i = G 0 • x b,i + (R τ • Â • C + G 0 • V) • s i + e i = G 0 • (1 -γ) • x b,i + γ • x 1-b,i + (R τ • Â • C + G 0 • V) • s i + e i
which is exactly the distribution from Game 5 .

Putting the above altogether, we find

| Pr[W 4 ] -Pr[W 5 ]| ≤ 2 -Ω(λ) • (4X) -n0 , which in turn implies | Pr[W 4 ] -Pr[W 5 ]| ≤ 2 -Ω(λ) , as claimed. Lemma 3.5. If σ ≥ 2 λ • n 0 • (4X) n0 +1 • ω(n 2 √ log n), then we have the inequality ∆ (D Z n ,σ , T • ∆x i + D Z n ,σ ) ≤ 2 -λ • (4X) -n0 . (The proof is in Appendix C.3.)

A DMCFE Scheme for Linear Functions

As in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], our DMCFE scheme combines two instances of the underlying centralized scheme of Section 3. While the second instance is used exactly in the same way as in the centralized construction, the first instance is used for the sole purpose of generating partial functional secret keys without having the senders communicate with one another. As in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], the senders have to initially run an interactive protocol in order to jointly generate public parameters for the two schemes. Note that this protocol is the only step that requires interaction among senders and it is only executed once. This interactive step ends with each sender holding an encryption key ek i = (s i , t i ) comprised of encryption keys for the two MCFE instances. The distributed protocol also ensures that a functional secret key t = i=1 t i for the all-one vector (1, 1, . . . , 1) ∈ Z be made publicly available for the first MCFE instance. Later on, when a decryptor wishes to obtain a partial functional secret key dk f,i for a vector y = (y 1 , . . . , y ) from the i-th sender S i , the latter can generate an MCFE encryption of the vector y i • s i ∈ Z n under his secret key t i . Having obtained partial functional secret keys dk f,i from all senders {S i } i=1 , the decryptor can then use the functional secret key t = i=1 t i to compute s y = i=1 y i • s i ∈ Z n .

Description

We assume global public parameters cp := λ, max , X, X, Y, Ȳ , n 0 , n 1 , n1 , n, n, , m, m, α, α 1 , ᾱ1 , σ, σ, t , f , L, q, q, AHF t , AHF f , which specify a security parameter λ and the following quantities

-Let max = λ k , n 1 = λ d , d = 3d + k -1, q = 2 λ d-1 +λ , q = 2 λ d-1 +λ , n1 = λ d, α 1 = 2 -λ d-1 +d log λ , ᾱ1 = 2 -λ d-1 + d log λ , α = 2 - √ λ , n 0 • max = O(λ d-2 ), n 0 = O(λ d-2 ), n = O(λ 2d-1 ), n = O(λ 4d+k-2 ), X = 1, Ȳ = 1, σ = 2 λ d-1 -2λ , σ = 2 λ d-1 -2λ , X = 2 • Y • σ √ n and the rest of the parameters Y, m, m are all in poly(λ) -A tag length t ∈ Θ(λ) and a length f ∈ Θ(λ) of function labels. -Dimensions n, m, n 0 , n 1 , n, m ∈ poly(λ) such that n > 3 • (n 0 + n 1 ) • log q , m > 2 • n • log q , n > 3 • (n + n1 ) • log q and m > 2 • n • log q .
-The description of balanced admissible hash functions AHF t : {0, 1} t → {0, 1} L and AHF f : {0, 1} f → {0, 1} L , for a suitable L ∈ Θ(λ). -A real α > 0 and a Gaussian parameter σ > 0, which will specify an interval

[-β, β] = [-σ √ n, σ √ n]
where the coordinates of the secret will live (with probability exponentially close to 1).

We define Ḡ ∈ Z n× m q to be the gadget matrix

Ḡ = [I n ⊗ (1, 2, 4, . . . , 2 log q ) | 0 n | . . . | 0 n ] ∈ Z n× m q
where I n ⊗ (1, 2, 4, . . . , 2 log q ) is padded with m -n • log q zero columns.

Setup(cp, 1 ): On input of a number of users < max , the senders {S i } i=1 run an interactive protocol at the end of which the following quantities are made publicly available.

-Random matrices

A i,b ← U (Z n×m q ), for each i ∈ [L], b ∈ {0, 1}. -Random matrices B i,b ← U (Z n× m q ), for each i ∈ [L], b ∈ {0, 1}. -Random matrices V ← U (Z n0×n q ), V ← U (Z n×n q ). -The sum t = i=1 t i ∈ Z n of Gaussian vectors t i ← D Z n ,σ for i ∈ [ ].
In addition, for each i ∈ [ ], the i-th sender S i privately obtains the following:

-The i-th term t i ∈ Z n of the sum t = i=1 t i . -A Gaussian vector s i ← D Z n ,σ , which is used to define S i 's encryption key ek i = s i ∈ Z n and the corresponding secret key

sk i = (s i , t i ) ∈ Z n × Z n.
The master public key is defined to be

mpk := cp, V, V, {A i,0 , A i,1 ∈ Z n×m q } L i=1 , {B i,0 , B i,1 ∈ Z n× m q } L i=1 , t , while S i obtains ek i = s i ∈ Z n and sk i = (s i , t i ) ∈ Z n × Z n for each i ∈ [ ].
DKeygenShare(sk i , t f ) : Given the secret key sk i = (s i , t i ) ∈ Z n × Z n and the label t f of a linear function f y : Z n0× → Z n0 described by a vector y = (y 1 , . . . , y ) ∈ [-Y, Y ] , conduct the following steps.

Compute τ

f = τ f [1] . . . τ f [L] = AHF f (t f ) ∈ {0, 1} L as well as B(τ f ) = B L,τ f [L] • Ḡ-1 B L-1,τ f [L-1] • Ḡ-1 . . . B 2,τ f [2] • Ḡ-1 B 1,τ f [1] • Ḡ-1 ( W ) ∈ Z n× m q , ( 14
)
where W = Ḡ • V ∈ Z m×n q . 2. Sample a noise vector e f,i ← D Z m ,αq . Then, compute

dk f,i = Ḡ • (y i • s i ) + B(τ f ) • t i + e f,i ∈ Z m q . ( 15
)
Output the partial functional decryption key dk f,i ∈ Z m q . DKeygenComb({dk f,i } i , t f ) : Given the label of a function described by a vector y = (y 1 , . . . , y ) ∈ [-Y, Y ] and partial functional keys {dk f,i } i=1 where dk f,i ∈ Z m q for each i ∈ [ ], conduct the following steps.

1. Compute τ f = AHF f (t f ) ∈ {0, 1} L and parse it as τ f = τ f [1] . . . τ f [L]. 2. Compute B(τ f ) ∈ Z n× m q as per (14). 3. Compute d t f = i=1 dk f,i -B(τ f ) • t mod q, where t ∈ Z n is taken from mpk.
4. Interpret d t f ∈ Z m q as a vector of the form d t f = Ḡ • s y + ẽf mod q, for some error vector ẽf ∈ [-B, B] m. Using the public trapdoor of Λ ⊥ ( Ḡ), compute the underlying

s y ∈ [-• β • Y, • β • Y ] n .
Output the functional secret key dk y = (y, s y ).

Encrypt(ek

i , x i , t) : Given ek i = s i ∈ Z n , x i ∈ [-X, X] n0 , and t ∈ {0, 1} t , 1. Compute τ = AHF(t) ∈ {0, 1} L and parse it as τ = τ [1] . . . τ [L]. 2. Letting W = G 0 • V ∈ Z m×n q , compute A(τ ) = A L,τ [L] • G -1 A L-1,τ [L-1] • G -1 . . . A 2,τ [2] • G -1 A 1,τ [1] • G -1 (W ) ∈ Z n×m q . ( 16
)
3. Sample a noise vector e i ← D Z m ,αq . Then, compute and output

C t,i = G 0 • x i + A(τ ) • s i + e i ∈ Z m q .
Decrypt(dk y , t, C t ) : On input of a functional secret key dk y = (y, s y ) for a vector y = (y 1 , . . . , y ) ∈ [-Y, Y ] , a tag t ∈ {0, 1} t , and an -vector of ciphertexts

C t = (C t,1 , . . . , C t, ) ∈ (Z m q ) , conduct the following steps. 1. Compute τ = AHF(t) ∈ {0, 1} L and parse it as τ = τ [1] . . . τ [L]. 2. Compute A(τ ) ∈ Z n×m q as per (16). 3. Compute f t,y = i=1 y i • C t,i -A(τ ) • s y mod q. 4. Interpret f t,y ∈ Z m
q as a vector of the form f t,y = G 0 • z + ẽ mod q, for some error vector ẽ ∈ [-B, B] m . Using the public trapdoor of Λ ⊥ (G 0 ), compute and output the underlying vector z

∈ [-• X • Y, • X • Y ] n0 .
The scheme's correctness is implied by that of the two underlying centralized schemes. In turn, these are correct by Lemma 3.1 and the choice of parameters.

Security

The proof of Theorem 4.1 is given in Appendix D. It proceeds with a sequence of games where the first (resp. last) game is the real experiment of Definition 2.14 where the challenger's bit is b = 0 (resp. b = 1).

In order to reduce the security of the centralized scheme to that of its decentralized variant, the proof first moves to a game where the partial functional key generation oracle of Definition 2.14 can be simulated using the functional key generation oracle of Definition 2.11. To this end, it relies on the security of the first MCFE instance. The reduction has the particularity that it has to send dummy encryption queries to its challenger in order to comply with Condition 2 of the "finalize" step in Definition 2.11. The next step is to move to a game where encryption queries (i, x i,0 , x i,1 , t) are answered by returning encryptions of x i,1 instead of x i,0 . For this purpose, we rely on the security of the second MCFE instance, which is possible since the partial key generation oracle can be simulated using the centralized key generation oracle. In order to make sure that the simulation does not break Condition 3 in the "finalize" step of Definition 2.11, the reduction only invokes its centralized key generation oracle in the very last partial key generation query involving an uncorrupted user. We note that a similar technique was used in [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], where keys were computed modulo a prime. Here, our reduction has to apply the same strategy over the integers. However, the technique still works as long as the message space of the first MCFE instance is large enough to contain functional secret keys i=1 y i • s i in each coordinate. The final transition restores the partial key generation oracle of Definition 2.14 to its original output distribution. To this end, we invoke again the security of the first MCFE instance and reverse the transition of the first step.

A One-or-less MCFE Compiler

In the definition of 1-challenge IND-sec security, (i.e., Definition 2.12), the adversary has to make the challenge encryption queries CQEncrypt(j, x 0 j , x 1 j , t ) for all uncorrupted slots j ∈ HS as long as a query of the form CQEncrypt(i, x 0 i , x 1 i , t ) is made for some slot i ∈ HS. Hence, it is not allowed to use the partial information that could be revealed by incomplete challenge queries.

It is desirable to strengthen the security definition and prove security even when the adversary is allowed to obtain partial ciphertexts by making challenge queries {CQEncrypt(i, x 0 i , x 1 i , t )} i∈I for a proper subset I ⊂ HS. In this section, we recall the definition of this security requirement and provide a compiler that takes a secure MCFE satysfying 1-challenge IND-sec security and upgrades it so as to achieve security in the sense of the stronger definition. The transformation relies on pseudorandom generators and adaptively secure multi-instance PRFs. A definition of the latter notion is given in this subsection.

Definition A.1 (1-or-less-challenge IND-sec). For an MCFE scheme with senders, we consider the following game between an adversary A and a challenger

C. The game involves a set HS (initialized to HS := [ ]), of honest senders and a set CS (initialized to CS := ∅), of corrupted senders.

Initialization:

The challenger C generates cp and runs (mpk, msk, {ek i } i=1 ) ← Setup(cp, 1 ). Then, it chooses a random bit b ← {0, 1} and gives the master public key mpk to the adversary A.

Encryption queries: The adversary can adaptively make encryption queries

QEncrypt(i, x, t), to which the challenger replies with Encrypt(ek i , x, t). Any further query involving the same pair (i, t) is ignored. Challenge queries: The adversary adaptively makes challenge queries of the form CQEncrypt(i, x 0 i , x 1 i , t ). The challenger replies with Encrypt(ek i , x b i , t ).

Only one tag t can be involved in a challenge query. If t denotes the tag of the first query, the challenger only answers subsequent challenge queries for the same t . Moreover, only one query (i, t ) is allowed for each i ∈ [ ] and subsequent queries involving the same i ∈ [ ] are ignored. Functional decryption key queries: The adversary can adaptively obtain functional decryption keys via queries QDKeygen(f ). At each query, the challenger returns dk f ← DKeygen(msk, f ). Corruption queries: For any user i ∈ HS, the adversary can adaptively make queries QCorrupt(i), to which the challenger replies with ek i and updates HS and CS by setting CS := CS ∪ {i} and HS := HS \ {i}. Finalize: The adversary outputs a bit b ∈ {0, 1}. The adversary A wins if β = b, where β is defined as β := b , unless one of the situations below occurred. 1. A challenge query CQEncrypt(i, x 0 i , x 1 i , t ) has been made for an index i ∈ CS with x 0 i = x 1 i . 2. An encryption query QEncrypt(i, x, t ) has been made for the challenge tag t and an index i ∈ [ ] 3. For the challenge tag t and some function f queried to QDKeygen, there exists a pair of vectors (x 0 , x 1 ) such that f (x 0 ) = f (x 1 ), where -

x 0 i = x 1 i for all i ∈ CS; -CQEncrypt(i, x 0 i , x 1 i , t
) have been asked for all i ∈ HS. If any of these events occurred, A's output is overwritten by β ← U ({0, 1}).

We say that an MCFE scheme provides ≤ 1Ch-IND security if, for any efficient adversary A, we have

Adv ≤1Ch-IND (A) := Pr[β = b] -1 2 ∈ negl(λ)
. The definition of 1-or-less IND security is identical to the 1Ch-IND definition, except that we removed Condition 3 of the Finalize step in Definition 2.12. In Definition A.1, we insist that the last condition of the Finalize step does not impose any restriction on the functions queried to QDKeygen if there exists a single index i ∈ HS for which no challenge query CQEncrypt(i, •, •, t ) was made.

In order to achieve security in the sense of Definition A.1, our compiler uses as a building block a pseudorandom function family that satisfies a definition of adaptive multi-instance PRF. This notion is defined as follows.

Definition A.2 (ad-mi-PRF). An efficiently computable function F : K×X →

Y is an adaptively secure N -instance PRF, for some N ∈ poly(λ), if no PPT adversary A has non-negligible advantage in winning the following game.

Initialization: The challenger C samples N secret keys k 1 , k 2 , . . . k N ← K and a uniformly random bit d ← U ({0, 1}).

Queries. The adversary A adaptively interleaves the following kinds queries:

Evaluation: Upon receiving a query Eval(i, X), where i ∈ [N ] and X ∈ X , the challenger returns ⊥ if it previously replied to a challenge query for the same pair (i, X). Otherwise, it replies with F ki (X) ∈ Y. Corruption: When the adversary makes a query Corrupt(i), the challenger returns ⊥ if it previously replied to a challenge query for i. Otherwise, the challenger returns k i ∈ K.

Challenge: A makes challenge queries Challenge(i , X ) for a unique arbitrary input X (any subsequent challenge query involving a different input X = X is ignored). If Eval(i , X ) or Corrupt(i ) was queried before, the challenger returns ⊥. Else, it returns

F k i (X ) if d = 1

The adversary's advantage is Adv

ad-mi-PRF A (λ) := Pr[d = d] -1 2 .
It is possible to show that any PRF that provides single-instance security in the sense of a "find-then-guess" definition is also secure in the sense of Definition A.2. In short, the proof proceeds using a hybrid argument over the challenge queries and guesses the index of an uncorrupted index in each hybrid. However, this reduction incurs a quadratic security loss in N . Since Lemma A.4 uses a reduction with N = 2 PRF instances, this would translate into a degradation factor 4 , which would eventually become 5 because of the bound [START_REF] Boneh | Public key encryption with keyword search[END_REF]. In Appendix A.2, we show that a PRF construction described in [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] can be proven secure in the sense of Definition A.2 without a O(N 2 ) loss in the reduction, so that our security loss is only linear in the number of slots . In comparison, the compiler of [START_REF] Abdalla | From single-input to multi-client inner product functional encryption[END_REF] loses a factor O( 2) but relies on any PRF.

A.1 The Transformation

The compiler is similar to the random-oracle-based transformation of Abdalla et al. [2, Section 4.2] -which is itself inspired by [START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF] -and its intuition is the following. The ciphertexts of individual slots contain partial MCFE ciphertexts Encrypt (ek i , x i , t) which are super-encrypted using a symmetric encryption scheme with secret key K t,i . The partial ciphertexts of the compiled scheme also contain shares k ijt of the secret key K i,t in such a way that, once all the partial ciphertexts are gathered for a given tag t, the decryptor can recover the secret K t,i = j=1 k ijt and thus the encryption Encrypt (ek i , x i , i). If only one such ciphertext is missing, then the secret key K t,i remains computationally hidden because the decryptor does not have all the shares. The symmetric encryption layer thus hides all the information that could leak when the adversary does not make encryption queries for all uncorrupted slots.

Given an MCFE scheme MCF E = (Setup , Encrypt , DKeygen , Decrypt ), an adaptively secure 2 -instances ad-mi-PRF F : K × T → {0, 1} λ and a PRG G : {0, 1} λ → {0, 1} |ct | , where |ct | is the length of the output of the algorithm Encrypt , we obtain the following compiled scheme MCF E. The security proof relies on the idea that, if the adversary A does not make all the allowed challenge encryptions queries, there must exist an honest slot j 0 ∈ HS such that CQEncrypt(j 0 , x 0 j0 , x 1 j0 , t ) is never asked. This ensures that none of the PRF values {k ij0t = F kij 0 (t )} i∈HS is ever exposed to the adversary, which implies that {k ij0t } i∈HS are pseudorandom in the adversary's view since F is a PRF. This implies that secret keys K t ,i := j=1 k ijt are also pseudorandom for all i ∈ HS. Hence, the ciphertexts C t ,i = Encrypt (ek i , x i , i) ⊕ G(K t ,i ) computationally hide the x i 's for all uncorrupted slots i. To translate this intuition into a formal security proof, we need a PRF family that provides security in the sense of Definition A.2.

Setup(cp

Theorem A.3. If MCF E is 1Ch-IND secure then the compiled MCF E scheme is ≤ 1Ch-IND secure.
Proof. Given an adversary A that breaks the MCF E scheme by winning the game of Definition A.1 with non-negligible probability, we give a construction of an adversary B that wins with the game of Definition 2.12 with noticeable advantage, thus breaking the MCF E scheme. The adversary B works as follows.

Initialization:

The challenger C gives B the public parameters mpk and keeps to itself the secret keys (msk , {ek i } i=1 ). In order to initialize the game with A, the reduction B samples 2 secret keys k ij ← K for all i, j ∈ [ ]. Then gives A the public parameters mpk := mpk . Encryption queries: For each encryption query QEncrypt(i, x, t) made by A, B sends to same query to its challenger and obtains C t,i = Encrypt (ek i , x, t).

Then, B computes k ijt := F kij (t), k jit := F kji (t) j=1 , K t,i := j=1 k ijt , C t,i := C t,i ⊕ G(K t,i
) and gives ct t,i := (C t,i , {k jit } j=1 ) to A. Challenge queries: If A makes a query CQEncrypt(i, x 0 i , x 1 i , t ), B relays it to its challenger and obtains C t ,i := Encrypt (ek i , x b i , t ). Then, B computes {k ijt := F kij (t ), k jit := F kji (t )} j=1 , K t i := j=1 k ijt , as well as C t ,i := C t ,i ⊕ G(K t i ). The adversary A is given ct t i := (C t i , {k jit } j=1 ). Functional decryption key queries: Each query QDKeygen(f ) made by A is relayed by B to its challenger, which replies with dk f . Then, B gives dk f := dk f to A. Corruption queries: For each corruption query QCorrupt(i) that A makes, B replies with ek i := (ek i , {k ij , k ji } j=1 ), where ek i is the key given by its challenger in response to the same corruption query. Finalize: When A outputs a result b , B distinguishes two situations.

-If A makes queries CQEnc(i, , , t ) for all slots i ∈ HS and the conditions of the Finalize step in Definition A.1 are all satisfied (i.e., A's output is not overwritten by a random bit β), B outputs the same bit b := b as A. -Otherwise, B outputs a random b ← U ({0, 1}). We call this event abort.

Next, we analyze the probability of B winning the game.

Pr[ b = b] = Pr[ b = b|abort] • Pr[abort] + Pr[ b = b|abort] • Pr[abort] = 1 2 • Pr[abort] + Pr[b = b|abort] • Pr[abort] = Pr[b = b] + 1 2 -Pr[b = b|abort] • Pr[abort] = Pr[b = b] + 1 2 -Pr[b = b|Ab] • Pr[Ab]
where Ab is the event that A does not make encryption queries for all honest slots in the challenge phase and the conditions in the finalize step of Definition A.1 are all satisfied.

In order to finish the proof, we need to prove the following claim.

Claim. If F is a ad-mi-PRF and G a PRG, then Pr[b = b|Ab] -1 2 is negligible.

Proof. We will prove this claim via a series of games. For each i ∈ {0, 1, 2}, we call W i the event that the challenger outputs 1 in Game i .

Game 0 : This is the original game in the one-or-less security experiment (cf. Definition A.1) for the compiled scheme. The challenger runs the setup algorithm of MCFE to obtain (mpk, msk , {ek i } i=1 ), samples k ij ← K, for all i, j ∈ [ ] and sets mpk := mpk , msk := msk and ek i := (ek i , {k ij , k ji } j=1 ). It gives mpk to A and handles queries QCorrupt(i) using ek i := (ek i , {k ij , k ji } j=1 ). To answer queries QEnc(i, x i , t), it computes k ijt := F kij (t), k jit := F kji (t) j=1 and K t,i := j=1 k ijt . Then, it computes C t,i := Encrypt (ek i , x i , t)⊕G(K t,i ). The adversary A is given ct t,i := (C t,i , {k jit } j=1 ). To answer challenge encryption queries CQEncrypt(i, x 0 i , x 1 i , t ), it replies with the result of QEnc(i, x b i , t ). As for functional decryption queries QDKeygen(f, msk), the challenger replies with dk f ← DKeygen(msk , f ). When A halts, it outputs a bit b and the challenger outputs 1 if and only if b = b, so that Pr[W 0 ] = Pr[b = b|Ab]. Game 1 : The challenger interacts with A exactly as in Game 0 except that, upon receiving a challenge query CQEncrypt(i, x 0 i , x 1 i , t ), it does the following. If x 0 i = x 1 i , it replies as in Game 0 . Otherwise, for each slot i ∈ [ ] such that x 0 i = x 1 i , it samples a uniform value for K t ,i ← U ({0, 1} λ ) which it uses as a seed for the pseudorandom generator G in order to compute C t ,i .

For any index i such that x 0 i = x 1 i , corruption queries Corrupt(i) are disallowed by the conditions of the Finalize step which must be satisfied (recall that we are conditioning on event Ab). The only information that A can gather about K t ,i is thus obtained from QEnc(j, x j , t) and CQEnc(j, x 0 j , x 1 j , t ) queries. By making these types of queries, A only learns the evaluations {k ijt = F kij (t)} j∈[ ] , for any t ∈ T \ {t }, and F kij (t ) j∈HS\{j0} , respectively. Since we are conditioning on Ab, there exists an index j 0 ∈ HS which is never the input of a query of the form CQEnc(j 0 , •, •, t ). In order to prove that Game 0 and Game 1 are computationally indistinguishable, we define Game 0 and Game 1 in the following way.

challenger. Then, it replies with (ek j , {k jτ , k τ j } τ =1 ). Notice that, if j 0 is a correct guess, we have j 0 ∈ HS, which implies that the adversary never learns {k j0i , k ij0 } i∈HS from corruption queries.

Encryption queries:

To answer QEncrypt(i, x, t) queries, B asks its PRF challenger for the evaluations k ijt := F kij (t), k jit := F kji (t) j=1 and computes

K t,i := j=1 k ijt . Then, it computes C t,i = Encrypt (ek i , x, t) as well as C t,i := C t,i ⊕ G(K t,i ). The ciphertext ct t,i := (C t,i , {k jit } j=1 ) is given to A.
Challenge queries: When receiving a challenge query CQEncrypt(i, x 0 i , x 1 i , t ), B aborts if i = j 0 . Otherwise, it considers the following two cases.

-If x 0 i = x 1 i = x i , then B responds as it would answer the encryption query QEncrypt(i, x i , t ).

-If x 0 i = x 1 i (which is only possible if i ∈ HS), the reduction B asks its challenger for the PRF evaluations {k ijt := F kij (t )} j =j0 . It also makes a challenge query for the input t and the secret key k ij0 . The challenger replies with a value y ij0t , which is either the evaluation F kij 0 (t ) for the unknown secret key k ij0 chosen by the PRF challenger or a random value. Then, B computes K t ,i := ( j =j0 k ijt ) ⊕ y ij0t and uses K t ,i as a seed for the PRG, by computing

C b t ,i := C b t ,i ⊕ G(K t ,i ). The adversary A is given ct t,i := (C b t,i , {k jit } j=1
). Guess: When A halts, it outputs a bit b . At this point, B aborts and outputs 0 if j 0 is not the smallest i ∈ [ ] such that no query CQEncrypt(i, •, •, t ) is made. Otherwise, B outputs 1 (meaning that its challenger always outputs pseudorandom values) if b = b and 0 otherwise.

If j 0 is not a correct guess, Game 0 and Game 1 have the same outcome since the challenger outputs 0 in both games. We thus assume that j 0 is a correct guess, in which case we know that j 0 ∈ HS. Moreover, if x 0 i = x 1 i , we necessarily have i ∈ HS. Therefore the reduction B never obtains the secret key k ij0 by making a Corrupt(•) query in the game of Definition A.2. In the same game, we also observe that the value F kij 0 (t ) is never asked by B to its PRF evaluation oracle. Indeed, encryption queries QEncrypt(•, •, t ) are not allowed on the challenge tag t and the constraint Ab implies that no challenge query CQEncrypt(j 0 , •, •, t ) can be made for the index j 0 .

We now observe that, if B's challenger always returns truly random values y ij0t at each challenge query, then A's view is identical to that of Game 1 . If B's challenger always returns pseudorandom values, A's view is as in Game 0 . We thus conclude that Adv ad-mi-PRF

B (λ) ≥ | Pr[W 0 ] -Pr[W 1 ]|.

A.2 A PRF Construction With Multi-Instance Security in the Adaptive Corruption Setting

We show that the centralized version of the distributed PRF of Libert et al. [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] provides security in the sense of Definition A.2. We first recall the construction.

Let λ be a security parameter and let ∈ Θ(λ), L ∈ Θ(λ). The scheme uses public parameters consisting of prime moduli p and q such that q/p > 2 L+λ • N • r, dimensions n, m, k ∈ poly(λ) such that m ≥ 2n • log q , an integer β > 0, a real α > 0 and a rounding parameter r = m L+2 • n • β • αq. The PRF family relies on the following building blocks.

• A balanced admissible hash function AHF : {0, 1} → {0, 1} L . • A family Π λ of ξ-wise independent hash functions π i : Z m p → Z k p for a suitable ξ > 0 that will be determined later on. Let a random member π of Π λ .

Let a Gaussian parameter

σ > 0 such that the interval [-β, β] = [-σ √ n, σ √ n]
contains the coordinates of the secret key with overwhelming probability. The PRF family assumes the availability of public parameters [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Section 3.1] for details).

pp := q, π, A 0 , {A i,0 , A i,1 ∈ Z n×m q } L i=1 , AHF, r, σ , where A 0 ∼ U (Z n×m q ) and A i,0 , A i,1 ∼ U (Z n×m q ) for each i ∈ [L]. Importantly, {A i,0 , A i,1 } L i=1 should be chosen in such a way that G -1 (A i,b ) ∈ Z m×m is Z q -invertible for all i ∈ [L] and b ∈ {0, 1} (see

Keygen(pp):

Given pp, sample a vector s ← D Z n ,σ so that s ∞ < β = σ √ n with overwhelming probability. The secret key is SK :

= s ∈ [-β, β] n . Eval(pp, SK, X): Given SK = s ∈ Z n and an input X ∈ {0, 1} , 1. Compute x = AHF(X) ∈ {0, 1} L and parse it as x = x 1 . . . x L . 2. Compute A(x) = A 0 • L i=1 G -1 A i,xi and z = A(x) • s p ∈ Z m p , (18)
and output y = π(z) ∈ Z k p .

We now prove that this construction is secure in the sense of Definition A.2 under the LWE assumption. The proof of Theorem A.5 is essentially identical to that of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Theorem 3.2]. Intuitively, it exploits the fact that the reduction knows the secret key at any time, which makes it easy to consistently answer adaptive corruption queries.

Theorem A.5. The above construction provides adaptive multi-instance security under the LWE assumption.

The proof relies on the following lemmas.

∈ R n×n satisfying σ n ( √ Σ) ≥ η 2 -n (Λ), we have ρ Σ,c (Λ + x ) ∈ [1 -2 -n , 1 + 2 -n ] • det(Σ) 1/2 /det(Λ).
for some j ∈ [N ]. We also define BAD as the event that A makes an evaluation query (j, X) such that the event bad x occurs. Note that the challenger can detect bad x since it knows Ā ∈ Z n ×m q , C ∈ Z n ×n The proof of the following claim is adapted from [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Appendix D].

Claim. If q/p > 2 L+λ • N • r, where r = m L+2 • n • β • αq, we have the inequality | Pr[W 4 ] -Pr[W 3 ]| ≤ Pr[BAD] ≤ 2 -Ω(λ) .
Proof. We use the fact that, for each query x = x 1 . . . x L , the matrix R x ∈ Z m×m is of the form

R x = R 0 • L i=1 G -1 A i,xi +R 1,x1 • L i=2 G -1 (A i,xi ) +µ 1,x1 • R 2,x2 • L i=3 G -1 A i,xi . . . +µ 1,x1 µ 2,x2 • • • µ L-2,x L-2 • R L-1,x L-1 • G -1 A L,x L +µ 1,x1 µ 2,x2 • • • µ L-1,x L-1 • R L,x L .
In order to bound Pr[bad x ], we note that, as argued in [10, Proof of Theorem 7.3], R 0 • Ā is statistically uniform over Z m×n q , conditionally on R 0 • E ∈ Z m×n . Hence, for a fixed choice of j ∈ [N ] and x ∈ {0, 1} L , the product R

x • Ā • (C • s j ) contains a term L i=1 G -1 (A i,xi ) G x •R 0 • Ā • (C • s j ), for which we know that G x • R 0 • Ā is statistically uniform over Z m×n q since G x is a Z q -invertible matrix by construction. We know that G x • R 0 • Ā • (C • s j )
is statistically close to the uniform distribution over Z m q . We thus have

Pr[bad x ] = Pr A • R x • s j p = R x • Ā • C • s j p ≤ m • 2rp q . ( 26
)
where

r = m L+2 • n • β • αq. Indeed, we have R x ∞ ≤ m(m L+1 -1) m-1 , s j ∞ ≤ β and E ∞ = max i∈[m]   n j=1 |e i,j |   ≤ √ n max i∈[m] e i ≤ n • αq.
since it considers a union bound to show that equality [START_REF] Chandran | Functional encryption: Decentralised and delegatable[END_REF] holds for all x ∈ {0, 1} L and j ∈ [N ] with overwhelming probability. This implies H ∞ R x • A • s j p | C • s j = 0 with high probability. In the right-hand-side member of (29), we also observe that G • s j p + e s,j,x is an injective function of s j . Indeed, we have

G • s j p + e s,j,x = (p/q) • G • s j -t s,j,x + e s,j,x
for some e s,j,x ∈ (0, 1) m , so that

(q/p) • ( G • s j p + e s,j,x ) = G • s j + e s,j,x (30)
for some e s,j,x ∈ (-q/p, 2 • q/p) m . When assessing the entropy of z j conditionally on A's view, we thus obtain

H ∞ (z j | C • s j ) = H ∞ R x • A • s j p + G • s j p + e s,x | C • s = H ∞ G • s j p + e s,x | C • s j (31) = H ∞ (s j | C • s j ) ≥ n • log σ -n • log q -1.
Here, the second equality follows from the fact that, for any random variables X, Y, Z defined over an additive group, we have

H ∞ (Y + Z | X) = H ∞ (Z|X) if H ∞ (Y |X) = 0.
The last inequality follows from Lemma A.6: the distribution of s j ∈ Z n conditionally on C • s j is s j,0 + D Λ ⊥ (C),σ,-sj,0 , where s j,0 ∈ Z n q is an arbitrary solution of C • s j,0 = C • s j . Then, Lemma A.6 implies that the point with highest probability in D Λ ⊥ (C),σ,-sj,0 occurs with probability ≤ 2 det(Λ ⊥ (C))/σ n . Since det(Λ ⊥ (C)) = q n with probability 1 -2 Ω(λ) , we have

H ∞ (s j | C • s j ) ≥ n • log σ -n • log q -1.
To extract statistically uniform bits from each uncorrupted z j , we need to take into account the fact that x may depend on pp. Assuming that P K (X ) = 0, for each uncorrupted j ∈ [N ], the source z j is taken from a distribution determined by X within a collection of less than 2 distributions (i.e., those for which P K (X ) = 0), which all have min-entropy n = n • log σ -n • log q -1. Moreover, the {z j } j∈[N ] are independent since they are obtained by applying the same function to N independent variables. If we call C ⊂ [N ] the subset of corrupted indexes, by applying Lemma A.9 and Lemma A.8 with ε = 2 -λ for a collection X of at most M = 2 distributions, we obtain that the joint distribution of {π 2 : Both QEncrypt(i, x, t ) and CQEncrypt(i, x 0 i , x 1 i , t ) have been made for an index i and the challenge label t , such that x 0 i = x 1 i . The non-trivial implication to prove is that 1Ch-IND security implies 1Ch-IND security. Towards a contradiction, suppose that there exists an adversary A that wins the 1Ch-IND game with noticeable advantage. We build an adversary A that breaks the 1Ch-IND security game. Our adversary A answers both corruption and functional decryption key queries made by A by relaying them to its challenger and forwarding the responses to A . For a query QEncrypt(i, x, t) made by A , A checks if a challenge query CQEncrypt(i, x 0 i , x 1 i , t) was made earlier. If no challenge query has been made so far for the pair (i, t), the reduction sends the same QEncrypt(i, x, t) query to its challenger and passes the the answer to A . Otherwise, it makes a Corrupt(i) query to its challenger and thereby obtains the encryption key ek i . To answer any subsequent query for slot i, the reduction simply uses ek i .

(z j )} j∈[N ]\C is ( • 2 -λ + 2 -)-close to the uniform distribution over (Z k p ) |[N ]\C| .

B Relation

To answer a challenge query QCEncrypt(i, x 0 i , x 1 i , t ), the reduction A forwards the query to its challenger and transmits the answer to A' if it did not previously make an encryption QEncrypt(i, x, t ) for the pair (i, t ). If A previously made an encryption query for the pair (i, t ), it also invokes its challenger and sends it the query Corrupt(i). Upon receiving ek i , A is able to answer any query concerning the i-th slot.

Notice that the adversary A is only allowed to make both encryption and challenge queries on the same pair (i, t ) if x 0 i = x 1 i . This implies that the reduction is allowed to make the query Corrupt(i) to its challenger, which allows it to answer all queries concerning the i-th slot. We know that Λ ⊥ (G 0 ) has a public trapdoor T 0 ∈ Z m×m such that G 0 • T 0 = 0 mod q and T 0 ∞ ≤ log q where T 0 ∞ := sup x =0 T 0 •x ∞ x ∞ . By using this short trapdoor, we are able to recover X • y ∈ Z n0 in the following way: observe that T 0 •f t,y = T 0 •E•y mod q. By [59, Lemma Moreover, the hypotheses imply

C Deferred

T 0 • E • y ∞ ≤ T 0 ∞ • E ∞ • y ∞ ≤ log q • • αq • Y < q/2.
Hence, T 0 • f t,y mod q actually reveals T 0 • E • y over Z m . Since T 0 is a Z-basis, it comes that we can recover E • y ∈ Z m , at which point we also get X • y mod q. Since X • y ∞ ≤ • X • Y < q/2 by hypothesis, the modular product X • y mod q is nothing but X • y ∈ Z

R τ = R τ • G -1 (W )
, where R τ is given below:

R τ = R L,τ [L] • G -1 A L-1,τ [L-1] • G -1 A L-2,τ [L-2] • • • • G -1 A 1,τ [1] +µ L,τ [L] • R L-1,τ [L-1] • G -1 A L-2,τ [L-2] • • • • G -1 A 1,τ [1] +µ L,τ [L] • µ L-1,τ [L-1] • R L-2,τ [L-2] • G -1 A L-3,τ [L-3] • • • • G -1 A 1,τ [1] . . . +µ L,τ [L] µ L-1,τ [L-1] • • • µ 3,τ [3] • R 2,τ [2] • G -1 A 1,τ [1] +µ L,τ [L] µ L-1,τ [L-1] • • • µ 2,τ [2] • R 1,τ [1]
R τ is thus a sum of L terms of products of at most 3 binary matrices. Since each binary matrix has infinity norm less than m we obtain the upper bound R τ ∞ ≤ L • m 3 . By [59, Lemma 4.4], we can bound the Euclidean norm of a Gaussian vector e ← D Z n ,α1q by e ≤ √ n • α 1 q, with probability exponentially close to 1. We thus obtain where e f,i ← D Z m,αq . -If the pair (i, f ) is such that similar queries (j, f ) have been made earlier for the same function f and for all indexes j ∈ HS \ {i}, C recalls the vectors {s j } j∈HS\{i} that were chosen to answer earlier queries. It computes s y = i=1 s i • y i ∈ Z n as in the centralized scheme of Section 3. Then, it defines

E ∞ = max i∈[m] n j=1 |e i,j | ≤ √ n • max i∈[m] n j=1 e 2 i,j ≤ n • α 1 q, so that R τ •E•s ∞ ≤ R τ ∞ • E ∞ • s ∞ ≤ Lm 3 •nα 1 q •σ √ n. By Lemma 2.
s f,i = s y - j∈HS\{i} y j • s j - i= h +1 s i • y i over Z, (32)
The challenger C then responds the query QDKeygen(i, f ) by encrypting s f,i ∈ Z n and returning

dk f,i = Ḡ • s f,i + B(τ f ) • t i + e f,i ∈ Z m q , ( 33
)
where e f,i ← D Z m ,αq . We note that the vectors s j sampled at each query do not have to be consistent across partial key generation queries for distinct functions (they just have to be consistent across queries QDKeygen(•, f ) involving the same function f ). This will not be necessary since we are just seeking to simulate the -If the pair (i, f ) is such that queries QDKeygen(j, f ) have been made before for the same function f on all indexes j ∈ HS \ {i}, C recalls the vectors {s j } j∈HS\{i} and {s f,j } j∈HS\{i} that were chosen to handle earlier queries for f . It then defines s y = i=1 y i • s i ∈ Z n which is the secret key that would be computed for y ∈ [-Y, Y ] using the real master secret key {s i } i=1 in the scheme of Section 3. It finally defines

s f,i = s y - j∈HS\{i} s f,j - i= h +1 s i • y i over Z, (34)
Then, B sends the query QEncrypt(i, y i • s i , s f,i , t f ) to its encryption oracle in the IND-sec game. Depending on the value of its secret bit b ∈ {0, 1}, the MCFE challenger replies with either

dk f,i = Ḡ • (y i • s i ) + B(τ f ) • t i + e f,i or dk f,i = Ḡ • s f,i + B(τ f ) • t i + e f,i , (35)
where e f,i ← D Z m,αq , and the response dk f,i is returned to A as a partial functional secret key for the vector y. At each encryption query (i, x 0,i , x 1,i , t) made by A, B can compute

C t,i = G 0 • x 0,i + A(τ ) • s i + e i ∈ Z m q , ( 36
)
itself by faithfully running the encryption algorithm as it knows {s i } i=1 . When A terminates, B checks if A made a query QDKeygen(i, f ) for a function f such that not all indexes j ∈ HS \{i} were the input of a query QDKeygen(j, f ). If so, B makes the missing queries for itself. Namely, for each such function f , B parses the corresponding vector as y = (y 1 , . . . , y ) ∈ [-Y, Y ] and defines Q f ⊂ HS to be the set of indexes j for which no query QDKeygen(j, f ) was made by A. For each j ∈ Q f , B does the following.

-If j is not the last unqueried index for f , B samples a Gaussian s j ← D Z n ,σ and sends the query QEncrypt(j, y j • s j , y j • s j , t f ) to its MCFE challenger. -If j is the last unqueried index for f , B defines

s f,j = i∈HS y i • s i - i∈HS\{j} y i • s i ( 37
)
and makes the encryption query QEncrypt(j, y j • s j , s f,j , t f ). Since the only functional secret key query made by B is for the vector 1 = (1, 1, . . . , 1) , B only needs to make sure that dummy encryption queries are made for pairs of vectors that sum to the same value over indexes in HS. This is ensured by defining the last term as [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF].

  It also updates the sets HS and CS by setting CS := CS ∪ {i} and HS := HS \ {i}. Finalize: The adversary outputs a bit b ∈ {0, 1}. The adversary A wins if β = b, where β is defined as β := b , unless of the situations below occurred.

  where τ = AHF(t ) and e i ← D Z m ,αq for all i ∈ [ ]. When A halts, it outputs b ∈ {0, 1} and the challenger defines b := b. We have Adv(A) := | Pr[W 0 ] -1/2|, where W 0 is event that b = b.

4 )

 4 are satisfied. If conditions (4) do not hold, the challenger ignores A's output b ∈ {0, 1} and overwrites it with a random bit b ← {0, 1} to define b = b . If conditions (4) are satisfied, the challenger sets b = b. By Lemma 2.8,

Game 5 :

 5 This game is like Game 4 but we modify the challenge oracle. Instead of encrypting X b = [x b,1 | . . . | x b, ] as in

Theorem 4 . 1 .

 41 The above DMCFE scheme provides sta-IND-sec security under the LWE assumption.

  and a uniformly random value from Y if d = 0. Guess. A outputs a guess d ∈ {0, 1} and wins if d = d.

Lemma A. 6 (

 6 Adapted from [59, Lemma 4.4]). For any n-dimensional lattice Λ, x , c ∈ R n and symmetric positive definite Σ

q

  and E ∈ Z m×n satisfying[START_REF] Brakerski | Multi-input functional encryption in the private-key setting: Stronger security from weaker assumptions[END_REF]. If bad x occurs, the challenger replaces A's output d by a random d ← {0, 1} and sets d = d . Otherwise, it sets d = d as before.

Proofs for the Scheme in Section 3 C. 1

 31 Proof of Lemma 3.1 (Correctness)Proof. Suppose that C t,i = G 0 • x i + A(τ ) • s i + e i ∈ Z mq , with each error vector e i ← D Z m ,αq and τ = AHF(t).Defining E = [e 1 | • • • |e ] ∈ Z m× , we have f t,y = i=1 y i • C t,i -A(τ ) • s y = G 0 • X • y + E • y mod q.

  4.4], we can bound the Euclidean norm of a Gaussian vector e ← D Z ,αq by e ≤ √ • αq with probability exponentially close to 1. It comes that E

3 Proof.

 3 If the matrices A i,b = A • R i,b + µ i,b • G ∈ Z n×m , for i ∈ [L] and b ∈ {0, 1}, with R i,b ← {-1, 1} m×m and µ i,b ∈ {0, 1}, defined as in equation[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF], then

C. 3

 3 [START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF], the statistical distance to be bounded is at most≤ m • Lm 3 •nα1q•σ √ n αq = 2 -λ . Proof of lemma 3.5Proof. By Remark 2.3, each column of T has norm smaller thant i ≤ O( n • (n 0 + n 1 ) log q) • ω( log n) = ω(n log n), so that T • ∆x i ∞ ≤ T • ∆x i ≤ 2Xn 0 • ω(n √ log n). By Lemma 2.4, the considered distance is smaller than n • 2Xn0•ω(n √ log n) σ ≤ 2 -λ • (4X) -n0 .D Proof of Theorem 4.1Proof. The proof considers a sequence of games. The first game corresponds to the real sta-IND-sec game where the challenger's bit is b = 0. The final game is the sta-IND-sec game where b = 1. We will prove that they are computationally indistinguishable assuming that the scheme of Section 3 provides IND-sec security in the sense of Definition 2.11. For each i, we denote by W i the event that the adversary outputs β = 1 in Game i . Game 0 : This is the real security sta-IND-sec security game, which corresponds to the game of Definition 2.14 with the sets CS and HS chosen before the initialization phase. Letting h = |HS| and |CS| =h , we assume w.l.o.g. that A chooses to corrupt the lasth senders: i.e., HS = {1, . . . , h } and CS = { h + 1, . . . , }. By definition, the adversary outputs β = 1 with probability Pr[W 0 ]. Game 1 : In this game, we modify the QDKeygen(•, •) oracle, which generates partial functional decryption keys. At each partial functional decryption key query QDKeygen(i, f ) for an index i ∈ HS and a function f described by a vector y = (y 1 , . . . , y ) ∈ [-Y, Y ] , the challenger C responds as follows: -If the pair (i, f ) is such that not all indexes j ∈ HS \ {i} have been the input of a query QDKeygen(j, f ) for the same function f , C samples a Gaussian vector s i ← D Z n ,σ and encrypts y i • s i ∈ Z n as dk f,i = Ḡ • (y i • s i ) + B(τ f ) • t i + e f,i ∈ Z m q ,

  1 ) : Takes in global parameters cp and a pre-determined number of users 1 , where cp specifies a security parameter 1 λ . It outputs a set of public parameters mpk, a master secret key msk, and a set of encryption keys {ek i } i=1 . We assume that mpk is included in all encryption keys ek i . Encrypt(ek i , x i , t) : Takes as input the encryption key ek i of user i ∈ [ ], a message x

i and a tag t ∈ T . It output a ciphertext C t,i . DKeygen(msk, f ) : Takes as input the master secret key msk and an -argument function f : M → R. It outputs a functional decryption key dk f . Decrypt(dk f , t, C) : Takes as input a functional decryption key dk f , a tag t, and an -vector of ciphertexts C = (C t,1 , . . . , C t, ). It outputs a function evaluation f (x) ∈ R or an error message ⊥. Correctness. For any set of public parameters cp, any (mpk, msk, {ek i } i=1 ) ← Setup(cp, 1 ), any vector x ∈ M n any tag t ∈ T and any function

Functional decryption key queries: The

  Only one tag t can be involved in a challenge query. If t denotes the tag of the first query, the challenger only replies to subsequent challenge queries for the same label t . Moreover, only one query (i, t ) is allowed for each i ∈ [ ] and subsequent queries involving the same i ∈ [ ] are ignored. The adversary outputs a bit b ∈ {0, 1}. The adversary A wins if β = b, where β is defined as β := b , unless of the situations below occurred.

	1. A challenge query CQEncrypt(i, x 0 i , x 1 i , t ) has been made for an index i ∈ CS with x 0 i = x 1 i .
	2. An encryption query QEncrypt(i, x, t ) has been made for the challenge
	tag t for some index i ∈ [ ].

A and a challenger C. The game involves a set HS (initialized to HS := [ ]), of honest senders and a set CS (initialized to CS := ∅), of corrupted senders.

Initialization:

The challenger C generates cp and runs (mpk, msk, {ek i } i=1 ) ← Setup(cp, 1 ). Then, it chooses a random bit b ← {0, 1} and gives the master public key mpk to the adversary A.

Encryption queries: The adversary can adaptively make encryption queries

QEncrypt(i, x, t), to which the challenger replies with Encrypt(ek i , x, t). Any further query involving the same pair (i, t) is ignored. Challenge queries: The adversary adaptively makes challenge queries of the form CQEncrypt(i, x 0 i , x 1 i , t ). The challenger replies with Encrypt(ek i , x b i , t ). adversary can adaptively obtain functional decryption keys via queries QDKeygen(f ). At each query, the challenger returns dk f ← DKeygen(msk, f ). Corruption queries: For any user i ∈ HS, the adversary can adaptively make queries QCorrupt(i), to which the challenger replies with ek i and updates HS and CS by setting CS := CS ∪ {i} and HS := HS \ {i}. Finalize:

  which allows them to generate their own secret keys sk i and encryption keys ek i , for i ∈ [ ], as well as a set of public parameters mpk.Encrypt(eki , x i , t) : Takes as input the encryption key ek i of user i ∈ [ ], a message x i and a tag t ∈ T . It output a ciphertext C t,i . DKeygenShare(sk i , t f ) : Takes as input a user's secret key sk i and the label t f of a function f : M → R. It outputs a partial functional decryption key dk f,i for the function described by t f . DKeygenComb({dk f,i } i , t f ) : Takes as input a set of partial functional decryption keys {dk f,i } i and the label t f of a function f : M → R. It outputs a full functional decryption key dk f for the function f described by t f Decrypt(dk f , t, C) : Takes as input a functional decryption key dk f , a tag t, and an -vector of ciphertexts C = (C t,1 , . . . , C t, ). It outputs a function evaluation f (x) ∈ R or a message ⊥ indicating a decryption failure.

Functional decryption key queries: Via queries

  For any user i ∈ HS, the adversary can adaptively make queries QCorrupt(i) and the challenger replies by returning (sk i , ek i ).

1 ), any x ∈ M n , any tag t ∈ T and any function f : M → R, if C t,i ← Encrypt(ek i , x i , t) for all i ∈ [ ] and dk f ← DKeyComb({DKeyGenShare(sk i , t f )} i , t f ), with overwhelming probability, we have Decrypt dk f , t,

C t = (C t,1 , . . . , C t, ) = f (x).

Definition 2.14 (IND-sec for DMCFE). For a DMCFE scheme with senders, we consider the following game between an adversary and a challenger. It involves a set HS of honest senders (initialized to HS := [ ]) and a set CS (initialized to CS := ∅) of the corrupted senders. Initialization: The challenger C generates cp and runs (mpk, {sk i } i=1 , {ek i } i=1 ) ← Setup(cp, 1 ). Then, it flips a fair coin b ← {0, 1} and gives the master public key mpk to the adversary A.

Encryption queries: The adversary A can adaptively make encryption queries

QEncrypt(i, x 0 , x 1 , t), to which the challenger replies with Encrypt(ek i , x b , t). For any given pair (i, t), only one query is allowed and subsequent queries involving the same (i, t) are ignored. QDKeygen(i, f ), A can adaptively obtain partial functional decryption keys on behalf of uncorrupted senders. At each query, the challenger returns dk f ← DKeygenShare(sk i , t f ) if i ∈ HS (if i ∈ CS, the oracle returns ⊥). Corruption queries:

  , 1 ) : Runs (mpk , msk , {ek i } i=1 ) ← Setup (cp, 1 λ ). Samples 2 secret keys k ij ← K for all i, j ∈ [ ]. Then, set mpk := mpk msk := msk andek i := (ek i , {k ij , k ji } j∈[ ] ) Encrypt(ek i , x i , t) : Given ek i = (ek i , {k ij , k ji } j=1 ) it computes k ijt := F kij (t), k jit := F kji (t) for all j ∈ [ ], C t,i := Encrypt (ek i , x i , t) and K t,i := j=1 k ijt . Next, it computes C t,i := C t,i ⊕ G(K t,i ). It outputs ct t,i = C t,i , {k jit } j=1 .DKeygen(msk, f ) : Given msk and an -argument function f : M → R. It outputs a functional decryption key dk f := DKeygen (msk , f ). Decrypt(dk f , t, {ct t,1 , ct t,2 , . . . , ct t, }) : Takes as input a functional decryption key dk f , a tag t ∈ T , and an -vector of ciphertexts C = (ct t,1 , . . . , ct t, ). For all i ∈ [ ] it computes K t,i = j=1 k ijt and C t,i := C t,i ⊕ G(K t,i ) and runs Decrypt (dk f , t, {C t,1 , C t,2 , . . . , C t, })

Between Definitions 2.11 and 2.12

	Proposition B.1. For any MCFE scheme, 1Ch-IND security implies IND secu-
	rity.

While their decentralized scheme is only proved secure under static corruptions, its centralized version is proved secure under adaptive corruptions.

Introduced in[START_REF] Banerjee | Pseudorandom functions and lattices[END_REF], the notation x p stands for the rounded value (p/q) • x ∈ Zp, where x ∈ Zq, and p < q.

The standard Leftover Hash Lemma cannot be applied since the source A(x ) • s p is not guaranteed to be independent of the seed. A deterministic extractor based on k-wise independent functions[START_REF] Dodis | Exposure-resilient cryptography[END_REF] is thus needed in[START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF].

Acknowledgements

Part of this work was funded by the French ANR ALAMBIC project (ANR-16-CE39-0006) and by BPI-France in the context of the national project RISQ (P141580). This work was also supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701).

Game b ' (b ∈ {0, 1}): This game is identical to Game b with the difference that the challenger initially chooses j 0 ← U ([ ]) as a guess for the smallest index j 0 ∈ HS such that no challenge query CQEnc(j 0 , •, •, t ) is ever made. The challenger aborts and outputs 0 if the guess eventually turns out to be wrong.

For each b ∈ {0, 1}, we have Pr

Lemma A. [START_REF] Abdalla | Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings[END_REF] shows that Game 0 and Game 1 are computationally indistinguishable if F is a secure PRF in the multi-instance setting. This implies

Game 2 : This game identical to Game 1 except that, at each challenge query CQEncrypt(i, x 0 i , x 1 i , t ) for which x 0 i = x 1 i , it also sets C t ,i uniformly random. In this game, we have Pr[W 2 ] = Pr[b = b|Ab] = 1 2 .

To see that Game 1 and Game 2 are computationally indistinguishable, recall that C t ,i = C t ,i ⊕ G(K t ,i ). When the seed K t ,i is uniformly generated the value G(K t ,i ) is pseudorandom, thus Game Proof. Suppose that A is an adversary that is able to distinguish between the two games. We construct an adversary B that breaks the ad-mi-PRF security of F when the challenger samples N = 2 secret keys k ij ← K for all i, j ∈ [ ] in the game of Definition A.2. Algorithm B proceeds in the following way.

Initialization: B starts by drawing j 0 ← U ([ ]) as a guess that j 0 is the smallest index such that no challenge query CQEncrypt(j 0 , •, •, t ) is made. Then, it runs (mpk , msk , {ek i } i=1 ) ← Setup(1 λ ) and mpk := mpk is given to A.

Corruption queries:

In order to answer a corruption query Corrupt(j), the reduction B aborts if j = j 0 since its guess for j 0 was incorrect. Otherwise, it obtains the values {k jτ , k τ j } τ =1 by making corruption queries to its PRF Lemma A.7 ([36, Lemma 5.3]). Let m ≥ 2n • log q and q ≥ 2 prime and let

Lemma A.8 ([32, Corollary 3]). Fix any integers n, m, M , any real ε < 1 and any collection X of M distributions over {0, 1} m of min-entropy n each. Define

and let F be any family of ξ-wise independent functions from m bits to k bits. With probability at least

Lemma A.9. Let F be a family of δ-sure -extractor for the finite collection X of distributions over the input space of F: namely, F satisfies

where F is the uniform distribution over F and U is the uniform distribution over the range of F. For any independent distributions

Proof. For any function f ∈ F, the distributions f (Z 1 ), f (Z 2 ), . . . , f (Z ) are independent since the initial distributions Z 1 , Z 2 , . . . , Z are independent. This implies that for, any function f ∈ F, we have

Let U 1 := (U 1 , U 2 , . . . , U ). For any f ∈ F, we also define the distribution

Since F is a δ-sure -extractor for the collection X , it follows that Pr

By using the identity ∆ ((F, Z F ), (F,

Lemma A.10 ([10, Lemma 2.7]). Let p, q be positive integers such that p < q.

Given R > 0 an integer, the probability that there exists e ∈ [-R, R] such that y p = y + e p , when y ← U (Z q ), is smaller than 2Rp q .

Proof (of Theorem A.5). The proof considers a sequence of hybrid games. In each game, we call W i the event that b = b.

Game 0 : This is the real experiment of Definition A.2, where the challenger initially samples N secret keys SK j = s j ← D Z n ,σ which are revealed to the adversary A in case of corruption queries. At each evaluation query (j, X), the challenger replies by returning

where

are satisfied, where X is the challenge input and X (1) , . . . , X (Q)

where τ (λ) is a noticeable function. Game 2 : In this game, we modify the generation of pp. Initially, the challenger samples a uniformly random matrix

It also defines

), the Leftover Hash Lemma implies that {A i,0 , A i,1 } L i=1 are statistically independent and uniformly distributed over

in such a way that the simulated A ib are statistically uniform under the constraint that G -1 (A ib ) be invertible over Z q . The analysis of [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] shows that the probability that

, so that the public parameters can be simulated in polynomial time. Since the distribution of pp is statistically unchanged, it follows that

At each query X, we can view A(x) as a GSW encryption

for some small norm R x ∈ Z m×m , where

If the conditions [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] are satisfied, at each evaluation query (j, X (i) ), the admissible hash function ensures that

for some small norm R x (i) ∈ Z m×m . Moreover, the unique challenge input X is mapped to an L-bit string x = AHF(X ) such that

Game 3 : We modify the distribution of pp and replace the uniform A ∈ Z n×m q by a lossy matrix of the form

where

) and E ← D Z m×n ,αq , for n n. Under the LWE assumption in dimension n , this change should not affect A's output distribution and we can easily build an

, where the factor n comes from the use of an LWE assumption with n secrets.

Due to the modification introduced in Game 3 , if the conditions [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] are satisfied, each evaluation query (j, X (i) ) obtains a response of the form

Note that the right-hand-side member of ( 24) uniquely determines C • s j with high probability: observe that R x (i) • Ā is statistically uniform over Z m×n q , so by Lemma A.7, the quantity R

Game 4 : We modify the evaluation oracle and introduce a bad event. We define bad x to be the event that for the input x ∈ {0, 1} L such that A(x) = A • R x , for some small-norm R x ∈ Z m×m , we have

The conditions of Lemma A.10 are satisfied since

which yields inequality [START_REF] Chase | Multi-authority attribute based encryption[END_REF]. By taking the union bound over all possible inputs x ∈ {0, 1} L and all indexes j ∈ [N ], we can bound the probability Pr

q . Since Game 3 and Game 4 are identical if BAD does not occur, we obtain the inequality

Recall that, if BAD does not occur, we have

at each query (j, X (i) ). We note that the right-hand-side member of ( 27) is completely determined by R x (i) • Ā and the product C • s j ∈ Z n q . This means that, for each uncorrupted index j ∈ [N ], A's evaluation queries (j, X) always reveal the same n • log q bits of information about s j ∈ Z n . Consequently, each uncorrupted SK j = s j ∈ Z n retains a lot of entropy after all evaluation queries. Game 5 : We modify the challenge oracle. If d = 1, at each challenge query (j, X), the adversary obtains a fresh random y j ← U (Z k p ) instead of the real evaluations y = π (A(x)) • s j p . Clearly, we have Pr[W 5 ] = 1/2 since the output distribution of the challenge oracle does not depend on d ∈ {0, 1}. In Game 4 , if d = 1, each challenge query (j, X ) obtains a response

The same arguments as in [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Appendix D] show that the right-hand-side member of ( 28) is statistically close to U (Z k p ). Indeed,

q , which is an injective function of s j . More precisely, if BAD does not occur and SK j = s j has not been corrupted, A obtains at most n • log q bits of information about s j .

We also note that z j can be written

for some e s,j,x ∈ {0, 1} m . Moreover, the proof of the claim implies that

Proof. Let us consider an efficient MCFE adversary A in the IND security game. We show that A implies an MCFE adversary in the 1Ch-IND game. Suppose that A makes encryption queries for Q distinct tags during the game. The proof uses a standard hybrid argument over the distinct tags that A queries throughout the attack. Let H k with k ∈ {0, 1, . . . , Q} be the game in which the challenger replies to encryption queries QEncrypt(i, x 0 i , x 1 i , t) in the following way.

-

Functional decryption queries:

For each query QDKeygen(f ) made by A k , B k sends the same query to its own challenger and passes the answer to A k . Corruption queries: For each query QCorrupt(i) made by A k , B k makes the same query to its own challenger and forwards the answer to A k . Finalize: When A k halts, B k outputs the same bit b as A k .

We can conclude that, for any efficient IND adversary A, there exists an efficient 1Ch-IND adversary B such that

Proposition B.2. 1Ch-IND security is equivalent to 1Ch-IND security.

Proof. Recall that 1Ch-IND refers to the same security notion as described in Definition 2.12, except that Condition 2 in the Finalize step is replaced by partial key generation oracle QDKeygen(•, •) in a way that is computationally indistinguishable from the previous game. We also note that the vector s f,i ∈ Z n encrypted in [START_REF] Fiat | Broadcast encryption[END_REF] may not even be in the lattice y i • Z n (in contrast with a vector encrypted by the real DKeygenShare algorithm). However, this will not be a problem here. Indeed, our goal is solely to simulate the QDKeygen(•, •) oracle in such a way that Game 1 remains computationally indistinguishable from Game 0 and, in the next transition from Game 1 to Game 2 , allows reducing the security of the scheme in Section 3 to that of our DMCFE scheme. Lemma D.1 shows that Game 1 is computationally indistinguishable from Game 0 as long as the centralized MCFE scheme of Section 3 is secure in the sense of Definition 2.11. We note that a weaker security definition than Definition 2.11 would be sufficient: as a centralized MCFE adversary, the reduction only needs to: (i) send a single functional secret key query for the vector (1, 1, . . . , 1) ∈ Z to its centralized MCFE challenger; (ii) make all its corruption queries at once after having received the master public key.

Game 2 : In this game, we modify the encryption oracle. At each encryption query QEncrypt(i, x 0,i , x 1,i , t), the challenger CH encrypts x 1,i ∈ [-X, X] n0 instead of x 0,i ∈ [-X, X] n0 (we assume that either x 0,i = x 1,i or i ∈ HS since, otherwise, A's output is eventually replaced by a random bit). Namely, it sample e i ← D Z m ,αq and computes

Lemma D.2 relies on the IND-sec security of the scheme in Section 3 to show that Game 2 is computationally indistinguishable from Game 2 under the LWE q,m,n1,α1 assumption. Game 3 : In this game, we modify again the QDKeygen(•, •) oracle and restore it to its original behavior, which is that of the real scheme. This game transition is exactly identical to the one from Game 0 to Game 1 , but in the converse direction. Lemma D.3 states that, as long as the MCFE scheme of Section 3 provides IND-sec security in the sense of Definition 2.11, Game 3 and Game 2 are computationally indistinguishable.

In Game 3 , it is easy to see that C and A are playing the actual sta-IND-sec game where the challenge bit of C is b = 1.

Putting the above altogether, we find that Game 0 and Game 3 are computationally indistinguishable so long as the centralized MCFE scheme of Section 3 provides security in the sense of Definition 2.11.

Lemma D.1. Game 0 and Game 1 are computationally indistinguishable assuming that the MCFE scheme of Section 3 provides IND-sec security. Under the LWE q, m,n, ᾱ1 assumption, we have

Proof. Let us assume that an adversary A can distinguish Game 1 from Game 0 with noticeable advantage ε. We construct a IND-sec adversary B against the centralized MCFE scheme with the same advantage ε.

Our MCFE adversary B obtains from its IND-sec challenger a master public key

where the common public parameters

specify the message space M = [-2 βY, 2 βY ] n and the functional secret key [-1, 1] . Then, B first sends its challenger a unique functional secret key query for the vector (1, 1, . . . , 1) and obtains in return

σ in the second MCFE instance. This allows B to create a master public key

where

is augmented with a description of a second balanced admissible hash function family AHF t : {0, 1} t → {0, 1} L . Before handing mpk to A, our centralized MCFE adversary B waits until A chooses the set CS ⊂ [ ] of players it wants to corrupt. We assume w.l.o.g. that A chooses CS = { h + 1, . . . , }. At this point, B sends corruption queries QCorrupt(i) to its own challenger for all i ∈ CS. The MCFE challenger replies by sending {t i } i∈CS , at which point B gives {sk i = (s i , t i )} i∈CS and mpk to A.

At any time, B can make a query QDKeygen(i, f ) for an index i ∈ HS and a function f described by a vector y = (y 1 , . . . , y ) ∈ Z . At each such query, B proceeds as follows:

-If the pair (i, f ) is such that not all indexes j ∈ HS \ {i} have been the input of a query (j, f ) for the same function f , B samples s i ← D Z n ,σ and defines

In both cases, B just ignores the responses of its challenger as these dummy encryption queries are only made to make sure that B's advantage will not be annihilated by Condition 2 in Definition 2.11. Finally, B halts and outputs whatever A outputs. We observe that B strictly complies with the rules of the IND-sec game at any time. In particular:

-It never makes a QEncrypt(i, •, •, •) query or a corrupted index i ∈ CS.

-By construction, B's encryption queries QEncrypt(i, y i •s i , s f,i , t f ) are all made for message pairs (y

The lemma's claim follows from the fact that, if the secret bit of B's MCFE challenger is b = 0, A's view is exactly the same as in Game 0 . If b = 1, the distribution of partial functional secret keys is given by [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF], which corresponds to Game 1 .

Lemma D.2. Game 2 and Game 1 are computationally indistinguishable assuming that the MCFE scheme of Section 3 provides security in the IND-sec sense. Under the LWE q,m,n1,α1 assumption, we have

Proof. Let A be an adversary that can distinguish between Game 1 and Game 2 with noticeable advantage ε. We build an adversary B against the centralized scheme that wins the IND-sec game (cf. Definition 2.11) with the same advantage. The reduction B begins by obtaining from its challenger a master public key

where the common public parameters cp := λ, max , X, Y, n 0 , n 1 , n, m, α, σ, t , L, q, AHF t .

The adversary A declares the set CS of corrupted senders, as mandated by the static security game. Then, B makes the relevant queries QCorrupt(i) for each i ∈ CS to its challenger and the latter replies with

) for each i ∈ [L] and b ∈ {0, 1}. It also samples t i ← D Z n,σ for i ∈ [ ] and computes t = i=1 t i . This allows B to answer A's static corruption queries by revealing (s i , t i ) ∈ Z n × Z n for all i ∈ CS. In addition, B can feed A with the public parameters for the decentralized scheme, which consist of mpk := ( mpk, mpk, t), where cp := λ, max , X, Ȳ , n, n1 , n, m, ᾱ, σ, f , L, q, AHF f , where X = 2 βY , and

For each encryption query QEncrypt(i, x 0,i , x 1,i , t) made by A for some honest sender i ∈ HS, B passes the same encryption query to its challenger and relays the response back to A. This response is of the form

where e i ← D Z m ,αq and b ∈ {0, 1} is the MCFE challenger's random bit. When A makes an functional decryption query QDKeygen(i, f y ), B parses the corresponding vector as y = (y 1 , . . . , y ) ∈ [-Y, Y ] and does the following:

-If there exists j ∈ HS \ {i} such that QDKeygen(j, f y ) has not been asked yet, then B samples s i ← D Z n ,σ and returns

with e f,i ← D Z m, ᾱq . -If QDKeygen(j, y ) queries have been made for all j ∈ HS \ {i}, B makes the functional decryption query QDKeygen(f y ) to its centralized MCFE challenger. The challenger replies with s y ∈ Z n . Using the s j ∈ Z n that were previously chosen for the function f , B computes When A halts, B outputs whatever A outputs. We observe that we have y j • s j ∈ [-X, X] n , X = 2 Y β, for all j ∈ HS. We also observe that, if A makes all encryption queries QEncrypt(j, x 0,j , x 1,j , t) for all indexes j ∈ HS for a given tag t, so does B for the same tag t.

By construction, B only makes a functional decryption query QDKeygen(f y ) for a function f y when A makes a partial functional key query QDKeygen(j, f y ) for the last honest sender's index j ∈ HS. In the Finalize step of Definition 2.14, Condition 3 requires that, for any function f y involved in queries QDKeygen(i, f y ) for all honest senders' indexes i ∈ HS, the condition f y (X 0 ) = f y (X 1 ) be satisfied for any pair of messages

] satisfying the two sub-conditions of Condition 3. This ensures that B's functional key queries never break the rules imposed by Condition 3 of the Finalize step of the game described by Definition 2.11.

From [START_REF] Goldwasser | Multi-input functional encryption[END_REF], it follows that, if secret bit of B's challenger is b = 0, B is playing Game Proof. The proof is almost identical to that of Lemma D.1, the only difference being that, at each encryption query (i, x 0,i , x 1,i , t) made by A, the reduction B encrypts x 1,i (instead of x 0,i in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]). The details are omitted.