Michel Abdalla
email: michel.abdalla@ens.fr

Fabrice Benhamouda
email: fabrice.benhamouda@normalesup.org

Romain Gay
email: rgay@berkeley.edu

From Single-Input to Multi-Client Inner-Product Functional Encryption

We present a new generic construction of multi-client functional encryption (MCFE) for inner products from single-input functional inner-product encryption and standard pseudorandom functions. In spite of its simplicity, the new construction supports labels, achieves security in the standard model under adaptive corruptions, and can be instantiated from the plain DDH, LWE, and Paillier assumptions. Prior to our work, the only known constructions required discrete-log-based assumptions and the random-oracle model. Since our new scheme is not compatible with the compiler from Abdalla et al. (PKC 2019) that decentralizes the generation of the functional decryption keys, we also show how to modify the latter transformation to obtain a decentralized version of our scheme with similar features.

Setup(1 λ , 1 n ) is defined as for MCFE in Definition 2.1. KeyGen(pp): Takes as input the public parameters pp and outputs n secret keys {sk i } i∈ [n] . KeyDerShare(pp, sk i , f ): Takes as input the public parameters pp, a secret key sk i from position i and a function f ∈ F ρ , and outputs a partial functional decryption key sk i,f .

Introduction

Functional encryption [BSW11, O'N10] is a generalization of standard encryption which allows for a more fine-grained control over the decryption capabilities of third parties. In these schemes, the owner of a master secret key can derive secret keys for specific functions via a key derivation algorithm. Then, given the encryption of a message x, the holder of a secret decryption key sk f for a function f can compute f (x) using the decryption algorithm. Informally, a FE scheme is deemed secure if it is infeasible for an adversary to learn any information about x other than what it can be computed using the secret keys at its disposal. + 14] is an extension of the functional encryption in which the function can be computed over several different inputs that can be encrypted independently. More precisely, the decryption algorithm of such schemes takes as input a secret key sk f for a function f together with n different ciphertexts Enc(x 1 ), . . . , Enc(x n ) and outputs the value of the function f applied to underlying plaintexts (x 1 , . . . , x n ).

Multi-input functional encryption [GGG

In the setting in which each ciphertext of a multi-input functional encryption scheme is generated by a different party or client P i . we often refer to these schemes as multi-client functional encryption (MCFE) schemes [CDG + 18a, GGG + 14]. In this setting, it is natural to assume that the adversary can corrupt these parties and learn their secret encryption keys. The master secret key, however, is still assumed to be owned by a trusted third party.

Another important property of multi-client functional encryption considered by Chotard et al. [CDG + 18a] is the inclusion of labels in the encryption process. More precisely, in a labeled MCFE scheme, the individual encryption algorithms each take a label as an additional parameter and decryption should only be possible when using ciphertexts generated with respect to the same label. That is, labels allow the users to have more control over the mix-and-match capabilities, as opposed to MCFE without labels, where the owner of a functional decryption key can mix and match all the ciphertexts.

Note that labels can be obtained without loss of generality for MCFE for all functions; however, this is not the case of the practical constructions for restricted classes of functions, such as inner products, which is the focus of this paper. Reciprocally, any MCFE with labels can be turned into a label-free MCFE for the same functionality, simply by setting the labels used by the encryption algorithm to be always a fixed value ⊥. Put simply, labels are an extra feature that offers a better control over the information leaked by each generated functional decryption key.

For instance, suppose we want to use MCFE to allow teachers to grade their students in a way that the students can use these grades in different college applications and that colleges only learn the average grades of the students with weights of their choice. In this scenario, each teacher would encrypt the grade of each student for their subject. Each college would have a functional decryption key to compute the weighted average of all the grades of each student. It is very important that the teachers use the student ID as a label, otherwise colleges would be able to compute weighted average of a mix of multiple students (like Maths from student A and Physics from student B), which significantly hinders privacy.

Prior work. As remarked in [AGRW17], most of the prior work in the multi-input setting are either feasibility results for general functionalities (e.g,. [GGG + 14,BGJS15,AJ15,BKS18]) or efficient constructions for particular functionalities (e.g.,[AGRW17,ACF + 18,CDG + 18a,DOT18,CDG + 18b,ABKW19]). In the latter case, which is the setting in which we are interested in this paper, the main functionality under consideration is the inner-product functionality, in which functions are associated to a collection y of n vectors y 1 , . . . , y n . In particular, on input a collection x of n vectors x 1 , . . . , x n , it outputs f y (x) = n i=1 x i , y i = x, y . As noted in prior works [ABDP15, AGRW17, CDG + 18a], inner-product functionalities can be quite useful for computing statistics or performing data mining on encrypted databases.

Among the constructions of multi-input functional inner-product encryption schemes without labels, the work of Abdalla et al. in [ACF + 18] is the one requiring the weakest assumptions since it can be built from any single-input functional encryption scheme satisfying some mild properties (recalled in Section 3). In particular, by instantiating it with the public-key functional inner-product encryption schemes in [ALS16], one can obtain constructions based on the DDH, Paillier, and LWE assumptions. Moreover, as recently shown in [ABKW19], their schemes remain secure even when the secret encryption keys can be adaptively corrupted by the adversary. Unfortunately, as we further discuss below, we do not know how to generalize the ACFGU scheme to the labeled setting. In fact, the construction from [ACF + 18] relies on an information-theoretic multi-input FE (as they put it, the functional encryption equivalent of a one-time pad) to obtain security in the restricted context of one challenge ciphertext per input slot. Then, they bootstrap security to many challenge ciphertexts using an extra layer of single-input FE. That information-theoretic approach cannot be emulated, since we need to hide messages for arbitrarily many labels in our case. Thus, an entropy argument can be used to show that we need to resort to a computational assumption, even for proving security in the context of one challenge ciphertext per input slot and label. In our case, we use PRFs.

Among the constructions of multi-input functional inner-product encryption schemes with labels, the works of Abdalla et al. [ABKW19] and Chotard et al. [CDG + 18b] currently represent the state of the art in this area. In particular, both schemes provide labeled MCFE schemes in the random-oracle model in discretelog-based groups. The main advantage of the work of Chotard et al. is that its ciphertexts are shorter and that it allows for multiple ciphertexts under the same label. However, it requires pairing groups. The main advantage of the work of Abdalla et al. is that it can be instantiated in pairing-free groups. However, its ciphertexts are longer and it only allows for one ciphertext per label, a restriction inhereted from [CDG + 18a]. As in the case of other discrete-log-based constructions of functional inner-product encryption schemes (e.g, [ABDP15, BJK15, ALS16, AGRW17]), the size of supported messages is restricted for both schemes since the decryption algorithm needs to compute discrete logarithms.

Contributions. In order to address the shortcomings of previous labeled MCFE schemes, the main contribution of this paper is to provide the first construction of labeled MCFE schemes in the standard model from more general assumptions than discrete-logarithm-based ones. As in the work of Abdalla et al. in [ACF + 18], our constructions can be built from any single-input public-key functional encryption scheme satisfying some mild properties (recalled in Section 3). In particular, by instantiating it with the schemes in [ALS16], one can obtain constructions based on the DDH, Paillier, and LWE assumptions. Our constructions have no restriction on the number of ciphertexts per label and are proven secure with respect to adaptive corruptions.

In order to achieve our main result, our security proof proceeds in two parts. First, we prove the security of our MCFE scheme in a setting in which the adversary is required to query the encryption oracle in all n positions for each label. Then, in a second step, we apply the compiler suggested in [ABKW19] to remove this requirement. Since the proof for the latter transformation given in [ABKW19] is in the random-oracle model, an additional contribution of our work is to provide an alternative proof for it in Section 4 which does not require random oracles.

Finally, since our main construction is not compatible with the transformation from [ABKW19] that decentralizes the generation of the functional decryption keys, we also show how to modify the latter to obtain a decentralized version of our scheme with similar features. As a result, we obtain the first decentralized labeled MCFE schemes in the standard model based on the DDH, Paillier, and LWE assumptions. + 19], the authors define multi-input functional encryption schemes with decentralized key generation and setup, in which users can join the system dynamically. They give a feasibility result for general functions, and also provide a construction for inner products, from a standard assumption (LWE). However, their construction does not handle labels.

Independent work. In a recent work [ACF

Overview of our construction. Following the proof strategy first used in [AGRW17] in the context of multi-input FE for inner products, we start with a scheme whose security only holds when there is only one challenge ciphertext per input slot. The novelty compared to multi-input FE is that we have to handle arbitrarily many labels, even if there is only one challenge ciphertext per slot and label.

One-time security with labels. We modify the scheme from [ACF + 18], where the one-time secure MIFE is simply obtained using a one-time pad of the messages. The functional decryption keys are simply the linear combination of these pads. Namely, for any input slot i, we have ct i := x i + t i , and for sk y := n i=1 t i , y i , where t i ← Z m L , m denotes the dimension of individual messages x i , and everything is computed modulo L, for some specified integer L. Here, we write y := (y 1 . . . y n ), the concatenation of n vectors, each of dimension m. To decrypt the set of ciphertext {ct i } i , one simply compute i ct i , y i , and subtract by the key sk y to get i x i , y i . Security follows by a perfect statistical argument.

The technical challenge is to emulate this idea to a setting where ciphertexts can be generated for many labels. Since the number of label is not a priori bounded, we cannot resort to a perfectly statistical argument: the master secret key (which in the previous scheme contains all the vectors t i ) is simply too small to contain all possible pads t i, for all labels ∈ Labels that would required to perform such an argument. We must resort to a computation argument. A natural but flawed idea would to generate the pads t i, using a PRF applied on a label ∈ Labels. This approach faces two issues: first, if one slot is corrupted, then the security of the entire system is compromised, since each input slot needs the PRF key to encrypt. Second, since the labels are only known at encryption time, the generation of functional decryption keys is unable to produce the value i y i , t i, .

To circumvent these issues we generate the pads t i, := j =i (-1) j<i PRF Ki,j ( ), where for all i < j ∈ [n],

the keys K i,j ← {0, 1}

λ , and K j,i = K i,j , and (-1) j<i denotes -1 if j < i, 1 otherwise. This construction has first been used in [KDK11] to decentralize the computation of the sum of private values in a noninteractive way. Each input slot i ∈ [n] needs the set of keys {K i,j } j∈ [n] to encrypt. Assuming the security of the PRF, it produces pseudorandom pads, which will be able to mask the messages x i simultaneously for all used label ∈ Labels. Thus, we prove that this holds even when some users i ∈ [n] are corrupted (in fact, up to n -2 can be corrupted). This solves the first issue mentioned above. To solve the second issue, namely, ensuring correctness holds for all possible labels, we use the structure property that holds for all label ∈ Labels: i∈[n] t i, = 0, where 0 denotes the zero vector. Otherwise stated, these pads are shares of a perfect n out of n secret sharing of 0. We use this by setting the ciphertext for slot i ∈ [n] and label ∈ Labels to be an encryption of the vector w i, := (0 . . . 0 x i 0 . . . 0) + t i, ∈ Z mn L . This way, we have w i, , y = x i , y i + t i, , y for all slots i ∈ [n], therefore: i∈[n] w i, , y = i∈ [n] x i , y i . The last step is to encrypt the vector w i, using any single-input, public-key FE for inner products. The functional decryption key is simply the functional decryption key of the single-input inner-product FE for the associated vector y. Correctness is preserved, since the decryption only needs to compute the inner product between w i, and y.

Full-fledged security. To obtain security with many challenge ciphertexts per input slot and label, we use similar techniques to those used in [ACF + 18] in the context of multi-input inner-product FE. However, these can only be applied when the adversary does not make use of the information revealed by partial ciphertexts {ct i, } i∈[n]\{missing} , where {missing} denotes the set of missing slots for label . Prior works [CDG + 18b, ABKW19] provides generic compilers that precisely avoid partial ciphertexts to leak any information about the underlying plaintext (decryption is only successful when ciphertexts for all slots are present), but they are only proven secure in the random oracle model, and for [CDG + 18b], use additional assumptions (pairings). Since our focus it to build simple MCFE schemes from weak assumptions, we give a new generic transformation (in Section 4) that avoids the leakage of information of partial ciphertexts, with no extra assumption (only PRFs, in the standard model), and that handles adaptive corruptions.

Decentralizing MCFE. In order to decentralize the generation of functional decryption keys, we adapt the construction from [ABKW19]. The main idea is to secret share the master secret key, since computing the functional secret key is a linear operation, it can be done non-interactively from these shares.

Outline. The rest of the paper is organized as follows. After giving the relevant technical preliminaries and definitions in Section 2, we give our new construction of MCFE from single-input FE for inner products in Section 3. In Section 4, we show how to generically strengthen the security of our MCFE construction, thereby removing any artificial restrictions on the security model. Finally, in Section 5, we show how to decentralize our MCFE to obtain a DMCFE.

Definitions and Security Models

Notation. We use [n] to denote the set {1, . . . , n}. We write x for vectors and x i for the i-th element. 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), which is Pr[G(λ, n, A) = 1].
The probability is taken over the random coins of G and A.

Multi-Client Functional Encryption

In this section, we recall the definition of MCFE [GGG + 14]. It is taken almost verbatim from [ABKW19], with the following differences: the use of a stronger security definition (see Remark 2.3) and the introduction of a master public key mpk, so that public-key functional encryption becomes a particular case of MCFE.

Definition 2.1. (Multi-Client Functional Encryption) Let F = {F ρ } ρ be a family (indexed by ρ) of sets F ρ of functions f : X ρ,1 × • • • × X ρ,nρ → Y ρ . 5 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] , a master secret key msk, and a master public key mpk. 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, mpk, sk i , x i , ): Takes as input the public parameters pp, a master public key mpk, 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, mpk) ← KeyGen(pp) and sk f ← KeyDer(pp, msk, f ), we have for x = (x 1 , . . . , x n ):

