Michel Abdalla

Florian Bourse

Hugo Marival

David Pointcheval

Azam Soleimanian

Hendrik Waldner

Multi-Client Inner-Product Functional Encryption in the Random-Oracle Model

Keywords: Functional encryption, multi-client, inner-product functionality, random oracle

Multi-client functional encryption (MCFE) is an extension of functional encryption (FE) in which the decryption procedure involves ciphertexts from multiple parties. It is particularly useful in the context of data outsourcing and cloud computing where the data may come from different sources and where some data centers or servers may need to perform different types of computation on this data. In order to protect the privacy of the encrypted data, the server, in possession of a functional decryption key, should only be able to compute the final result in the clear, but no other information regarding the encrypted data. In this paper, we consider MCFE schemes supporting encryption labels, which allow the encryptor to limit the amount of possible mix-and-match that can take place during the decryption. This is achieved by only allowing the decryption of ciphertexts that were generated with respect to the same label. This flexible form of FE was already investigated by Abdalla et al. [Asiacrypt 2019] and Chotard et al. [Asiacrypt 2018]. The former provided a general construction based on different standard assumptions, but its ciphertext size grows quadratically with the number of clients. The latter gave a MCFE based on Decisional Diffie-Hellman (DDH) assumption which requires a small inner-product space. In this work, we overcome the deficiency of these works by presenting three constructions with linear-sized ciphertexts based on the Matrix-DDH (MDDH), Decisional Composite Residuosity (DCR) and Learning with Errors (LWE) assumptions in the random-oracle model. We also implement our constructions to evaluate their concrete efficiency.

Introduction

Functional encryption (FE) [BSW11,O'N10] is an encryption scheme that goes beyond all-ornothing decryption, allowing users in possession of a secret functional decryption key to learn a specific function of the encrypted message, and nothing else. More formally, in an FE scheme for a class of functions F , a ciphertext encrypting a message x can be used in conjunction with a functional decryption key dk f , derived for a function f from F , in order to compute f (x) while no more information about x should be leaked. Due to its generality, FE encompasses many existing notions, such as identity-based encryption [BF01,Coc01,Wat05] and attribute-based encryption [GPSW06,OSW07,Wat11]. Now, general purpose FE is seen as a holy grail for modern cryptography. Several works have made progress towards this goal [GGH + 13,Wat15,BCP14], but no constructions are known from standard assumptions. Since general-purpose FE still remains far from reality, different lines of work focused on building FE for specialized classes of functions, such as predicate encryption or inner-product FE.

Inner-product FE (IPFE) is a special case of FE [ABDP15] in which the encrypted messages are vectors x, and the functional decryption keys dk y , are associated with vectors y of the same dimension, and the decryption yields the inner-product between those two vectors (i.e., x, y ). It was first considered by [ABDP15] as the first efficient encryption scheme going beyond all-or-nothing decryption. The class of functions defined is simple enough to allow for practical instantiation, as it is only linear, but still allows for many applications. In particular, it allows for any bounded depth computation by properly increasing the size of the inputs [ALS16,AR17]. + 14] 1 , is a natural extension of FE where data comes from different sources/clients that may not trust each other and can be independently and adaptively corrupted by the adversary. The special case of Multi-input FE (MIFE) [ACF + 18,AGRW17] corresponds to the setting where the clients are honest but curious, and each coordinate of a vector can be encrypted separately before being combined during the decryption procedure. The main challenge to overcome when designing MCFE is that the different parts of the ciphertext have to be crafted without sharing any randomness, as opposed to what happens in all the existing constructions for single-input IPFE (or simply IPFE).