Pr [Dec(pp, sk f , Enc(pp, mpk, sk 1 , x 1 , ), . . . , Enc(pp, mpk, sk n , x n , )) = f (x)] = 1.
When ρ is clear from context, the index ρ is omitted. Note that the case of (single-input) functional encryption as defined in [BSW11, O'N10] corresponds to the case n = 1, and Labels = {⊥}. For such schemes, we also consider the public-key variant, where sk 1 =⊥, that is, the encryption algorithm only requires the public parameters pp and the master public key mpk to encrypt the message x 1 . In this setting, sk 1 is omitted.

Except for public-key single-input functional encryption, the master public-key can be included in each secret key sk i and we omit it.

We follow the notation of [ABKW19] here, where the algorithm Setup only generates public parameters that determine the set of functions for which functional decryption keys can be created, and the secret/encryption keys and the master secret keys are generated by another algorithm KeyGen, while the functional decryption keys are generated by KeyDer.

In the following, we define security as adaptive left-or-right indistinguishability under both static (sta), and adaptive (adt) corruption. We also consider two variants of these notions (any, pos + ) related to the number of encryption queries asked by the adversary for each slot. 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(pp, mpk, sk i , x i , ) on a query (i, x i , ).

Key derivation oracle

QKeyD(f ): Outputs sk f = KeyDer(pp, 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 .6 -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 } i∈CS , for any query QKeyD(f ), we define x 0 i := x i and x 1 i := x i for any slot i ∈ CS and any slot queried to QEnc(i, x i , ), and 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.

-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.

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

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

Adv xx-yy-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 the context.

Remark 2.3 (The role of the oracle QEnc). The security definitions we give are slightly stronger than those given in [ABKW19], since the oracle QEnc gives out information that is not captured by Condition (*), for pos + , hence the use of the notation pos + instead of pos in [ABKW19]. For any, this addition of QEnc has no effect, as QEnc queries can be simulated using QLeftRight. But for pos + /pos, there is no equivalence in general between the security definition with and without the encryption oracle. We add this oracle QEnc so that we can reduce the security with respect to one label to the security with respect to multiple queried labels, via a simple hybrid argument (which would not be valid without the QEnc oracle), as done in [CDG + 18b]. This will be used in our generic compiler from pos + to any security, in Section 4. Now we define a seemingly weaker security notion than xx-yy-IND, which we call xx-yy-IND-1-label, since the adversary is restricted to query the oracle QLeftRight on at most one label, and it cannot query the oracle QEnc oracle on that label. Using a standard hybrid argument (cf Lemma 2.5), we show that this is equivalent to the original xx-yy-IND security defined above. These restrictions will make the proofs easier in the rest of the paper. 1, where the oracles are defined as for Definition 2.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, mpk, sk i , x i , ) on a query (i, x i , ). If this oracle is queried on the same label that is queried to QLeftRight, the game ends and return 0.

Condition (*) is defined as for Definition 2.2. We define the advantage of an adversary A in the following way:

Adv xx-yy-IND-1-label MCFE,A (λ, n) = Pr[xx-yy-IND-1-label MCFE 0 (λ, n, A) = 1] -Pr[xx-yy-IND-1-label MCFE 1 (λ, n, A) = 1] .
Lemma 2.5 (From one to many labels). Let MCFE be a scheme that is xx-yy-IND-1-label secure, for xx ∈ {sta, adt} and yy ∈ {pos + , any}. Then it is also secure against PPT adversaries that query QLeftRight on many distinct labels (xx-yy-IND security). Namely, for any PPT adversary A, there exists a PPT adversary B such that:

Adv xx-yy-IND MCFE,A (λ, n) ≤ q Enc • Adv xx-yy-IND-1-label MCFE,B (λ, n),
where

Adv xx-yy-IND-1-label MCFE,B
(λ, n) denotes the advantage of B against an experiment defined as above, except QLeftRight can be queried on at most one label and QEnc must not be queried on that label. By q Enc we denote the number of distinct labels queried by A to QLeftRight in the original security game.

Proof (Sketch).

First, let us consider the case of yy = any security. The proof uses a hybrid argument which goes over all the labels 1 , ... Q queried to both the oracles QEnc and QLeftRight. In the k'th hybrid, the queries for the first k'th labels to the QLeftRight oracle are answered with the right plaintext, and the the last Q -k labels are answered with the left plaintext. To go from hybrid k -1 to k, B uses its own QEnc oracle to answer A's queries to QLeftRight for labels j for j < k, and j > k (using the right and left plaintext respectively), and uses its own oracle QLeftRight for label k . The queries made by A to QEnc and QCor are answered straightforwardly by B from its own oracles. Note that the queries made by B satisfy the 1-label restriction, since QLeftRight is only queried on k , and QEnc is not queried on k .

For the case of yy = pos + security, to go from hybrid k -1 to k, B uses the QEnc oracle to answer QLeftRight queries for labels j for j < k and j > k (using the right and left plaintext respectively). For the label k , B uses its own oracle QLeftRight to answer A's queries to both QLeftRight and QEnc. So far, the reduction works as for the case of yy = any security. However, the difference is yy = pos + security requires additional conditions on the queries made to QLeftRight, in particular, if one honest slot is queried to QLeftRight for k , then all honest slots should be queried. Thus, we need to distinguish two cases: case 1) k is queried to QEnc, but never on QLeftRight, in which case B uses its own QEnc oracle; case 2) k is queried to QLeftRight at some point (and by definition of pos + security, that means it's queried to all honest slots). In case 2, the queries of B to QLeftRight will satisfy the condition required by the yy = pos + security game, namely, if QLeftRight is queried on k for some honest input slot, then it has to be queried on the same label k for all honest input slots. Note that this restriction doesn't apply to the queries made to QEnc. In case 1, we use the fact that the two hybrid games k -1 and k are exactly the same. Therefore, at the end of the simulation, B checks whether case 1 occurs, and if it does, simply outputs 0 to its own experiment, ignoring A's output. Otherwise, it means it is case 2, and B forwards the output from A to its own experiment.

We summarize the relations between the six security notions in Fig. 2, where xx-pos-IND is the notion defined in [ABKW19] (i.e., it is like xx-pos + -IND without the QEnc oracle).

Decentralized Multi-Client Functional Encryption

Now, we introduce the definition of decentralized multi-client functional encryption (DMCFE) [CDG + 18a]. As for our definition of MCFE, we separate the algorithm Setup which generates public parameters defining in particular the set of functions, from the algorithm KeyGen. We do not consider public-key variants of DMCFE and hence completely omit the master public key mpk.

sta-yy-IND

MCFE β (λ, n, A) CS ← A(1 λ , 1 n ) pp ← Setup(1 λ , 1 n ) ({ski} i∈[n] , mpk, msk) ← KeyGen(pp) α ← A QEnc(•,•,•),QLeftRight(•,•,•,•),QKeyD(•) (pp, mpk, {ski} i∈CS ) Output: α if Condition (*) is satisfied, 0 otherwise. adt-yy-IND MCFE β (λ, n, A) pp ← Setup(1 λ , 1 n ) ({ski} i∈[n] , msk, mpk) ← KeyGen(pp) α ← A QCor(•),QEnc(•,•,•),QLeftRight(•,•,•,•),QKeyD(•) (pp, mpk) Output: α if Condition (*) is satisfied, 0 otherwise.
F ρ of functions f : X ρ,1 × • • • × X ρ,nρ → Y ρ .Let Labels = {0, 1}
* or {⊥} be a set of labels. A decentralized multi-client functional encryption scheme (DMCFE) for the function family F and the label set Labels is a tuple of six algorithms DMCFE = (Setup, KeyGen, KeyDerShare, KeyDerComb, Enc, Dec):

A scheme DMCFE is correct, if for all λ, n ∈ N, pp ← Setup(1 λ , 1 n ), f ∈ F ρ , ∈ Labels, x i ∈ X ρ,i , when {sk i } i∈[n] ← KeyGen(pp), sk i,f ← KeyDerShare(sk i , f ) for i ∈ [n], and sk f ← KeyDerComb(pp, sk 1,f , . . . , sk n,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 .
We remark that there is no master secret key msk. Furthermore, similarly to [CDG + 18a], our definition does not explicitly ask the setup to be decentralized. Our DMCFE construction based on DDH (Section 5) however has a setup which can be easily decentralized.

We consider a similar security definition for the decentralized multi-client scheme. We point out that contrary to [CDG + 18a], we do not differentiate encryption keys from secret keys. This is without loss of generality, as corruptions in [CDG + 18a] only allow to corrupt both keys at the same time.

Definition 2.7. (Security of DMCFE) The xx-yy-IND security notion of an DMCFE scheme (xx ∈ {sta, adt} and yy ∈ {any, pos + }) is similar to the one of an MCFE (Definition 2.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): Given as input f ∈ F and a client i ∈ [n], it returns sk i,f := KeyDerShare(pp, sk i , f ).
Remark 2.8 (Weaker security definition for DMCFE). Some prior works, including [ABKW19], give a weaker security definition for DMCFE, where the adversary can only get access to all the shares of functional decryption keys at once. This fails to capture the scenario where the adversary get some, but not all, shares of functional decryption keys. In that case, the adversary should not be able to recover any meaningful information. For instance, consider the following scenario: all clients except client 1 want to learn the input of client 1. Client 1 will not participate in the generation of such functional decryption key, since that would clearly violate her privacy. Thus, the scheme should not reveal any information on her encrypted value as long there are some missing shares of functional decryption keys. This is not addressed by the security definition of [ABKW19] since the adversary gets all the shares at the same time. Instead, we allow the adversary to corrupt functional decryption keys share by share, as in the security definition originally introduced in [CDG + 18a].

Inner-Product Functionality

We describe the functionalities supported by the constructions in this paper. 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 ip ρ = {f y1,...,yn : (R m ) n → R} where f y1,...,yn (x 1 , . . . , x n ) = n i=1 x i , y i = x, y ,
where the vectors satisfy the following bounds:

x i ∞ < X, y i ∞ < Y for i ∈ [n],
and where 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.

Pseudorandom Functions (PRF)

We make use of a pseudorandom function PRF K ( ), indexed by a key K ∈ {0, 1} λ , that takes as input a label ∈ Labels, and outputs a value in the output space Z. For a uniformly random key K ← {0, 1} λ , this function is computationally indistinguishable from a truly random function from Labels to Z. Definition 2.9 (PRF). For any PRF from Labels to Z, any bit β ∈ {0, 1}, any security parameter λ, and any adversary A, we define the experiment IND PRF β as follows.

IND PRF β (λ, A) K ← {0, 1} λ α ← A O PRF (•) (1 λ )
Output: α We define the advantage of an adversary A in the following way:

Adv PRF,A (λ) = Pr[IND PRF 0 (λ, A) = 1] -Pr[IND PRF 1 (λ, A) = 1] .
A PRF is secure, if for any any polynomial-time adversary A, there exists a negligible function negl such that: Adv PRF,A (λ) ≤ negl(λ).

Symmetric-Key Encryption (SE)

A symmetric encryption with key space K consists of the following PPT algorithms:

-Enc(K, m): given a symmetric key K and a message m, outputs a ciphertext.

-Dec(K, ct): given a symmetric key K and a ciphertext ct, outputs a message (or ⊥ if it fails to decrypt).

For all message in the message space, we have Pr[Dec(k, Enc(k, m)) = m] = 1, where the probability is taken over the random choice of K ← K. We say a symmetric-key encryption with key space K is compatible with a PRF with output space Z if K = Z.

Definition 2.10 (SE). For any SE with key space K, any bit β ∈ {0, 1}, any security parameter λ, and any adversary A, we define the experiment IND PRF β as follows.

IND SE β (λ, A) K ← K α ← A O SE (•) (1 λ )
Output: α We define the advantage of an adversary A in the following way:

Adv SE,A (λ, n) = Pr[IND PRF 0 (λ, A) = 1] -Pr[IND SE 1 (λ, A) = 1] .
A SE is secure, if for any any polynomial-time adversary A, there exists a negligible function negl such that: Adv SE,A (λ) ≤ negl(λ).

MCFE from Public-Key Single-Input FE

In this section, we build a multi-client FE for inner products generically from any public-key single-input FE and a standard PRF.

Construction

The construction resembles the multi-input FE from [ACF + 18], where an inner layer of information-theoretic one-time FE is combined with an outer layer of single-input FE. We manage to extend this paradigm to the setting where the encryption additionally takes a label as input: the one-time pads are replaced by pads which are pseudorandom for all used labels , using techniques similar to those used in [ABKW19] to decentralize the generation of functional secret keys.

The underlying single-input FE is required to satisfy simple structural properties, originally defined in [ACF + 18] and recalled below (converted to the public-key setting), which are satisfied by all known existing single-input FE for inner products.

Setup(1 λ , 1 n ) :

pp ipfe ← Setup ipfe (1 λ , 1 n ), with L implicitly defined from pp ipfe Return pp = pp ipfe KeyGen(pp) : (msk ipfe , mpk ipfe ) ← KeyGen ipfe (pp ipfe ); msk := msk ipfe For i ∈ [n], j > i : Ki,j = Kj,i ← {0, 1} λ Return {ski = (mpk, {Ki,j} j∈[n] )} i∈[n]
and msk Enc(pp, ski, xi ∈ R m , ∈ Labels) :

Parse ski = (mpk ipfe , {Ki,j} j∈[n] ) t i, := j =i (-1) j<i PRF K i,j ( ) ∈ Z mn L wi := (0 . . . 0 xi 0 . . . 0) + t i, mod L cti ← Enc ipfe (pp ipfe , mpk ipfe , wi)
Return cti KeyDer(pp, msk, y ∈ R mn ) :

Return sky ← KeyDer ipfe (pp ipfe , msk ipfe , y) Dec(pp, sky, {cti} i∈[n] ) :

For i ∈ [n], E( wi, y mod L, noisei) ← Dec ipfe,1 (pp ipfe , sky, cti) Return Dec ipfe,2 (pp ipfe , E( w1, y mod L, noise1)) • • • • • E( wn, y mod L, noisen)) Fig. 5.
Inner-Product MCFE for Fρ, ρ = (Z, n, m, X, Y ) built from a public-key FE FE := (Setup ipfe , Enc ipfe , KeyDer ipfe , Dec ipfe ) for Fρ ipfe , ρ ipfe = (Z, 1, n • m, 2X, Y ). We assume FE satisfies the two-step decryption property (see Definition 3.1), hence the existence of PPT algorithms Setup ipfe , Dec ipfe,1 and Dec ipfe,2 . Here, for any K ∈ {0, 1} λ , PRF K : Labels → Z mn L is a pseudorandom function (see Section 2.4).

Definition 3.1 (Two-step decryption [ACF + 18]). A public-key FE scheme FE = (Setup, KeyGen, KeyDer, Enc, Dec) for the function ensemble F ip ρ , ρ = (Z, 1, m, X, Y ) satisfies the two-step decryption property if it admits PPT algorithms Setup , Dec 1 , Dec 2 and an encoding function E such that:

1. For all λ ∈ N, Setup (1 λ , 1 n ) outputs pp where pp includes ρ = (Z, 1, m, X, Y ) and a bound B ∈ R + , as well as the description of a group G (with group law •) of order L > n • m • X • Y , which defines the encoding function E : Z L × Z → G. 2. For all (msk, mpk) ← KeyGen(pp), x ∈ Z m , ct ← Enc(pp, mpk, x), y ∈ Z m , and sk ← KeyDer(msk, y), we have Dec 1 (pp, sk, ct) = E( x, y mod L, noise) ,

for some noise ∈ Z that depends on ct and sk. Furthermore, it holds that P r[|noise| < B] = 1 -negl(λ), where the probability is taken over the random coins of KeyGen and KeyDer. Note that there is no restriction on the norm of x, y here. 3. The encoding E is linear, that is: for all γ, γ ∈ Z L , noise, noise ∈ Z, we have

E(γ, noise) • E(γ , noise ) = E(γ + γ mod L, noise + noise ) . 4. For all γ < n • m • X • Y , and |noise| < n • B, Dec 2 (pp, E(γ, noise)) = γ.
Definition 3.2 (Linear encryption [ACF + 18]). A secret-key FE scheme FE = (Setup, KeyGen, KeyDer, Enc, Dec) is said to satisfy the linear encryption property if there exists a deterministic algorithm Add that takes as input a ciphertext and a message, such that for all x, x ∈ Z m , the following are identically distributed:

Add(Enc(pp, msk, x), x ), and Enc pp, msk, (x + x mod L) .

Recall that the value L ∈ N is defined as part of the output of the algorithm Setup (see the two-step decryption property above).

Correctness. The correctness of the scheme in Fig. 5 follows from (i) the correctness and Definition 3.1 (two-step decryption) of the single-input scheme, and (ii) the fact that for all ∈ Labels, i∈[n] t i, = 0, by definition of the vectors t i, . Thus, writing w i := (0 . . . 0 x i 0 . . . 0)+t i, mod L, we have i∈[n] w i mod L = x mod L ∈ Z mn L , where x ∈ R nm denotes the concatenation of the n vectors x 1 , . . . , x n . More precisely, consider any vector

x := (x 1 • • • x n ) ∈ (Z m ) n , y ∈ Z mn , such that x ∞ < X, y ∞ < Y and let pp ← Setup(1 λ ), ({sk i } i∈[n]
, msk) ← KeyGen(pp), sk y ← KeyDer(pp, msk, y), and ct i ← Enc(pp, sk i , x i , ) for all i ∈ [n].

By (2) of Definition 3.1, the decryption algorithm Dec(pp, sk y , {ct i } i∈[n] ) computes E( w i , y mod L, noise i ) ← Dec ipfe,1 (pp, sk i , ct i ) where for all i ∈ [n], |noise i | < B with probability 1 -negl(λ), where B ∈ R + is the bound output by Setup ipfe .

By (3) of Definition 3.1 (linearity of E) we have:

E( w 1 , y mod L, noise 1 ) • • • • • E( w n , y mod L, noise n ) = E   i∈[n] w i , y , i∈[n] noise i   = E   x, y mod L, i∈[n] noise i   . Since x, y < n • m • X • Y < L and i∈[n] noise i < n • B, we have Dec ipfe,2 E( x, y mod L, i∈[n] noise i ) = x, y ,
by (4) of Definition 3.1.

Static Security

Now we proceed prove the sta-pos + -IND-security of the scheme, that is, security with static corruption, which serves as a warm up to the more complicated proof of adt-pos + -IND-security, that we give later. Using the generic transformation in Section 4, we can remove the pos + restriction, and obtain adt-any-IND security.

Theorem 3.3 (sta-pos + -IND-security). If the FE scheme FE = (Setup ipfe , KeyGen ipfe , KeyDer ipfe , Enc ipfe , Dec ipfe ) is an any-IND-secure FE scheme for the inner product functionality defined as F ip ρ ipfe , ρ ipfe = (Z, 1, m, 2X, Y ), and PRF is secure, then MCFE from Fig. 5 is sta-pos + -IND-secure for the functionality defined as F ip ρ , ρ = (Z, n, m, X, Y ). Namely, for any PPT adversary A, there exist PPT adversaries B and B such that:

Adv sta-pos + -IND MCFE,A (λ, n) ≤ 2q Enc • Adv any-IND FE,B (λ) + 2(n -1)q Enc • Adv PRF,B (λ),
where q Enc denotes the number of distinct labels queried to QLeftRight.

G0, G1, G2 , G3 , G4 :

CS ← A(1 λ , 1 n ) ({ski} i∈[n] , msk) ← KeyGen(pp) α ← A QLeftRight(•,•,•,•),QEnc(•,•,•),QKeyD(•) (pp, {ski} i∈CS ) Output: α if Condition (*) is satisfied, or 0 otherwise.

QKeyD(y):

Return sky ← KeyDer(pp, msk, y)

QEnc(i, x j i , ): t i, ← Gen(i, ) wi := (0 . . . 0 x j i 0 . . . 0) + t i, mod L cti ← Enc ipfe (pp ipfe , mpk ipfe , wi) Return cti QLeftRight(i, x j,0 i , x j,1 i , ): For simplicity, we consider the case where A only queries QLeftRight on one label , and never queries QEnc on . We build PPT adversaries B and B such that:

t i, ← Gen(i, ) wi := (0 . . . 0 x j,0 i + x 1,1 i -x 1,0 i 0 . . . 0) + t i, mod L wi := (0 . . . 0 x j,1 i 0 . . . 0) + t i, mod L cti ← Enc ipfe (pp ipfe , mpk ipfe , wi) Return cti Gen(i, ): Parse ski = {Ki,j} j∈[n] t i, := j =i (-1) j<i PRF K i,j ( ) ∈ Z mn L If i ∈ HS := {i1, . . . , i h }, then: • If i = i1, t i, := j∈CS (-1) j<i PRF K i,j ( ) + h t=2 RF(t, ). • If i = it, for t ∈ [2, . . . , h], t i, := j∈[n]\{i t ,i 1 } (-1) j<i PRF K i,j ( ) -RF(t, ). Return t i,
Adv sta-pos + -IND-1-label MCFE,A (λ, n) ≤ 2 • Adv any-IND FE,B (λ) + 2(n -1) • Adv PRF,B (λ), where Adv sta-pos + -IND-1-label MCFE,A (λ, n) is defined as Adv sta-pos + -IND MCFE,A
(λ, n), except with the limitations mentioned above, namely, A can query QLeftRight on at most one label, which cannot be queried to QEnc. Then we use Lemma 2.5 to obtain the theorem.

First, consider the case where there is only one honest user. In this case, the security follows directly from the any-IND security of FE. Namely, in that case we build a PPT adversary B such that