Multi-client FE (MCFE), introduced in [GGG

MCFE with labels, introduced in [GGG + 14] and recast in the context of the inner-product functionality by [CDG + 18a], allows for more control over the data during encryption. In an MCFE scheme with labels, ciphertexts strictly depend on labels. When combining ciphertexts during decryption, data associated with different labels cannot be mixed to give a valid decryption or useful information. Thus, the data from different sources can only be combined if they have the same label. The construction suggested in [CDG + 18a] for the inner-product functionality is based on the Decisional Diffie-Hellman (DDH) assumption, and one of its drawbacks is that the decryption algorithm needs to compute the discrete logarithm of a group element, which means it can only support a small range of values for the inner-products, thus limiting its possible applications. Abdalla et al. [ABG19] proposed a general conversion from single-input to MCFE. In their scheme, each client i encrypts its message x i as the vector (0|| . . . ||0||x i ||0|| . . . ||0) + t i, where t i, is generated by a PRF with shared keys such that n i=1 t i, = 0, with n the number of clients. From there, by applying a layer of single-input IPFE they get a labeled MCFE. This explains why the size of the ciphertext in their scheme is quadratic w.r.t the number of the slots/clients. Note that their scheme also needs a master secret key of size O(n 2 ) which is the number of keys k i,j shared between clients i and j.

Challenges and Contributions

This paper aims at constructing efficient labeled MCFE schemes based on different assumptions. Our contributions can be summarized as follows: Efficient decryption and shorter ciphertext. We present two constructions: one based on the Decisional Composite Residuosity (DCR) assumption and the other one based on the Learning with Errors (LWE) assumption. These constructions can cope with the drawbacks in the constructions of [CDG + 18a] and [ABG19], i.e. they do not require a discrete-logarithm computation in the decryption algorithm while the size of the ciphertext is smaller (w.r.t the number of clients). The security proof for our constructions based on DCR and LWE can be more challenging than MCFE based on DDH. This difficulty comes from the fact that MCFE is in the symmetric key setting and the hybrid argument for many challenges can be complicated. More precisely, one needs to show that in the current hybrid game, given the information regarding the master key that is leaked through all other queries (encryption, functional keys, and random-oracle (RO) queries) the master key still has enough entropy to hide the chosen bit in the challenge ciphertext. This is easier to prove in DDH-based MCFE schemes since the master secret key is uniformly distributed over Z q and the ciphertexts are defined in a group with the same order. This common modulus not only helps to interpret the leaked information more straightforwardly, but also to prove that the chosen bit can be perfectly hidden. However, for our DCR-based MCFE, this is not the case, and one needs to check how the leaked information can change the lattice to which the master secret key belongs (since the master key is distributed over the lattice Z n ) and how it can affect the challenge which is a value modulo N . By relying on a theorem from lattice-based cryptography and setting the parameters similarly to the single-input IPFE [ALS16], and also by a proper simulation of random-oracle queries one can guarantee that the information leaked through the encryption queries is still tolerable, and that the security proof works. Slightly in detail, the proper simulation of random-oracle queries let us to unify the leakage from all other ciphertexts. This unified information is the same as the leaked information from the public-key in [ALS16]. Then, we can use the same strategy of [ALS16] to show that challenge ciphertext hides the chosen bit statistically w.r.t a selective-security notion. But the good point is that all other steps which are based on the computational-assumption DCR are adaptively secure. Thus, we only need to lift the security back to adaptive in our statistical argument, which is possible by a proper choice of parameters. All is left is to discuss the simulation of RO queries such that it can unify and properly interpret the leakage from all other ciphertexts. Here, we use random self-reducibility of DCR assumption which let us build polynomially many random samples of DCR from one given sample. Then RO queries can be replaced with these random samples. The common point about all these samples is that they are indistinguishable from elements in the class of N residues in Z N 2 and so they all have the same structure z N mod N2 . Having this N common among all the RO queries is what we needed as a tool to unify the leakage from ciphertexts. More precisely, now the leakage from all other ciphertexts can be interpreted independently of as s mod λ (where s is the secret-key, H( ) s is appeared in the ciphertexts, and λ is such that z N λ = 1 mod N 2 ).

For our LWE-based MCFE (which can bee seen as the main contribution), it is more challenging since the leaked information through the encryption queries cannot be simulated during the security proof, because of the noise terms introduced by the LWE assumption. We overcome this challenge by using noise flooding techniques, and avoid the inefficiency drawback by rounding the ciphertext down to a smaller space. This way, the noise vanishes during this rounding operation. The remaining leakage concerns a part of the master key that is uniformly random, and can be easily simulated. More precisely, in our LWE-based construction, ciphertext includes a multiplication term Z i • H( ) where Z i = (s i , t i ) comes from the master key and H( ) is a hash function modeled as RO. This has to be a RO on Z q leading us to replace it with LWE samples (which give randomness over Z q ) i.e., H( ) = (a , Sa + e ). The term t i • e is what can dramatically leak information about Z i . In the proof of Agrawal et al. [ALS16] for IPFE, the term Sa can be placed in the ciphertext directly since the client knows the secret S. But for our labeled MCFE this is not the case and the term e has to be there which leads to the leakage t i • e . Thus, we map the ciphertext from Z q to a small space Z q 0 such that the term t i • e is small enough to be neglected after this change. The term t i • Sa would be hidden through the term s i • a where s i is uniform 2 . These two strategies give us the guarantee that no information about t i is leaked through encryption queries. We then show that given the other sources of information that the adversary may access (functional keys and corruption queries), the master secret key t i still has enough entropy to be used in a left-over hash lemma argument and statistically hides the message-challenge w.r.t a selective-security notion. Then similar to our discussion for DCR-based MCFE, one can simply lift the security to the adaptive case by a proper choice of parameters. Now we discuss a bit about the simulation of RO queries relying on the computationalassumption LWE. A curious reader may already have noticed that unlike DCR-based MCFE where we use random self-reducibility of the DCR assumption, we may not be able to do the same here. Fortunately, the definition of the LWE problem already provides polynomially many samples for the same secret S as (a , Sa + e ) where S is a vector. We simply extend it to the case where S is a matrix. Note that the requirement for a matrix-secret instead of vector-secret comes from the security proof, since having S as a matrix gives t i as a vector (note that in the ciphertext we have

Z i • H( ) = s i • a + t i • (Sa + e )
where Z i = (s i , t i ) is the secret-key). Then having t i as a vector provides enough entropy in the term (x 1 -x 0 ) • (t 1 , . . . , t n ) T which will be used in a left-over-hash-lemma argument to conclude that the challenge ciphertext is statistically independent of chosen bit.

Various assumptions. Following the constructions proposed by Chotard et al. [CDG

+ 18a],
we present a generalization of their scheme, relying on the Matrix-DDH (MDDH) assumption3 . Our Labeled MCFE based on DCR assumption is the first labeled MCFE scheme based on this assumption and with linear ciphertext size. Our labeled MCFE based on LWE is the most efficient MCFE scheme based on this assumption compared to [ABG19,LT19], albeit in the RO model. Decentralization (with linear size of the secret key). Abdalla et al. [ABG19,ABKW19] presented a compiler converting a MCFE scheme to a decentralized MCFE (DMCFE) requiring a square size of the secret key (w.r.t the number of clients)4 . Chotard et al. [CDG + 18a] also extended their DDH-based MCFE scheme to its decentralized counterpart using pairings and with linear key size. Here we present a generalization of their scheme to get DMCFE with linear key size and without pairings. In our proof, the security assumption/requirement associated with underlying building blocks is also weaker than [CDG + 18a]. This part is discussed in Appendix D. Implementation. We also have implemented our constructions showing that for applications with large message spaces our DCR-based MCFE scheme is quite reliable while for small message space our LWE-based MCFE scheme is more efficient. This gives enough flexibility to choose the scheme that better fits the application. Apart from the size of the message space, other parameters are chosen so that the schemes can support different applications.

Related Work

Here, we mainly discuss the three mentioned works [ABG19,CDG + 18a,LT19] which are directly relevant to our contributions. The main security notions used in these papers are one-security and pos + -security. In one-security, the adversary can ask for many labels but for each label it can issue only one complete ciphertext. In pos + -security, the adversary can ask for many ciphertexts per label. 5In [CDG + 18a], instead of proving pos + -security, the authors first prove one-security for their construction and then apply a compiler similar to [ACF + 18,AGRW17] to lift the security to pos + . As in [ACF + 18,AGRW17], this compiler is actually a single-input IPFE layer. We also use this technique in this paper. The security in [CDG + 18a] relies on the DDH assumption in the RO model. The ciphertext in their scheme has the form ct i, = g x i • H( ) s i . The main challenge in the proof is to bound the leakage from the ciphertexts (as we are in the symmetric key setting with many ciphertexts to be handled directly). The idea is to change the RO queries in an indistinguishable way such that all the encryption queries, except for the challenge, have the same form (i.e., H( ) = g u where u = r • a, a = (1 a) T , r , a R ← Z p ) leading to the same leakage s i • a from all other encryption queries. This leakage, along with the leakage from the functional secret keys and corrupted individual encryption keys, would change the distribution of the master secret key such that the multiplication

s i • u * (where u * = u 1 a + u 2 a ⊥ , u 1 R ← Z p , u 2 R ← Z * p )
perfectly hides the chosen bit in the challenge. More precisely, the secret key is computed as

s i + a ⊥ γ(x 1 i -x 0 i ) where γ = -1/u * • a T and s i R ← Z 2 p .
The ciphertext is of linear size while one needs to compute a discrete-logarithm during the decryption.

In [ABG19], as we mentioned at the beginning of this section, each client builds a value t i, such that t i, = 0. For the security proof, they simply change the values of t i, among the slots such that each t i, is replaced with a random value except one of them associated with an honest slot, called i * , which takes care of the relation t i, = 0. Then, one-security would be

Scheme |ski| |pp| |ct| q σ (msk) model [ABG19]+ [ALS16] O(nκ) O(n0(n0 + n) log q) n 2 log q poly(n0) poly(n0) SM [LT19] O(κ 5 ) O(κ 13 ) O(nκ 7 log q) 2 κ 2 O(2 κ 2 ) SM our scheme n0 + m0 n0 + m0 n log q0 Ω(n0 ω(1) q0B) ω(1) ROM
i, = G T 0 • x i + A( ) T
• s i + noise has a product term A T ( ) • s i which hides the chosen bit in the challenge. Unlike our constructions, the matrix A( ) is built from some public matrices and the label , rather than a RO, using an idea from [LST18] to derive A( ) from some public matrices using the Gentry-Sahai-Waters (GSW) fully homomorphic encryption scheme [GSW13]. That is, A( ) is the product of GSW ciphertexts dictated by a special hash applied to . The security proof relies on the fact that, with noticeable probability, A( ) is a GSW encryption of 1. From there, it can be indistinguishably changed to the GSW-encryption of 0 in all other encryption queries, except for the challenge. Finally, an argument similar to [CDG + 18a] (through the lossy form of matrix A) is used to conclude the proof. [ALS16]. In this table, κ and n 0 are security parameters where n 0 is the size of the secret. In our scheme, m 0 > Ω(log q) for selective security and m 0 > Ω(log q + 4n • log P ) for the adaptive case where n is the number of slots and P defines the bound of the message-space. And we also have q 0 = poly(n 0 ) and B is a constant as the bound of the error-space. And σ stands for the standard-deviation used in the generation of msk. So as one can conclude from this table, for the client i, the size of its secret-key sk i and also the size of public-parameters pp in [ABG19], depend on the number of clients n, while in [LT19] and in our scheme they are constant (w.r.t n). Still one can argue that for the scheme of [LT19], the size of sk i and pp is much larger comparing with our scheme. Note that the security parameter for their scheme is κ and for our scheme is n 0 which means that our scheme has linear-size of sk i and pp w.r.t to the security parameter. While in [LT19] they are polynomials respectively of degree 5 and 13 (w.r.t the security parameter). In [ABG19], the size of public-parameters also depends on n 0 which is the security-parameter for the underlying LWE scheme [ALS16]. In our scheme the only public-parameter is the hash function (modeled as random oracle) and it is a vector of size n 0 + m 0 . While [ALS16] has some matrices as the public parameters leading to a size of degree 2 polynomial for |pp| (w.r.t the security parameter), while in our scheme it is linear. About size of the ciphertext ct, in [ABG19], it has square-size w.r.t the number of clients and in [LT19] has 7-degree-size w.r.t the security parameter. While in our scheme it is linear w.r.t to n and logarithmic w.r.t the security parameter.

Putting together, this table shows that having constant or linear size of sk i , pp or ct w.r.t n can be challenging and leads to a polynomial-size of large degree w.r.t other parameters. We avoid this inefficiency by relying on the RO assumption.

Preliminaries

Notation. We use [n] to denote the set {1, . . . , n}. We write x for vectors and x i for the i-th element. In this paper, κ stands for the security parameter. The function poly(•) shows an arbitrary polynomial function. The computational indistinguishability of two distributions G 0 and G 1 , is denoted by G 0 ∼ = G 1 . The function negl(•) denotes the negligible function. In this paper all the algorithms are Probabilistic Polynomial Time (p.p.t.) with respect to the length of the input. For security parameter κ and additional parameters n, we denote the winning probability of an adversary A in a game or experiment G as Win G A (κ, n). The probability is taken over the random coins of G and A. We define the distinguishing advantage between games G 0 and G 1 of an adversary A in the following way:

Adv G A (κ, n) = Win G 0 A (κ, n) -Win G 1 A (κ, n) .

Multi-Client Functional Encryption

A labeled MCFE scheme is formally defined as follows, which is an adaptation of the MIFE definition [GGG + 14] with labels.

Definition 1. (Multi-Client Functional Encryption) Let F = {F ρ } ρ be a family (indexed by ρ) of sets F ρ of functions f : X ρ,1 × • • • × X ρ,nρ → Y ρ . 7
Let Labels = {0, 1} * or {⊥} be a set of labels. A multi-client functional encryption scheme (MCFE) for the function family F and the label set Labels is a tuple of five algorithms MCFE = (Setup, KeyGen, KeyDer, Enc, Dec):

Setup(1 κ , 1 n ): Takes as input a security parameter κ and the number of parties n, and generates public parameters pp. The public parameters implicitly define an index ρ corresponding to a set F ρ of n-ary functions (i.e., n = n ρ ). KeyGen(pp): Takes as input the public parameters pp and outputs n secret keys {sk i } i∈ [n] and a master secret key msk. KeyDer(pp, msk, f ): Takes as input the public parameters pp, the master secret key msk and a function f ∈ F ρ , and outputs a functional decryption key sk f . Enc(pp, sk i , x i , ): Takes as input the public parameters pp, a secret key sk i , a message x i ∈ X ρ,i to encrypt, a label ∈ Labels, and outputs ciphertext ct i, . Dec(pp, sk f , ct 1, , . . . , ct n, ): Takes as input the public parameters pp, a functional key sk f and n ciphertexts under the same label and outputs a value y ∈ Y ρ .

A scheme MCFE is correct, if for all κ, n ∈ N, pp ← Setup(1 κ , 1 n ), f ∈ F ρ , ∈ Labels, x i ∈ X ρ,i , when ({sk i } i∈[n]
, msk) ← KeyGen(pp) and sk f ← KeyDer(pp, msk, f ), we have Pr [Dec(pp, sk f , Enc(pp, sk 1 , x 1 , ), . . . , Enc(pp, sk n , x n , )) = f (x 1 , . . . , x n )] = 1.

Please note that each slot i in a MCFE scheme has a different secret key sk i , which can be individually corrupted. In addition, one also needs to consider corruptions to handle possible collusions between different parties. In the following, we formally define the security notion of a MCFE scheme.

Definition 2. (Security of MCFE)

Let MCFE be an MCFE scheme and Labels a label set. For β ∈ {0, 1}, we define the experiment IND MCFE β in Fig. 1, where the oracles are defined as:

Corruption oracle QCor(i): Outputs the encryption key sk i of slot i. We denote by CS the set of corrupted slots at the end of the experiment. Left-Right oracle QLeftRight(i, x 0 i , x 1 i , ): Outputs ct i, = Enc(pp, sk i , x β i , ) on a query (i, x 0 i , x 1 i , ). We denote by Q i, the number of queries of the form QLeftRight(i, •, •, ). Encryption oracle QEnc(i, x i , ): Outputs ct i, = Enc(sk i , x i , ) on a query (i, x i , ). Key derivation oracle QKeyD(f ): Outputs dk f = KeyGen(msk, f ). and where Condition (*) holds if all the following conditions hold:

-If i ∈ CS (i.e., slot i is corrupted): for any query QLeftRight(i,

x 0 i , x 1 i , ), x 0 i = x 1 i . IND MCFE β (κ, n, A) pp ← Setup(1 κ , 1 n ) ({ski} i∈[n] , msk) ← KeyGen(pp) α ← A QCor(•),QLeftRight(•,•,•,•),QEnc(•,•,•),QKeyD(•) (pp) Output: α if Condition (*) is satisfied,
or a uniform bit otherwise Fig. 1: Security games for MCFE -For any label ∈ Labels, for any family of queries {QLeftRight(i,

x 0 i , x 1 i , ) or QEnc(i, x i , )} i∈[n]\CS
, for any family of inputs {x i ∈ X } i∈CS , for any query QKeyD(f ), we define x 0 i = x 1 i = x i for any slot i ∈ CS and any slot queried to QEnc(i, x i , ), we require that:

f (x 0 ) = f (x 1 ) where x b = (x b 1 , . . . , x b n ) for b ∈ {0, 1}. We insist that, if one index i /
∈ CS is not queried for the label , there is no restriction.

The weaker versions of the security are defined as xx-yy-zz-IND MCFE β (xx, yy, zz may be empty when we do not have the corresponding restriction), where, -When xx = sta: the adversary should output the set CS at the beginning of the game, and it does not have access to the oracle QCor after that. -When yy = one: for any slot i ∈ [n] and ∈ Labels, Q i, ∈ {0, 1}, and if Q i, = 1, then for any slot j ∈ [n] \ CS, Q j, = 1. In other words, for any label, either the adversary makes no left-right query or makes exactly one left-right query for each i ∈ [n] \ CS. -When yy = pos + : for any slot i ∈ [n] and ∈ Labels, if Q i, > 0, then for any slot j ∈ [n]\CS, Q j, > 0. In other words, for any label, either the adversary makes no left-right encryption query or makes at least one left-right encryption query for each slot i ∈ [n] \ CS. -When zz = sel: the adversary should output the challenges at the beginning of the game, and it does not have access to the oracle QLeftRight after that. This case is referred as the selective security.

We define the advantage of an adversary A in the following way:

Adv xx-yy-zz-IND MCFE,A (κ, n) = Pr[xx-yy-zz-IND MCFE 0 (κ, n, A) = 1] -Pr[xx-yy-zz-IND MCFE 1 (κ, n, A) = 1] .
A multi-client functional encryption scheme MCFE is xx-yy-zz-IND secure, if for any p.p.t. adversary A, there exists a negligible function negl such that:

Adv xx-yy-zz-IND MCFE,A (κ, n) ≤ negl(κ).
We omit n when it is clear from the context. We also often omit A from the parameter of experiments or games when it is clear from context.

Definition 3. (1-label Security)

Let MCFE be an MCFE scheme, F = {F ρ } ρ a function family indexed by ρ and Labels a label set. For xx, yy, zz defined as Theorem 2, and β ∈ {0, 1}, we define the experiment xx-yy-zz-1-label MCFE β exactly as in Fig. 1, where the oracles are defined as for Theorem 2, except:

Left-Right oracle QLeftRight(i, x 0 i , x 1 i , ): Outputs ct i, = Enc(pp, sk i , x β i , ) on a query (i, x 0 i , x 1 i ,
). This oracle can be queried at most on one label. Further queries with distinct labels will be ignored. Encryption oracle QEnc(i, x i , ) Outputs ct i, = Enc(pp, sk i , x i , ). If this oracle is queried on the same label that is queried to QLeftRight, the game ends and returns 0.

Condition (*) is defined as for Theorem 2. We define the advantage of an A as follows:

Adv xx-yy-zz-IND-1-label MCFE,A (κ, n) = Pr[xx-yy-zz-IND-1-label MCFE 0 (κ, n, A) = 1] -Pr[xx-yy-zz-IND-1-label MCFE 1 (κ, n, A) =
(κ, n) ≤ q Enc • Adv xx-yy-zz-IND-1-label MCFE,B
(κ, n), By q Enc we denote the number of distinct labels queried by A to QLeftRight.

Inner-Product Functionality

We describe the functionalities supported by the constructions in this paper, by considering the index ρ of F in more detail.

The index of the family is defined as ρ = (R, n, m, X, Y ) where R is either Z or Z L for some integer L, and n, m, X, Y are positive integers. If X, Y are omitted, then X = Y = L is used (i.e., no constraint). This defines

F ρ = {f y 1 ,...,yn : (R m ) n → R} where f y 1 ,...,yn (x 1 , . . . , x n ) = n i=1 x i , y i = x,
y , the vectors satisfy the following bounds:

x i ∞ < X, y i ∞ < Y for i ∈ [n]
, and x ∈ R mn and y ∈ R mn are the vectors corresponding to the concatenation of the n vectors x 1 , . . . , x n and y 1 , . . . , y n respectively.

We note that since this work focuses on labeled MCFE schemes for the IP functionality, the setup algorithm of all our constructions implicitly takes this functionality as an input.

Constructions

In this section, we present our MCFE constructions for the inner-product functionality based on the MDDH, DCR and LWR assumptions. Intuitively, we extend single-input IPFE techniques to their counterpart MCFE schemes by considering each slot as an independent client such that the clients can share the required randomness through the random oracle. While the IPFE constructions are based on a combination of the randomness and the public-key, we replace it with a combination of random oracle and the master key in our MCFE schemes. The use of random oracles for generating randomness also explains why we ended up with one-IND security (which can be easily extended to pos + -security via an existing compiler [CDG + 18b]). Regarding the security proof, we present in Section 3.5 a general proof sketch covering the main proof idea of all three constructions, despite some differences in the actual proof details.

MCFE based on the MDDH Assumption

In this section, we present a MCFE scheme supporting labels, based on the MDDH assumption. One can see this construction as an extension of single-input IPFE scheme where the term h r i is replaced with H( ) S i (the value h i is the public-key of IPFE scheme) and the value H( ) generates the required randomness. The MDDH assumption was initially introduced in [EHK + 13]. We recap it here:

Adv MDDH D ,k ,A (κ) := | Pr[A(1 κ , G, [A], [Aw]) = 1] -Pr[A(1 κ , G, [A], [u]) = 1]|, Setup(1 κ , n) : G := (G, p, g) ← GGen(1 κ ) Select H : Labels → G k+1
Return pp := (G, H).

KeyGen(pp)

:

Si ← Z m×(k+1) p , ski = Si, msk = {Si} i∈[n] Return ({ski} i∈[n] , msk) Enc(pp, ski, xi ∈ Z m p , ) : ci, := Si • u + xi where [u ] := H( ) ∈ G k+1 Return cti, := [ci, ] ∈ Z m p KeyDer(pp, msk, y ∈ Z mn p ) : For y = (y1, . . . , yn), with yi ∈ Z m p sky := i∈[n] S i yi Return sky Dec(pp, sky, {cti, } i∈[n] , y, ) : [u ] = H( ) ∈ G k+1 C := i∈[n] [ci, ] • yi -[u ] • sky Return log(C)
G = (G, g, p) ← GGen(1 κ ), A ← D ,k , w ← Z k p , u ← Z p .
We say that the D ,k -Matrix Diffie-Hellman Assumption (D ,k -MDDH) holds in group G, if for all p.p.t. adversaries A, there exists a negligible function negl such that:

Adv MDDH D ,k ,A (κ) ≤ negl(κ).
Our MDDH-based MCFE construction is given in Fig. 2.

Theorem 7. Assume that the D k -MDDH assumption holds, then the MCFE scheme described in Fig. 2 is one-IND-secure in the random oracle model.

The correctness and the security of this construction are given in Appendix A.

MCFE based on the DCR Assumption

In this section we present a MCFE scheme based on the DCR assumption in the random-oracle model. As we mentioned, the main benefit of this construction is that one can retrieve the final result without computing the discrete-logarithm value. The following notations are used in this section. D Z k ,σ stands for the Gaussian distribution over Z k with the standard deviation σ and the mean 0 (this notation is also used in the next section). Z N is the additive group of integers modulo N and Z * N denotes the multiplicative group of integers modulo N . That is, including all a ∈ Z N such that gcd(a, N ) = 1 where gcd(b, c) is the greatest common divisor of b and c. Let N = pq be a safe modulus, meaning that p and q are large safe primes in the form of p = 2p + 1 and q = 2q + 1, where p , q > 2 κ . In this paper SP(κ) is the algorithm producing safe-primes p, q as above. It is believed that for a given N as above it is hard to find p, q.

The single-input functional encryption scheme based on the Paillier cryptosystem has been proposed by Agrawal et al. [ALS16]. Their IPFE scheme is presented in Appendix B.1. In their construction, the encryption algorithm includes 2 main parts:

ct 0 = g r where r R ← {1, . . . , [ N 4 ]} and ct i = (1 + N ) x i • h r i for i = 1, . .

. , n

where h i = g s i is the public key. The term h r i = g rs i can be replaced with H( ) s i which removes the need for sharing a random r among the clients, since the random oracle H(•) is publicly known. This explains the intuition for our MCFE scheme represented in Fig. 3. Regarding the security proof, the indistinguishable changes in RO-queries lead to an indistinguishable change in the (sub)lattice the master key belongs to (Note that the master secret key is chosen from lattice Z n by a Gaussian distribution D σ ). From there, a theorem from lattice-based cryptography and similar parameter setting to the single-input IPFE [ALS16] can guarantee the new distribution of the master secret key (along side the proper change in the RO-query associated with the challenge) is well enough for the security proof to work.

Definition 8 (Decisional Composite Residuosity (DCR) Assumption).

Let N = pq for two safe-primes p and q. We define the advantage of an adversary A for the DCR assumption

Setup(1 κ , n) :
-run SP(κ) to get (p, q) and compute N = pq.

-Let H : Labels → Z * N 2 be a full-domain hash function.

-set X < N/2n

Return pp = (N, H, X)

KeyGen(pp) : -sample s ← DZn,σ where σ > √ κ • N 5/2 for the selective security σ > κ + 2n • log(2X) • N 5/2
for the adaptive security.

Return msk = s and ski = si.

Enc(pp, ski, xi, i, ) :

To encrypt a message x ∈ Z n with |xi| ≤ X:

-compute: cti = (1 + N ) x i .H( ) s i mod N 2 .
Return ct = {cti}i KeyDer(pp, msk, y) :

For vector y ∈ Z n with |yi| ≤ Y < N/2n: -compute sky = Σiyi.si Return sky Dec(pp, y, sk, {cti, } i∈[n] , l) : compute C = i ct y i i, • H( ) -sk Return C -1 mod N 2 N
Fig. 3: MCFE based on the DCR assumption in the following way:

Adv DCR N,A (κ) := | Pr[A(1 κ , z N mod N 2 ) = 1] -Pr[A(1 κ , z) = 1]|, where z ← Z * N 2 .
We say that the DCR Assumption holds, if for all p.p.t. adversaries A, there exists a negligible function negl such that:

Adv DCR N,A (κ) ≤ negl(κ).
Theorem 9. Assume that the DCR assumption holds, then the MCFE scheme described in Fig. 3 is one-IND-secure in the random-oracle model.

The proof of the correctness and security can be found in Appendix B.2.

MCFE based on LWE Assumption

In this section, the notation a denotes the largest integer number smaller than a.

Learning With Errors. The problem of Learning with Errors (LWE) was introduced in a seminal work of Regev [Reg05]. The idea for LWE problem is to provide a system of linear equations such that each equation is associated with an error term. Regev showed that in this case the number of equations does not really matter and it is hard to find any information about the secret. This problem is formally defined as follows.

Definition 10 (Decisional LWE assumption). Let q, α be functions of parameter n 0 . The Learning with Error (LWE q,α ) problem is to distinguish two following distributions given access to polynomially many samples for a fixed vector

s R ← Z n 0 q , D = {(a, a, s + e) : a R ← Z n 0 q , e R ← D Z,αq }, D = {(a, u) : a R ← Z n 0 q , u R ← Z q }
Concretely, for any adversary A there exists a negligible function negl such that:

Adv LWE A (n 0 ) = | Pr[A D(s,•) (α, q, n 0 ) = 1] -Pr[A D (•) (α, q, n 0 ) = 1]| ≤ negl(n 0 )
where the oracles D(s, •) and D (•) output samples respectively from D (with a fixed secret s) and D .

Our MCFE Construction Based on LWE

In this section we propose a MCFE construction based on the LWE problem as an extension of single-input FE presented by Agrawal et al. [ALS16] (see Appendix C.1). Although the intuition for our construction is similar to the previous constructions, we highlight here the differences that are the use of a rounding-map, and the part of the secret key that is uniform. In [ALS16] the mheLWE assumption is used to simulate all the queries in a correct way, as the inputs of the assumption are enough for this purpose. After applying this assumption (on one ciphertext) a product between parts of the master secret key and a uniformly random vector appears in the ciphertext. If the first factor of this multiplication has enough min-entropy, conditioned on the information available to the adversary, applying the leftover hash lemma guarantees that this product seems uniform, which concludes the proof. Now all is left to prove is that the part of the master secret key that is involved has enough min-entropy conditioned on what the adversary can see. Since in [ALS16], we are in the public-key setting, all the information (regarding the master key) the adversary can extract from all other honestly generated ciphertexts is the same as what it gets from the public-key. Thus, the leakage of all the honestly generated ciphertexts can be precisely quantified, and simulated using only the information contained in the public parameters. In this work, we need to change to the symmetric-key setting (as is the case in MCFE), so it is not as straightforward to quantify the leakage from all the ciphertext queries, and the information required to simulate the ciphertexts during the proof cannot be hidden in the public parameters. And in fact, in our case this leakage is really noticeable, especially since the ciphertexts are generated by different parties and each ciphertexts can leak information about different parts of the master secret key. Leveraging the use of a random oracle, we argue that the leakage coming from all the ciphertext queries can be deduced from leakage about some secret matrix, together with some noise term, under the LWE assumption. The leakage about the secret matrix is completely hidden by the uniform secret key s i , whereas the rounding-map completely removes the noise term t i • e when the parameters are carefully selected.

In our construction we are using a rounding-map which is formally defined as follows.

Definition 11 (Rounding-map from Z q to Z q 0 ). For q ≥ q 0 ≥ 2, a rounding map . q 0 : Z q -→ Z q 0 is defined as x q 0 = (q 0 /q) • x where x = x mod q and • is a classical rounding function over integers8 . This notation can be extended component-wise to vectors and matrices over Z q .

Our MCFE scheme based on the LWE assumption is given in Fig. 4. The setting of the parameters is discussed separately in Appendix C.3.

Theorem 12. The presented MCFE scheme in Fig. 4, is an one-IND-secure MCFE scheme under the LWE assumption and in the random-oracle model.

The proof of the correctness and security can be found in Appendix C.2.

Security Analysis

Proof (Proof Overview). To prove the security of our constructions under the different assumptions, we consider the case where A only queries QLeftRight on one label , and never queries QEnc on . In more detail, we show that: Adv one-1-label MCFE,A (κ, n) ≤ negl(κ), where Adv one-1-label MCFE,A (κ, n) is defined as described in Theorem 3. Then we use Theorem 4 to obtain the theorem.

For the proof of the 1-label security we proceed via a hybrid argument, using the games described in Fig. 5. The game G 0 corresponds to one-1-label MCFE 0 (κ, n, A) and the game G 7 to one-1-label MCFE 1 (κ, n, A). This yields:

Adv one-1-label MCFE,A (κ, n) = |Win G 0 A (κ, n) -Win G 7 A (κ, n)|.
Setup(1 n0 , n) :

-set integers m0, q0 ≥ 2, q > q0, K = nP V and α ∈ (0, 1).

-let H : Labels → Z n0+m0 q be a full-domain hash function

Return pp = (m0, q, α, K, P, V )

KeyGen(pp) : -sample Zi = (si, ti) R ← Z 1×n0 q × D Z 1×m 0 ,αq
Return msk = {Zi} i∈ [n] and ski = Zi.

Enc(pp, ski, xi, i, ) :

To encrypt xi ∈ {0, . . . , P -1}:

-compute cti, = Zi • H( ) + q K • xi q0
Return cti, KeyDer(pp, msk, y) :

For the vector y ∈ V:

-compute:

sky = i∈[n] yi • Zi ∈ Z 1×(m0+n0)
Return sky Dec(pp, y, sk, {cti, } i∈[n] , ) :

-compute

µ = i∈[n] yi • cti, -sk • H( ) q0 mod q0 Return µ ∈ {-K + 1, . . . , K -1} that minimizes | q0 q q K • µ -µ |.
Fig. 4: MCFE based on the LWE assumption.

Intuitively, we change the random-oracle queries for = * and = * in a somehow orthogonal way. Meaning that, the proper change for = * , changes the distribution of the master key (indistinguishable in the adversary's view) such that the multiplication of this master key and the new value for RO-query associated with * can perfectly (for MDDH scheme) or statistically (for DCR and LWE schemes) hide the message in the challenge.

Game G 1 : In game G 1 , we replace the hash function H, that is evaluated in every randomoracle query , with a random function RF. The random function has different outputs corresponding to the different schemes: The random function outputs an element z ← Z k+1 p in the case of the MDDH scheme, an element z ← Z * N 2 in the case of the DCR scheme and a couple (a, u) with a ← Z n 0 q and u ← Z m 0 q in the case of the LWE scheme. This results in a perfect transition from G 0 to G 1 . This results in:

|Win G 0 A (κ, n) -Win G 1 A (κ, n)| = 0. Game G 2 :
In game G 2 , we answer the random-oracle queries for the label = * with an element that is indistinguishable from a random element, by relying on the corresponding computational assumption. We describe the random-oracle outputs under the label in more detail: MDDH: we output a vector z such that z is contained in the span of A, i.e. z = Ay with a random vector y ← Z k p . DCR: we output an element

z N mod N 2 , with a random element z ← Z * N 2 . LWE: we output a tuple (a, S • a + e), with S R ← Z m 0 ×n 0 , a R ← Z n 0 q , e R ← D Z m 0 ,αq .
(we note that before proceeding to the next game for LWE scheme we need some extra games where we remove t i • e and t i • S from all ciphertexts queries through the property of the rounding-map and the uniform distribution of s i ). This results in:

|Win G 1 A (κ, n) -Win G 2 A (κ, n)| ≤ negl(κ).
where negl(κ) depends on the advantage of the attacker to the underlying assumption. Here we note that the current modifications also change the distribution of the master key in the adversary's view (in an indistinguishable way). MDDH the master secret key for MDDH scheme is distributed as

S + γ(x * 1 -x * 0 ) • (a ⊥ ) T for some γ ∈ Z q .
DCR the master secret key for DCR scheme is distributed as s + λ(x 0 ) • µ for some µ ∈ Z n . Where λ = 2p q is the order of elements z N mod N 2 . LWE the master secret key t for LWE scheme is distributed as t + (x MDDH: we rely on the fact that A has rank k and find a vector a ⊥ ← Z k+1 p such that (a ⊥ ) A = 0 (this means (A, a ⊥ ) is a base for Z k+1 ). Then we set RF( * ) = A • RF ( * ) + a ⊥ • RF ( * ) such that RF ( ) = 0 (which is satisfies except with negligible probability negl), for random functions RF and RF . DCR: we rely on an isomorphism ε from

Z N × Z * N to Z * N 2 to write the random element RF( * ) = z mod N 2 in its corresponding representation ε -1 (z) = (1 + N ) a • b N mod N 2 for a, b ∈ Z *
N (which is satisfied expect with negligible probability negl). LWE: we set RF( * ) = S • a + e + RF ( * ) where RF is a random function (again here there is an extra game which remove the term t i • e from the ciphertext-challenge). This results in:

|Win G 2 A (κ, n) -Win G 3 A (κ, n)| ≤ negl(κ). Game G 4 :
In game G 4 , we change the answers for left-or-right oracle queries under from encryptions of x 0 i to encryptions of x 1 i . for the MDDH we manage to show this change is perfectly-indistinguishable, while for the DCR and LWE schemes it needs a statistical argument to justify the transition from game G 3 to game G 4 . It follows that:

|Win G 3 A (κ, n) - Win G 4 A (κ, n)| = f (κ).
where for MDDH, f (κ) = 0 and for DCR and LWE schemes f (κ) = 2 -κ . In fact, we prove that a multiplication (which has already appeared in the ciphertextchallenge) of the master secret key (in its new representation) and the new values RF( * ) can perfectly (for MDDH) or statistically (for DCR and LWE) hide the message in the challenge. Games G 5 , . . . , G 8 One can define these games as the backward-counterparts of games G 3 to G 0 while hidden bit associated with the challenge is b = 1.

Putting everything together, we obtain the theorem.

Game cti, u justification/remark G0 Enc(pp, ski, x 0 i , ) H( ) G1 Enc(pp, ski, x 0 i , ) RF

Implementation

To show the efficiency of our schemes, we provide three implementations of schemes described on Figs. 2 to 4. In this table encryption time is per slot. Before describing the choices made during implementation, we show the timings for these implementations on Fig. 6. Before heading into details relative to each implementation, let us review the choices common to the three implementations. Instantiating the random oracle. We chose to replace the random oracle by the SHA-256 hash function, thus we were able to take advantage of the OpenSSL library, that provides efficient and well spread implementation of SHA-256. As the size of the random oracle were different to the output size of SHA-256, we used it multiple times, changing the input each time by incrementing a counter that was concatenated with the label. Choice of the message space. We tested our code with vectors of dimension 100, computing the sum of the first 100 squares. We wanted to keep the message space as small as 2 20 = 1048576, in order for the LWE ciphertexts to be held by 32 bits integers, then the message space was kept the same for the DCR implementation for fair comparison. It is worth noting that the DCR implementation could have encrypted vectors with coordinates up to 4000 bits large without being any slower, since the complexity only depends on the dimensions of the vectors, and the only bound on the message space is that it has to stay smaller than the RSA number N . On the other hand, the DDH implementation is limited by the computation of a discrete logarithm regardless of the parameter choice, and the LWE implementation can hardly increase the message space without having to pump the parameters Indeed, the modulus is tied only to message space and not so to security as in the case of DCR, so we don't have this spare space in the message space. We wanted to keep the ciphertexts small enough so that we can rely on fast hardware optimizations on arithmetic operations, using bigger message spaces would require to use large number libraries, but is definitely doable.

Discussion. The timings we have are very reasonable, and can be brought down quite a lot for any given application. We tried to push the parameters so that our implementations can be trusted as proofs of concept without knowing what applications will come in the future, but for given specific requirements in terms of security and efficiency, there is a lot of room for improvement. We also tried to give a flexible implementation that can be used to estimate the timings for different parameters easily. This also leaves room for optimization once the parameters are chosen for a particular application. If we are to compare the different schemes, it looks like the scheme based on LWE is much more efficient than the scheme based on DCR. One has to be careful when making such comparisons. Indeed, the DCR scheme supports very big messages, because the modulo N has to be set very large for security reasons. In comparison, the efficiency of the LWE scheme would degrade with the size of the messages to encrypt, so for applications with large messages, the DCR implementation might actually become much faster. Details of implementation for each of mentioned schemes are separately discussed in Appendix E.

A MCFE based on the MDDH Assumption

Here we discuss the correctness and the security of our MDDH-based MCFE construction (Fig. 2). Correctness. To prove the correctness of our construction, we consider the output of the decryption procedure for a correctly generated encryptions of the vectors x 1 , . . . , x n ∈ Z p under the same label ∈ Labels using a correctly generated functional key sk y with y := (y 1 , . . . , y n ) ∈ Z mn p :

C = i∈[n] [c i, ] • y i -[u ] • sk y = i∈[n] [S i • u + x i ] • y i -[u ] • i∈[n] S i y i = i∈[n] [ S i • u , y i + x i , y i ] - i∈[n] [ S i • u , y i ] = i∈[n] [ x i , y i ] = [ x, y ]
Since the decryption procedure outputs log(C), correctness directly follows.

After showing the correctness of our scheme, we are also proving its security.

Adv one-IND MCFE,A (κ, n) ≤ q Enc 4 • Adv MDDH B (κ) + 2 p -1 + 2 p ,
where q Enc denotes the number of distinct labels queried to QLeftRight.

Proof. To prove this statement, we consider the case where A only queries QLeftRight on one label , and never queries QEnc on . We build a p.p.t. adversary B such that:

Adv one-1-label MCFE,A (κ, n) ≤ 4 • Adv MDDH B (κ) + 2 p-1 + 2 p ,
where Adv one-1-label MCFE,A (κ, n) is defined as described in Theorem 3. Then we use Theorem 4 to obtain the theorem.

For the proof of the 1-label security we proceed via a hybrid argument, using the games described in Fig. 8. The game G 0 corresponds to one-IND MCFE 0 (κ, n, A) and the game G 4 to one-IND MCFE 1 (κ, n, A). This yields:

Adv one-1-label MCFE,A (κ, n) = |Win G 0 A (κ, n) -Win G 7 A (κ, n)|.
Game G 1 : In game G 1 , we replace the hash function H, that is evaluated in every random-oracle query , with a truly random function RF. This results in a perfect transition from G 0 to G 1 . Namely, in Theorem 15, we show that:

|Win G 0 A (κ, n) -Win G 1 A (κ, n)| = 0.
Game G 2 : In game G 2 , we replace the random function RF, that is evaluated in every randomoracle query , with an element in the span of a matrix A, sampled from a matrix distribution D k . To generate the final element in the span, we multiply A with a random element in Z k p , sampled using the random function RF . The transition from G 1 to G 2 is justified by the Multi-MDDH assumption. Namely, in Theorem 16, we exhibit a p.p.t. adversary B 0 such that:

|Win G 1 A (κ, n) -Win G 2 A (κ, n)| ≤ Adv MDDH B 0 (κ) + 1 p -1 .
Game G 3 : In game G 3 , we answer a random-oracle query for the label with an element that is generated as a linear combination of A and a ⊥ , with a ⊥ ← Z k+1 p such that (a ⊥ ) A = 0. For every other random-oracle query = , the output is still an element in the span of A. The transition between G 2 and G 3 is justified by the MDDH assumption. Namely, in Theorem 17, we exhibit a p.p.t. adversary B 1 such that:

|Win G 2 A (κ, n) -Win G 3 A (κ, n)| ≤ Adv MDDH B 1 (κ) + 1 p .
Game G 4 : In game G 4 , we change the answers for left-or-right oracle queries under from encryptions of x 0, i to encryptions of x 1, i . We rely on complexity leveraging and a statistical argument to justify the transition from game G 3 to game G 4 . Namely, in Theorem 18, we show that:

|Win G 3 A (κ, n) -Win G 4 A (κ, n)| = 0. Game G 5 :
In game G 5 , we answer a random-oracle query for the label in the same way as for every other label = , i.e. with an element in the span of A. The transition from game G 4 to G 5 is symmetric to the transition from G 2 to G 3 , justified by the MDDH assumption. Namely, it can be proven as in Theorem 17 that there exists a p.p.t. adversary B 2 such that:

|Win G 4 A (κ, n) -Win G 5 A (κ, n)| ≤ Adv MDDH B 2 (κ) + 1 p .
We defer to the proof of Theorem 17 for further details.

Game G 6 : In game G 6 , we answer every random-oracle query with the evaluation of a random function RF( ) instead of an element in the span of A. The transition from game G 5 to G 6 is symmetric to the transition from G 1 to G 2 , justified by the Multi-MDDH assumption. Namely, it can be proven as in Theorem 16 that there exists a p.p.t. adversary B 3 such that:

|Win G 5 A (κ, n) -Win G 6 A (κ, n)| ≤ Adv MDDH B 3 (κ) + 1 p -1 .
We defer to the proof of Theorem 16 for further details. Game G 7 : This game is one-IND MCFE 1 (κ, n, A). The transition from G 6 to G 7 is symmetric to the transition from G 0 to G 1 . Namely, it can be proven as in Theorem 15 that:

|Win G 6 A (κ, n) -Win G 7 A (κ, n)| = 0.
We defer to the proof of Theorem 15 for further details.

Putting everything together, we obtain the theorem.

Game ct i, u justification/remark G0 Enc(pp, ski, x 0, i , ) H( ) G1 Enc(pp, ski, x 0, i , ) RF( ), with RF( ) ∈ Z k+1 p
Replace the hash function with a random function

G2 Enc(pp, ski, x 0, i , ) A ← D k A • RF ( ), with RF ( ) ∈ Z k p
Simulate the hash function using the span of A (Multi-MDDH)

G3

Enc(pp, ski, x 0, i , )

A ← D k , a ⊥ ← Z k+1 p \ {0} s.t. (a ⊥ ) A = 0 A • RF ( ) + a ⊥ • RF ( ), if = A • RF ( ), if =
with RF ( ) ∈ Z k p and RF ( ) ∈ Z * p For = simulate using a random element from the span of A and a ⊥ G4 Enc(pp, ski, x 1, i , )

A ← D k , a ⊥ ← Z k+1 p \ {0}, s.t. (a ⊥ ) A = 0 A • RF ( ) + a ⊥ • RF ( ), if = A • RF ( ), if = with RF ( ) ∈ Z k p and RF ( ) ∈ Z * p Change from left to right encryption G5 Enc(pp, ski, x 1, i , ) A ← D k A • RF ( ),
| Pr[A(G, [A], ([Aw i ]) i∈[n] ) = 1] -Pr[A(G, [A], ([v i ]) i∈[n] ) = 1]| ≤ Adv MDDH B (κ) + 1 p -1 , with A ← D k , w i ← Z k p and v i ← Z k+1 p for all i ∈ [n].
Lemma 15 (Transition from G 0 to G 1 ). For any p.p.t. adversary A, it holds that

|Win G 0 A (κ, n) -Win G 1 A (κ, n)| = 0.
Proof. This is a perfect simulation of the random-oracle H using a random function RF( ) ∈ Z k+1 p , which gives us

|Win G 0 Adv,A (κ, n) -Win G 1 Adv,A (κ, n)| = 0.
Lemma 16 (Transition from G 1 to G 2 ). For any p.p.t. adversary A, there exists a p.p.t. adversary B such that

|Win G 1 A (κ, n) -Win G 2 A (κ, n)| ≤ Adv MDDH B (κ) + 1 p -1 .
Proof. We replace the random function RF( ) ∈ Z k+1 p in the random oracle with a truly random element in the span of A, where matrix A is sampled from the Gaussian distribution D k and multiplied with a random element generated by RF ( ) ∈ Z k p . This directly mirrors the random selfreducibility of MDDH assumption as described in Theorem 14,which

|Win G 2 A (κ, n) -Win G 3 A (κ, n)| ≤ Adv MDDH B (κ) + 1 p .
Proof. We change the output of the random oracle for the query from an element output in the span of A to a linear combination of the matrices A and the vector a ⊥ . In more detail, we generate a random vector in Z k+1 p by sampling u 1 ← Z k p and u 2 ← Z * p and computing A • u 1 + a ⊥ • u 2 . Due to the way in which a ⊥ is constructed and the we can span the whole space Z k+1 p using A and a ⊥ . This sampling is justified by the MDDH assumption, it changes the view of the adversary by statistical distance of 1 p , which yields to the above mentioned bound.

Lemma 18 (Transition from G 3 to G 4 ). For any p.p.t. adversary A, it holds that

|Win G 3 A (κ, n) -Win G 4 A (κ, n)| = 0.
Proof. We proceed in two different steps for this part of the proof:

1. We apply a complexity leveraging argument to change the games G 3 and G 4 from the adaptive security case into the selective security case. The resulting games are denoted with G 3 and G 4 . 2. We use a statistical argument to prove the transition from G 3 to G 4 . 1. Let A t be an adversary in the adaptive secure games G t and B t an adversary in the corresponding selectively secure games G t , for t = 3, 4.

We transform the adversary A t into a selective adversary B t , such that:

Adv Gt At (κ, n) ≤ 2 -n • (2X) -2mn • Adv G t B t (κ, n), for t = 3, 4.
We describe the simulation of the adaptive security by the adversary B t to A t , for t = 3, 4, when B t interacts with the corresponding selective security experiment.

2. After adversary B t made its guesses z i = (x 0, i , x 1, i ) for the set label and all i ∈ [n]. It simulates A t 's experiment using its own selective experiment. When B t receives a challenge query from A t , it checks if the guess was successful. If it was, it continues simulating A t 's experiment, otherwise, it returns 0. When the guess is successful, B t perfectly simulates A t 's view.

To show that the two distributions (with u , a ⊥ = 0):

{S i } i∈[n],z i and {S i - 1 u , a ⊥ (x 0, i -x 1, i )(a ⊥ ) } i∈[n],z i
are indistinguishable, we show the simulation of B t for the different queries:

Corruption oracle QCor(i): If slot i gets corrupted (and the simulation happened successfully), it holds that x 0, i = x 1, i under label . This results in S i -

1 u ,a ⊥ (x 0, i -x 1, i )(a ⊥ ) = S i - 1 u ,a ⊥ • 0 • (a ⊥ ) = S i .

Key oracle QKeyD(y):

The key generation procedure will output:

sk y = i∈[n] S i • y i - 1 u , a ⊥ (a ⊥ )(x 0, i -x 1, i ) • y i = i∈[n] S i • y i - 1 u , a ⊥ (a ⊥ ) ( x 0, i , y i -x 1, i , y i ) =0 ,
which is equal to a functional key generated using {S i } i∈[n],z i .

Left-or-Right query

QLeftRight(i, x 0 i , x 1 i , ): The term -1 u ,a ⊥ (x 0, i -x 1, i
)(a ⊥ ) also appears in the encryption queries under label . The ciphertext under label has the structure

[S i u ] - 1 u , a ⊥ (x 0, i -x 1, i )(a ⊥ ) [u ] + [x 0, i ] =[S i u ] + [- 1 u , a ⊥ • u , a ⊥ =1 (x 0, i -x 1, i ) + x 0, i ] =[S i u ] + [x 1, i ].
Encryption query QEnc(i, x i , ): If an encryption query gets asked for a label = , with u = A • RF ( ), then the ciphertext has the following structure:

[S i u ] - 1 u , a ⊥ (x 0, i -x 1, i )(a ⊥ ) [A • RF ( )] + [x i ] =[S i u ] + [- 1 u , a ⊥ (x 0, i -x 1, i ) (a ⊥ ) A =0 •RF ( )] + [x i ] =[S i u ] + [x i ]

B MCFE Based on DCR Assumption

B.1 A Review on Single-Input FE based on DCR

In this section, we recall the single-input functional encryption scheme based on Paillier, proposed by Agrawal et al. [ALS16]. Their construction is presented in Fig. 9 which is mainly based on the idea of [BCP03]. Bresson et al. [BCP03] present a public key cryptosystem with two trapdoors: one is λ which needs the knowledge of the factorization of N , and the second trapdoor is the secret key which makes the decryption possible without knowing λ. The security of this scheme is based on a variant of the DDH assumption over Z * N 2 . Agrawal et al. extended this idea to cyclic subgroups of 2N residues modulo N 2 to design a secure functional encryption system based on the DCR assumption. They showed that the decryption algorithm based on the second trapdoor can be adopted to the FE setting by having functional secret keys (instead of the secret key in public-key setting [BCP03]). The use of cyclic group of 2N residues modulo N 2 (instead of the quadratic residues group in [BCP03]) and the DCR assumption makes it possible to ensure that secret keys do not leak sensitive information in FE case [ALS16].

Remark 19 (A note on the space and distribution of master secret key). The master secret key is sampled from Z through a Gaussian sampler. This can guarantee the correctness and the security as well. More precisely, everyone holding the secret key and ciphertext should be able to compute the value C mod N 2 and it means that sk has to be given over Z or modulo any multiple of λ (due to the fact that the order of g is λ and ct -sk 0 = ct sk mod λ 0 mod N 2 ). Having sk modulo λ can leak the value of λ through different secret key queries and it means that anyone can directly decrypt the ciphertext to get the plain message x in a similar way to [Pai99] or [BCP03] based on the first trapdoor. Thus, the value sk cannot be given modulo k • λ for an arbitrary k ∈ Z. Moreover, during the security proof, it is required that the master secret key is defined over the same set that sk is defined (since the distribution of the master secret key in the view of the adversary is conditioned on the secret key values). Putting it all together, the master secret key s should be sampled from the set Z and Gaussian distribution is a good candidate for this sampling. In fact, based on its density function if the standard deviation is noticeably larger than N , then it seems like uniform distribution modulo N and this fact is used in the security proof.

Setup(1 κ , n) :

-run SP(κ) to get safe-primes p, q.

-compute N = pq

-sample g R ← Z * N 2 -compute g = g 2N mod N 2 .
Return pp = (N, g)

KeyGen(pp) : -sample s ← D Z n ,σ where D Z n ,σ is the Gaussian distribution of standard deviation σ > √ κ • N 5/2 . -compute hi = g s i mod N 2 . Return mpk = {hi} i∈[n] msk = s
Enc(pp, mpk, x) :

For vector x ∈ Z n with ||x||∞ ≤ X < N/n:

-sample r R ← {0, . . . , [ N 4 ]}. -compute ct0 = g r mod N 2 , cti = (1 + N ) x i • h r i mod N 2 Return ct = (ct0, {cti}i)
KeyDer(pp, msk, y) :

For vector y ∈ Z n with ||y||∞ ≤ Y < N/n:

-compute sky = Σiyi.si over Z Return sky Dec(pp, mpk, y, sk, ct) :

-compute C = i ct y i i • ct -sk 0 Return C -1 mod N 2 N

Definition 20 (Carmichael function).

The Carmichael function is defined as :

λ(n) =        lcm(λ(p a 1 1 ), . . . , λ(p a k k )) n = p a 1 1 • p a 2 2 • . . . • p a k k p a-1 (p -1) n = p a , p = 2 or a < 2 p a-1 (p -1)/2 n = p a , p = 2, a > 2
All through the paper we denote λ(N ) as λ. The following lemma is due to the Carmichael theorem.

Theorem 21 (Carmichael Theorem). Assume that N = pq is a safe-prime modulus, then for any w ∈ Z * N 2 :

w λ = 1 mod N w N λ = 1 mod N 2
The following lemma is introducing an isomorphism between

Z N × Z * N and Z * N 2 . Lemma 22 ([Pai99]). The function ε : Z N × Z * N -→ Z * N 2 , defined as ε(a, b) = (1 + N ) a • b n , is a bijective map.
Now, we are ready to discuss the correctness and security of our DCR-based MCFE scheme (Fig. 3). Correctness. We show that our construction in Fig. 3 is correct. Note that (1 + N ) is of order N and the following statement is satisfied.

∀ a ∈ Z : (1 + N ) a = (1 + aN ) mod N 2 .
Now by the obtained value from decryption algorithm, we have:

C = i ct y i i .H( ) -sk = (1 + N ) Σ n i=1 x i .y i mod N mod N 2 ⇒ C = (1 + (Σ n i=1 x i • y i mod N ) • N ) mod N 2 ⇒ C -1 mod N 2 N = Σ n i=1 x i .y i mod N
Security Analysis. In this section we analysis the security of our construction. Our security proof is based on a combination of proof techniques of [CDG + 18a] and [ALS16]. In the security proof we aim for adaptive security9 , we have a sequence of games such that any two adjacent games can be proved indistinguishable based on a computational assumption or a statistical argument. Sketch of the proof. Here we give a simple but not accurate intuition of the proof. Many details are missing due to the sake of simplicity.

We start with the real game conditioned the hidden bit is b = 0 (game G 0 ). Then we try to replace the RO-queries with RF ( ) N through the DCR assumption where RF ( ) is a truly random function (games G 1 and G 2 ). From this point we start a hybrid argument over RO-queries, while all the RO-queries are answered by RF ( ) N , the RO-query associated with the challenge would be replaced with RF( ) (Game G 2.q.2 ) which tanks to the isomorphism ε can be seen as (1 + N ) a • b N . These two changes are somehow orthogonal meaning that through H( ) = RF ( ) N we can simultaneously change the distribution of the master secret key (s + λ(x 1 -x 0 ) • µ for some µ ∈ Z) such that this change is indistinguishable in the adversary's view. Then thanks to the new distribution of the master key and the change H( q ) = (1 + N ) aq • b N q , one can see that a new term as x b + a q λ • (x 1 -x 0 ) mod N would be appeared in the challenge-ciphertext.

From there we just need to say that this term can statistically hide the bit b in the challenge (by a statistical argument in G 2.q.4 ).

We remark that our statistical argument (game G 2.q.4 ) is the only game in the sequence which we cannot directly prove its indistinguishability from its previous game, in an adaptive setting10 . Though, the positive side is that since this restriction is happening only in the statistical argument, by a technique similar to the complexity leveraging, one can find the proper parameters to lift the security again to the adaptive, without losing any factor of security. That is why in the construction we have considered two cases for the parameters-setting. This will help the user to set the parameters based on its chosen security model.

Game description justification

G0 cti = (1 + N ) x i0 • H( ) s i mod N 2 H( ) ∈ Z * N 2
real game b = 0

G1 cti = (1 + N ) x i0 • RF( ) s i H( ) = RF( ) ∈ Z * N 2 RO G2 cti = (1 + N ) x i0 • RF ( ) N s i H( ) = RF ( ) N ∈ Z * N 2 DCR G2.q.1 cti = (1 + N ) x i0 • RF ( ) N s i ≥ q (1 + N ) x i1 • RF ( ) N s i < q H( ) = RF ( ) N G2.q,1 = G1 G2.q.2 cti =    (1 + N ) x i0 • RF ( ) N s i > q (1 + N ) x i0 • RF( ) s i = q (1 + N ) x i1 • RF ( ) N s i < q H( ) = RF ( ) N = q RF( ) = q DCR G2.q.3 cti =    (1 + N ) x i0 • RF ( ) N s i > q (1 + N ) x i0 +a s i b N s i = q (1 + N ) x i1 • RF ( ) N s i < q H( ) = RF ( ) N = q (1 + N ) a b N = q Theorem 22 G2.q.4 cti =      (1 + N ) x i0 • RF ( ) N s i > q (1 + N ) xi1 +a s i b N s i = q (1 + N ) x i1 • RF ( ) N s i < q H( ) = RF ( ) N = q (1 + N ) a b N = q stat.argu. G2.q.4 ∼ = G2,q+1.1 backward steps G3 cti = (1 + N ) x i1 • RF ( ) N s i H( ) = RF ( ) N G3 = G2.q Enc +1,1 G4 cti = (1 + N ) x i1 • RF( ) s i H( ) = RF( ) ∈ Z * N 2 DCR G5 cti = (1 + N ) x i1 • H( ) s i H( ) ∈ Z * N 2 RO real game b = 1
Avd one-IND ≤ (2q Enc + 2) • Avd DCR + 4q Enc • negl 1 (κ) + q Enc • 2 -κ
where q Enc is the number of random-oracle queries which are used in some LR encryption queries, negl 1 shows the advantage of an adversary in distinguishing Z N from Z * N and the term 2 -κ is appeared due to the fact that in our Gaussian distribution σ > √ κ • N 5/2 .

Proof. We define a sequence of games started from G 0 which is the real game when the challenger answers to LR queries through the chosen bit b = 0 and ended with G 5 which is the real game for the bit b = 1.Thus,

Adv one-IND MCFE,A (κ, n) = |Win G 0 A (κ, n) -Win G 5 A (κ, n)|.
This sequence of games is shown in Fig. 10. In this table RF, RF , RF a , RF b are different random functions respectively from labels set Labels to

Z * N 2 , Z * N 2 , Z * N , Z * N .
Game G 0 : is the real game where the challenger answers to the queries QLeftRight(x 0 , x 1 , i, ) by Enc(x 0 , i, ). Note that hash function is modeled as random oracle H onto Z * N 2 . Game G 1 : is similar to the game G 0 , except that, each new RO-query is answered by a fresh truly random in Z * N 2 . That is, H( ) = RF( ). All other queries are simulated by running the real algorithms (based on these current RO values). Clearly,

|Win G 0 A (κ, n) -Win G 1 A (κ, n)| = 0.
Game G 2 : is similar to the game G 1 , except that, each RO-query is answered by H( ) = RF ( ) N mod N 2 . Theorem 25 proves that,

|Win G 2 A (κ, n) -Win G 1 A (κ, n)| ≤ Adv DCR B (κ) + q Enc • negl 1 .
An adversary attacking to the random self-reducibility of DCR can simply simulate the game for the attacker to the indistinguishability of G 2 and G 1 . The random self-reducibility of DCR expresses that from a single sample w ← D (similarly, w ← D ) given by the DCR challenger, one can build many random samples w from the same distribution D (respectively, D ). Game G 3 : is similar to the game G 2 , except that, queries QLeftRight(x 0 , x 1 , i, ) are answered by Enc(x 1 , i, ). In Theorem 26, we show that these two games are indistinguishable by a hybrid argument on RO-queries, yielding that,

|Win G 3 A (κ, n) -Win G 2 A (κ, n)| ≤ q Enc • (2 • Adv DCR B (κ) + 2 • negl 1 (κ) + 2 -κ ).
We prove this claim through a sequence of hybrids on the RO-queries. As we already mentioned in the proof-sketch, by the previous changes on the RO-queries, we are ready to start our statistical argument here. We will show that the master secret key in the adversary's view belongs to a sublattice. While in the challenge, the message is added to the master secret key module N . From there, we use a theorem from the lattice-based cryptography saying that if the variance of Gaussian distribution is enough larger than N, then sampling from this sublattice module N is close to uniform distribution over Z N , which then can hide bit b. Games G 4 , G 5 : These games are respectively the counterparts of G 2 , G 1 , G 0 and their indistinguishability relies on a similar reasoning in the backward steps.

Lemma 24 (Random self-reducibility of DCR [Pai99]). The DCR assumption is random self reducible. Concretely, for any k ∈ N,

Adv DCR,k A (κ) ≤ Adv DCR A (κ) + k • negl 1
where Adv DCR,k A (κ), is the advantage of adversary receiving k random samples of DCR. I.e.,

Adv DCR,k A (κ) = | Pr[A (w R ← D) = 1] -Pr[A (w R ← D ) = 1]| where w = {w i } k i=1 and D = {z R ← Z * N 2 } and D = {z N mod N 2 : z R ← Z * N 2 }.
The term negl 1 (κ) is appeared due to the fact that instead of a q R ← Z N , as it is in Theorem 22, we have

a q R ← Z * N . More precisely, negl 1 (κ) ≤ 1 √ N which is the advantage of the adversary in distinguishing Z N from Z * N .
Game G 2.q.4 : is similar to the game G 2.q.3 , except that, the encryption queries QLeftRight(x 0 , x 1 , i, q ) for label q corresponding to the qth RO-query is answered by Enc(x 1 , i, q ). Note that G 2.q.4 = G 2.q+1,1 and G 2,q Enc +1,1 = G 3 . In Theorem 27, we prove that

|Win G 2.q.4 A (κ, n) -Win G 2.q.3 A (κ, n)| ≤ 2 -κ .
Note that if qth RO-query is not used by any encryption query, then the games G 2.q.4 and G 2.q.3 are identical. But for the case that it is used by an encryption query, we claim that G 2.q.4 ∼ = G 2.q.3 . This step is similar to the security proof technique of single-input FE scheme based of Paillier in [ALS16]. The difference is that the information leaked through different ciphertext in our MCFE scheme are the same as what the adversary gets in single-input FE through the public key11 . The formal proof is as follows:

Lemma 27 (Transition from G 2.q.3 to G 2.q.4 ). If σ > κ + 2n • log(2X) • N 5/2 and X < N/2n, then for any adversary A,

|Win G 2.q.4 A (κ, n) -Win G 2.q.3 A (κ, n)| ≤ 2 -κ .
Proof. Here at first we prove that the selective12 versions of these two games are indistinguishable and then by a technique similar to complexity leveraging we extend the security to their adaptive versions 13 . Let G * 2.q.3 and G * 2.q.4 be the selective versions of G 2.q.3 and G 2.q.4 , respectively. We show that, |Win

G * 2.q.4 A (κ, n) -Win G * 2.q.3 A (κ, n)| ≤ 2 -κ .
We define a new game G b 2.q.3 , depending on a random bit b R ← {0, 1} such that when b = 0 it is the same as G * 2.q.3 and when b = 1 is the same as G * 2.q.4 . Thus, in the game G b 2.q.3 , we have QLeftRight(x 0 , x 1 , i, q ) = (1 + N ) x q ib +aqs i • b N s i q = ct iq (where x q ib is the i-th entry of the message x q b associated with the challenge q ) and all other queries are answered similar to the game G * 2.q.3 . We claim that ct iq for i = 1, . . . , n, statically hides b ∈ {0, 1}. To prove this, we try to show that conditioned on all the leaked information, X • (x q b + a q s) mod N can statistically hide bit b where X is an invertible matrix modulo N and independent of bit b. This can complete the proof.

Let x q β = (x q 1,β , . . . , x q n,β ), β ∈ {0, 1} are the challenges associated with label q and x q = 1 g (x q 1 -x q 0 ) where g = gcd(x q 1,1 -x q 1,0 , . . . , x q n,1 -x q n,0 ). Without loss of generality, we assume the n 0 first entries of x q are zero, and all remaining entries are non-zero. The matrix X is considered as X = X top X bot where X top and X bot are as follows:

X top =         I n 0 -x q n 0 +2 x q n 0 +1 -x q n 0 +3 x q n 0 +2
. . . . . .

x q n x q n-1         , X bot = (x q ) T
For this matrix, det(XX T ) = ( n-1 i=n 0 +1 (x q i ) 2 ) • ||x q || 4 . Each (x q i ) 2 is small and non-zero. Thus, the term ( n-1 i=n 0 +1 (x q i ) 2 ) is non-zero modulo N otherwise it gives a factorization for N . Similarly, we can assume that gcd(||x q ||, N ) = 1, otherwise it gives a non-trivial factor of N . Putting together, det(X) 2 = 0 mod N which means X is invertible over Z N . Coming back to the main goal, we show that X • (x q b + a q s) mod N hides the bit b. In fact, what we would show is that X top • (x q b + a q s) mod N is completely independent of b and X bot • (x q b + a q s) mod N is close to uniform and therefore statistically hides b.

-Step 1: X top • (x q b + a q s) mod N is completely independent of b: This is satisfied due to the fact that X top • (x q 0 -x q 1 ) = 0 over integers (one can check it through the construction of matrix X top ).

-Step 2: X bot • (x q b + a q s) mod N is close to uniform: Which can be written as

x q , x q b + a q x q , s mod N.

(1)

Let s 0 = (s 0 1 . . . , s 0 n ) be a possible value for the master key. Now we try to find the distribution of s from the adversary's view. The adversary can get information about the master secret key through:

1. All ciphertexts associated with l = q : the leaked information about s 0 comes from RF ( ) N s 0 mod N 2 , = q . Note that the adversary also knows RF ( ) N through the RO queries. 2. Secret key queries: the leaked information is essentially y, s 0 for all the key quires y. 3. Corruption queries: It leaks the value s 0 i for the corrupted slot i. Thus, the distribution of master key in the adversary's view is

{s 0 + t : t R ← D Λ,σ,-s 0 }
where the lattice Λ is as follows 14 :

Λ = {t : t = λ • (x q 1 -x q 0 ) • µ, µ ∈ Z}
And that is because for s = s 0 + t, RF ( ) N s = RF ( ) N s 0 mod N 2 ⇐⇒ s = s 0 mod λ, for = q y, s = y, s 0 over Z for all secret key queries y s i = s 0 i for the corrupted slot i.

Note that the first equality is satisfied due to the fact that RF ( ) is a random function onto Z * N 2 and RF ( ) N is of order λ. We have also relied on the Condition( * ) of the security definition (Theorem 2), in two last equalities (and in the construction of vector t and matrix X as well). Due to the norm bounds, x 1 -x 0 , y = 0 mod N means that x 1 -x 0 , y = 0 over Z which is used in the second equality. We write the lattice Λ as Λ = λ • Z • x q . Conditioned on the leaked information, the distribution x q , s is:

s 0 , x q + D λ•||x q || 2 •Z,||x q ||σ,-c where c = s 0 , x q ∈ Z Agrawal et al. showed that if σ > √ κ • N 5/2 , then D λ•||x q || 2 •Z,||x q ||σ,-c over Λ 0 = λ • ||x q || 2 • Z modulo the lattice Λ 0 = λ • ||x q || 2 • (N Z) is within statistical distance 2 -κ from the uniform distribution over Λ 0 Λ 0 [GPV08]. And since gcd(λ•||x q || 2 , N ) = 1, then Λ 0 Λ 0 is isomorphic to Z N .
This means that x q , s modulo N is within statistical distance 2 -κ from the uniform distribution over Z N . Now by the Eq. ( 1), since a q ∈ Z * N is invertible modulo N , the term x q , x q b is statistically hidden. This completes the proof for |Win

G * 2.q.4 A (κ, n) -Win G * 2.q.3 A (κ, n)| ≤ 2 -κ .
Then by applying a technique similar to complexity leveraging, we have:

Win G 2.q.3 A (κ, n) = (2X) 2n • Win G * 2.q.3 A (κ, n), and Win G 2.q.4 A (κ, n) = (2X) 2n • Win G * 2.q.4 A (κ, n) Thus, Win G 2.q.4 A (κ, n) -Win G 2.q.3 A (κ, n) = (2X) 2n • (Win G * 2.q.4 A (κ, n) -Win G * 2.q.3 A (κ, n)) Meaning that if |Win G * 2.q.4 A (κ, n) -Win G * 2.q.3 A (κ, n)| ≤ 2 -κ • (2X) -2n then, |Win G 2.q.4 A (κ, n) - Win G 2.q.3 A (κ, n)| ≤ 2 -κ .
Clearly, if in the last part of the proof one sets σ > κ + 2n • log(2X)•N 5/2 then the above reasoning result in |Win

G 2.q.4 A (κ, n) -Win G 2.q.3 A (κ, n)| ≤ 2 -κ
which proves the adaptive security.

Our DCR-based MCFE scheme can simply be extended to pos + -IND secure, IND secure or to the decentralized version through some existing general compilers. These extensions are given in Appendix F.1.

Game Description

G0 ct i, = Zi • H( ) + q K • x 0 i justification LWE assumption G1 ct i, = Zi • H( ) + q K • x 0 i = (si + ti • S) • a + ti • e + q K • x 0 i H( ) = a S • a + e justification
ti • e absorbed by the rounding, requires q = q0Bn0 ω (1) , where |ti

• e | ≤ B G2 ct i, = (si + ti • S) a + q K • x 0 i H( ) = a S•a +e justification
ti • e γ absorbed by the rounding Here . stands for .

G2.γ.1 ct i, =      (si + ti • S) • a + q K • x 0 i > γ si • a + ti • (S • a + e ) + q K • x 0 i = γ (si + ti • S) • a + q K • x 1 i < γ H( ) = a S•a +e justification LWE assumption G2.γ.2 ct i, =      (si + ti • S) • a + q K • x 0 i > γ (si • a + ti S • a + e + u + q K x 0 i = γ (si + ti • S) • a + q K • x 1 i < γ H( ) =
G2.γ.3 ct i, =      (si + ti • S) • a + q K • x 0 i > γ (si + ti • S) • a + ti • u + q K • x 0 i = γ (si + ti • S) • a + q K • x 1 i < γ H( ) =
q 0 and (a , S • a + e ) ∈ Z n 0 q × Zq are LWE samples.

Game Description

G2.γ.4 ct i, =          s i • a + q K • x 0 i > γ s i • a + ti • u + q K • x 0 i = γ s i • a + q K • x 1 i < γ H( ) = a S•a +e = γ a S•a +e + u = γ
where u = RF( γ ) justification statistical argument, requires σ ≥ 10nV and m = Ω(log(q)) G2.γ.5

ct i, =      s i • a + q K • x 0 > γ s i • a + ti • u + q K • x 1 i = γ s i • a + q K • x 1 i < γ H( ) = a S•a +e = γ a S•a +e + u = γ where u = RF( γ )
justification Same steps backwards

G2.γ.6 ct i, =    (si + ti • S) • a + q K • x 0 i > γ (si + ti • S) • a + q K • x 1 i = γ (si + ti • S) • a + q K • x 1 i < γ H( ) = a S•a +e justification
the next game is G2.γ+1.1 and G2.q Enc .5 = G3

G3 ct i, = (si + ti • S) • a + q K • x 1 i H( ) = a S•a +e justification
ti • e absorbed by the rounding

G4 ct i, = si + ti • S • a + ti • e + q K • x 1 i = Zi • H( ) + q K • x 1 i H( ) = a S•a +e justification LWE assumption G5 ct i, = Zi • H( ) + q K • x 1 i
Fig. 13: Overview of the games our MCFE scheme based on LWE.

Here . stands for .

q 0 and (a , S • a + e ) ∈ Z n 0 q × Zq are LWE samples.

Game G 1 : is similar to the game G 0 , except that, each new RO-query is answered by a fresh sample of LWE q,α . Thus:

|Win G 1 A (n 0 , n) -Win G 0 A (n 0 , n)| ≤ Adv LWE B (n 0
). We note that since the LWE assumption is already involved with polynomially many samples, the upper-bound does not depend to the number of queries. For the indistinguishability of G 0 and G 1 , we consider an extension of LWE problem which is as hard as the original definition. This extension considers samples with the same given coefficients but different secrets which would let to have a matrix as the secret. Game G 2 : is similar to the game G 1 , except that, the value t i e is absorbed in the rounding. If q ≥ q 0 Bn 0 ω (1) where |t i • e | ≤ B with overwhelming probability, then games G 1 and G 2 are indistinguishable. The proof of indistinguishability is similar to the proof of Theorem 28. Giving that:

|Win G 2 A (n 0 , n) -Win G 1 A (n 0 , n)| ≤ q Enc • negl 1 (n 0 )
, where negl 1 is the probability of distinguishing t i • e from 0 after applying the rounding map • q 0 . This change would let us remove the value t i • ∵ from all the encryption-queries such that this change is indistinguishable for the adversary. Game G 3 : is similar to the game G 2 , except that, the encryption queries QLeftRight(x 0 , x 1 , i, ) are answered by Enc(x 1 , i, ). In Theorem 31, we show that these two games are indistinguishable by a hybrid argument on RO-queries. And:

|Win G 3 A (n 0 , n) -Win G 2 A (n 0 , n)| ≤ 2q Enc • (2 negl 1 (n 0 ) + Adv LWE B (n 0 )) + q Enc • 2 -κ .
Intuitively, by the current change in the RO-queries, we show that one can simultaneously change the distribution of the master secret key t i as t i + µ(x 1 -x 0 ) for some µ ∈ Z such that this change is indistinguishable for the adversary. Then, we show that if we change the vector H( q ) associated with the challenge to a random vector u, the multiplication of the new master key and u can statistically hide the message in the challenge. Games G 4 , G 5 : Now from here we come back in reverse, in a similar way from G 2 to the game G 0 . The last game G 5 is similar to the real game with b = 1.

Lemma 30 (Transition from G 0 to G 1 ). For any adversary A, there exists an adversary B such that:

|Win G 1 A (n 0 , n) -Win G 0 A (n 0 , n)| ≤ Adv LWE B (n 0 ).
Proof.

|Win G 3 A (n 0 , n) -Win G 2 A (n 0 , n)| ≤ 2q Enc • (2 negl 1 (n 0 ) + Adv LWE B (n 0 )) + q Enc • 2 -κ .
Proof. For each γ = 1, . . . , q Enc , six games G 2.γ.1 , . . . , G 2.γ.6 are defined such that G 2 ∼ = G 2.1.1 , and for any γ, G 2.γ.

1 ∼ = G 2.γ.2 ∼ = G 2.γ.3 ∼ = G 2.γ.4 ∼ = G 2.γ.5 ∼ = G 2.γ.6 and G 2.γ.6 ∼ = G 2.γ+1.1 where G 2.q Enc .6 ∼ = G 3 .
Lemma 33 (Transition from G 2.γ.3 to G 2.γ.4 ). If Ω(log q + 4n log P ) ≤ m 0 and nP 2 < q then:

Win G 2.γ.5 A (n 0 , n) -Win G 2.γ.4 A (n 0 , n)| ≤ 2 -κ
Proof. Here at first we prove that the selective16 versions of these two games are indistinguishable and then by a technique similar to the complexity leveraging we lift the security to their adaptive versions. Let G * 2.γ.4 and G * 2.γ.5 be the selective versions of G 2.γ.4 and G 2.γ.5 , respectively. We show that Win

G * 2.γ.5 A (n 0 , n) -Win G * 2.γ.4 A (n 0 , n)| ≤ 2 -κ
We define a new game G b 2.γ , depending on a random bit b R ← {0, 1} such that when b = 0 it is the same as G * 2.γ.4 and when b = 1 is the same as G * 2.γ.5 . Thus, in the game G b 2.γ , we have

QLeftRight(x 0 , x 1 , i, γ ) = s i • a + t i • u + q K x γ ib = ct iγ (note that u = RF( γ )
and x γ ib is the i-th entry of the message x γ b associated with the challenge γ ) and all other queries are answered similar to the game G * 2.γ.3 . We claim that ct iγ for i = 1, . . . , n, statistically hides b ∈ {0, 1}. To prove this, we try to show that conditioned on all the leaked information, X • T γ b can statistically hide bit b where X is an invertible matrix module q and independent of bit b and T γ b is as follows:

T γ b =    t γ 1b . . . t γ nb    , t γ ib = t i • u + q K x γ ib (2)
This can complete the proof. Let x γ β = (x γ 1,β , . . . , x γ n,β ), β ∈ {0, 1} are the challenges associated with label γ and x γ = 1 g (x γ 1 -x γ 0 ) where g = gcd(x γ 1,1 -x γ 1,0 , . . . , x γ n,1 -x γ n,0 ). Without loss of generality, we assume the l first entries of x γ are zero, and all remaining entries are non-zero.

The matrix X is considered as X = X top X bot where X top and X bot are as follows:

X top =         I l -x γ l+2 x γ l+1 -x γ l+3 x γ l+2 . . . . . . x γ n x γ n-1         , X bot = (x γ ) T For this matrix, det(XX T ) = ( n-1 i=l+1 (x γ i ) 2 ) • ||x γ || 4 . Each (x γ i )
2 is small and non-zero (meaning that for all i, gcd((x γ i ) 2 , q) = 1). Thus, the term ( n-1 i=l+1 (x γ i )

2 ) is non-zero modulo q. On the other hand, gcd(||x γ ||, q) = 1 due to the fact that nP 2 < q. Putting together, det(X) 2 = 0 mod q which means X is invertible over Z q . Coming back to the main goal, we show that X • T γ b mod q hides the bit b. In fact, what we would show is that X top • T γ b mod q is completely independent of b and X bot •T γ b mod q is close to uniform and therefore statistically hides b.

-Step 1: X top • T γ b mod q is completely independent of b: This is satisfied due to the fact that X top • (x γ 0 -x γ 1 ) = 0 over q. One can check this relation through the construction of matrix X top .

-Step 2: X bot • T γ b mod q is close to uniform: For this, we show that the residual distribution of following vector, conditioned on all the leaked information, has high minimum entropy.

X bot • T = X bot •    t 1 . . . t n   

Definition 37. (Security of DMCFE)

The xx-yy-zz-IND security notion of a DMCFE scheme is similar to the one of an MCFE scheme (Theorem 2), except that there is no master secret key msk and the key derivation oracle is now defined as:

Key derivation oracle QKeyD(f, i): Output sk i,f := KeyDerShare(sk i , f ).

D.1 Decentralized-MCFE with partial functional-keys

In a decentralized version of MCFE no authority is in charge of generating individual secret keys, but rather each client takes care of its secret keys. The compiler by Abdalla et al.

[ABKW19,ABG19] transferring MCFE to DMCFE, uses an information-theoretically secure layer on the functional-keys requiring a square-size of the key in the key-generation phase.

Meaning that, we can go from MCFE to DMCFE with no need for a new assumption. We refer the readers to their general compiler while the underlying MCFE scheme is realized by our DCR-based MCFE scheme. As their compiler is general we do not discuss it here in detail, but it worth to mention that their scheme has O(n 2 ) key-size while the ciphertext-size is of the same order of the underlying MCFE. They have proved the security for the case that the adversary is restricted to ask for all the partial functional-keys. Chotard et al. [CDG + 18a] presented a DMCFE scheme with linear size of the key and based on pairing (for their spacial MCFE based on DDH assumption).17 As it might be clear, in MCFE the only part which relies on the authority is the functional decryption-key generation which is sk y = y i s i . This value can be computed in a decentralized way as follows; One may see sk y as sy, 1 which can again be computed by a MCFE with message t i = s i y i for the client i and the decryption-key would be like s i where s i is the secret-key chosen by the client i. A MPC protocol or a trysted setup preparing s i = 0, would complete the puzzle for the decentralization. The DMCFE [CDG + 18a] needs pairing, this requirement comes from the fact that for their underlying MCFE (based on DDH assumption) the inner-product value (here s i y i ) needs to be small which may not be satisfied as s i is chosen uniformly from Z p . One can go around this problem by pairing.

Here we discuss how we can extend their construction for some MCFE schemes which do not need discrete-logarithm computation during the decryption and consequently no pairing would be needed in the DMCFE construction. We try to give a general construction in order to use it for both of our MCFE scheme (DCR-based and LWE-based MCFE). The point about this construction is that, one can prove the security against the static corruption and with no restriction on the completeness of partial functional-keys.

In the following theorem sel1 stands for the case that in the security game, there is only a single functional-key query which should be asked at the beginning of the game. This is a very weak security requirement, which not only the existing MCFE scheme can fulfill it, but also one that may come up with more efficient constructions satisfying only this weak version of security.

Theorem 38. The DMCFE scheme in Fig. 14

is sta-yy-IND secure, if MCFE 1 is sta-yy-IND secure and MCFE 2 is sel1-sta-pos + -IND secure. Concretely, Adv sta-yy-IND A,DMCFE (κ, n) ≤ 2Adv sta-yy-IND B,MCFE 1 (κ, n) + 2Adv sel1-sta-yy-IND B ,MCFE 2 (κ, n).
We proceed through a sequence of the games such that the first game is the real game associated with bit b = 0 and the last game is the real game associated with bit b = 1. The intuition for the proof is as follows: we note that the encryption algorithm is only involved with MCFE 1 . Thus, we can use the security of MCFE 1 to change the message x 0 to x 1 , if we can be sure that the only information leaking through the queries QKeyD(y, i) is y i sk 1,i (which is the functional-key Game Description Justification

G0 ct i, ← Enc1(sk1,i, x 0 i , i, ), sk2,i = 0 ski,y = Enc2(sk2,i, yisk1,i, H(y)) real game b = 0 G1 ct i, ← Enc1(sk1,i, x 0 i , i, ), sk2,i = 0 ski,y = Enc2(sk2,i, yisk 1,i , H(y)) st. yisk 1,i = yisk1,i security of MCFE2 G2 ct i, ← Enc1(sk1,i, x 1 i , i, ), sk2,i = 0 ski,y = Enc2(sk2,i, y i sk 1,i , H(y )) security of MCFE1 G3 ct i, ← Enc1(sk1,i, x 1 i , i, ), sk2,i = 0 ski,y = Enc2(sk2,i, yisk1,i , H(y)) st. yisk 1,i = yisk1,i security of MCFE2 G4 ct i, ← Enc1(sk1,i, x 1 i , i, ), sk2,i = 0 ski,y = Enc2(sk2,i, yisk1,i, H(y))
real game b = 1

Fig. 15: Overview of games for Theorem 38 -for each i ∈ CS, the adversary B, sends a corruption query to its challenger and sends back the response sk 2,i along side sk 1,i . -when B receives challenges QLeftRight(i, x 0 i , x 1 i , ) from A, it responds with Enc 1 (sk 1,i , x 0 i , i, ). -when B receives QKeyD(y, i) from A:

-if i * = 0, the adversary B sends query QLeftRight(i, y i sk 1,i , y i sk 1,i , y) to its challenger and sends back the result to A.

-if i * = 0, for any j ∈ HS it samples sk 1,j and sets m 0 j,y = y j sk 1,j , m 1 j,y = y j sk 1,j . For any j ∈ CS it sets m 0 j,y = m 1 j,y = y j sk 1,j

Then, it sends QLeftRight(i, m 0 i,y , m 1 i,y , y) to its challenger and receives sk i,y = Enc 2 (sk 2,i , m b i,y , i, y) and sends back sk i,y to A.

when A outputs a bit b , at first B checks if its guess for i * is correct where otherwise it aborts. It sets m 0 i * ,y and m 1 i * ,y and also m 0 j,y , m 1 j,y for other missing slots j, such that j∈[n]-i * m 0 j,y + m 0 i * ,y = j∈[n]-i * m 1 j,y + m 1 i * ,y and sends QLeftRight(i, m 0 j,y , m 1 j,y , y) to its challenger for any missing slot j. Finlay, it outputs bit b .

Lemma 40 (Transition from G

1 to G 2 ). If MCFE 1 is sta-yy-IND secure, then two games G 1 and G 2 are indistinguishable. Concretely, |Win G 1 A (κ, n) -Win G 2 A (κ, n)| ≤ Adv MCFE 1 B (κ, n).
Let B be the adversary attacking to the security of MCFE 1 , and A the attacker trying to distinguish between two games G 1 and G 2 . The adversary B simulate the game for the adversary A as follows:

the adversary B runs pp 2 ← Setup 2 (1 κ , 1 n ) and chooses sk 2,i such that sk 2,i = 0. It also chooses random values sk 1,i . -for each i ∈ CS, the adversary B sends a corruption query to its challenger and sends back the response sk 1,i along side sk 2,i . -when B receives the challenges QLeftRight(i, x 0 i , x 1 i , ) from A, sends it directly to its challenger and receives Enc 1 (sk 1,i , x b i , i, ) which would be returned to A. -when B receives queries QKeyD(y, i) from A, it simply runs Enc 2 (sk 2 , i.y i sk 1,i , H(y)) and turn back the result to A. -it outputs bit b given by the adversary A.

We remark that with a similar trick of guessing a missing slot i * and answering to the corruption and QKeyD queries on-the-fly but in a consistent way, one can extend the security proof of the DMCFE compiler presented in [ABG19] against partial functional-keys and adaptive corruptions.

E Details of Implementation

E.1 DDH Implementation

Choice of the group. We chose to use an elliptic curve with a prime order that is 256 bits long, already predefined in the openssl library. Hence, we used brainpoolP256t1, however, the design of the implementation allows us to switch easily to another curve by changing the public parameters generation. Decryption. The decryption is the most constraining part of the implementation because it needs to compute a discrete logarithm. Here, we solve this problem by sequentially testing all numbers. The decryption is thus efficient enough since our output is small, but if the output grows bigger, the decryption time becomes hard to manage. It is possible to trade-off memory for space, using a baby-step giant-step algorithm to compute the discrete logarithm.

E.2 DCR Implementation

Choice of parameters. As this implementation is a proof of concept, we decided to use very conservative parameters, to show that the scheme can run with very large parameters. We advice anyone who wants to use this work for an application to chose more carefully the parameters that fits their requirements for security and efficiency. We used the OpenSSL library for big numbers for all the elements in the scheme, as well as their RSA key generation in order to generate the public parameters, and chose a 4096 bits number N . The discrete Gaussian was also overshot, and was required to be at least as large as N 6 . We also required the output of the hash function to be at least 256 bits larger than the modulo, in order to be very close to the uniform distribution (statistical distance less than 2 -256 ). Discrete Gaussian sampling. One of the main challenges in this implementation was to sample a very large Gaussian distribution over the integers. We used the sampler described in [MW17] for large standard deviations. To keep the implementation simple and readable, we decided to only use integers for computations, so once again, with further work, this stage can be optimized, for both more precise sampling (we overshoot the target a lot) and also faster sampling. We also took a very small ε = 2 -256 when taking a bound on the smoothing parameter of Z. This shouldn't be required by most application, so there is room for improvement there also. Our base sampler has standard deviation 64, is implemented using CDT, and has tails cut above 1023 and under -1023. At each step, z i is s i divided by 16, which again, leaves space for improvement if taking a more precise bound on the smoothing parameter. Observations and possible optimizations. The main bottleneck in this implementation is the size of the secret keys. The secret keys are very large, thus requiring a lot of space, and slowing down key generation as well as encryption and decryption. Indeed, the secret keys are used as exponents during encryption and decryption, and they cannot be reduced modulo the order of the group since it has to remain a secret. This implies that those operation get slower and slower as the size of the secret keys grow. A first step to improve the implementation is to get a closer look at the concrete requirements for security of the scheme, and sample a Gaussian distribution with a standard deviation that matches more closely the requirements.

E.3 LWE Implementation

Number representations and modulo. In order to have more efficient code, we chose to work with 128 bits numbers, so we had to choose a modulo that is smaller than 2 128 . To get the most efficient possible modulo operation, we picked the twelfth Mersenne prime q = 2 127 -1. The ciphertexts were stored on 32 bits integers, ensuring big enough rounding for security, but large enough for correctness. Choice of parameters. As discussed previously, we decided to encrypt vectors of size 100, and have a message space of K = 1048576. The dimensions for the keys are 500 for each of the s and t parts, and the standard deviation chosen is 1000. Note that this is not the standard deviation for the error for the LWE assumption, the standard deviation for the LWE assumption does not appear in the scheme since we are instead using rounding. We don't give a precise security estimate, since the proof allows for a trade-off in the computational security against statistical security, meaning that the rounding errors can be smaller if we decide to take a smaller standard deviation for the LWE problem, leading to less statistical loss during the proof, but also relying on an easier LWE instance. For a given application, it is possible to optimize for the security requirements, depending on the number of samples given to the adversary, the time it has got to execute its attack and other considerations. We chose those parameters for a security of over a hundred bits for reasonable applications.

F Extensions on MCFE

F.1 Extensions of our DCR-based MCFE

Extension to vectors per slots. In the previous section we presented an MCFE scheme for the case that each client has a single input. This helped to simplify the proof. But our construction can easily be extended to vectors associated with clients (slots). In Fig. 16, we can consider |y i,j |, |x i,j | ≤ N 2nm where y i,j , x i,j are respectively the jth component of ith slot (client) of the key and message vectors. Here (1 + N ) x i • H s i ( ) is the column vector ((1 + N ) x i,1 • H s i,1 ( ), . . . , (1 + N ) x i,m • H s i,m ( )).

Setup(1 κ , n, m) :

-run SP(κ) to get (p, q) -compute N = pq.

-Let H : Labels → Z * N 2 be a full-domain hash function. Security extension (from one to pos + ). Abdalla et al. [ACF + 18] gave a general conversion from one-time MIFE to many-challenges MIFE. More precisely, they showed that by having Extension to DMCFE. We note that for the adaptive case during the complexity leveraging phase, for the second layer of MCFE (to compute s i y i ), one needs to guess just a scaler s i y i . This comes from the fact that in this layer there is only one secret-key query (corresponding with vector 1). Thus, σ > κ + log(1 + N 2 ) • N 5/2 . For the correctness of the second layer, we need N > s i y

F.2 Extensions of our LWE-based MCFE

Extension to vectors per slot. For the sake of simplicity we proved the security when each client has a single scalar as it input. The construction can be simply extended to vectors-per-slot by considering K = mnP V i.e, one should replace n with mn in the parameters setting.

Security extension (from one to pos + ). One can use a single-input FE and an MCFE both based on LWE assumption in the compiler of [CDG + 18b] to get pos + security. The construction is depicted in Fig. 18.

Setup(1 κ , m, n.n0, n0 ) :

-set integers m0, m0 , q , q0 ≥ 2, q > q0, K = mnP V, K = mq0V and α, α ∈ (0, 1).

-let H : Labels → Z n 0 +m 0 q be a full-domain hash function

Return pp = (m0, m0 , q, q , α, α , P, V )

KeyGen(pp) :

-sample Zi = (si, ti) R ← Z m×n 0 q × D Z m×m 0 ,αq -sample A R ← Z m 0 ×n 0 q , and

Z i R ← τ
where τ is a special distribution over Z m×m 0 .

Return msk = (Zi, Z i ) i∈ [n] and ski = (Z i , Zi).

Enc(pp, ski, xi, i, ) :

To encrypt xi ∈ {0, . . . , P -1} m :

-set Xi = Zi • H( ) + q K

• xi mod q s.t.

Xi ∈ {0, . . . , q}

-set Xi = Xi q 0 ∈ {0, . . . , q0} m -sample s i R ← Z n 0 q , e i R ← D Z m 0 ,α q
-set ct 0 i, = A • s i + e i mod q -compute ct 1 i, = q K Xi + Z i As i mod q

Return ct i, = (ct 0 i, , ct 1 i, ) KeyDer(pp, msk, y) :

For the vector y with y ∈ {0, . . . , V } m :

-compute sky = µi -sky, H( )

q 0 mod q0 Return µ ∈ {-K + 1, . . . , K -1} that minimizes | q0 q q K • µ -µ |.

Definition 5 (

 5 Matrix Distribution [EHK + 13]). Let , k ∈ N with > k. We call D ,k a matrix distribution if it outputs (in polynomial time and with overwhelming probability) matrices in Z ×k p of full rank k. We define D k = D k+1,k . Definition 6 (D ,k -Matrix Diffie-Hellman Assumption [EHK + 13]). Let D ,k be a matrix distribution. We define the advantage of an adversary A for the D ,k -Matrix Diffie-Hellman Assumption in the following way:

Fig. 2 :

 2 Fig. 2: MCFE based on the MDDH assumption. C is computed by group operations

  Fig. 5: Overview of the games to prove the security of the MCFE schemes.

Fig. 7 :

 7 Fig. 7: Capacity of the implementations and memory cost.

Fig. 9 :

 9 Fig. 9: Single-input FE based on the DCR assumption [ALS16]

Fig. 10 :

 10 Fig. 10: Overview of the games for MCFE based on the DCR assumption

  +e + u = γ where u = RF( γ ) justification ti • e γ absorbed by the rounding

  Fig. 12: Overview of the games our MCFE scheme based on LWE.

-

  Fig. 16: DCR-based MCFE (vectors per slots)

  i , this means N > Y • s i . Based on the Markov's inequality Pr[|s i | ≤ σ] ≥ 1-negl(κ) if σ = Θ(κ ) and > 0. Then, N > Y • n • σ 2 and since Y < N/2L, one can set N > √ N L • σ 2 .

  sky i = y T i Z i . Return sk = (sky, {sky i } i∈[n] ) Dec(pp, y, sk, {ct i, } i∈[n] , ) : -compute -set µi = y T i ct 1 i, -sky i , ct 0 i, mod q -find µi ∈ {-K + 1, . . . , K -1} that minimize | q /K • µi -µ i | µ = i∈[n]

Fig. 18 :

 18 Fig. 18: MCFE based on LWE (pos + secure)

Table 1 :

 1 Comparison for LWE-based MCFE schemes reduced to the PRF property. 6 Despite relying on standard assumptions, their scheme needs O(n 2 ) secret key and the ciphertext-size is O(n 2 ). In [LT19], similarly to [CDG + 18a], each ciphertext ct

  Table 1 compares our LWE-based MCFE scheme with the schemes of [ABG19] and [LT19]. We have considered the instantiation of [ABG19] based on the LWE-based IPFE scheme of

1] . Lemma 4. (From one to many labels [ABG19]) Let

	MCFE be a scheme that is xx-yy-zz-
	IND-1-label secure. Then it is also secure against p.p.t. adversaries that query QLeftRight on
	many distinct labels (xx-yy-zz-IND security). Namely, for any p.p.t. adversary A, there exists a
	p.p.t. adversary B such that: Adv xx-yy-zz-IND MCFE,A

  Operation mpk Generation msk Generation sky Derivation Encryption Decryption Fig.6: Timings of the concrete implementations, encrypting vectors of dimension 100. The code was run on a laptop running an Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz. m is the discrete-logarithm value to be retrieved (the inner-product value).

	DDH	0.038843 s	0.028417 s	negligible	0.000439 s m µs
	DCR	0.201445 s	1.576873 s	negligible	0.280378 s 0.313167 s
	LWE	n/a		0.017957 s	0.048872 s	0.001207 s 0.000989 s
		Parameter Message space	Ciphertext size Secret key size
		DDH	bounded by computation 512 bits	512 bits
		DCR	4096 bits		9192 bits	55152 bits
		LWE	20 bits		32 bits	704000 bits

Theorem 13 .

 13 Assume that the D k -MDDH assumption holds, then the MCFE scheme described in F ig. 2 is one-IND-secure in the random-oracle model. Namely, for any p.p.t. adversary A, there exist a p.p.t. adversary B such that:

  yields Adv MDDH

	B	(κ) + 1 p-1
	as a bound.

Lemma 17 (Transition from G 2 to G 3 ). For any p.p.t. adversary A, there exists a p.p.t. adversary B such that

  At first we note that clearly LWE problem with samples (a , a • s i + e i, ) for i = 1, . . . , m 0 (i.e., when each equation crosses through m 0 different secrets s 1 , . . . , s m 0 ) is as hard as the original LWE problem. Now, for samples (a , b i, ) from its challenger, the adversary B sends (a , b ) to A where i-th entry of b equals b i, . If b i, is a • s i + e i, , then b = S • a + e where the i-th row of S is as s i , which in this case it simulate the game G 1 . If each b i, is chosen uniformly, then b is uniform, which simulate the game G 0 .

	Lemma 31 (Transition from G 2 to G 3 ). two mentioned games G 2 and G 3 in Theorem 23
	are indistinguishable. More precisely,

However, the authors have named it as multi-input functional encryption.

Note that we haveZi • H( ) = si • a + ti • (Sa + e )

which is a generalization of the DDH assumption including many other assumptions such as k-LIN and 2-Scasc [EHK+ 13], as special cases.

One can decrease the size of the key to O(n) by relying on RO and CDH assumption (similar to the DSum construction in [CDG + 18b]). But this will add a new computational assumption which is not appropriate in many applications

Note that these security notions are respectively called without repetition and with repetition in [CDG + 18a,CDG + 18b] . Here we are following the terminologies of [ABG19].

In their construction, they apply the compiler, for going from one to pos + , which gives pos + directly.

All the functions inside the same set Fρ have the same domain and the same range.

i.e., a is a if a ≤ a + 1/2 and it is ( a + 1) if a > a + 1/2.

x * 0 ) • µ for some µ ∈ Z n (here for the sake of simplicity, many details are missing). Game G 3 : In game G 3 , we answer random-oracle queries for the label as follows:

I.e., zz = ∅.

More precisely, the security notion here is selective per label (lSEL) where the adversary is restricted not to issue LR-challenges on a new label as far as it has not completed the challenges associated with the label in the progress. While it may ask secret-key queries or corruption-queries adaptively. This security notion make sense specially in the time-stamp applications that one can not come back to the previous time-labels. This is, in a predefined time-stamp all the ciphertexts should be provided otherwise any ciphertext would be discarded before going to the next time-stamp.

Note that in MCFE, we are in the symmetric key setting and the security game is involved with many ciphertexts queries

In fact, we can prove that their variants for selective per label are indistinguishable.

We emphasize that the standard complexity leveraging argument over a computational assumption reduces the strength of the computational argument, whereas here it's only leveraging on the statistical argument, so it's not as harmful.

One may tend to consider the lattice Λ as a linear combination of (linearly independent) LR encryption queries. But it essentially leaks the same information as what we have already considered

Note that in MCFE, we are in the symmetric key setting and the security game is involved with many ciphertexts queries

In fact, we can prove that their variants for selective per label are indistinguishable.

Chotard et al. [CDG +

18b] also presented a compiler with liner size of the key but based on an additional assumption CDH. Adding a new assumption may not be a good idea when the underling MCFE is based on other assumptions such as DCR or LWE.

Note that though [ABKW19] is presenting the compiler for DMCFE, it is easy to specific it for MCFE. Simply by unifying the algorithms KeyDerShare and KeyDerComb and replacing it with KeyDer algorithm.

Acknowledgments.

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud), the European Community's Horizon 2020 Project FENTEC (Grant Agreement no. 780108), and the French FUI ANBLIC Project.

Proof. Let A be the attacker to the DCR assumption. It simulates the game for adversary A as follows:

-A receives a sample w from its challenger.

-It samples α i , β i R ← Z N for i = 1, . . . , k.

-It sets w i = w α i • β N i mod N 2 and sends back w i to A .

-A outputs the bit b given by A .

To show this simulation is correct, one should prove that if w ← D (similarly, w ← D ), then each w i is uniformly sampled from D (respectively, D ). If w ← D, then by Theorem 22, we can set w = (1 + N ) a b N mod N 2 . Thus, w i = (1 + N ) aα i • (b α i β i ) N mod N 2 . Since a ∈ Z N is invertible expect with negligible probability negl 1 , aα i mod N is uniform over Z N . Similarly, b α i β i mod N is uniform over Z * N except with negligible probability negl 1 (because b α i is invertible in Z N ). Then, again by isomorphism ε, the value

if w ← D , then there exists ι ∈ Z * N 2 such that w = ι N . Thus, w i = (ι α i β i ) N mod N 2 . Since ι is invertible over Z N 2 , then ι α i β i is uniform over Z * N 2 except with negligible probability negl 1 . Consequently, w i is uniformly sampled from D .

Lemma 25 (Transition from G 1 to G 2 ). For any adversary A, there exists an adversary B such that:

Proof. Assume that B is the attacker to the random-self-reducibility of DCR problem (Theorem 24) and A is the adversary trying to distinguish between games G 1 and G 2 . When the adversary A issues RO-queries, the adversary B simply returns RF( ) = w where w is a sample from tis challenger. All other queries are answered by running the real algorithms.

If

Lemma 26 (Transition from G 2 to G 3 ). Two mentioned games G 2 and G 3 in Theorem 23 are indistinguishable. More precisely,

where q Enc and negl 1 are as explained in Theorem 23.

Proof. For each q = 1, . . . , q Enc , four games G 2.q.1 , to G 2.q.4 are defined such that G 2 ∼ = G 2.1.1 , and for any q, G 2

Game G 2.q.1 : without loss of generality, we consider a partial order relation for RO-queries. For the ciphertext associated with labels less than q , the LR queries are answered by bit b = 1 while the other LR queries are answered by b = 0. Clearly, G 2 = G 2.1.1 . Game G 2.q.2 : is similar to the previous game, except that, qth RO-query associated with label q is answered by RF( q ). By the DCR assumption,

Game G 2.q.3 : is similar to the previous game, except that, qth RO-query associated with label q is answered by (1 + N ) aq • b N q where a q = RF a ( q ), b q = RF b ( q ). By the isomorphism ε in Theorem 22, we have:

C MCFE based on the LWE Assumption

C.1 A Review on Single-Input FE based on LWE Agrawal et al. [ALS16] proposed a single-input FE based on the LWE problem which is shown in Fig. 11. In this construction P = {0, . . . , P -1} n and V = {0, . . . , V -1} n are respectively the message and the key space associated with secret keys, for integers P, V . The inner product between message and key vectors belongs to {0, . . . , K -1} with K = nP V and the prime modulus q is significantly larger than K. With this construction, inner-product is evaluated over Z and the decryption algorithm is completely efficient. Their single-input FE scheme is secure under a new hardness assumption named mheLWE. They also proved a reduction from LWE to mheLWE. Their construction is reminded through Fig. 11.

Return mpk = U and msk = Z.

Enc(pp, mpk, x) :

To encrypt the vector x ∈ P:

KeyDer(pp, msk, y) :

To generate a secret key for the vector y ∈ V:

Return sky Dec(pp, mpk, y, sk, ct) :

-compute µ = y, ct1 -sk, ct0 mod q

C.2 Correctness and Security of our LWE-based MCFE

Our security proof is using the following lemma which is applied in the security-reduction from LWE problem to LWR problem in [BPR12].

Lemma 28 (Extracted from Theorem 3.2 1) , then for any distribution over a fixed vector s ∈ Z n 0 q , the statistical difference between two distributions {(a, a, s q 0 ) : a ← Z n 0 q } and {(a, a, s + e q 0 ) :

The above lemma shows that if the modulus q is chosen super-polynomially big, then the noise term in the LWE problem can be absorbed in the rounding.

Here we discuss the correctness and security of our LWE-based MCFE scheme. Decryption Correctness. To show the correctness of the scheme, we first define e i = ct i, -

To guarantee the correctness, the relation

Meaning that if q 0 > K(nV + 1), then the scheme is correct. Security Analysis. To simplify the proof and without loss of generality, we consider the case where m = 1, meaning that the input of each client is a scaler rather than a vector.

Theorem 29. The presented MCFE scheme in Fig. 4, is an one-IND-secure MCFE scheme under the LWE assumption and in the random-oracle model. More precisely:

where q Enc is the number of random-oracle queries, and the term 2 -κ is appeared due to the fact that in our Gaussian distribution parameters depend on κ. The term negl 1 comes from the advantage of an adversary in Theorem 28.

Proof. We define a sequence of the games started from G 0 , which is the real game when the challenger answers to LR queries through the chosen bit b = 0, and ended with G 5 , which is the real game corresponding with the bit b = 1. Thus,

This sequence of games is shown in Figs. 12 and13.

Game G 0 : is the real game where the challenger answer to QLeftRight(x 0 , x 1 , i, ) by Enc(x 0 , i, ). Note that hash function is modeled as random oracle RO onto Z n 0 +m 0 q . Game G 2.γ.1 : is similar to its previous game, except that, for the label γ , the term t i • e γ is added to the ciphertext. Again the proof of the indistinguishability is similar to the proof of Theorem 28. Thus,

where G 2.γ.1 is the game before G 2.γ.1 (which might be G 2 or G 2.γ-1,6 ). The intuition for this change is to add a random value beside the message which can statistically hide the message in the challenge. Game G 2.γ.2 : is similar to the previous game, except that, RO-query for label γ is replaced by S • a γ + e γ + u . Similar to the transition from game G 0 to G 1 , one should consider LWE problem with samples (a γ , a γ • s i + e i, γ ) for i = 1, . . . , m 0 . Lemma Theorem 32 formally proves the computational indistinguishability G 2.γ.2 from its previous game i.e.,

Intuitively, this change will let us to remove t i • S from the ciphertexts by moving t i • S beside s i where s i is uniform and can hide t i • S. Game G 2.γ.3 : is similar to the previous game, except that, for the label γ , the term t i • e γ is removed from the ciphertext. Again the proof of the indistinguishability is similar to the proof of Theorem 28. Thus,

Game G 2.γ.4 : is similar to the game G 2.γ.3 , except that, in the master secret key generation (and thus in all ciphertexts), s i is computed as s i -t i • S where we sampled a fresh random s i . Clearly, this two games are identical, since s i is uniformly random. I.e.,

Game G 2.γ.5 : is similar to the previous game, except that, the query QLeftRight(x 0 , x 1 , i, γ ), associated with label γ and corresponding to γth RO-query, is answered by Enc(x 1 i , γ ). In Theorem 33 we show:

Lemma 32 (Transition from G 2.γ.1 to G 2.γ.2 ). If the LWE assumption holds, then two games G 2.γ.1 and G 2.γ.2 are indistinguishable and:

Proof. Note that if γth RO-query is not used by any encryption query, then the games G 2.γ.4 and G 2.γ.5 are identical. But for the case that it is used by an encryption query, we claim they are indistinguishable. This step is similar to the security proof technique of single-input FE scheme based of LWE in [ALS16] 15 . The formal proof is as follows:

Then using (a variant of) the leftover hash lemma with randomness X bot • T and seed u, we will then conclude that conditioned on all the leaked information, the pair (u, X bot • T • u) is close to uniform and hence it statistically hides bit b in Eq. ( 2).

Theorem 35 confirms that X bot • T has the min-entropy m 0 log(4/3). Thus, thanks to the leftover hash lemma, having the min-entropy conditioned on I = (X top , X top T), the pair (u,

Which is less than 2 -κ , when -H ∞ (X bot • T|I) + log q ≤ -2κ. Resulting in the condition log(3/4) • (log q + 2κ) ≤ m 0 . Now by applying a complexity leveraging technique, we have,

and consequently, the indistinguishability of the adaptive variants would be concluded.

Lemma 34. In Theorem 33, conditioned on all the leaked information, the min-entropy of

Proof. Here we describe what are the leaked information about T in the adversary's view.

1. all the ciphertexts for = γ : we note that these ciphertexts don't contain any information about T.

2. secret key queries: it is essentially Σ i y i • Z i . And conditioning on this information is the same as conditioning on X top • T, since y can be written as a linear combination of rows of X top . 3. corruption queries for slot i: it leaks the key Z i .

We first consider the distribution of X bot • T conditioned on (X top , X top T). Note that in X top T and X bot T matrices X top and X bot act in parallel on the columns of T. We can hence restrict ourselves to the distribution of X bot T i conditioned (X top , X top T i ), where T i stands for the ith column of T. Fix T * i arbitrary. The distribution of

, we can apply Theorem 35. Thus, after conditioning with respect to (X top , X top T), each column of X bot T has min-entropy ≥ log(4/3). Due to the fact that columns are independent, we have that,

KeyGen(pp):

-run sk1,i ← KeyGen 1 (pp 1 ) -interactively produce sk2,i st.

sk2,i = 0 Return sk = (sk1,i, sk2,i)i.

KeyDerShare(pp, ski, i, y):

To generate a key for y Return ski,y ski,y = Enc2(sk2,i, yisk1,i, i, H(y)) KeyDerComb(pp, {ski,y}i): -run sk ← Dec2(1, 0, {ski,y}i, H(y)). Rutern sk Enc(pp, ski, x, i, ): To encrypt a message x -run ct i, ← Enc1(sk1,i, xi, i, ). Return ct i, Dec(y, sk, {ct i, }i, ):

-run C = Dec1(y, sk, {ct i, }i, ) Return C Fig. 14: DMCFE from MCFE value for MCFE 1 ). To prove that queries QKeyD(y, i) leak no information beyond y i sk 1,i , we should be able to replace the keys sk 1,i with some randoms sk 1,i in Enc 2 (sk 2,i , y i sk 1,i , H(y)) (which is the to QKeyD(y, i)), as far as y i sk 1,i = y i sk 1,i . The formal description of the games are as follows:

Game G 0 : is the real game associated with b = 0. Game G 1 : is similar to the previous game, except that, each key sk i,1 is replaced with a new key sk i,1 such that y i sk i,1 = y i sk i,1 . All the queries are answered by the real algorithm based on the new keys sk i,1 . The indistinguishability between game G 1 and G 0 reduces to the security of MCFE 2 . Intuitively, there are two main possible cases here. One is that QKeyD(y, i) are asked over all the slots, which would be directly reduced to the pos + -security of MCFE 2 knowing the last honest slot which takes care of the equality y i sk i,1 = y i sk i,1 . And the second case is when for some indices i no query QKeyD(y, i) or QCorrupt(i) is issued. For this case, we try to fill up the missing slots such that again y i sk i,1 = y i sk i,1 is satisfied and then again rely on the pos + -security of MCFE 2 . The formal proof is given in Theorem 39 expressing that:

Game G 2 : is similar to the previous game, except that, the message x 0 is replaced x 1 . Here we rely on the security of MCFE 1 . The simulation of sk i,y is possible, tanks to the previous change removing the sk 1,i from sk i,y . The formal proof for indistiguishability between G 1 and G 2 is given in Theorem 40 showing that

Games G 3 , G 4 : are backward-version of games G 1 and G 0 with similar reasoning, which end up with the real game associated with b = 1.

Lemma 39 (Transition from G 0 to G 1 ). In Theorem 38 If MCFE 2 is sel1-sta-pos + -IND secure, then two games G 0 and G 1 are computationally distinguishable.

Proof. Let B be the attacker to the security of MCFE 2 , and A is the adversary trying to distinguish between G 0 and G 1 . B samples i * ← {0, 1, . . . , n} as its guess for the missing index, expecting that A will never ask queries QKeyD(y, i * ) for a vector y or corrupt the slot i * , otherwise B just aborts. If i * = 0, it means for a vector y, the queries QKeyD are issued for all the positions.

-B runs sk 1,i ← KeyGen 1 (pp 1 ) for i = 1, . . . , n.

a one-time MIFE and putting a single-FE layer on it, we can get MIFE secure against manyciphertexts challenges. Chotard et al. [CDG + 18b] used the same idea proving that if each client use another layer of single-input FE over the output of MFCE scheme, then the security can be extended from one-ciphertext per label to many-ciphertexts per label (pos + ). The point is that the outer layer and the inner one should be compatible. It means that the ciphertext produced by the inner layer should belong to the message space of the outer layer and the secret key produced by the inner layer should belong to the (functional) key space of the outer layer. As it is also pointed out in [CDG + 18b] because of the restriction on the compatibility, the suggested conversion is not general. In Fig. 17 we have directly instantiated the mentioned conversion by a single-input FE compatible with our MCFE construction. The security proof is eliminated due to the similarity to [ACF + 18] and [CDG + 18b]. Note that this technique works when m > 2. Thus, we have considered the inputs of the clients as vectors. In this instantiation as the outer layer, we are using the single-input FE scheme based on DCR assumption such that the message space is an encoding of Z (as (1 + N ) x i • H s i ( ), see Fig. 17).

Setup(1 κ , n, m) :

-run SP(κ) to get (p, q)

-Let H : Labels → Z * N 2 be a full-domain hash function. Return msk = (s s s, ŝ) and ski = (si, ŝi).

Enc(pp, ski, x x xi, i, l) :

To encrypt a message xi ∈ Z m with |xij| ≤ X <;

-compute hi = g ŝi mod N 2 .

-sample ri R ← {0, . . . , [ N 4 ]}.

-set ct i, = g r i mod N 2 , (1 + N ) x i .H( Security extension (from pos + to any). Another limitation of the security definition (Theorem 2) is the reliance on the assumption that when the adversary makes a LRencryption query it has to complete the ciphertext. In this section for the simplicity, when there is no yy = one or yy = pos + restriction in the security definition we call it any-security. Abdalla et al.

[ABKW19] and Chotard et al. [CDG + 18b] have separately presented two compilers converting pos + -secure-MCFE to any-secure-MCFE, the former has a square-size of the ciphertext 18 . While the latter is using pairing making it possible to achieve linear-size of the ciphertext and is based on Q-fold DBDH assumption. Note that both schemes are relying on the random oracle assumption which is what our MCFE construction is already involved with.