Adv sta-pos + -IND-1-label MCFE,A (λ, n) ≤ Adv any-IND FE,B (
λ). Given pp ipfe , B first samples the keys K i,j for all i, j ∈ [n], thanks to which it can compute pp, {sk i } i∈[n] , and send (pp, {sk i } i∈CS ) to A. B can answer all queries to QEnc(i, x j i , ), by returning Enc(pp, sk i , x j i , ), since it know sk i for all i ∈ [n]. Call i the only honest slot. B can answer all queries to QEnc(i, •, •, •) and QLeftRight(i, •, •, •) for i = i , using pp and {sk i } i∈ [n] . Whenever A queries QLeftRight(i , x j,0 i , x j,1 i , ), B queries its own left right oracle on (0 . . . 0 x j,0 i 0 . . . 0), (0 . . . x j,1 i 0 . . . 0), to receive ct i := Enc ipfe (pp ipfe , mpk ipfe , sk i , (0 . . . x j,β i 0 . . . 0)), where β ∈ {0, 1}, depending on the experiment B is interacting with. Then, B computes t i , as described in Fig. 5, and returns Add(ct i , t i , ) to A, which, according to the property from Definition 3.2 (linear encryption), is identically distributed to Enc ipfe (pp ipfe , mpk ipfe , (0 . . . x j,β i 0 . . . 0) + t i , mod L). Whenever A queries QKeyD on input y, B queries its own QKeyD on the same input, and forwards the output to A. For all y queried to QKeyD, we have (0 . . . x j,0 i 0 . . . 0), y = (0 . . . x j,1 i 0 . . . 0), y , by Condition (*). Moreover, for all β ∈ {0, 1}, (0 . . . x j,β i 0 . . . 0) ∞ < 2X. Thus, the queries B sends to its left-right oracle are legitimate. This concludes the case where there is only one honest user.

Second, we consider the case where there is more than one honest user. For this case, we proceed via a hybrid argument, using the games described in Fig. 6. Note that G 0 corresponds to sta-pos + -IND (λ, n, A), with the one label restriction. Thus, we have:

Adv sta-pos + -IND-1-label MCFE,A (λ, n) = Win G0 A (λ, n) -Win G4 A (λ, n) . Game G 1 .
In game G 1 , we change the way the vectors t i, used by QEnc and QLeftRight are generated, switching the values PRF Ki 1 ,i t ( ) to RF(t, ), for all t ∈ [2, h], where we write the set of honest users HS := {i 1 , . . . , i h }, and RF denotes a random function, computed on the fly (see Fig. 6). The transition from G 0 to G 1 is justified by the security of the PRF. Namely, in Lemma 3.4, we exhibit a PPT adversary B 0 such that:

Win G0 A (λ, n) -Win G1 A (λ, n) ≤ (h -1) • Adv PRF,B0 (λ)
, where h ≤ n denotes the number of honest users. Game G 2 . In game G 2 , the vectors w i used to generate the challenge ciphertexts contain an additional vector (0 . . . 0 x 1,1 i -x 1,0 i 0 . . . 0). The transition from G 1 to G 2 is justified by the any-IND security of FE. Namely, in Lemma 3.5, we exhibit a PPT adversary B 1 such that:

Win G1 A (λ, n) -Win G2 A (λ, n) ≤ Adv any-IND FE,B1 (λ)
.

Game G 3 . In game G 3 , the vectors w i used in the challenge ciphertexts are of the form: w i := (0 . . . 0 x j,1 i 0 . . . 0). The transition from G 2 to G 3 is justified by the any-IND security of FE. Namely, in Lemma 3.6, we exhibit a PPT adversary B 2 such that:

Win G2 A (λ, n) -Win G3 A (λ, n) ≤ Adv any-IND FE,B2 (

λ).

Game G 4 . This game is sta-pos

+ -IND MCFE 1 (λ, n, A).
The transition from G 3 to G 4 is symmetric to the transition from G 0 to G 1 , justified by the security of the PRF. Namely, it can be proven as in Lemma 3.4 that there exists a PPT adversary B 3 such that:

Win G3 A (λ, n) -Win G4 A (λ, n) ≤ (h -1) • Adv PRF,B3 (
λ), where h ≤ n denotes the number of honest users. We defer to the proof of Lemma 3.4 for further details.

Putting everything together, we obtain the Lemma 3.4 (Transition from G 0 to G 1 ). There exists a PPT adversary B such that

Win G0 A (λ, n) - Win G1 A (λ, n) ≤ (h -1) • Adv PRF,B (λ).
Proof. We can use the security of the PRF on all keys K i,j where i, j ∈ HS, since these are hidden from the adversary A. We show that using the security of the PRF on h -1 carefully chosen such keys is sufficient to transition from G 0 to G 1 . Namely, if we write HS := {i 1 , . . . , i h }, where the indices i 1 < i 2 < • • • < i h are ordered, we use the security of the PRF on keys of the form K i1,j for all j ∈ HS \ {i 1 }.

We build the adversary B as follows. Given CS sent by A, it samples pp ipfe ← Setup ipfe (1 λ , 1 n ) and msk ipfe ← KeyGen ipfe (pp ipfe ). For all i ∈ [n] \ {i 1 }, for all j > i, B samples K i,j = K j,i ← {0, 1}

λ , thanks to which it can compute sk i := {K i,j } j∈ [n] for all i ∈ CS and send them to A. B can simulate the oracle QKeyD using msk ipfe , and answers the queries to QEnc(i, x j i , ) for i ∈ CS, and QLeftRight(i, x j,0 i , x j,1 i , ) for i ∈ CS using sk i .

To answer QEnc(i 1 , x j i1 , ) or QLeftRight(i 1 , x j,0 i1 , x j,1 i1 , ), B computes

t i1, := j∈CS (-1) j<i1 PRF Ki 1 ,j ( ) + h t=2

RF(t,

).

To answer QEnc(i t , x j it , ) or QLeftRight(i t , x j,0 it , x j,1 it , ), for t ∈ [2, . . . , h], B computes

t it, := j∈[n]\{it,i1} (-1) j<it PRF Ki t ,j ( ) -RF(t, ).
Here, RF(t, ) is either a truly random function, or PRF Ki 1 ,i t ( ), depending on the experiment B is interacting with. In fact, we implicitly use a hybrid argument which goes over all t ∈ [2, . . . , h] here, in order to switch the values PRF Ki 1 ,i t ( ) to RF(t, ). Thus, we obtain

Win G0 A (λ, n)-Win G1 A (λ, n) ≤ (h-1)•Adv PRF,B (λ).
Lemma 3.5 (Transition from G 1 to G 2 ). There exists a PPT adversary B 1 such that

Win G1 A (λ, n) - Win G2 A (λ, n) ≤ Adv any-IND FE,B1 (λ)
.

Proof. The adversary B 1 works as follows. Given CS sent by A, and pp ipfe from its own experiment, B 1 samples K i,j = K j,i ← {0, 1} λ for all i < j ∈ [n], thanks to which it can send the sk i for all i ∈ CS, together with pp ipfe to A. Since B 1 knows the sk i for all i ∈ [n], it can answer the oracle QEnc as described in Fig. 6.

Whenever A queries QKeyD on input y, B 1 queries its own oracle on the same input, and forwards the answer to A.

Since we are considering pos + -IND security, we know A queries all honest slots on QLeftRight(•, •, •, ) and we denote by i t the last honest slot queried on QLeftRight(•, •, •, ). We call

∆ x := (x 1,1 1 -x 1,0 1 , . . . , x 1,1 n - x 1,0 n ),
where for all i ∈ HS, (i, x 1,0 i , x 1,1 i , ) is the first query of the form QLeftRight(i, •, •, ), and for all i ∈ CS, we define x 1,1 i -x 1,0 i := 0 ∈ Z m (note that QLeftRight can be queried on a corrupted slot, but by Condition (*), that means the query is of the form (i, x 1,0 i , x 1,1 i , )). Whenever A queries QLeftRight(i, x j,0 i , x j,1 i , ), B 1 computes the vectors t i, for all i ∈ [n], using sk i and computing the random function RF on the fly, as described in Fig. 6. Then, if i = i t , it computes w i := (0 . . . 0 x j,0 i 0 . . . 0) + t i, mod L, and returns Enc ipfe (pp ipfe , mpk ipfe , w i ) to A. If i = i t , then B 1 queries its left-right oracle on input (0, ∆ x ) to get ct i := Enc ipfe (pp ipfe , mpk ipfe , 0) or ct i := Enc ipfe (pp ipfe , mpk ipfe , ∆ x ), depending on the experiment B 1 is interacting with. Note that at this point, ∆ x is entirely known to B 1 , since i t is the last honest slot to be queried to QLeftRight(•, •, •, ). Then, B 1 computes w i := (0 . . . 0 x j,0 i 0 . . . 0) + t i, mod L and returns ct i := Add(ct i , w i ), which, according to the property from Definition 3.2 (linear encryption), is identically distributed to Enc ipfe (pp ipfe , mpk ipfe , w i mod L) or Enc ipfe (pp ipfe , mpk ipfe , w i + ∆ x mod L), (again, depending on which experiment B 1 is interacting with). For y queried to QKeyD, we have ∆ x , y = 0, by Condition (*). Moreover, ∆ x ∞ < 2X. Thus, the queries B 1 sends to its left-right oracle are legitimate. Finally, B 1 returns ct i to A.

To conclude, we show that when B 1 is interacting with any-IND FE 0 (λ, 1, A), then it simulates the game G 1 , whereas it simulates the game G 2 when it is interacting with any-IND FE 1 (λ, 1, A). It is clear for the case any-IND FE 0 (λ, 1, A). For the case any-IND FE 1 (λ, 1, A), we consider the vectors {u t } t∈[h] , where we write HS := {i 1 , . . . , i h } and we denote by u 1 := -h t=2 RF(t, ) and u t := RF(t, ), for all t ∈ [2, . . . , n]. These are shares of a perfect h out of h secret sharing of 0, that is, they are uniformly random conditioned on t∈[h] u t = 0. Thus, {u t } t∈[t]\{t } ∪ {u t + ∆ x } is a set of shares for a secret sharing of the vector ∆ x . Thus, the following distributions are identical:

{u t } t∈[h]\{t } ∪ {u t + ∆ x } and {u t + (0 . . . x 1,1 it -x 1,0 it 0 . . . 0)} t∈[h] , where for all t ∈ [h], u t ← Z mn L such that t∈[h] u t = 0.
The uppermost distribution corresponds to the simulation by B 1 when it is interacting with any-IND FE 1 (λ, 1, A), while the lowermost distribution corresponds to the game G 1.ρ . This concludes the proof.

Lemma 3.6 (Transition from G 2 to G 3 ). There exists a PPT adversary B 2 such that Win G2 A (λ, n) - Win G3 A (λ, n) ≤ Adv any-IND FE,B (λ).
Proof. We build an adversary B 2 against the any-IND security of FE as follows.

Given CS sent by A, and pp ipfe from its own experiment, B 2 samples K i,j = K j,i ← {0, 1} λ for all i < j ∈ [n], thanks to which it can send the sk i for all i ∈ CS, together with pp ipfe to A, and answer the oracle queries to QEnc as described in Fig. 6.

Then, whenever A queries QKeyD on input y, B 2 queries its own oracle on the same input, and forwards the answer to A. Whenever A queries QLeftRight(i, x j,0 i , x j,1 i , ), B 2 computes t i, using sk i and computing the random function RF on the fly, as described in Fig. 6. Then, B 2 queries its left-right oracle on input (0 . . . 0 x j,0 i -x 1,0 i 0 . . . 0), (0 . . . 0 x j,1 i -x 1,1 i 0 . . . 0) to get

ct i := Enc ipfe (pp ipfe , mpk ipfe (0 . . . 0 x j,β i -x 1,β i 0 . . . 0)),
where β ∈ {0, 1}, depending on the experiment B 2 is interacting with. Finally, B 2 computes v i := (0 . . . 0 x 1,1 i 0 . . . 0) + t i, mod L, and returns ct i := Add(ct i , v i ) to A, which, according to the property from Definition 3.2, is identically distributed to Enc ipfe (pp ipfe , mpk ipfe , (0 . . .

0 x j,β i -x 1,β i + x 1,1 i 0 . . . 0) + t i, mod L).
For all y queried to QKeyD, Condition (*) implies that (0 . . . 0 x j,0 i -x 1,0 i 0 . . . 0), y = (0 . . . 0 x j,1 i -x 1,1 i 0 . . . 0), y for all queries (i, x j,0 i , x j,1 i , ) to QLeftRight. Moreover, for all β ∈ {0, 1}, we have (0 . . . 0 x j,β i -x 1,β i 0 . . . 0) ∞ < 2X. Thus, the queries B 2 sends to its left-right oracle are legitimate.

Adaptive Security

Now we proceed to prove the adt-pos + -IND-security of the scheme, that is, security with adaptive corruption. As before, using the generic transformation in Section 4, we can remove the pos + restriction, and obtain adtany-IND security.

Theorem 3.7 (adt-pos + -IND-security). If the FE scheme FE = (Setup ipfe , KeyGen ipfe , KeyDer ipfe , Enc ipfe , Dec ipfe ) is an any-IND-secure FE scheme for the inner product functionality defined as F ip ρ ipfe , ρ ipfe = (Z, 1, m, 2X, Y ), and PRF is secure, then MCFE from Fig. 5 is adt-pos + -IND-secure for the functionality defined as F ip ρ , ρ = (Z, n, m, X, Y ). Namely, for any PPT adversary A, there exist PPT adversaries B and B such that:

Adv adt-pos + -IND MCFE,A (λ, n) ≤ 2(n + 1)n(n -1) 2 q Enc • Adv PRF,B (λ) + 2(n + 1)q Enc • Adv any-IND FE,B (λ)
,

where q Enc denotes the number of distinct labels queried to QLeftRight.

G 0 , G 1 , 2 , G 3 , G 4 : κ ← {0, . . . , n}, β ← {0, 1}, for all t ∈ [2, . . . , κ ], ut ← Z mn L ({ski} i∈[n] , msk) ← KeyGen(pp) α ← A QEnc(•,•,•,•),QKeyD(•),QCor(•) (pp)
Output α if Condition (*) is satisfied AND the guess κ is correct; 0 otherwise.

QEnc(i, x j i , ): Return Enc(pp, ski, x j i , )
QKeyD(y):

Return sky ← KeyDer(pp, msk, y)

QCor(i): Return ski QLeftRight(i, x j,0 i , x j,1 i , ): Parse ski := {Ki,j} j∈[n] , v i, := j =i (-1) j<i PRF K i,j ( ) ∈ Z mn L , t i, := v i, .
We write {i1, . . . , iκ} the set of explicitly honest slots, in the order they are revealed (that is, i1 is the first revealed, i2 is the second, and so forth). If κ ≥ 2 then do the following.

• If i = i1, then t i, := v i, + κ t=2 ut. • If i = it, for t ∈ [2, . . . , κ ], then t i, := v i, -ut.
• If i = it, for t > κ , that means κ > κ , the guess was incorrect. Ends the game and output 0.

wi := (0 . . . 0 x j,0 i 0 • • • 0) + t i, mod L If κ ≥ 2: wi := (0 . . . 0 x j,0 i + x 1,1 i -x 1,0 i 0 • • • 0) + t i, mod L wi := (0 . . . 0 x j,1 i 0 . . . 0) + t i, mod L cti ← Enc ipfe (pp ipfe , wi) Return cti Fig. 7.
Games for the proof of Theorem 3.7. We say the guess κ is correct if it equals the size of Q, the set of explicitly honest slots.

WLOG, we can assume that adversary A only queries QLeftRight on one label , that isn't queried to QEnc. Namely, we show that there exist PPT adversaries B and B such that:

Adv adt-pos + -IND-1-label MCFE,A (λ, n) ≤ 2(n + 1)n(n -1) 2 • Adv PRF,B (λ) + 2(n + 1) • Adv any-IND FE,B (λ) .
The theorem then follows from Lemma 2.5. We proceed via a hybrid argument, using the games described in Fig. 7. In this proof, we use the fact that any slot i that is queried on QLeftRight(i, x 1,0 i , x 1,1 i , ) with x 1,0 i = x 1,1 i cannot be corrupted (otherwise Condition (*) from Definition 2.4 would be violated). We call such a slot explicitly honest (note that a slot can be honest without being explicitly honest, if it is only queried on QLeftRight(i, x j,0 i , x j,1 i , ) with x j,0 i = x j,1 i for instance). That is, a slot i ∈ [n] is explicitly honest if the first query on this slot, QLeftRight(i,

x 1,0 i , x 1,1 i , ), is such that x 1,0 i = x 1,1 i .
In the adaptive setting, the challenger does not know in advance which slot is going to be honest; and simply guessing the set of such slots would incur an exponential security. Instead, we use a more sophisticated proof strategy that relies on a hybrid argument on the number of explicitly honest slots (this number needs to be known in advance by the challenger, which can simply guess it, incurring only a polynomial security loss).

Game G 0 : is as xx-yy-IND-1-label 0 , except the size of Q, which denotes the set of explicitly honest slots, is initially guessed by the experiment, by choosing a uniformly random κ ← {0, . . . , n}. The game behaves exactly as xx-yy-IND-1-label 0 , except it ignores the A's output α, and outputs 0 instead, in case the guess κ was incorrect. Since this guess is correct with probability 1 n+1 , we have

Win G 0 A (λ, n) = 1 n + 1 • Win xx-yy-IND-1-label 0 A (λ, n) .
Game G 1 : in this game, we change the distribution of the ciphertexts output by QLeftRight, for the case κ ≥ 2. For these, the vector (0 . . . 0 x j,0 i 0 . . . 0) to be encrypted is added a share of a perfect κ out of κ secret sharing of 0. This game is similar to the game G 1 from Fig. 6 for the proof of Theorem 3.3. We justify this transition using the security of the PRF, as in Lemma 3.5, with the crucial difference that corruptions are adaptive here. Thus, the set of explicitly honest slots Q is not known in advance by the reduction. As explained above, guessing the entire set would incur an exponential security loss. Instead we introduce gradually the shares, starting with a 2 out of 2 perfect secret sharing, then 3 out of 3, and so forth, via a hybrid argument, until we reach the κ out of κ secret sharing among all queried slots. To go from one hybrid to another, we only require to guess a pair of users (i, j) (as opposed to guessing the entire set of honest users) to use the security of the PRF on the key K i,j . Namely, in Lemma 3.8, we show that there exists a PPT adversary B 0 such that:

Win G 0 A (λ, n) -Win G 1 A (λ, n) ≤ n(n -1) 2 • Adv PRF,B0 (λ)
Game G 2 : in this game, the vectors w i used to generate the ciphertexts output by QLeftRight contain an additional vector (0 . . . 0 x 1,1 i -x 1,0 i 0 . . . 0). The transition from G 1 to G 2 is justified by the any-IND security of FE, similarly than the transition from G 1 to G 2 in Fig. 6 for the proof of Theorem 3.3. Namely, in Lemma 3.9, we exhibit a PPT adversary B 1 such that:

Win G 1 A (λ, n) -Win G 2 A (λ, n) ≤ Adv any-IND FE,B1 (λ).
Game G 3 : in this game, the vectors w i used in the ciphertexts output by QLeftRight are of the form:

w i := (0 . . . 0 x j,1 i 0 . . . 0) + t i, mod L. The transition from G ρ-1.2 to G ρ-1.3 is justified by the any-IND security of FE, similarly than the transition from G 2 to G 3 in Fig. 6 for the proof of Theorem 3.3. Namely, in Lemma 3.10, we build a PPT adversary B 2 such that:

Win G 2 A (λ, n) -Win G 3 A (λ, n) ≤ Adv any-IND FE,B2 (λ).
Game G 4 . The transition G 3 to G 4 is symmetric to the transition from G 0 to G 1 , justified by the security of the PRF. Namely, it can be proven as in Lemma 3.8 that there exists a PPT adversary B 3 such that:

Win G 3 A (λ, n) -Win G 4 A (λ, n) ≤ n(n -1) 2 • Adv PRF,B3 (λ).
We defer to the proof of Lemma 3.8 for further details. Since G 4 is exactly as the game xx-yy-IND MCFE 0 except it guesses κ ← {0, . . . , n}, we have

Win G 4 A (λ, n) = 1 n + 1 • Win xx-yy-IND-1-label 1 A (λ, n).
Putting everything together, we obtain the theorem.

Lemma 3.8 (Transition from G 0 to G 1 ). There exists a PPT adversary B 0 such that Win

G 0 A (λ, n) - Win G 1 A (λ, n) ≤ n(n -1) 2 • Adv PRF,B0 (λ). G 0.µ , for µ ∈ {0, . . . , n}: κ ← {0, . . . , n}, for all t ∈ [2, . . . , κ ], ut ← Z mn L ({ski} i∈[n] , msk) ← KeyGen(pp) α ← A QEnc(•,•,•,•),QKeyD(•),QCor(•) (pp)
Output α if Condition (*) is satisfied AND the guess κ is correct; output 0 otherwise.

QEnc(i, x j i , ): Return Enc(pp, ski, x j i , )
QKeyD(y):

Return sky ← KeyDer(pp, msk, QCor(i):

Return ski QLeftRight(i, x j,0 i , x j,1 i , ): Parse ski := {Ki,j} j∈[n] , v i, := j =i (-1) j<i PRF K i,j ( ) ∈ Z mn L . We denote by {i1, . . . , iκ} the set of explicitly honest slots in the order the are revealed, and we write θ := min(κ , µ). If θ ≥ 2, then do the following:

-If i = i1, then t i, := v i, + θ t=2 ut. -If i = it, for t ∈ [2, . . . , θ], then t i, := v i, -ut. -If i = it, for t ∈ [θ + 1, . . . , κ ], then t i, := v i, .
-If i = it, for t > κ , that means κ > κ , the guess was incorrect. Ends the game and output 0.

If θ < 2, then t i, := v i, . wi := (0 . . . 0 x j,0 i 0 • • • 0) + t i, mod L cti ← Enc ipfe (pp ipfe , wi) Return cti
Fig. 8. Games for the proof of Lemma 3.8. We say the guess κ is correct if it equals the number of explicitly honest slots.

Proof. The proof uses a sequence of hybrid games defined in Fig. 8. Note that G 0.0 is the same as G 0 , and G 0.n is the same as G 1 .

show that for all µ ∈ [n] there exists a PPT adversary B 0.µ-1 such that:

| Pr[G 0.µ-1 = 1] -Pr[G 0.µ = 1] ≤ n(n -1) • Adv PRF,B0.µ-1 (λ).
First, we show we show that there exists a PPT adversary B 0 such that:

| Pr[G 0 = 1] -Pr[G 0.2 = 1] ≤ n(n -1) • Adv PRF,B 0 (λ).
Note that we go directly from G 0 to G 0.2 since the games G 0 and G 0.1 are the same. If κ < 2, the two games G 0 and G 0.2 are the same. We consider the case where κ ≥ 2.

The simulation guesses the first and second explicitly honest slots i and j , by sampling random i , j ← [n], with i < j . This guessing incurs a security loss of n(n-1)

2

. If the guess is incorrect, then, the simulation ends and returns 0. If the guess is correct, then, we can use the security of the PRF on the key K i ,j to switch PRF K i ,j ( ) to a uniformly random value RF( ) over Z mn L . Then, we argue that RF( ) is identically distributed to RF( ) + u 2 , where u 2 ← Z mn L . Note that the former distribution corresponds to G 0 , whereas the latter distribution corresponds to G 0.2 . Then, we switch RF( ) back to PRF K i ,j ( ), using the security of the PRF on K i ,j once again.

We can argue similarly that for all µ ∈ [3, . . . , n], there exists a PPT adversary B 0.µ-1 such that:

| Pr[G 0.µ-1 = 1] -Pr[G 0.µ = 1] ≤ n(n -1) • Adv PRF,B0.µ-1 (λ).
This is proved in the same way as above, except the simulation guesses the first and θ'th explicitly honest slots, where θ := min(κ , µ), and uses the security of the PRF to add the vector u θ ← Z mn L . Summing up for all µ ∈ [2, . . . , n], we obtain a PPT adversary B 0 such that:

| Pr[G 0 = 1] -Pr[G 1 = 1] ≤ n(n -1) 2 • Adv PRF,B0 (λ).
Lemma 3.9 (Transition from G 1 to G 2 ). There exists a PPT adversary B 1 such that Win

G 1 A (λ, n) - Win G 2 A (λ, n) ≤ Adv any-IND FE,B1 (λ).
Proof. We build a PPT adversary B 1 such that:

Pr [G 1 (λ, n, A) = 1] -Pr [G 2 (λ, n, A) = 1] ≤ Adv any-IND FE,B1 (λ).
Given pp ipfe from its own experiment, B 1 samples κ ← {0, . . . , n} and K i,j = K j,i ← {0, 1}

λ for all i < j ∈

[n]. If κ ≤ 2, then B 1 samples ({sk i } i∈[n]
, msk) ← KeyGen(pp), and simulate the game G 1 (λ, n, A) as described in Fig. 7 (note that G 1 is the same as G 2 when κ < 2).

If κ ≥ 2, B 1 does the following. It answers the queries QCor and QEnc using {sk i } i∈[n] , as described in Fig. 7. Whenever A queries QKeyD on input y, B 1 queries its own oracle on the same input, and forwards the answer to A.

Whenever A queries QLeftRight(i, x j,0 i , x j,1 i , ), B 1 computes the vectors t i, , using sk i and computing the vectors u 1 , . . . , u κ on the fly, as described in Fig. 7. Then, if the slot i queried is not the κ 'th explicitly honest slot, then B 1 computes w i := (0 . . . 0 x j,0 i 0 . . . 0) + t i, mod L, and returns Enc ipfe (pp ipfe , w

i ) to A. If i is the κ 'th explicitly honest slot, then B 1 computes ∆ x := (x 1,1 1 -x 1,0 1 , . . . , x 1,1 n -x 1,0 n )
, where for all explicitly honest slots i, (i, x 1,0 i , x 1,1 i , ) is the first query to QLeftRight(i, •, •, ), and for the others slots i, x 1,1 i -x 1,0 i = 0 ∈ Z m . Note that if the guess κ is correct, at this point, all the explicitly honest slots have been revealed. Then, it queries its left-right oracle on input (0, ∆ x ) to get ct i := Enc ipfe (pp ipfe , 0) or ct i := Enc ipfe (pp ipfe , ∆ x ), depending on the experiment B 1 is interacting with. Then, B 1 computes w i := (0 . . . 0 x j,0 i 0 . . . 0)+t i, mod L and returns ct i := Add(ct i , w i ), which, according to the property from Definition 3.2, is identically distributed to Enc ipfe (pp ipfe , w i mod L) or Enc ipfe (pp ipfe , w i + ∆ x mod L), (again, depending on which experiment B 1 is interacting with). Finally, B 1 returns ct i to A. If B 1 later discovers that the guess κ was incorrect (if there are newly revealed explicitly honest slots), then it ends the simulation and returns 0 to its own Since we consider pos + -IND security, all honest slots are queried to QLeftRight(•, •, •, ). Thus, Condition (*) implies that for all y queried to QKeyD, we have ∆ x , y = 0. Moreover, ∆ x ∞ < 2X. Thus, the queries B 1 sends to its left-right oracle are legitimate.

To conclude, we show that when B 1 is interacting with any-IND FE 0 (λ, 1, A), then it simulates the game G 1 , whereas it simulates the game G 2 when it is interacting with any-IND FE 1 (λ, 1, A). The case any-IND FE 0 (λ, 1, A) is clear. To prove the case any-IND FE 1 (λ, 1, A), we consider the vectors {u t } t∈[κ ] , where u t ← Z mn L for all t ∈ [2, . . . , κ ], and u 1 := -κ t=2 u t . These are shares of a perfect κ out of κ secret sharing of 0, that is, they are uniformly random conditioned on t∈[κ ] u t = 0. Thus, the set {u t } t∈[κ -1] ∪ {u κ + ∆ x } is a set of shares for a secret sharing of the vector ∆ x . Thus, the following distributions are identical:

{u t } t∈[κ -1] ∪ {u κ + ∆ x } and {u t + (0 . . . x 1,1 it -x 1,0 it 0 . . . 0)} t∈[κ ] ,
where for all t ∈ [κ ], u t ← Z mn L such that t∈[κ ] u t = 0. The uppermost distribution corresponds to the simulation by B 1 when it is interacting with pos + -IND FE 1 (λ, 1, A), while the lowermost distribution corresponds to the game G 2 .

Summarizing, we have:

Win G 1 A (λ, n) -Win G 2 A (λ, n) ≤ Adv any-IND FE,B1 (λ)
.

Lemma 3.10 (Transition from G 2 to G 3 ). There exists a PPT adversary B 2 such that Win

G 2 A (λ, n) - Win G 3 A (λ, n) ≤ Adv any-IND FE,B2 (λ)
.

Proof. We build an adversary B 2 against the any-IND security of FE as follows. Given pp ipfe from its own experiment, B 2 forwards pp ipfe to A and samples K i,j = K j,i ← {0, 1}

λ for all i < j ∈ [n], thanks to which it can answer the queries to QCor and QEnc. It also samples κ ← {0, . . . , n}.

Then, whenever A queries QKeyD on input y, B 2 queries its own oracle on the same input, and forwards the answer to A. Whenever A queries QLeftRight(i, x j,0 i , x j,1 i , ), B 2 computes t i, as described in Fig.

(x j,0 i , x j,1 i ) to QLeftRight(i, •, •, ); for κ = κ ≥ 2, it implies (0 . . . 0 x j,0 i -x 1,0 i 0 . . . 0), y = (0 . . . 0 x j,1 i -x 1,1 i 0 . . . 0), y . Moreover, for all b ∈ {0, 1}, we have (0 . . . 0 x j,b i 0 . . . 0) ∞ < X and (0 . . . 0 x j,b i -x 1,b i 0 . . . 0) ∞ < 2X.
Thus, the queries B 2 sends to its left-right oracle are legitimate. When b = 0, B 2 simulates G 2 , whereas it simulates G 3 when b = 1.

From pos + -IND to any-IND Security

In this section, we give a compiler that generically transforms any adt-pos + -IND secure (D)MCFE into an adt-any-IND secure (D)MCFE. Our construction builds upon the compiler from [ABKW19, Section which does not support labels. Our technical contribution is to handle multiple labels, many challenge ciphertexts per label and input slots, and adaptive corruptions, without resorting to the random oracle model, as opposed to [ABKW19, Section 4.2]. This is the first generic transformation to support such features, and when combined with our MCFE from Section 3, it gives the first MCFE for inner products whose adtany-IND security is proven in the standard model. Our construction is given in Fig. 9. It is stated in terms of DMCFE, but a similar transformation works for MCFE. where q Enc denotes the number of distinct labels queried to QLeftRight.

Setup (1 λ , 1 n ) : Return pp ← Setup(1 λ , 1 n ) KeyGen (pp) :
Proof. WLOG, we can consider the security where only one label is queried to QLeftRight, and that label is not queried to QEnc. Namely, we show there exist PPT adversaries B, B and B such that: The theorem follows from Lemma 2.5 (from one to many labels). We call the unique label queried to QLeftRight (if QLeftRight is not queried, the security follows trivially).

Intuitively, the proof uses the adt-pos + -IND security of DMCFE for the case where all honest slots are queried to QLeftRight(•, •, •, ), and the security of the PRF together with the IND-CPA security of SE for the case where not all honest slots are queried to QLeftRight(•, •, •, ).

Decentralized Multi-Client Function Encryption

In this section, we modify the generic construction of Section 3 to make it decentralized. Since our construction makes generic use of any single-input inner-product FE, we cannot directly use directly the transformation from [ABKW19], because the master secret key msk may be arbitrary, and not necessarily the concatenation of the parties' secret keys sk i (for i ∈ [n]), as required by [ABKW19]. Moreover, the functional decryption keys sk f may not be computed just from sk i . We present a different generic transformation that decentralizes any MCFE assuming the underlying single-input FE has an additional structural property, that is fulfilled by most known constructions of single-input inner FE for inner products. This property is called special key derivation (see below), and is very similar to special key derivation for MCFE defined in [ABKW19].

We obtain a stronger security notion than [ABKW19], in the sense that the adversary is able to corrupt functional decryption key share by share, and can try to infer information from incomplete functional decryption keys (see Remark 2.8 for more details on the difference between the security notions). This is the same security as in the original DMCFE from [CDG + 18a], except we achieve the decentralization with no extra assumption, simply by performing an additive secret sharing of the master secret key of the underlying single-input FE.

Definition 5.1 (FE with Special Key Derivation). Let FE = (Setup, KeyGen, KeyDer, Enc, Dec) be a public-key FE scheme for the inner product functionality F ip ρ , where ρ = (Z, 1, n • m, X, Y ) where n, m, X, Y are positive integers. FE is said to have special key derivation modulo M if:

-The algorithm KeyGen(pp) generates a master secret key of the form msk := U ∈ Z κ×mn M , for some constant κ (which can depend on pp).

sk y ← KeyDer(pp, msk, y) outputs sk y = (y, U • y ∈ Z κ M ). For our security proof, we require M to be a prime number.

Instantiations. All the stateless IPFE constructions in [ALS16] satisfy the special key derivation property. More precisely, the DDH construction has special key derivation modulo p, the prime order of the underlying cyclic group, and κ = 2 (using notations from [ALS16], the matrix U is defined by U 1,i = s i and U 2,i = t i ). The Paillier and LWE constructions have special key derivation modulo any large enough prime number M so that U • y is the same modulo M and over the integers with overwhelming probability over the generation of msk. For Paillier, κ = 1 and U 1,i = s i , while for LWE, κ = m and U = Z (using notations from [ALS16]).

Construction. The construction is provided in Fig. 10.

Correctness. The only remaining part of correctness to be proven for the scheme in Fig. 10 is to show that the key computed by the algorithms KeyDerShare and KeyDerComb corresponds to the one that would have been computed by KeyDer. This follows from the following fact: where q Enc denotes the number of distinct labels queried to QLeftRight.

sk y = n i=1 sk i,y = n i=1 U i • y = U • y .

  Definition 2.2. (Security of MCFE) Let MCFE be an MCFE scheme, F = {F ρ } ρ a function family indexed by ρ and Labels a label set. For xx ∈ {sta, adt}, yy ∈ {any, pos + }, and β ∈ {0, 1}, we define the experiment xx-yy-IND MCFE β in Fig. 1, where the oracles are defined as:

  Definition 2.4. (1-label Security) Let MCFE be an MCFE scheme, F = {F ρ } ρ a function family indexed by ρ and Labels a label set. For xx ∈ {sta, adt}, yy ∈ {any, pos + }, and β ∈ {0, 1}, we define the experiment xx-yy-IND-1-label MCFE β exactly as in Fig.

Fig. 1 .

 1 Fig. 1. Security games for MCFE

Fig. 3 .

 3 Fig. 3. Security games for PRF. The oracle O PRF ( ) returns PRF K ( ) if β = 0; RF( ) otherwise, where RF denotes a random function computed on the fly.

Fig. 4 .

 4 Fig. 4. Security games for SE. The oracle O SE (m0, m1) returns Enc(K, m β ).

Fig. 6 .

 6 Fig. 6. Games for the proof of Theorem 3.3. Here, HS := [n] \ CS. Condition (*) is given in Definition 2.1. Here, RF denotes a random function that is computed on the fly. WLOG, QLeftRight is only queried on label , and QEnc isn't queried on .

  n, A), and G 4 corresponds to sta-pos + -IND MCFE 1

  7. If κ < 2, then B 2 queries its left-right oracle on input (0 . . . 0 x j,0 i 0 . . . 0), (0 . . . 0 x j,1 i 0 . . . 0) to get ct i := Enc ipfe (pp ipfe , (0 . . . 0 x j,b i 0 . . . 0)), where b ∈ {0, 1}, depending on the experiment B 2 is interacting with. If κ ≥ 2, then B 2 queries its left-right oracle on input (0 . . . 0 x j,0 i -x 1,0 i 0 . . . 0), (0 . . . 0 x j,1 i -x 1,1 i 0 . . . 0) to get ct i := Enc ipfe (pp ipfe , (0 . . . 0 x j,b i -x 1,b i 0 . . . 0)), where b ∈ {0, 1}, depending on the experiment B 2 is interacting with. Then, B 2 returns ct i := Add(ct i , t i, ) to A. Since we are considering pos + -IND security, all honest slots are queried on QLeftRight(•, •, •, ), thus for κ = κ < 2, for all y queried to QKeyD, Condition (*) implies that (0 . . . 0 x j,0 i 0 . . . 0), y = (0 . . . 0 x j,1 i 0 . . . 0), y for all queries

  {ski} i∈[n] ← KeyGen(pp) For i, j ∈ [n] : ki,j ← {0, 1} λ Return {sk i = (ski, {ki,j, kj,i} j∈[n] )} i∈[n]Enc (pp, sk i , xi, ) :Parse sk i = (ski, {ki,j, kj,i} j∈[n] ) cti ← Enc(pp, ski, xi) For all j ∈ [n] : ki,j( ) := PRF k i,j ( ) Ki( ) := ⊕ j∈[n] ki,j( ) ct i ← Enc SE (Ki( ), cti) Return (ct i , {kj,i( )} j∈[n] ) KeyDerShare (pp, sk i , f ) : Parse sk i = (ski, {ki,j, kj,i} j∈[n] ) Return sk i,f ← KeyDerShare(ski, f ) KeyDerComb (pp, {sk i,f } i∈[n] ) : sk f := KeyDerComb(pp, {sk i,f } i∈[n] ) Return sk f Dec (pp, sk f , ct 1 , . . . , ct n ) : Parse {ct i = (ct i , {kj,i( )} j∈[n] )} i∈[n] For i ∈ [n] : Ki( ) = ⊕ j∈[n] ki,j( ) cti ← Dec SE (Ki( ), ct i )Return Dec(pp, sk f , ct1, . . . , ctn).

Fig. 9 .

 9 Fig. 9. Compiler from an xx-pos + -IND DMCFE, DMCFE, into an xx-any-IND DMCFE, DMCFE , using an IND-CPA symmetric-key encryption scheme SE.

  Theorem 4.1 (Security). Let the tuple DMCFE = (Setup, KeyGen, KeyDerShare, KeyDerComb, Enc, Dec) be an adt-pos + -IND-secure DMCFE scheme for a family of functions F. Let SE = (Enc SE , Dec SE ) be an IND-CPA symmetric-key encryption scheme. Let PRF be a pseudorandom function. Then the DMCFE scheme DMCFE = (Setup , KeyGen , KeyDerShare , KeyDerComb , Enc , Dec ) described in Fig.9is adt-any-IND secure. Namely, for any PPT adversary A, there exist PPT adversaries B, B , and B such that:Adv adt-any-IND DMCFE ,A (λ, n) ≤ q Enc • Adv adt-pos + -IND DMCFE,B (λ, n) + q Enc n 2 • Adv IND-CPA SE,B (λ) + 2q Enc n 2 • Adv PRF,B (λ),

  n) ≤ Adv adt-pos + -IND DMCFE,B (λ, n) + n 2 • Adv IND-CPA SE,B (λ) + 2n 2 • Adv PRF,B (λ).

  Theorem 5.2 (adt-pos + -IND-security). If the FE scheme FE = (Setup ipfe , KeyGen ipfe , KeyDer ipfe , Enc ipfe , Dec ipfe ) is an any-IND-secure FE scheme for the inner product functionality defined as F ip ρ ipfe , ρ ipfe = (Z, 1, m, 2X, Y ), if FE has the special key derivation property modulo the prime number M , and if PRF is secure, then DMCFE from Fig.10is adt-pos + -IND-secure for the functionality defined as F ip ρ , ρ = (Z, n, m, X, Y ). Namely, for any PPT adversary A, there exist PPT adversaries B and B such that:Adv adt-pos + -IND MCFE,A (λ, n) ≤ 2n 2 (n -1)q Enc • Adv PRF,B (λ) + 2q Enc • Adv any-IND FE,B (λ),

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

We could define a stronger security notion without this restriction. However, in this paper, as in the prior works on MCFE, we add this restriction. In particular, we allow the secret key for the slot i to decrypt ciphertexts for the slot i. We leave achieving stronger security as an interesting open problem.

Acknowledgments. This work was supported in part by the European Union's Horizon 2020 Research and Innovation Programme under grant agreement 780108 (FENTEC), by the ERC Project aSCEND (H2020 639554), by the French Programme d'Investissement d'Avenir under national project RISQ P141580, and by the French FUI project ANBLIC. The third author was partially supported by a Google PhD Fellowship in Privacy and Security. Part of this work was done while the second author was at IBM Research, Yorktown Heights, USA, and the third author was at École normale supérieure, Paris, France.

Formally, for all b ∈ {0, we define G b as adt-yy-IND DMCFE 1 (λ, n, A), except the game guesses an honest slot that is not going to be queried to QLeftRight(•, •, •, ), by sampling uniformly at random i ← {0, ..., n}, where i = 0 means that all honest slots are queried to QLeftRight(

For all j ∈ [n], we prove that there exist PPT adversaries B and B such that:

To prove the statement above, we use the fact that if there is a query QLeftRight(i, x j,0 i , x j,1 i , ) with x j,0 i = x j,1 i , then the slot i ∈ [n] cannot be corrupted without violating the Condition (*) from the security definition given in Definition 2.2. We call such a slot explicitly honest, and such a query explicitly honest. We define hybrid games H ρ for all ρ ∈ {0, . . . , n}, defined as G 0 , except that every explicitly honest query QLeftRight(i, x j,0 i , x j,1 i , ) is answered by Enc (pp, sk i , x j,1 i , ) if i ≤ ρ, and is answered by Enc (pp, sk i , x j,0 i ,

The game H 0 is the same as G 0 , and H n is the same as G 1 . We prove that for all j ∈ [n], for all ρ ∈ [n], there exist PPT adversaries B ρ and B ρ such that:

The transition from H ρ-1 and H ρ-1 is justified as follows. If the slot ρ is never queried on an explicitly honest query, then the two games are the same by definition. Otherwise, we use the security of the PRF to switch the key k ρ,i ( ) to uniformly random (note that we can do so since the slots ρ and i are known beforehand by the reduction). If the guess i is correct (i.e i is honest but never queried to QLeftRight), then the key k ρ,i ( ) := PRF k ρ,i ( ) only appears in the output QLeftRight(ρ, •, •, ). So, for these challenge ciphertexts, we have a uniformly random key K ρ ( ), which allows us to use the IND-CPA security of SE, and changes encryption of x j,0 ρ as in G ρ-1 into encryption of x j,1 ρ , as in G ρ . Then we switch back the key k ρ,i from uniformly random to pseudo-random, using the security of the PRF once again. Summarizing, we have:

Summing up for all ρ ∈ [n], we obtain the following for all j ∈ [n]:

Thus, we have:

Therefore, we obtain:

KeyGen(pp) :

(msk ipfe , mpk ) ← KeyGen ipfe (pp ipfe ); msk := msk ipfe :

and msk KeyDerShare(pp, ski, y ∈ R mn ) : :::

G0, :: G3:

Output: α if Condition (*) is satisfied, or a 0 otherwise.

QCor(i):

Return ski = (Ui, {Ki,j} j∈[n] )

QKeyD(y):

::: G0, ::: G1, ::::::: G2, G3 :

Return Enc(pp, ski, x j i , )

:::

G1, :: G2:

or 0 otherwise.

QCor(i):

Pick Ui uniformly under the constraint ∀y ∈ Si, ski,y = Ui • y Return ski := (Ui, {Ki,j} j∈[n] ) QKeyD(y, i): Add y to Si. Then, do the following. Let A be a PPT adversary against the security of MCFE. We proceed via a hybrid argument, using the games described in Fig. 11. Note that G 0 corresponds to the game adt-pos + -IND DMCFE 0 (λ, n, A), and G 3 corresponds to the game adt-pos + -IND DMCFE 1 (λ, n, A). Thus, we have:

A (λ, n) . Game G 1 . In game G 1 , we change the way the oracles QCor and QKeyD answer: instead of using each individual share U i , they generate their answers on-the-fly to be consistent with previous answers and KeyDer ipfe (pp ipfe , msk ipfe , y) in the case of QKeyD. The transition from G 0 to G 1 is justified by linear algebra: the two games are identically distributed. This comes from the fact that in both games, the partial functional decryption keys sk i,y are uniformly random over Z κ×nm M subject to: -∀i ∈ [n], y, y ∈ Z nm , α ∈ Z M : sk i,y + α • sk i,y = sk i,y+α•y , and -∀y ∈ Z nm , i∈[n] sk i,y = Uy. These keys can be efficiently sampled on-the-fly subject to these constraints, as described in Fig. 11. Game G 2 . In game G 2 , the challenge ciphertexts encrypts x j,1 i instead of x j,0 i . The transition from G 1 to G 2 is justified by the adt-pos + -IND security of MCFE proven in Theorem 3.7. Game G 3 . In game G 3 , we change back the way the oracles QCor and QKeyD answer to match adt-pos + -IND DMCFE 1

(λ, n, A). The transition from G 2 to G 3 is similar to the one from G 1 to G 0 : G 3 and G 2 are perfectly indistinguishable.

Putting everything together, we obtain the theorem.


Kunihiko Tajiri

Hirotaka Muto

Marty-Dessus Didier

Laurent Berquez

Gilbert Teyssedre

Marie-Laure Locatelli

Sombel Diaham

Virginie Griseri

Flora Carrasco

Behavior of space charge in polyimide and the influence on power semiconductor device reliability

Keywords: passivation material, space charge, LIMM, DC conductivity, power semiconductor device

Polyimide is widely used in film form as a passivation material for power semiconductor devices such as Si, SiC, GaN, etc. The magnitude of the electric field at the edge termination area of these semiconductor devices is becoming higher due to the increase of operational voltage and/or demand for shrinking the edge termination area to increase device active area. Hence it is concerned that the accumulation of space charge in the encapsulation and passivation material may affect the insulation performance of these devices, for example, the degradation of withstand voltage due to distortion of the internal electric field caused by space charge accumulation. To design space charge resistance of semiconductor devices, it is important to understand the space charge behavior in polyimide films with a thickness of several to several tens of µm. This chapter addresses practical implementation, specifications and issues on space charge in polyimide insulation on power semiconductor devices focusing on the space charge measurements in thin polyimide films using the latest developed LIMM method and DC conductivity measurements.

Introduction

In recent years, high voltage electronics and power electronics applications have emerged needing the use of power semiconductor devices with widely used Si and wide bandgap materials such as SiC, GaN. In these devices, thin polymer material have been widely used as passivation coating to protect device surfaces. Particularly, polyimide (PI) is of great interest due to its excellent thermal and electrical properties and its easy processing. Some of the most important applications of these materials films are as inter-level dielectric insulators and as electronic device surface passivation [START_REF] Zelmat | Investigations on high temperature polyimide potentialities for silicon carbide power device passivation[END_REF]. The typical image of PI layer at the edge surface of semiconductor chip is shown in Figure 1. Space charge is generally reported as a triggering mechanism for the degradation of insulators [START_REF] Mazzanti | Electrical aging and life models: the role of space charge[END_REF], and considered as a cause of the decrease of electrical breakdown voltage of those polymer films. Furthermore, the space charge could degrade semiconductor leakage current characteristics by strengthening the electric field in semiconductor substrate region. The influence of space charge transportation and accumulation on surface of semiconductor chip has been discussed in [START_REF] Rahimo | The impact on power semiconductor device operation due to local electric field alterations in the planer junction termination[END_REF][4] [START_REF] Imperiale | TCAD modeling of encapsulation layer in high-voltage, hightemperature operation regime[END_REF][6] using TCAD simulation. Reliability tests of IGBT devices under accelerated conditions were reported in [START_REF] Tanaka | Robust HVIGBT module design against high humidity[END_REF] [START_REF] Kitajima | Lifetime estimation model of HVIGBT considering humidity[END_REF] showing that the degradation (increase) of leakage current of the device is caused possibly by the formation of space charge on the surface at semiconductor edge termination area. The decrease of withstand voltage of HV IGBT due to accumulated space charge (Q ss ) on the surface of device edge termination area has been demonstrated by TCAD simulation as shown in Figure 2. Attempts have also been made to evaluate the space charge resistance of a real chip by evaluating the withstand voltage of a semiconductor chip using a guard probe electrode to simulate an external electric field due to space charge as shown in Figure 3 To evaluate the actual influence by the space charge accumulation, it is necessary to clarify the space charge distribution around the edge termination area of semiconductor chip. Many trials have been performed to measure the space charge characteristics in polyimide and encapsulation material such as silicone gel as described below. Earlier reports featuring space charge in PI [START_REF] Kaneko | Effects of electrode material on injection and space charge formation in polyimide[END_REF][START_REF] Sessler | Electrical conduction in polyimide films[END_REF][START_REF] Liang | Effect of film thickness on the electrical properties of polyimide thin films[END_REF] reported the processes indirectly e.g. through charging current measurements or directly as with pulsed electroacoustic (PEA) method with relatively thick films (125 µm) [START_REF] Kaneko | Effects of electrode material on injection and space charge formation in polyimide[END_REF]. In [START_REF] Kaneko | Effects of electrode material on injection and space charge formation in polyimide[END_REF], the effect of humidity in air and difference due to electrode material (Al and Au) on space charge formation with time evolution are discussed.

Recently, the Laser Intensity Modulation Method (LIMM) [START_REF] Petre | A comparison of different mathematical treatments for solving the inverse problem in focused laser intensity modulation method[END_REF] have been performed to investigate space charge characteristics in thin PI films with few µm in thickness under the DC field up to 125 kV/mm, close to breakdown voltage [START_REF] Locatelli | Space charge formation in polyimide films and polyimide/SiO2 double-layer measured by LIMM[END_REF][START_REF] Carrasco | Assessment of the High Field Behaviour of Polyimide Films: Experimental Methods and Impact of Electrode Material[END_REF][START_REF] Carrasco | Effect of film thickness and electrode material on space charge formation and conductivity in polyimide films[END_REF][START_REF] Tajiri | Electric field enhancements due to space charge in thin polyimide film[END_REF]. In [START_REF] Tajiri | Electric field enhancements due to space charge in thin polyimide film[END_REF], the space charge characteristics were reported under DC voltage of from low field of 2.5 to 125 kV/mm with the correlation with DC conductivity trends. Considering the encapsulation material, some studies have been performed through charge accumulation measurement in silicone gel by using PEA [START_REF] Shiota | Space charge behavior and electrical conduction of silicone gel[END_REF][19] and LIPP (Laser-Induced Pressure Pulse) [START_REF] Breit | Investigations on DC conductivity and space charge in silicone gel[END_REF] methods, and space charge characteristics of only surface information and total amount of charge have been measured in [START_REF] Shiota | Space charge behavior and electrical conduction of silicone gel[END_REF][19] and [START_REF] Breit | Investigations on DC conductivity and space charge in silicone gel[END_REF], respectively.

As described, many attempts have been made to evaluate the influence of space charge, quantitative evaluation has been under development, especially in thin PI. However, the space charge distribution in the PI film, which is important for providing space charge tolerance of semiconductor chip, is gradually becoming apparent along with the influence of the operating environment. In this chapter, the latest developments with space charge measurements in thin polyimide films using the LIMM method, with the focus on local field strengthening and correlation with conductivity measurements.

Space charge evaluation methods

PEA method

Since the 1980s, the PEA method has been used to measure the space charge of sheet or film samples in order to investigate space charge phenomena and evaluate the aging of dielectrics. A space charge distribution by converting a pressure wave generated by applying a pulse electric field to a sample under high voltage application, and converting the pressure wave into an electric signal using a piezoelectric element. The thickness of the sample that can be evaluated by PEA is more than 100 µm and its spatial resolution is about several tens of µm.

(F)LIMM method

The (Focused) Laser Intensity Modulation Method or (F)LIMM is a thermal wave method dedicated to the space charge analysis of thin dielectric films (with a thickness from 5 μm to 50 μm) [START_REF] Singh | A review of developments in thermal techniques for charge profile measurements in polymer electrets[END_REF][START_REF] Collins | Practical application of the thermal pulsing technique to the study of electrets[END_REF]. This method is originally proposed by Lang [START_REF] Lang | A technique for determining the polarization distribution in thin polymer electrets using periodic heating[END_REF] in the 1980s, and the characterization of space charge distribution had been performed under volt-off after external DC voltage application. Recent development has been reported that LIMM measurement is carried out under volt-on [START_REF] Velazquez-Salazar | Thermal modeling and calibration in (F)LIMM using an external bias field: Theory and experiment[END_REF]. The LIMM is much suitable to clarify the space charge characteristics in a polymer film with only several μm thickness, which is a typical thickness of passivation layer on a semiconductor chip. Figure 4 shows the schematic diagram of On-line LIMM. A DC potential (Vht) is applied to the top electrode of the measuring cell through a lowpass filter. (F)LIMM currents are recorded after pre-amplification and extracted from noise by a lock-in amplifier. To protect a damage from an eventual breakdown of the sample, an electrical protection device was introduced at the output of the measuring cell. Figure 4. Schematic diagram of (F)LIMM [START_REF] Velazquez-Salazar | Thermal modeling and calibration in (F)LIMM using an external bias field: Theory and experiment[END_REF] The thermal gradient created by the laser beam induces periodical and local expansions that lead to relative charge displacement regarding to the electrodes within the irradiated volume. Varying the laser beam modulation frequency, one can control the depth of thermal diffusion and then calculate its effect on the total current signal. Finally, a mathematical treatment allows charge density profiles reconstruction in the direction of the sample thickness. A modulated laser beam of a frequency f heating a surface S of a top electrode sputtered on a dielectric non-polar sample of thickness L, to which an additional DC voltage Vht is applied, the fundamental (F)LIMM equation for the complex current I(f) can be expressed by [START_REF] Velazquez-Salazar | Thermal modeling and calibration in (F)LIMM using an external bias field: Theory and experiment[END_REF]:

(1) z is the direction normal to the sample, α z the coefficient of thermal expansion (K -1 ), αε the coefficient of thermal dependence of the dielectric permittivity (K -1 ),  the permittivity, E i (z) the internal electric field along z-axis (V.m -1 ) and T(z,f) the simulated spatial variation of the temperature versus frequency.

Space charge behavior in polyimide film

Space charge distribution in polyimide film

In this subsection, the LIMM measurement results of PI film in a typical case using cumulative DC voltage application. Figure 5 shows the sample structure and the example of LIMM measurement protocol. The thickness of PI film is 20 μm. The polarization steps consist in applying a DC electric field from 25 to 125 kV/mm with positive or negative polarity. The corresponding positive or negative DC voltages are applied on the top electrode of the sample in air at room temperature, whereas the Si substrate is grounded. After each polarization step, a depolarization process is performed by shortcircuiting the sample. A cumulative protocol is applied for successive voltage steps on the sample as shown in the right side of Figure 5. Volt-on and volt-off steps of each 60 min are applied on the sample from 25 to 125 kV/mm, with the steps of 25 kV/mm. LIMM measurements are performed throughout the whole protocol, with every 10 min scanning of 63 frequency points from 10 Hz to 10 kHz.

Figure 6 shows LIMM current waveform under the field of 25, 50, 75, 100, and 125 kV/mm, positive polarity. The space charge and internal electric field distributions are deduced from Eq. ( 1) as shown in Figure 7 (a) and (b), respectively. In this case, positive and negative space charges are confirmed close to and at the depth of from 4-10 µm from top Au electrode, respectively, which causes the enhancement of positive field strengthening at 2-6 µm depth. The maximum values of these are confirmed to increase along with the applied DC field. Time evolution of maximum peaks of enhanced electric field in both polarities are shown in Figure 8. As mentioned so far in this subsection, the space charge and enhanced electric field characteristics in polyimide under external DC voltage on and off can be evaluated including depth-profile, time evolution, as will be explained in subsection 3.2, can be evaluated by using LIMM method. Negative charge peak increases.

Positive field peak increases.

DC conductivity

To clarify the influence of space charge accumulation to the conductivity behavior, space charge density and internal electric field are compared with DC conductivity. Figure 9, 10, and 11 show the maximum space charge density of negative charge, maximum positive internal electric field, and DC conductivity, respectively, under the applied field from 25 to 125 kV/mm for both polarities. To compare these figures, no remarkable influence on the conductivity by space charge accumulation inside polyimide at this level work. To establish a direct link between space charge dynamics and conduction phenomena, further evaluations are still necessary.

Effect of space charge on semiconductor devices

As describe in Section 1, the degradation (increase) of leakage current of the device is caused possibly by the formation of space charge on the surface at semiconductor edge termination area. Figure 10 shows the electric field enhancement ratio defined in Eq. ( 2) confirmed in the LIMM measurement depending on the applied DC field of from -25 to 25 kV/mm. It is confirmed that the enhancement ratio in PI film is negligibly small (less than 1.1) for applied fields less than 10 kV/mm. However, it can reach much higher like 1.4 at higher applied field like 25 kV/mm. This result implies that electric field at edge termination area should be carefully designed under such an operational electric field as is the case of SiC devices to prevent the influence of space charge accumulation. It should be noted that not only inside polyimide, but space charge accumulations in encapsulation material and the interface between polyimide and encapsulation as its structure shown in Figure 1 are also needed to be clarified. Moreover, the influence of environmental conditions such as temperature and humidity on the space charge behavior should be taken into account.

Conclusion

It has been presented that the space charge distribution can be clarified in thin polyimide film using LIMM method from relatively low field of 2.5 kV/mm up to 125 kV/mm which is close to breakdown field. The electric field enhancement due to space charge accumulation is shown to be 1.4 times at 25 kV/mm under room temperature condition. To design much reliable structure against space charge accumulation in polyimide and encapsulation material, its distributions are needed to be clarified by the further study.

Figure 1 .

 1 Figure 1. Power module and edge termination structure of semiconductor chip

  [START_REF] Yamatake | New Technology for Evaluating Insulation Reliability of Termination of Power Semiconductor Chip[END_REF].

Figure 2 .Figure 3 .

 23 Figure 2. Avalanche voltage simulation results of HVIGBT chip for different Qss 0 1.0 2.0 3.0 4.0 Applied voltage (a.u.)

Figure 5 .Figure 6 .FrequencyFigure 7 .Figure 8 .

 5678 Figure 5. Typical sample structure and LIMM measurement protocol (cumulative voltage application of 25-125 kV/mm, positive polarity)

Figure 9 .

 9 Figure 9. Maximum negative space charge density

Figure 10 .

 10 Figure 10. Peak value of internal electric field linked to field strengthening (filled circle) and enhancement ratio of those peaks (open square) versus applied electric field

Acknowledgments

The authors would like to express our gratitude to all the people who have involved in this work, especially, Dr. Thierry Lebey who is former Director of LAPLACE for his tremendous support during the collaborative research about LIMM evaluation.