Jérémy Chotard

Edouard Dufour-Sans

Romain Gay

Hieu Duong

Phan

David Pointcheval

Dynamic Decentralized Functional Encryption

Keywords: Dynamic, Decentralized, Functional Encryption, Inner Product

We introduce Dynamic Decentralized Functional Encryption (DDFE), a generalization of Functional Encryption which allows multiple users to join the system dynamically, without relying on a trusted third party or on expensive and interactive Multi-Party Computation protocols. This notion subsumes existing multi-user extensions of Functional Encryption, such as Multi-Input, Multi-Client, and Ad Hoc Multi-Input Functional Encryption. We define and construct schemes for various functionalities which serve as building-blocks for latter primitives and may be useful in their own right, such as a scheme for dynamically computing sums in any Abelian group. These constructions build upon simple primitives in a modular way, and have instantiations from well-studied assumptions, such as DDH or LWE. Our constructions culminate in an Inner-Product scheme for computing weighted sums on aggregated encrypted data, from standard assumptions in prime-order groups in the Random Oracle Model.

Introduction

At TCC [START_REF] Shi | Privacy-preserving aggregation of time-series data[END_REF]Boneh,Sahai,and Waters [BSW11] formalized Functional Encryption (FE), a new paradigm of Public-Key Encryption that allows the owner of the secret key to generate restricted keys, enabling third parties to recover function evaluations of the plaintext from a ciphertext. The formalization of FE gave many researchers a common framework in which to consider their schemes: the nuances between Identity-Based Encryption (IBE), Hierarchical IBE, Fuzzy IBE, and different forms of Attribute-Based Encryption (ABE) [BF01, BBG05, SW05, GPSW06] could now be captured simply by specifying which functionality the scheme aims to implement. The set of algorithms to be implemented and the indistinguishibility game in which to prove security were now standard.

But for all its successes, Functional Encryption has two, somewhat related, important limitations: (1) In many contexts, FE encourages centralization. In his 2015 position paper The Moral Character of Cryptographic Work, Rogaway pointed out that a switch from Public-Key Encryption to Identity-Based Encryption would represent "a radical change in the trust model", as the authority with knowledge of the master secret key would have the ability to fully recover every message encrypted under its public key, even though those messages would be intended for a variety of parties. This criticism can be extended to many other functionalities of Functional Encryption. (2) The kind of controlled computation enabled by Functional Encryption does not extend to computations involving data from multiple parties. This is limiting because a significant component of the public's privacy concerns today is related to data being made available to a third-party for the advertised purpose of retrieving some form of intelligence of the public's needs, from the computation of simple statistics to the training of advanced machine learning models. This means FE is not an appropriate framework for addressing this pressing issue.

Our Contributions

1. First, we fill the gap left by the definition of FE by introducing a new primitive we term Dynamic Decentralized Functional Encryption (DDFE). DDFE allows aggregating data coming from different parties, does not require a trusted party with a master secret key, and accounts for participants trusted third-party distributing the participant's secret keys, cannot accommodate new participants, and does not allow the participants to choose which functions can be computed by whom via functional decryption key derivation. Most PSA schemes in the literature focus on computing (non-weighted) sums of the participants' data [CSS12, JL13, BJL16]. Note that Private Stream Aggregation usually relies on a Differential Privacy component as an added privacy protection, while we leave the addition of a Differential Privacy layer in DDFE for future work.

Multi-Authority Functional Encryption (MAFE) was introduced by Chandran et al. [CGJS15].

Like DDFE, it is a strongly decentralized variant of Functional Encryption. It allows for encrypting messages for sets of authorities along with an access policy. These authorities can then generate keys for individual identities. Armed with a single ciphertext and a set of functional decryption keys from the appropriate authorities, the decrypter can recover a function of the plaintext that is specified by the access policy on the identities for which the functional keys were computed. Unlike DDFE, MAFE does not account for the possibility of multiple ciphertexts being decrypted together, and having their data interact with one another.

Multi-Client Functional Encryption (MCFE) was defined in [GGG + 14,GKL + 13] along with Multi-Input Functional Encryption (MIFE), and also enables computing functions of multiple parties' data in the presence of a trusted third-party distributing both the parties' secret keys and functional decryption keys. That is, both MIFE and MCFE extend Functional Encryption to a setting where the input is spread across different sources. Each source can encrypt its data independently, and the ciphertexts can then be aggregated and decrypted with functional decryption keys. Generation of the latter still requires a trusted authority, which owns a so-called master secret key: a single point of failure for the cryptosystem.

As opposed to MIFE, the encryption algorithm of an MCFE takes an additional input, referred to as a label, which enforces a finer-grained control on access to the encrypted data. Unlike in MIFE, where individual ciphertexts can be arbitrarily combined, in MCFE, only ciphertexts generated for the same label can be used together to decrypt. This limits how much information is revealed by each functional decryption key, thereby strengthening security. Typically, labels are used as timestamps. In this context, a functional decryption key can only compute, say, statistics on aggregated data for the same time frame.

Any MCFE for a given functionality directly implies an MIFE for the same functionality, by simply using a fixed label for all encryptions1 . Reciprocally, an MIFE for general functions would directly imply an MCFE for general functions, since the label can be part of the plaintext, and the function can check that every slot used the same label. However, this is not true for the case of smaller classes of functions for which there are practical schemes, such as Inner-Products.

The first construction of MIFE for inner products was given in [AGRW17], from standard assumptions in pairing groups. This was later improved by [ACF + 18], which gave a generic construction from any single-input FE for inner products. The first construction of MCFE from standard assumptions was given by Chotard et al. [CDG + 18] for computing inner products, although the security they achieved admits several limitations compared to the standard MCFE security definition.

Decentralized Multi-Client Functional Encryption (DMCFE). Chotard et al. [CDG + 18] also defined a new variant of MCFE, called Decentralized MCFE (DMCFE), for which they gave Inner-Product instantiations from pairings. The DMCFE variant did away with the trusted third-party, as it enabled participants to choose their own secret keys and generate functional decryption keys non-interactively.

However, it still had an interactive setup, with no easy way of adding new participants, and it suffered from the same security caveats as the MCFE it was a variant of.

In a follow-up work, [LT19] provided a construction in the standard model from the LWE assumption, which still suffers from the same security restrictions as [CDG + 18]. The works [ABKW19, ABG19] improved the security guarantees obtained, the former using the DDH assumption in the ROM, the latter using a generic construction from any single-input FE for inner products. Both schemes however have individual ciphertexts of size proportional to the total number of users. Thus, we use different techniques to obtain the desirable security notion without having asymptotically large ciphertexts.

Ad Hoc Multi-Input Functional Encryption. In [ACF + 20], the authors define the notion of Ad Hoc Multi-Input Functional Encryption, where users can join the system on-the-fly, and functional decryption keys can be generated in a decentralized way, by each client, without interaction. They give a feasibility result for all functions, and a practical construction for inner products.

The definition of DDFE we put forth is more general than [ACF + 20]. For instance, in our definition, the algorithm that generates functional decryption key does not necessarily require a specified group of users: schemes with potentially more flexibility than Ad Hoc MIFE can be captured by our definition.

Moreover, their scheme for inner product cannot handle labels, which implies that ciphertexts computed by each client individually can be mix and matched arbitrarily. As explained above, this implies that each functional decryption key reveals large amounts of information on the encrypted values, and renders the security vacuous whenever sufficiently many keys are issued. Labels help mitigate this leakage by enforcing a better granularity on the way the encrypted data is accessed.

Besides, the security model of [ACF + 20] does not explicitly address the information that can be leaked when decrypting partial ciphertexts, that is, ciphertexts coming from an incomplete group of users. Preventing the adversary from recovering information on partial ciphertexts is made more challenging in our construction, which handles labels.

Outline

We first provide a definition of DDFE in Section 2, along with a security definition and functionalities of interest. In Section 3, we recall some useful preliminaries and definitions. We then showcase our constructions: a generic construction of AoNE is presented in Section 4, while a specific instantiation is studied in Section 5. We use it modularly in Section 6 to construct a DSum scheme. In Section 7, we capitalize on both those primitives to construct a DDFE scheme for the Inner-Product functionality.

Definitions and Security Models

In this section, we provide the formal definition of our new primitive of Dynamic Decentralized Functional Encryption (DDFE), together with several security models. Then, we list a few instantiations with some concrete functionalities.

Notations

In the following, [n] will denote the set of integers {1, . . . , n}. For any set A, L(A) will denote the set of finite lists of elements of A, while S(A) will denote the set of finite subsets of A. Unlike sets, lists are ordered and may contain repeated elements.

Dynamic Decentralized Functional Encryption

In defining DDFE, one of our key concerns is generality: we want to achieve for multi-user primitives what Functional Encryption did for single-user primitives. We resist as much as possible the temptation to let the idiosyncrasies of the functionalities we present and implement in this work leak into the definition of DDFE itself. Perhaps the best example of this is in the role of the label. We believe labels, as used in MCFE, are useful for practical use, because in limiting what can be decrypted, they limit data leakage and make it possible to consider using the same primitive over a long time. However, we recognize that some primitives which are of practical use without labels may arise, that some schemes using labels may want to have them interact in more complex ways than perfect matching, and that there is value in our definitions being able to capture existing work. In Section 2.3, we give more details on how our umbrella notion captures a large set of existing primitives, ranging from Public-Key Encryption to Ad Hoc Multi-Input Function Encryption as introduced in Agrawal et al. [ACF + 20].

Definition 1 (Dynamic Decentralized Functional Encryption). A dynamic decentralized functional encryption scheme over a set of public keys PK for functionality F : L(PK × K) × L(PK × M) → {0, 1} * consists of five algorithms:

-Setup(λ): Generates and outputs public parameters pp. Those parameters are implicit arguments to all the other algorithms; -KeyGen(): Generates and outputs a party's public key pk ∈ PK and the corresponding secret key sk pk ; -Encrypt(sk pk , m): Takes as input a party's secret key sk pk , a value m ∈ M to encrypt, and outputs a ciphertext ct pk ; -DKeyGen(sk pk , k): Takes as input a party's secret key sk, a key space object k, and outputs a functional decryption key dk pk,k ; -Decrypt (dk pk,k pk ) pk∈U K , (ct pk ) pk∈U M : Takes as input a finite list of functional decryption keys (dk pk,k pk ) pk∈U K , a finite list of ciphertexts (ct pk ) pk∈U M , where U M , U K ∈ L(PK) are the lists of senders and receivers, respectively. It outputs a value y ∈ {0, 1} * .

We call a DDFE scheme Public-Key if its encryption algorithm does not make use of the secret key sk pk .

Correctness: We require that, for all security parameters λ ∈ N, for all polynomial size lists U M , U K ∈ L(PK) of public keys issued by KeyGen(), (pk, k pk ) pk∈U K ∈ L(PK × K) and (pk, m pk ) pk∈U M ∈ L(PK × M), it holds that the probability for

Decrypt((dk pk,k pk ) pk∈U K , (ct pk ) pk∈U M ) = F ((pk, k pk ) pk∈U K , (pk, m pk ) pk∈U M )
is 1, taken over pp ← Setup(λ), dk pk,k pk ← DKeyGen(sk pk , k pk ), for all pk ∈ U K , and ct pk ← Encrypt(sk pk , m pk ) for all pk ∈ U M .

We stress that each user is identified by a public key pk, which it can generate on its on with the associated secret key, using KeyGen. Anyone can thus dynamically join the system, by publishing its public key.

Remark 2 (Empty keys). Note that, unlike with standard, Single-Input FE, we do not require the empty key to be in K, because we operate over lists of elements of PK × K, so we simply define as the empty list. In both Single-Input Functional Encryption and DDFE, the empty key serves to capture all the information about the plaintext that intentionally leaks from every ciphertext (see [BSW11, Section 2]). In Single-Input FE, this is typically only used to highlight the fact that encryption leaks the length of the message. It is crucial to the security of any Functional Encryption scheme which accepts messages of variable lengths and leaks the length of the message, for otherwise it would be easy to win the IND security game by querying QLeftRight for two messages of different lengths (see Definition 17). With the leakage clearly stated in the functionality of the scheme, such a query would trigger the condition in the game's Finalize, and it would cause the adversary's guess to be discarded. But in the case of DDFE, more information is usually publicly associated with a ciphertext that simply its length. For instance, the set of users the data should be aggregated with, or the aggregation label, are typically public. Besides, it happens that the leakage of a set of ciphertexts is more than the cumulative leakage of the indidivual ciphertexts. Our AoNE and DSum schemes have this property, and it is expressed by their functionality outputting the relevant information when evaluated on the empty key with a (possibly non-singleton) list of ciphertexts.

Definition 3 (IND-Security Game for DDFE). Let us consider a DDFE scheme. No adversary A should be able to win the following security game against a challenger C, with unlimited and adaptive access to the oracles QNewHonest, QEncrypt, QLeftRight, QDKeyGen, and QCorrupt described below:

-Initialize: the challenger C runs the setup algorithm pp ← Setup(λ) and chooses a random bit b $ ← {0, 1}. It provides pp to the adversary A; -Participant creation queries QNewHonest: the challenger C runs the key generation algorithm (pk, sk pk ) ← KeyGen() to simulate a new participant, stores the association (pk, sk pk ) and returns pk to the adversary; -Encryption queries QEncrypt(pk, m): Recovers the secret key sk associated to pk and outputs the ciphertext ct ← Encrypt(sk, m). If pk is not associated with any secret key, nothing is returned; -Challenge queries QLeftRight(pk, m 0 , m 1 ): runs and forwards the output of QEncrypt(pk, m b ). Wlog.

we assume m 0 = m 1 . -Functional decryption key queries QDKeyGen(pk, k): Recovers the secret key sk associated to pk and outputs the functional decryption key dk k ← DKeyGen(sk, k). If pk is not associated with any secret key, nothing is returned; -Corruption queries QCorrupt(pk): Recovers the secret key sk associated to pk and outputs it. If pk is not associated with any secret key, nothing is returned; -Finalize: A provides its guess b on the bit b, and this procedure outputs the result β of the security game, according to the analysis given below.

The output β of the game depends on some conditions, where HS is the set of honest participants at the end of the game (the set of public keys generated via QNewHonest-queries and not corrupted via QCorrupt). Finalize outputs the bit β = (b = b), unless the following condition (*) is satisfied, in which case Finalize outputs a random bit β.

The condition (*) is true if there exist two lists of public keys U M , U K ∈ L(PK), two lists of messages (m 0 = (pk, m 0 pk ) pk∈U M , m 1 = (pk, m 1 pk ) pk∈U M ), and a list of keys k = (pk, k pk ) pk∈U K , such that F (k, m 0 ) = F (k, m 1 ), with m 0 pk = m 1 pk , for all pk ∈ U M such that pk ∈ HS; -QLeftRight(pk, m 0 pk , m 1 pk ) or QEncrypt(pk, m pk )-queries have been asked for all pk ∈ U M ∩ HS; -QDKeyGen(pk, k pk )-queries have been asked for all pk ∈ U K ∩ HS.

We say DDFE is IND-secure if for any adversary A,

Adv IND DDFE (A) = |2 × Pr[β = 1] -1| is negligible.
Intuitively, condition (*) means that the adversary can trivially recover b and win the game, which is thus not a real attack, hence a meaningless output with a random bit. Otherwise, β = 0 is a wrong guess and β = 1 is a correct guess during a meaningful attack. As usual, we are interested in adversaries with non-negligible advantage. Note however that the condition of trivial win cannot, in general, be checked in polynomial time. This is because there are exponentially many choices that can be made for the various lists, including the participant public keys and the values of the messages. Even if we impose strict requirements on the functionality, such as the presence of a label and a set of participants, it might not be possible to guarantee that the condition can be checked in polynomial time without a direct analysis of the structure of the functionality. There may exist functionalities for which such a check is a computationally hard problem. The issue of how to efficiently check for violations is thus left to the cryptosystem designers and provers. In the following, we will consider functionalities for which this condition can be efficiently checked. Now we present several weaker variants of the above security notion.

Definition 4 (sym-IND-Security Game for DDFE). We define a symmetric-key variant of the above security game in which the Finalize procedure outputs 0 if the adversary makes a query of the form (pk, m 0 , m 1 ) to QLeftRight and queries the same pk to QCorrupt. This means that the secret key sk pk not only allows users to encrypt on behalf of party pk, but also empowers them to decrypt the ciphertext generated by party pk. Thus, the challenge messages m 0 and m 1 have to be the same to avoid the adversary trivially recovering the random bit β. That is, the oracle QEncrypt should be used instead of QLeftRight.

Definition 5 (sel-IND-Security Game for DDFE). We define a selective variant of the above security game in which the adversary is forced to send all its queries to QNewHonest, upon which it receives the corresponding public keys. Then it sends all its queries to the oracles QEncrypt, QLeftRight, QDKeyGen and QCorrupt in one shot, and receives all of the outputs at once.

Note that our security notions is strong, in the sense that it allows the adversary to generate malicious public keys on its own. The challenger does not know the corresponding secret keys (which may not exist) for such public keys. More precisely, we allow dishonest key registrations, as originally introduced in [CKS08] in the context of NIKE.

Versatility of the Notion of DDFE

The notion of DDFE captures many existing primitives. We go over some such primitives and provide details here.

We first show that the notion of public-key encryption is captured by DDFE. That is, we can cast the former as a DDFE for a specific functionality that we present here. Apart from being a warm-up before delving into more advanced primitives, this shows that DDFE is not fundamentally restricted to secret-key primitives.

Public-Key Encryption. Here, the message space M = {0, 1} * × PK comprises pairs of plaintext and public keys. The key space is restricted to the identity function over the plaintexts: {f id }. The functionality takes as input the list of pairs (pk, m pk ) from all senders pk ∈ U M . In our case, the list U M will contain only one user pk 1 who wishes to send the plaintext pt ∈ {0, 1} * to user pk 2 . This information is contained in the message m pk 1 = (pt, pk 2 ).

The functionality also takes the list of pairs (pk, k pk ) from all receivers pk ∈ U K . In our case, the list U K only contains the recipient pk 2 . The associated key space object is the identity function f id , which is the only function available here.

The functionality outputs the plaintext if the intended recipient is the actual recipient. That is F (pk 2 , f id ), (pk 1 , (pt, pk 2 )) = pt if pk 2 = pk 2 , ⊥ otherwise. On any input that does not have that format (for instance on lists U M and U K of more than one element), the functionality will also output ⊥.

The above example can be generalized straightforwardly to capture single-input Functional Encryption [BSW11], by considering a larger key space {f } that is not only restricted to the identity function.

Decentralized Attribute-Based Encryption. The notion of DDFE can also capture existing decentralized primitives, such as the notion of decentralized Attribute-Based Encryption introduced in [LW11], as shown below. It also captures the more general Multi-Authority Functional Encryption [CGJS15].

Here, the message space M = {0, 1} * × P × L(PK) comprises tuples, each of which contains a plaintext, a predicate, and a list of public keys. The key space K = A × ID comprises pairs of an attribute and an identifier.

The functionality takes as input the list of pairs (pk, m pk ) from all senders pk ∈ U M . In our case, the list U M will contain only one user pk who wishes to send the plaintext pt ∈ {0, 1} * to any user with proper credentials, that is, whose attributes satisfy an access policy expressed by a predicate P ∈ P. This predicate takes as inputs attributes that are handled by different authorities, listed in U. All of this information is contained in the message m pk = (pt, P, U).

The functionality also takes the list of pairs (pk, k pk ) from all receivers pk ∈ U K . In our case, the list U K contains the authorities involved. For each authority, the associated key space object is an attribute, and a global identifier.

The functionality is defined as

F (pk i , (att i , GID i )) pk i ∈U K , (pk, (pt, P, U)) = pt if U = U K ,
all the identifiers GID i are the same, and the predicate P on the attributes att i evaluates to true. If these conditions are not met, or if the input does not have the right syntax (e.g. the list U M has more than one element), the functionality outputs ⊥.

Ad Hoc Multi-Input FE. We now show that DDFE captures more advanced decentralized primitives, such as Ad Hoc Multi-Input FE, introduced in [ACF + 20].

Here, the message space M = {0, 1} * , the key space K comprises pairs (f, U) where f : {0, 1} → {0, 1} * is an -ary function for arbitrary ∈ N, and U is a list of users.

The functionality takes as input the list of pairs (pk, m pk ) from all senders pk ∈ U M , and the list of pairs (pk, k pk ) from all receivers pk ∈ U K . If all the key space objects agree on a function on the inputs of the list of users U M , the functionality outputs the evaluation of the function:

F (pk i , (f i , U i )) pk i ∈U K , (pk j , m j ) pk j ∈U M = f (m 1 , . . . , m ) if f i = f and U i = U M for all i, and |U M | = . It outputs ⊥ otherwise.
Limitations of DDFE. Whereas the notion of DDFE is a strong generalization of preexisting decentralized variants of Functional Encryption, capturing functionalities not covered by Ad Hoc MIFE or MAFE, it does not cover everything. Function Private [BS15] and Delegatable [CGJS15] variants of Functional Encryption have been introduced, and our definitions leave room for similar variants of DDFE. Some important cryptographic protocols, such as Private Information Retrieval, Oblivious Pseudo Random Functions, or Non-Interactive Key Exchange, similarly cannot be written as DDFE functionalities. DDFE fails to capture key exchange because its definition doesn't allow us to express cryptographic properties of a function evaluation: the idea that the result of an evaluation would "look random" cannot be written as a functionality. It also cannot capture the aforementioned two party interactive protocols because it is non-interactive by nature, while interactivity is a core requirement for PIR and OPRFs, to ensure the protocol is not run more times than any party whishes for.

DDFE Functionalities

We now give some examples of concrete functionalities. The first two will be of independent interest, but also layers to improve the security and the functionalities of the later Inner-Product DDFE constructions.

All-or-Nothing Encapsulation (AoNE) allows several parties of a group to encapsulate individual messages, that can all be extracted by anybody if and only if all the parties of this group have sent their contributions. Otherwise, the messages remain hidden. The set U M of public keys describes the group of parties and the label imposes a constraint on which encapsulations can be considered together: if for a given pair (U M , ) all the parties in U M send their encapsulations, all the messages can be recovered by anybody, otherwise the messages remain hidden. Note that all the players have to agree on the pair (U M , ) for their encapsulation, and any encapsulation naturally leaks that pair (U M , ).

Definition 6 (All-or-Nothing Encapsulation). AoNE is defined on messages of length L as follows:

K = ∅ M = {0, 1} L × S(PK) × {0, 1} * .
Then, F ( , (pk, (x, U, ))) = (U, ) and

F ( , (pk, m pk ) pk∈U M ) = (pk, x pk ) pk∈U M if condition (*) ⊥ otherwise.
and AoNE condition (*) is:

∃ ∈ {0, 1} * , ∀pk ∈ U M , m pk = (x pk , U M , ).
Decentralized Sum (DSum) allows several parties of a group to commit to values, so that their sum is automatically revealed when all the parties of this group have sent their contributions. Otherwise, the values remain hidden. The set U M of public keys describes the group of parties and the label imposes a constraint on which values can be added together: if for a given pair (U M , ) all the parties in U M send their values, the sum can be recovered by anybody, otherwise the individual values remain hidden.

As above, all the players have to agree on the pair (U M , ) for their encryption, and any encryption naturally leaks that pair (U M , ). The terminology sum is an abuse, as it works for any Abelian group.

Definition 7 ((A, +)-Decentralized Sum). DSum is defined for any Abelian group (A, +) as follows:

K = ∅ M = A × S(PK) × {0, 1} * .
Then, F ( , (pk, (x, U, ))) = (U, ) and

F ( , (pk, m pk ) pk∈U M ) = pk∈U M x pk if condition (*) ⊥ otherwise. and DSum condition (*) is: ∃ ∈ {0, 1} * , ∀pk ∈ U M , m pk = (x pk , U M , ).
Inner-Product DDFE (IP-DDFE). We now present a more advanced functionality for Inner Products.

It allows senders with public key pk, as part of a group U M , to encrypt inputs x pk under a label . But they maintain control on which computations will be performed on their inputs, as they all have to agree on the weights y pk to produce the functional decryption key that allows the inner-product. The set U M of public keys describes the group of parties and the label imposes a constraint on which values can be aggregated together, the set U K of public keys describes the support of the inner-product, and (y pk ) pk specifies the weights. If U M = U K and all the ciphertexts are provided (by all the senders on the same pair (U M , )), with the appropriate functional decryption key (with the same (U K , (y pk ) pk ), one can get the inner-product value, otherwise the individual values remain hidden. As above, all the players have to agree on the pair (U M , ) for their encryption, and any encryption naturally leaks that pair (U M , ). Similarly, all the players have to agree on (U K , (y pk ) pk ) for the functional decryption key, otherwise they are useless.

Because our construction is based on prime-order groups, we need to impose a bound on the messages and the keys to guarantee that we can perform the discrete logarithm efficiently and recover the result of the functional evaluation in polynomial time.

Definition 8 (Inner-Product DDFE.). IP-DDFE is defined for a dimension d ∈ N and a bound B ∈ N, and the sets U M and U K must perfectly match:

K = {(y pk , pk) pk∈U K where y pk ∈ [-B, B] d and U K ∈ S(PK)} M = [-B, B] d × S(PK) × {0, 1} * .
Then, F ( , (pk, (x, U, ))) = (U, ) and

F ((pk, k pk ) pk∈U K , (pk, m pk ) pk∈U M ) = pk∈U K x pk y pk if condition (*) ⊥ otherwise.
and IP-DDFE condition (*) is:

-U K = U M -∃(y pk ) pk∈U K ∈ S([-B, B] d ), ∀pk ∈ U K , k pk = (y pk , pk) pk∈U K -∃ ∈ {0, 1} * ,∀pk ∈ U K , m pk = (x pk , U M , )
We stress that in all the above definition, F should always be understood to be equal to ⊥ on inputs on which it was not explicitly defined above.

Notations and Assumptions

Groups

Prime Order Groups. We use a prime-order group generator GGen, a probabilistic polynomial time (PPT) algorithm that on input the security parameter 1 λ returns a description G = (G, p, P ) of an additive cyclic group G of order p for a 2λ-bit prime p, whose generator is P .

We use implicit representations of group elements as introduced in [EHK + 13]. For a ∈ Z p , define We will always use this implicit notation of elements in G, i.e., we let

[a] ∈ G be an element in G. Note that from a random [a] ∈ G, it is generally hard to compute the value a (discrete logarithm problem in G). Obviously, given [a], [b] ∈ G and a scalar x ∈ Z p , one can efficiently compute [ax] ∈ G and [a + b] = [a] + [b] ∈ G.
Pairing-Friendly Groups. We also use a pairing-friendly group generator PGGen, a PPT algorithm that on input 1 λ returns PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e), a description of asymmetric pairing-friendly groups where G 1 , G 2 , G T are additive cyclic groups of order p for a 2λ-bit prime p, P 1 and P 2 are generators of G 1 and G 2 , respectively, and e : G 1 × G 2 → G T is an efficiently computable (nondegenerate) bilinear map. Define P T := e(P 1 , P 2 ), which is a generator of G T . We again use implicit representation of group elements. For s ∈ {1, 2, T } and a ∈ Z p , define [a] s = aP s ∈ G s as the implicit representation of a in G s . Given [a] 1 , [b] 2 , one can efficiently compute [ab] T using the pairing e. For two matrices A, B with matching dimensions define e(

[A] 1 , [B] 2 ) := [AB] T ∈ G T .

Intractability Assumptions

Definition 9 (Computational Diffie-Hellman Assumption). The CDH assumption states that, in a prime-order group

G $ ← GGen(1 λ ), no PPT adversary can compute [xy], from [x] and [y] for x, y $ ← Z p , with non-negligible success probability. Equivalently, this assumption states it is hard to compute [a 2 ] from [a] for a $ ← Z p . This comes from the fact that 4[xy] = [(x + y) 2 ] -[(x -y) 2 ].
Definition 10 (Decisional Diffie-Hellman Assumption). The DDH assumption states that, in a group G $ ← GGen(1 λ ), no PPT adversary can distinguish between the two following distributions with non-negligible advantage:

{([a], [r], [ar]) | a, r $ ← Z p } and {([a], [r], [s]) | a, r, s $ ← Z p }.
Equivalently, this assumption states it is hard to distinguish, knowing [a], a random element from the span of

[a] for a = ( 1 a ) , from a random element in G 2 : [a] • r = [ar] = ( [r] [ar] ) ≈ ( [r] [s]
) .

Definition 11 (Decisional Bilinear Diffie Hellman Assumption). The DBDH assumption states that, in a pairing group PG $ ← PGGen(1 λ ), for any PPT adversary, the following advantage is negligible, where the probability distribution is over a, b, c, s

$ ← Z p : Adv DBDH PG (A) =| Pr[1 ← A(PG, [a] 1 , [b] 1 , [b] 2 , [c] 2 , [abc] T )] -Pr[1 ← A(PG, [a] 1 , [b] 1 , [b] 2 , [c] 2 , [s] T )]|.
Definition 12 (Q-fold DBDH). For any integer Q, the Q-fold DBDH assumption states for any PPT adversary, the following advantage is negligible, where the probability distribution is over a, b, c i , s i $ ← Z p :

Adv Q-DBDH PG (A) =| Pr[1 ← A(PG, [a] 1 , [b] 1 , [b] 2 , {[c i ] 2 , [abc i ] T } i∈[Q] )] -Pr[1 ← A(PG, [a] 1 , [b] 1 , [b] 2 , {[c i ] 2 , [s i ] T } i∈[Q] )]|.
This Q-fold DBDH assumption is equivalent to classical DBDH assumption:

Lemma 13 (Random Self Reducibility of DBDH). For any adversary A against the Q-fold DBDH, running within time t, there exists an adversary B running within time t + 2Q(t G T + t G 2 ), where t G T and t G 2 denote respectively the time for an exponentiation in G T and G 2 (we only take into account the time for exponentiations here), such that

Adv Q-DBDH PG (A) ≤ Adv DBDH PG (B). Proof. Upon receiving a DBDH challenge (PG, [a] 1 , [b] 1 , [b] 2 , [c] 2 , [s] T ), B samples α i , c i $ ← Z p com- putes [c i ] 2 := [α i • c] 2 + [c i ] 2 , [s i ] T := [α i • s] T + [c i • ab] T for all i ∈ [Q],
and gives the challenge

(PG, [a] 1 , [b] 1 , [b] 2 , {[c i ] 2 , [s i ] T } i∈[Q] ) to A.

Non-Interactive Key Exchange

We give a definition of Non-Interactive Key Exchange below. This a rephrasing of the m-CKS-heavy model (with dishonest key registrations) as originally introduced in [CKS08] and further refined in [FHKP13].

Definition 14 (Non-Interactive Key Exchange). A NIKE scheme consists of three PPT algorithms:

-Setup(λ): Generates and outputs public parameters pp. Those parameters are implicit arguments to all the other algorithms; -KeyGen(): Generates and outputs a party's public key pk ∈ PK and the corresponding secret key sk pk ; -SharedKey(pk, sk pk ): Takes as input a public key and a secret key corresponding to a different public key. Deterministically outputs a shared key K.

Correctness: We require that, for all security parameters λ ∈ N, it holds that:

Pr SharedKey(pk, sk pk ) = SharedKey(pk , sk pk ) = 1,
where the probability is taken over pp ← Setup(λ), (pk, sk pk ) ← KeyGen(), (pk , sk pk ) ← KeyGen(). • If b = 0, the challenger returns SharedKey(pk , sk pk );

• If b = 1, the challenger returns a (uniformly) random value, which it stores so it can consistently answer further queries to QTest(pk, pk ) or QTest(pk , pk) -Corruption queries QCorrupt(pk): Recovers the secret key sk associated to pk from H and outputs it, then removes the key-pair from H. If pk is not associated with any secret key (i.e. it is not in H), then nothing is returned; -Finalize: A provides its guess b on the bit b, and this procedure outputs the result β of the security game, according to the analysis given below which aims at preventing trivial wins.

Finalize outputs the bit β = (b = b) unless a QCorrupt query was made for any public key which was involved in a query to QTest, or a QReveal query was made for a pair of public keys which was also involved in a QTest query, in which case a random bit β is returned. We say NIKE is secure if for any adversary A, the following advantage is negligible:

Adv NIKE (A) = 2 × | Pr[β = 1] -1/2|.
Definition 16 (Static Security Game for NIKE). We define a static variant of the security game above in which the adversary does not have access to the QCorrupt oracle, which means all parties created by the challenger will remain honest, and the only corrupt parties are entirely managed by the adversary.

Definition of Symmetric Key Encryption

A symmetric key encryption SKE = (SEnc, SDec) with key space K is defined as:

-SEnc(K, m): given a key K and a message m, outputs a ciphertext ct; -SDec(K, ct): given a key K and a ciphertext ct, outputs a plaintext.

Correctness. For all m in the message space and all K in the key space, we must have the equality SDec(K, SEnc(K, m)) = m.

Security. We say SKE is secure if for any PPT adversary A, the following advantage is negligible:

Adv SKE (A) = 2 × Pr b = b : K $ ← K, b $ ← {0, 1} b ← A(1 λ ) QLeftRight(•,•) -1 ,
where the oracle QLeftRight, when queried on m 0 , m 1 , returns SEnc(K, m b ).

One-Time Security. We say SKE is One-Time Secure if the above security holds for only one QLeftRightoracle query. Note that if the key space is larger than the message space, on can simply use the one-time pad to build a One-Time Secure symmetric encryption. Otherwise, a pseudo-random generator can stretch the key to the right length.

Single-Input Functional Encryption

For some of our constructions, we will need a instatiations of single-input Functional Encryption (for a specific functionalities). A Functional encryption scheme for a family of functions F consists of the following PPT algorithms:

-KeyGen(λ): on input a security parameter, it outputs a master secret key msk and a public key pk.

-Encrypt(pk, m): outputs a ciphertext ct.

-DKeyGen(msk, f ): on input the master secret key and a function f ∈ F, it outputs a decryption key dk f . -Dec(ct, dk f ): deterministic algorithm that returns a message or a rejection symbol ⊥ if it fails.

Correctness. For any message m, and any function f in the family F, we have: The adversary A has unlimited and adaptive access to the left-right encryption oracle QLeftRight, and to the key generation oracle QDKeyGen. We say FE is IND-secure if for any adversary A,

Pr[Dec(ct, dk f ) = f (m)] = 1,
Adv IND FE (A) = |2 × Pr[β = 1] -1| is negligible.
We can also define a weaker selective variant, where pairs (m 0 , m 1 ) to QLeftRight-queries are known from the beginning.

Identity-Based Encryption. Here we define the functionality that corresponds to Identity-Based Encryption, originally envisioned in [Sha84], and first realized in [BF01, Coc01]. The functionality is described by an identity space I, which can be of exponential size. Each function is described by an identity id ∈ I, and given as input a pair (m, id ) where m is a payload, and id ∈ I is an identity, the function outputs m if id = id , nothing otherwise.

Inner Product Functionality. For any dimension d ∈ N and cyclic group G of prime order p, the inner product functionality corresponds to the set of functions described by a vector y ∈ Z d p that on input a vector [x] ∈ G d , outputs [x y]. FE schemes for the inner-product functionality were originally introduced in [ABDP15], later in [ALS16] with adaptive security.

We will make use of the following property, satisfied by several FE schemes, including [ABDP15, ALS16]. For concreteness we recall the scheme from [ALS16] in Appendix A.

Property 18 (Linear Homomorphism). An FE scheme for the inner product functionality (IP-FE.Setup, IP-FE.Encrypt, IP-FE.DKeyGen, IP-FE.Dec) satisfies the linear homomorphism property if there exists a PPT algorithm Add such that for all x, x ∈ Z d p , the following are identically distributed: 4 All-or-Nothing Encapsulation from IBE

IP-FE.

Technical Overview

Our generic construction only requires an IBE. Messages are encrypted under the public key of each member of the group successively, using the set of participants U M and the label as the identity.

The |U M |-layers deep encryption is accompanied by the functional decryption key of the IBE for the encrypting participant and the same identity. The only way to recover the messages is to gather all the decryption keys in order to decrypt all layers of IBE encryption: this requires having access to all the ciphertexts. IBE is a well-studied primitive, which admits constructions from multiple hardness assumptions, including pairings [BF01], LWE [GPV08], or more recently the CDH assumption [DG17]. This directly implies feasability of AoNE from these assumptions. To keep the size of the ciphertext polynomial in the number of users, we use rate-1 IBE, using hybrid encryption. In Section 5 we give a more efficient construction directly from pairings, inspired by the IBE from [BF01].

A Generic Construction of All-or-Nothing Encapsulation

Our construction uses an Identity-Based encryption scheme IBE.

-Setup(λ): Return pp ← IBE.Setup(λ) -KeyGen(): Return (pk, sk pk ) ← IBE.KeyGen().

-Encrypt(sk pk , m): Parse m = (x pk , U M , ) where x pk ∈ {0, 1} L , U M ∈ S(PK), and ∈ {0,

1} * . If pk / ∈ U M , return ⊥. Let n = |U M | be the cardinal of U M ,
and, for some universally accepted order, number the elements in U M as U M = {pk 1 , . . . , pk n }. Let α pk,0 = x pk , and for i going from 1 to n, compute

α pk,i := IBE.Encrypt(pk i , (α pk,i-1 , U M || )).
We write α pk,U M , = α pk,n Compute γ pk,U M , = IBE.DKeyGen(sk pk , U M || ). Return (α pk,U M , , γ pk,U M , , U M , ).

-DKeyGen(sk, k): There are no keys in this functionality, so no DKeyGen; -Decrypt( , (ct pk ) pk∈U M ): Parse the ciphertexts, for all pk ∈ U M , as

ct pk = (α pk,U M , , γ pk,U M , , U M , ),
with common (U M , ) (otherwise return ⊥). For each pk ∈ U M , we recover x pk as follows: with U M = {pk 1 , . . . , pk n }, recompute the α pk,i for i going from n to 0 as α pk,n = α pk,U M , and α pk,i = IBE.Decrypt(γ pk i ,U M , , α pk,i+1 ). Output (pk, x pk ) pk∈U M .

Correctness: Correctness follows immediately from the correctness of IBE.

Remark 19 (Rate-1 IBE). To avoid ciphertexts having length exponential in |U M |, we require that IBE has rate-1 encryption. That is, the ciphertext has the same size as the plaintext plus a polynomial in the security parameter. This can be obtained generically via hybrid encryption: the IBE is used to encrypt a symmetric key, that is used to encrypt the actual message. Assuming such properties of the IBE scheme, our ciphertexts have length linear in |U M |.

Remark 20. The astute reader will have noticed that the γ pk,U M , seem to be playing the role of a Functional Decryption Key. Indeed, AoNE could have been defined with keys allowing decryption of the ciphertext if the appropriate key shares (i.e., for that pair (U M , )) are contributed by all parties. However, our applications of AoNE are such that we would always end up giving out the key share with the corresponding ciphertext, so we gave a definition which is more practical for our uses and may allow constructions in settings where the alternative with keys would be harder to design.

Remark 21. Note that while we show here how to construct AoNE from IBE, it's also possible to construct IBE from AoNE. A possible construction uses only two AoNE identities, one of which creates AoNE ciphertexts that serve as IBE ciphertexts, while the other creates AoNE ciphertexts that serve as IBE functional keys. The secret key for the first identity is made public (it is part of the IBE's public key) while that for the latter remains private. Identities are encoded as labels, and groups are always chosen as the pair of identities. Now to recover the message behind a ciphertext, even generated with the known AoNE secret key of the first identity, one needs an AoNE ciphertext from the second identity for the same label/identity, which effectively acts as an IBE secret key.

Security Proof

Theorem 22 (IND-Security of AoNE ). The All-or-Nothing Encapsulation scheme described in Section 4.2 is IND-secure (as per Definition 3) assuming the IBE scheme is IND-secure (as per Definition 17).

The proof can be found in Appendix B.1.

5 All-or-Nothing Encapsulation from Bilinear Maps

Technical Overview

This construction is essentially an instantiation of the generic construction given in Section 4.2 using Boneh and Franklin's IBE [BF01]. However, we make a few optimizations exploiting the structure of the Boneh-Franklin IBE (BF) to achieve short ciphertexts. First, we use the IBE as a Key-Encapsulation Mechanism to generate a symmetric key, which we then use to encrypt the message. Second, we exploit the randomness reusability of El Gamal-like schemes, from which BF benefits, to only commit to a randomness once. The size difference between the message and the ciphertext in BF comes entirely from that commitment to randomness, so sharing it across all encryptions removes the dependence on the size of the set of participants in the size of the ciphertext. We provide a direct security analysis of the resulting scheme in Section 5.3.

A Construction of All-or-Nothing Encapsulation from Bilinear Maps

Our construction uses pairing-friendly groups, a hash function modeled as a random oracle in the security analysis, and a (One-Time Secure) symmetric encryption scheme.

-Setup(λ): Generate PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) $ ← PGGen(1 λ ), a full domain hash function H from {0, 1} * into G 1 , and return pp = (PG, H). For the sake of clarity, for any input x, we will denote H(x) = h x P 1 = [h x ] 1 , where h x is the unknown discrete logarithm.

-KeyGen(): Sample t pk $ ← Z p and return (pk, sk pk ) = ([t pk ] 2 , t pk ).

-Encrypt(sk pk , m): Parse sk pk = t pk ∈ Z p and m = (x pk , U M , ) where x pk ∈ {0, 1} L , U M ∈ S(PK), and ∈ {0,

1} * . If pk / ∈ U M , return ⊥. Otherwise, sample r pk $ ← Z p and compute the symmetric key K pk,U M , as e   H(U M || ), r pk •   pk ∈U M pk     =   h U M || • r pk • pk ∈U M t pk   T ,
and use it to encrypt x pk as c pk = SEnc(K pk,U M , , x pk ). Compute its share S pk,U

M , = t pk •H(U M || ) = [t pk • h U M || ] 1 , and output the ciphertext ct pk = (c pk , [r pk ] 2 , S pk,U M , , U M , ).
-DKeyGen(sk, k): There are no keys in this functionality, so no DKeyGen; -Decrypt( , (ct pk ) pk∈U M ): Parse the ciphertexts, for all pk ∈ U M , as ct pk = (c pk , [r pk ] 2 , S pk,U M , , U M , ), with common (U M , ). For each pk ∈ U M , compute

K pk,U M , = e   pk ∈U M S pk ,U M , , [r pk ] 2   =   h U M || • r pk • pk ∈U M t pk   T
and recover x pk as x pk = SDec(K pk,U M , , c pk ).

Correctness: First, note that the use of K pk,U M , is consistent across Encrypt and Decrypt. Then, the two evaluations correspond to h U M • r pk • pk ∈U M t pk T . Now correctness immediately follows from the correctness of the underlying symmetric encryption scheme.

Remark 23. Note that the sum pk ∈U M S pk ,U M , is common to all ciphertexts for the same pair (U M , ) and can thus be precomputed and reused, such that n messages can be recovered in time O (n).

Security Proof

Theorem 24 (IND-Security of AoNE ). The All-or-Nothing Encapsulation scheme described in Section 5.2 is IND-secure (as per Definition 3) under the DBDH assumption, in the random oracle model.

The proof can be found in Appendix B.2.

6 Decentralized Sum

Technical Overview

The starting point of our construction is the "Sum-of-PRFs" technique used by Chase and Chow [CC09]. The technique aims to enable a set of parties to evaluate local PRFs for a common label , such that the sum of their local PRFs is zero. It relies on shared seeds between each pair of participants, that are computed on-the-fly using Non-Interactive Key Exchange. Those PRFs can then be added to each participant's input, masking the individual contribution but revealing their sum, because adding the masked ciphertexts causes the PRF evaluation to cancel out.

Remarkably, this is not enough to achieve IND security in the DDFE setting. As such, the random mask would be a deterministic function of the set of participants U M and the label . So, repeated QLeftRight queries to the same pair (U M , ) with different messages would enable an adversary to break security, simply by subtracting two ciphertexts associated with the same pair (U M , ) so as to remove the identical masks. This issue can be addressed with a layer of AoNE encryption. Since our AoNE construction is asymmetric and its encryption is randomized, the layer prevents the adversary from combining ciphertexts for the same pair (U M , ) in a meaningful way. Only when all the ciphertexts are revealed can the adversary remove the AoNE layer, and get access to the underlying ciphertexts. In that case however, the information recovered by the adversary is part of the information revealed by the functionality. For instance, the adversary can subtract two deterministic ciphertexts to obtain the different of the underlying messages. This information can also be learnt by subtracting two sums that are revealed by correctness of the scheme. In general, we show that when the AoNE layer can be removed, the Finalize condition imposes sufficient constraints on the adversary's queries that trivial attacks are no longer on the table.

Moreover, the AoNE layer that lets us achieve full IND security, instead of having to settle for sym-IND security, since, as explained, the AoNE is an asymmetric form of encryption.

A Generic Construction of Decentralized Sum DDFE for (A, +)

For our construction, we assume a NIKE scheme NIKE, an All-or-Nothing Encapsulation scheme AoNE for messages of length the size of an element of A, and a PRF family (F K ) K that takes keys from the NIKE and messages from {0, 1} * and outputs pseudo-random elements in A.

- -Encrypt(sk pk , m): Parse m as (x, U M , ), with x ∈ A, U M ∈ S(PK), and ∈ {0, 1} * . Let pk be our encryptor's public key2 . If pk / ∈ U M , then return ⊥. Otherwise, for all pk = (NIKE.pk , AoNE.pk ) ∈ U M such that pk = pk, compute K pk,pk = NIKE.SharedKey(NIKE.sk pk , NIKE.pk ) and r pk,pk ,U M , = F K pk,pk (U M || ). Compute c pk = x + pk <pk r pk,pk ,U M ,pk >pk r pk,pk ,U M , , where the sums are on pk ∈ U M , on which a total ordering is defined. Return

ct pk = (AoNE.Encrypt(AoNE.sk pk , (c pk , U M , )), U M , );
-DKeyGen(sk, k): There are no keys in this functionality, so no DKeyGen; -Decrypt( , (ct pk ) pk∈U M ): Get (c pk ) pk∈U M = AoNE.Decrypt( , (ct pk ) pk∈U M ), and return pk∈U M c pk .

Correctness:

The (c pk ) should be consistent between Encrypt and Decrypt by correctness of AoNE. Besides:

pk∈U M ct pk = pk∈U M   x pk + pk <pk,pk ∈U M r pk,pk ,U M , - pk >pk r pk,pk ,U M ,   = pk∈U M x pk + pk,pk ∈U M pk <pk r pk,pk ,U M , -r pk,pk ,U M , = pk∈U M
x pk by correctness of NIKE.

Security Proof

Theorem 25 (IND-Security of DSum ). The Decentralized Sum scheme described in Section 6.2 is IND-secure (as per Definition 3) so long as NIKE is IND-secure (as per Definition 15) and (F K ) K is a secure PRF family.

The proof can be found in Appendix B.3.

7 Inner-Product DDFE

Technical Overview

Our starting point is Chotard et al.'s Inner-Product MCFE [CDG + 18]: as they do, we use a Random Oracle to generate shared randomness across participants for a given label (in our case a (U M , ) pair). However, their construction has several drawbacks, which we overcome:

1. Their security game requires that if one ciphertext is queried for a label , all such ciphertexts must be queried (for the same label and for all other honest parties). We lift this requirement by protecting ciphertexts with a layer of AoNE.

Their

Encrypt algorithm is a deterministic function of the message and the label , and thus they do not tolerate repeated queries to the same participant for the same label. We address this by adding a layer of IP-FE, which randomizes ciphertexts. IP-FE keys are provided in our KeyGen algorithm, and they are protected by an AoNE layer to ensure ciphertexts can only be decrypted once the all the partial functional decryption keys are present. 3. Their scheme, being MCFE, only works in the context of a fixed group. We show how using a PRF to dynamically generate independent secret keys for different groups removes this constraint. 4. To enable non-interactive generation of functional decryption keys in DMCFE, they introduce pairings, and perform message-related operations in G 1 while key-related operations take place in G 2 . Instead, we use our DSum to enforce proper key aggregation, which simplifies the scheme to a pairing-free group3 . DSum has the added benefit that it is a DDFE functionality and thus non-interactive, meaning our Inner-Product scheme is also non-interactive, while their DMCFE has an interactive setup.

A construction of IP-DDFE

To build our IP-DDFE, we use a cyclic group G of prime order p where DDH holds, a random oracle H : {0, 1} * → G, an single-input FE for the inner product functionality, where each function is described by a vector y ∈ Z d p , and on input a vector

[x] ∈ G d , outputs [x y].
We require that IP-FE is IND secure, and satisfies Property 18. We also use an All-or-Nothing Encapsulation scheme AoNE, a Distributed Sum DSum over (Z p , +), and a PRF family (F K ) K that outputs in Z d p .

- • AoNE keys (AoNE.pk, AoNE.sk pk ) ← AoNE.KeyGen(),

Setup(λ): Generate G = (G, p, P ) $ ← GGen(1 λ ).
• and DSum keys (DSum.pk, DSum.sk pk ) ← DSum.KeyGen(). Set the public key pk = (IP-FE.pk, AoNE.pk, DSum.pk) and the secret key sk pk = (K, IP-FE.sk pk , AoNE.sk, DSum.sk). Return the key pair (pk, sk pk ).

-Encrypt(sk pk , m): Parse m as (x, U M , ), where Then compute s k = pk∈U y T pk s pk,U = DSum.Decrypt( , (d pk,k ) pk∈U ). For all pk ∈ U, compute z pk ∈ G as

x ∈ Z d p , U M ∈ S(PK), ∈ {0, 1} * , s pk,U M = F K (U M ) ∈ Z d p , [h ] = H( ) ∈ G, and
c pk ← IP-FE.Encrypt(IP-FE.sk pk , [x] + s pk,U M • [h ]). Return ct pk = AoNE.Encrypt(AoNE.sk pk , (c pk , (AoNE.pk ) pk ∈U M , "ct"|| )), U M , ; -DKeyGen(sk pk , k): Parse k as (y pk , pk ) pk ∈U K . Compute s pk,U K = F K (U K ) ∈ Z d
) pk ∈U K , (ct pk ) pk∈U M ): If U M = U K return ⊥. Now let U = U M = U K . Let k ∈ K be such that k = k pk for all pk ∈ U. If
z pk ← IP-FE.Decrypt(d pk,k , c pk ). Let ∈ {0, 1} * such that all ct pk for pk ∈ U contain . If there is no such , return ⊥. Otherwise, compute [h ] = H( ) ∈ G and return the discrete logarithm in base [1] of   pk∈U z pk   -s k • [h ].
Correctness: We write s pk,U = F K pk (U). By correctness of AoNE, the use of c pk in Encrypt and in Decrypt is consistent, as well as the use of d pk,k in DKeyGen and Decrypt; By correctness of DSum, we have s k = pk∈U y T pk s pk,U ; By correctness property of IP-FE, we have z pk = [y T pk x pk + y T pk s pk,U h ]. Thus we eventually compute and return the discrete logarithm of

  pk∈U z pk   -s k • [h ] =   pk∈U [y T pk x pk + y T pk s pk,U h ]   -   pk∈U y T pk s pk,U   • [h ] =   pk∈U y T pk x pk + y T pk s pk,U h   -   pk∈U y T pk s pk,U h   =   pk∈U y T pk x pk   7.3 Security Proof
Theorem 26 (sel-sym-IND-Security of our IP-DDFE ). The Inner-Product DDFE scheme described in Section 7.2 is sel-sym-IND-secure (as per Definition 5) under the DDH assumption, assuming IP-FE is sel-IND secure, the AoNE scheme is sel-sym-IND-secure, the DSum scheme is sel-sym-IND-secure, and (F K ) K is a secure PRF family.

The proof can be found in Appendix B.4.

A Single-Input FE for Inner Products

Here we recall the IPFE from [ALS16] on a cyclic group G. Its IND security is proven in [ALS16], under the DDH assumption in G.

-

IP-FE.KeyGen(G, d ∈ N): a $ ← DDH, U $ ← Z d×2 p , pk = ([a], [Ua]), msk = U. Return (pk, msk). -IP-FE.Enc(pk, x ∈ Z d p ): r $ ← Z p , return ar x + Uar ∈ G d+2 .
-IP-FE.DKeyGen(msk, y ∈ Z d p ): return

-U y y ∈ Z d+2 p . -IP-FE.Dec(pk, [c], k): return [c] k ∈ G.

B Security Proofs

B.1 Theorem 22 (IND-Security of AoNE)

The All-or-Nothing Encapsulation scheme described in Section 4.2 is IND-secure (as per Definition 3) assuming the IBE scheme is IND-secure (as per Definition 17).

Proof. Let q p , q c denote (polynomial) upper bounds on the number of adversary queries to the QNewHonest oracle, and the number of unique pairs (U M , ) for which the adversary sends at least one QEncrypt or QLeftRight query, respectively. We define the following games for i ∈ {0, . . . , q c }:

Game G i : The challenger does as specified in Definition 3, except for queries to QLeftRight. Queries to QLeftRight take as arguments a public key pk and two messages m 0 = (x 0 , U M,0 , 0 ) and m 1 = (x 1 , U M,1 , 1 ). Note that by functionality and by description of the scheme, the response reveals U M,b , b , so if the adversary wants to avoid the Finalize condition ignoring its guess, it must have 0 = 1 = and U M,0 = U M,1 = U M . Now let (U M,j , j ) be the j'th such pair queried to QEncrypt or QLeftRight.

In G i , the challenger will respond to QLeftRight queries by encrypting m 0 if i < j and m b otherwise, where b $ ← {0, 1} is the random bit chosen by the challenger.

Note that in G 0 , all challenge ciphertexts contain the left message, while in G qc all challenge ciphertexts contain the right message. Thus we only need to show that G

i-1 ∼ c G i for all i ∈ [q c ]. G i-1 ∼ c G i :
We proceed by contradiction, and, from a PPT adversary A which can distinguish between G i-1 and G i with noticeable advantage, we construct a PPT algorithm B which breaks the IND-security of IBE with noticeable advantage.

B starts playing the IBE IND-security game and gets a public key IBE.pk. We need to choose the participant whose AoNE public key will be AoNE.pk = IBE.pk carefully, because we wont be able to answer QDKeyGen requests for them. The key is to notice that if the adversary is going to distinguish between G i-1 and G i , the two need to be different, meaning the adversary A needs to make at least one query to QLeftRight on (U M,i , i ) with x 0 = x 1 with noticeable probability, and that, conditioned on that event, A retains noticeable advantage. We can thus safely assume that A will make such a query, and abort otherwise. From then on, if it were the case that for every pk ∈ U M , the adversary either makes a QEncrypt or QLeftRight query on (U M , ) or pk is eventually not honest4 , then the condition in the Finalize part of the security game (see Definition 3) would notice that x 0 = x 1 and set the adversary's guess at random, rendering the adversary's efforts fruitless. We can thus safely assume that there is a pk * ∈ U M such that pk * will be created via QNewHonest5 , and the adversary will not query QEncrypt or QLeftRight on (U M , ) for pk * or query QCorrupt on pk * .

We proceed by guessing which query to QNewHonest will eventually be pk * . We cannot simply guess a member of U M because we do not know anything about U M during the initialization phase of the game, and by the time the ith (U M , ) pair is queried, it is possible that many queries have been made to the QNewHonest oracle, and at that point it would be too late to embed the IBE public key in the adversary's view. Instead, we guess the index t * ∈ [q p ] of the query to QNewHonest which eventually yields a public key pk t * which we hope matches pk * . At that index, we respond with pk t * = IBE.pk. Because the adversary will only make polynomially many queries to QNewHonest, our advantage is only polynomially degraded by this guess and the reduction remains valid.

Having done this, we can naturally answer most queries involving pk t * by using the oracles of the IND security game of IBE and the fact that our IBE is public key. That is, we answer all QEncrypt and most (see below) QLeftRight queries by running IBE.Encrypt ourselves and making IBE.QDKeyGen queries.

The exceptions are QLeftRight queries to any pk ∈ U M for (U M , ). Let n = |U M | and ζ ∈ [n] be such that pk * is the ζth public key in U M for the universally agreed upon order. In responding to QLeftRight(pk, (x 0 , U M , ), (x 1 , U M , )), we will compute two sequences of α's as follows:

for s ∈ {0, 1}, k ∈ [ζ -1], let α s pk,0 = x s and α pk,k = IBE.Encrypt(pk k , (α pk,k-1 , U M || )). Now compute α pk,ζ = IBE.QLeftRight((α 0 pk,ζ-1 , U M || ), (α 1 pk,ζ-1 , U M || ))
, and compute the rest of the α's and the resulting ciphertext as per AoNE.Encrypt.

When IBE.b = 0, the adversary A is playing G i-1 . When IBE.b = 1, the adversary A is playing G i . We only need to check that we do not violate the Finalize condition of the IBE IND-security game. But this is clear because the only IBE.QLeftRight query we make is for (U M , ), and for that pair we never get a AoNE.QLeftRight or AoNE.QEncrypt query so we never make an IBE.QDKeyGen query. This concludes our proof.

B.2 Theorem 24 (IND-Security of AoNE)

The All-or-Nothing Encapsulation scheme described in Section 5.2 is IND-secure (as per Definition 3) under the DBDH assumption, in the random oracle model.

(see Definition 3) would notice that x 0 = x 1 and set the adversary's guess at random, rendering the adversary's efforts fruitless. We can thus safely assume that there is a pk * ∈ U M such that pk * will be created via QNewHonest, and the adversary will not query QEncrypt or QLeftRight on (U M , ) for pk * or query QCorrupt on pk * .

We proceed by guessing which query to QNewHonest will eventually be pk * . We cannot simply guess a member of U M because we do not know anything about U M during the initialization phase of the game, and by the time the ith query to the Random Oracle is made, it is possible that many queries have been made to the QNewHonest oracle, and at that point it would be too late to embed the DBDH challenge in the adversary's view. Instead, we guess the index j * ∈ [q p ] of the query to QNewHonest which eventually yields a public key pk j * which we hope matches pk * . At that index, we respond with pk j * = [b] 2 . Because the adversary will only make polynomially many queries to QNewHonest, our advantage is only polynomially degraded by this guess and the reduction remains valid.

Having done this, we can no longer "naturally" respond to QEncrypt or QLeftRight queries for pk j * even on pairs of sets of participants and labels distinct from (U M , ) because we do not know the discrete logarithm of pk j * (its implicit secret key), which we would need to compute S pk,U M , as described in Encrypt. Instead, we sample responses to Random Oracle queries by sampling an element of Z p and raising [1] 1 to that randomness, and store that randomness so we can both give consistent answers to further queries and compute S pk,U M , by raising [b] 1 to the appropriate power. The only exception to that rule is that the ith unique random oracle request will be answered with [a] 1 , and subsequent requests for the same (U M , ) pair will be answered consistently.

During initialization, we set a counter count to 0 and, when encrypting for queries to QLeftRight on (U M , ) such that x 0 = x 1 , we increment it and replace [r pk ] 2 by [c count ] 2 from our q r -fold DBDH tuple and e(H(U M || ), r pk • pk j * ) in the computation of K pk,U M , by [v count ] T from our q r -fold DBDH tuple. We respond to QEncrypt queries (or QLeftRight queries with x 0 = x 1 ) by encrypting honestly with a uniformly sampled r pk ∈ Z p . The target group element e([a] 1 , [b] 2 ) can be raised to the r pk to generate honest ciphertexts; We respond to QCorrupt queries for public keys other than pk j * naturally, since we know the discrete logarithm of the public key. If anything goes wrong with our guesses and we get a query we can't respond to, we guess at random for the q r -fold DBDH game and abort. Now notice that when we get an "honest" q r -fold DBDH tuple, that is v i = abc i for all i ∈ [q r ], the adversary is playing G i,0 . On the other hand, when we are getting a fake tuple and we instead have v i = s i , then the randomness in s i masks any information in the computation of K pk,U M , , causing it to be uniformly random, as it would be in G i,1 . Thus, when A has noticeable advantage against our AoNE, B will have noticeable advantage against q r -fold DBDH, which violates the DBDH assumption. This concludes our proof.

B.3 Theorem 25 (IND-Security of DSum)

The Decentralized Sum scheme described in Section 6.2 is IND-secure (as per Definition 3) so long as NIKE is IND-secure (as per Definition 15) and (F K ) K is a secure PRF family.

Proof. We use a hybrid argument that goes over all the pairs (U M , ) that are contained in QLeftRightqueries. Writing Q the number of such pairs, and ordering these pairs as they are revealed to the experiment, we define for all i ∈ {0, . . . , Q} the game G i as the security game given in Definition 3, except the QLeftRight-queries containing one of the first i'th pairs are always answered with the left challenge message m 0 , as opposed to m b for the chosen random bit b $ ← {0, 1}. Let A be a PPT adversary. For any game G, we write Adv G (A) the advantage of A in the game G. Note that G 0 is the security game defined in Definition 3, whereas Adv G Q (A) = 0, since the adversary's view in G Q does not depend on the random bit b $ ← {0, 1}. Thus, it suffices to show that for all i ∈

[Q], G i-1 ∼ c G i .
We denote by (U M , ) the i'th pair.

We stress that in Definition 3, in case of a QLeftRight-query, we assume the two messages to be distinct, otherwise this is actually equivalent to a QEncrypt-query. This remark will be crucial in the rest of the proof.

We distinguish two cases: Case 1) there exists pk ∈ U M that is output of QNewHonest, never queried to QCorrupt, QLeftRight and QEncrypt are never queried on a query containing pk, U M , . Intuitively, that means the adversary does not get a complete ciphertext for U M , . In that case, we can use the security of AoNE; Case 2) all pk ∈ U M that are output of QNewHonest are either queried to QCorrupt, or part of query containing (U M , ) to QLeftRight or QEncrypt. Intuitively, that means the adversary gets a complete ciphertext for U M , , as it may have generated on its own all the ciphertexts under dishonest keys.

As case 1) is easily dealt with by leveraging the security of AoNE, we now focus on case 2): For all pk ∈ U M , in case of multiple QLeftRight-queries for the same tuple (pk, U M , ), there is a unique value ∆ pk ∈ A such that all QLeftRight-queries of the form pk, (x 0 pk , U M , ), (x 1 pk , U M , ) , they are such that x 0 pk -x b pk = ∆ pk , unless the Finalize procedure outputs a random bit, independent of A's guess. This is because when the ciphertext is complete, the adversary can legitimately decrypt and recover both the sum involving x b pk and x b pk , subtract the two sums, and obtain x b pk -x b pk . Thus, this value must be independent of the random bit b unless the adversary trivially wins the game, i.e. the condition (*) from Definition 1 holds, in which case Finalize outputs a random bit.

Moreover, when a query (pk, (x 0 pk , U M , ), (x 1 pk , U M , )) is sent to QLeftRight, then pk cannot be queried to QCorrupt, unless the Finalize procedure outputs a random bit. Indeed, recall A can legitimately recover a sum involving x b pk , since we are in case 2). If Adv corrupts pk, then it can compute a partial ciphertext for x pk = 0 A , the neutral element of A on (U M , ), use this ciphertext with the other challenge ciphertexts and recover a sum involving x pk = 0. Subtracting the two sums, A recovers the value x b pk , which must not depend on b, unless A trivially wins the game, that is, unless Finalize outputs a random bit. This means x 0 pk = x 1 pk , which is a contradiction, since by definition of the security game, QLeftRight is only queried for different messages -QEncrypt is used otherwise.

Simply put, in case 2), when pk is queried as part of a query containing U M , , the challenger knows pk cannot be queried to QCorrupt. We call such pk explicitly honest. We will make crucial use of that observation in the rest of the proof. If there is no explicitly honest client, that means no queries to QLeftRight containing (U M , ), then G i-1 and G i are clearly the same. Thus, we focus on the case where there are explicitly honest clients.

Note that there must be at least two such explicitly honest clients, unless Finalize outputs a random bit: Suppose (pk, (x 0 pk , U M , ), (x 1 pk , U M , )) is the only explicitly honest query to QLeftRight, then the sum A can legitimately recover depends on the random bit b $ ← {0, 1} chosen by the experiment only in the value x b pk used in the sum. Therefore, it must be the case that x 0 pk = x 1 pk , which is again a contradiction.

The rest of the proof follows a similar strategy than the adaptive security proof of [ABG19, Theorem 3.7] in the context of multi-client inner-product FE. Namely, the challenger cannot simply guess the set of explicitly honest clients, since that would incur an exponential security loss. Instead, it guesses the number κ of explicitly honest clients, and gradually introduces a κ-out-of-κ secret sharing of 0 in the output of QLeftRight-queries on explicitly honest clients. This is done step by step in the proof, so that the reduction has to guess only a pair of explicitly honest clients at each step, which only incurs a polynomial security loss. To prove that G i-1 ∼ c G i in case 2), we introduce the following hybrid games.

Game G i-1 : this game is as G i-1 , except the challenger guesses the number of explicitly honest clients. Writing q pk the number of queries made to QNewHonest, the challenger samples κ $ ← [2, q pk ]. If eventually the challenger realizes the guess was incorrect, it aborts the experiments and outputs a random bit. Otherwise, nothing changes. It is clear that

Adv G i-1 (A) = Adv G i-1 (A) q pk -1
. For all t ∈ [0, κ], we define the following games.

Game G i-1,t : this game is as G i-1 , except that for the first explicitly honest client pk 1 , QLeftRight pk 1 ,

(x 0 pk 1 , (U M , )), (x 1 pk 1 , (U M , ))) uses c pk 1 = x b pk 1 + pk <pk 1 ,pk ∈U M r pk 1 ,pk ,U M , - pk >pk 1 ,pk ∈U M r pk 1 ,pk ,U M , - j∈[2,t] u j ,
where u j $ ← A for all j ∈ [t]. Similarly, for the ρ'th honest client pk ρ with 1 < ρ ≤ t, QLeftRight pk ρ , (x 0 pk ρ , (U M , )), (x 1 pk ρ , (U M , ))) uses

c pk ρ = x b pk ρ + pk <pk ρ ,pk ∈U M r pk ρ ,pk ,U M , - pk >pk ρ ,pk ∈U M r pk ρ ,pk ,U M , + u ρ .
The changes from G i-1 are highlighted in gray. It is clear that G i-1,0 is the same as G i-1 . To transition from G i-1,0 to G i-1,2 , the challenger first guesses the first and the second explicitly honest clients, denoted pk 1 and pk 2 , respectively. If the guess is incorrect, the challenger aborts and return a random bit. This incurs a security loss of q pk (q pk -1) 2

. Then the challenger uses the security of the NIKE to switch the K pk 1 ,pk 2 to uniformly random. Then it uses the security of the PRF to switch the values r pk 1 ,pk 2 ,U M , to uniformly random over A. Since this value appears positively and negatively in the values c pk 1 and c pk 2 used by QLeftRight, we can add the offset -u 2 to c pk 1 and u 2 to c pk 2 , as in game G i-1,2 . Then, we switch back the value r pk 1 ,pk 2 ,U M , from truly random to pseudo-random, and the key K pk 1 ,pk 2 to pseudo random, using the security of the PRF and the NIKE, respectively. Note that these security notions can only be used when the guess on pk 1 , pk 2 is correct, which is sufficient-when the guess is incorrect, the challenger outputs a random bit anyway, regardless of the adversary's behavior.

We now show how to transition from G i-1,t-1 to G i-1,t for all t ∈ [3, κ]. It is similar to the transition from G i-1,0 to G i-1,2 . Namely, the challenger guesses the first and the t'th honest clients. If the guess is unsuccessful, the challenger aborts and outputs a random bit. As before, this incurs a security loss of q pk (q pk -1) 2

. Then the challenger uses the security of the NIKE to switch the K pk 1 ,pk t to uniformly random, the security of the PRF to switch the values r pk 1 ,pk t ,U M , to uniformly random over A. Since this value appears positively and negatively in the values c pk 1 and c pk t used by QLeftRight, we can add the offset -u t to c pk 1 , which becomes:

x b pk 1 + pk <pk 1 ,pk ∈U M r pk 1 ,pk ,U M , - pk >pk 1 ,pk ∈U M r pk 1 ,pk ,U M , - j∈[2,t-1]
u j -u t and u t to c pk t , which becomes:

x b pk t + pk <pk t ,pk ∈U M r pk t ,pk ,U M , - pk >pk t ,pk ∈U M r pk t ,pk ,U M , + u t ,
as in game G i-1,t (changes from G i-1,t-1 are highlighted in gray). Then, we switch back the value r pk 1 ,pk t ,U M , from truly random to pseudo-random, and the key K pk 1 ,pk t to pseudo-random, using the security of the PRF and the NIKE, respectively. Now, we show that the game G i-1,κ is identically distributed to G i , using the fact that the following are identically distributed:

{u t } t∈[2,κ] and {u t + ∆ pk t } t∈[2,κ] ,
where u t $ ← A for all t ∈ [2, κ]. The leftmost distribution corresponds to G i-1,κ , whereas the right most distribution corresponds to G i . To see this, note that for all t ∈ [2, κ], we have x b pk t + ∆ pk t = x 0 pk t , even in case of multiple QLeftRight-queries for the same tuple (pk t , U M , ). Moreover, by definition of the security game, we know that t∈[κ] x 0 pk t = t∈[κ] x 1 pk t unless Finalize outputs a random bit. This implies t∈ [2,κ]

∆ pk t + ∆ pk 1 = 0. Thus, x b pk 1 -t∈[2,κ] ∆ pk t = x b pk 1 -∆ pk 1 = x 0 pk 1 . This concludes the proof that G i-1 ∼ c G i , therefore, G i-1 ∼ c G i . G 0 ∼ c G 1 :
This transition rests on the security of the PRF. It requires going through multiple hybrid games, and for brevity we only describe the process at a high-level. We successively switch the way each honest participant (created by QNewHonest and not queried to QCorrupt) computes its s pk,U for all U (one honest participant at a time, all of the participant's U's at a time) from being honestly computed to being sampled uniformly at random in Z d p , with one hybrid game per successive participant. If at any point, an adversary can tell the difference between two successive games with noticeable advantage, it's easy to convert this into an algorithm which distinguishes PRF outputs from real randomness with noticeable advantage, which contradicts the security claim of the PRF. The Hybrid Lemma allows us to conclude.

G 1 ∼ c G 2 : We proceed by contradiction. From a PPT adversary A which distinguishes between G 1 and G 2 with noticeable probability, we build B which wins the sel-sym-IND security game of DSum as follows: use the oracles of the DSum challenger to naturally handle all DSum related operations in the IP-DDFE challenger. The exceptions are QDKeyGen queries: for those, write lq = (y T pk s pk,U K , (DSum.pk ) pk ∈U K , k) and rq = (v, (DSum.pk ) pk ∈U K , k) where v = hc = pk∈HS y T pk s pk if this is the last honest participant that remained to be queried for this set U K (for some ordering on the participants), otherwise v = 0. Then make a query DSum.QLeftRight for that public key with left ciphertext lq and right ciphertext rq. When DSum.b = 0, A is playing G 1 . When DSum.b = 1, A is playing G 2 . Because we use k as a label and we chose our challenges in such a way that the sums on the left always equal the sums on the right, we never trigger the DSum's Finalize conditions. This concludes this transition.

G 2 ∼ c G 3 : We proceed by contradiction. From a PPT adversary A which distinguishes between G 2 and G 3 with noticeable probability, we build B which wins the sel-sym-IND security game of AoNE as follows: use the oracles of the AoNE challenger to naturally handle all AoNE related operations in the IP-DDFE challenger. The exceptions are QDKeyGen queries: for those, write lq = IP-FE.DKeyGen(IP-FE.sk pk , y pk ) and rq = lq if that query is complete, rq = 0 otherwise. Then make a query AoNE.QLeftRight for that public key with left ciphertext lq and right ciphertext rq. When AoNE.b = 0, A is playing G 2 . When AoNE.b = 1, A is playing G 3 . Because we use k as a label (with the "key" prefix isolating this from encryption related queries) and we chose our challenges in such a way that the contents differ only when we know a complete request won't be made, we never trigger the AoNE's Finalize conditions. This concludes this transition.

G 3 ∼ c G 4 : We proceed by contradiction. From a PPT adversary A which distinguishes between G 3 and G 4 with noticeable probability, we build B which wins the sel-sym-IND security game of AoNE as follows: use the oracles of the AoNE challenger to naturally handle all AoNE related operations in the IP-DDFE challenger. The exceptions are QEncrypt and QLeftRight queries: for those, write lq = c pk and rq = c pk if that query is complete, rq = 0 otherwise. Then make a query AoNE.QLeftRight for that public key with left ciphertext lq and right ciphertext rq. When AoNE.b = 0, A is playing G 3 . When AoNE.b = 1, A is playing G 4 . Because we use U M , as a label (with the "ct" prefix isolating this from key generation related queries) and we chose our challenges in such a way that the contents differ only when we know a complete request won't be made, we never trigger the AoNE's Finalize conditions. This concludes this transition. pk,U M , + s pk,U M h ]), where (x 0 pk,U M , , x 1 pk,U M , ) is the pair of vectors used in the first complete query to QLeftRight containing (pk, U M , ). We do so using a hybrid argument that goes over the pairs (U M , ) used in complete queries to QLeftRight. Denoting q c the number of such pairs, we introduce hybrid games G 4,i-1 for all i ∈ [q c + 1], which answers the first i -1'st pairs as in G 5 , and the last q c -i + 1 pairs as in G 4 . Clearly, G 4,0 is the same as G 4 , and G 4,qc is the same as G 5 . Thus, it suffices to show that for all i ∈ [q c + 1], we have G 4,i-1 ∼ c G 4,i . We prove this in Lemma 27.

G 5 ∼ c G 6 : We will switch the generation of c pk used by QLeftRight on complete queries from Proof. We use the following hybrid games.

G 4,i-1,1 : is as G 4,i-1 , except for all pk that are part of a complete query to QLeftRight that contains (U M,i , i ), QLeftRight answers any query containing pk using c pk = IP-FE.Encrypt IP-FE.pk, [x b pk + s pk,U M,i h i + γh i (x 0 pk,U M,i , i -x b pk,U M,i , i )] , for a γ $ ← Z p (the same γ is used for all outputs). These two games are identically distributed, as can be shown using the fact that the following are identically distributed:

s pk,U M , and s pk,U M , + γ(x 0 pk,U M , -x b pk,U M , ),

where s pk,U M , $ ← Z p . Note that we can use this fact since we are in a selective game, where the challenge x 0 pk,U M , , x b pk,U M , , is chosen before, and thus, independently, of the value s pk,U M , $ ← Z p . The leftmost distribution corresponds to G 4,i-1 , whereas the rightmost distribution corresponds G 4,i-1,1 . This is due to the fact that the extra terms γ(x 0 pk,U M , -x b pk,U M , ) only appears in the outputs of QDKeyGen on complete queries as:

pk ∈U M,i y pk s pk ,U M,i + γ pk ∈U M,i y pk (x 0 pk ,U M,i , i -x b pk ,U M,i , i ) =0 ,
where the sum equals 0 unless the Finalize procedure of the IP-DDFE outputs a random bit. That is, the extra terms actually only appear in the output of QLeftRight on complete queries that contain (U M,i , i ), as defined in G 4,i-1,1 .

G 4,i-1,2 : is as G 4,i-1,1 , except that for all pk that are part of a complete query to QLeftRight that contains (U M,i , i ), QLeftRight answers any query containing pk using c pk = IP-FE.Encrypt IP-FE.pk, [x b pk + s pk,U M,i h i + ω i (x 0 pk,U M,i , i -x b pk,U M,i , i )] , where ω i G 4,i-1,3 : is as G 4,i-1,2 , except that for all pk that are part of a complete query to QLeftRight that contains (U M,i , i ), QLeftRight answers any query containing pk using c pk = IP-FE.Encrypt IP-FE.pk, [x b pk + x 0 pk,U M,i , i -x b pk,U M,i , i + s pk,U M,i h i + ω i (x 0 pk,U M,i , i -x b pk,U M,i , i )] , where ω i $ ← Z p . These two games are identically distributed, as can be shown using the fact that the following are identically distributed:

ω i and ω i + 1,
where ω i $ ← Z p . The leftmost distribution corresponds to G 4,i-1,2 , whereas the rightmost distribution corresponds G 4,i-1,3 . G 4,i-1,4 : is as G 4,i-1,3 , except for all pk that are part of a complete query to QLeftRight that contains (U M,i , i ), QLeftRight answers any query containing pk using c pk = IP-FE.Encrypt IP-FE.pk, [x b pk + x 0 pk,U M,i , i -x b pk,U M,i , i + s pk,U M,i h i + γh i (x 0 pk,U M,i , i -x b pk,U M,i , i )] . This transition is reverse to the transition from G 4,i-1,1 to G 4,i-1,2 . Similarly, it uses the DDH assumption in G.

G 4,i : is as G 4,i-1,4 , except for all pk that are part of a complete query to QLeftRight that contains (U M,i , i ), QLeftRight answers any query containing pk using c pk = IP-FE.Encrypt IP-FE.pk, [x b pk + x 0 pk,U M,i , i -x b pk,U M,i , i + s pk,U M,i h i ] . This transition is reverse to the transition from G 4,i-1 to G 4,i-1,1 . Similarly, it uses the fact that the following are identically distributed: s pk,U M,i , i and s pk,U M,i , i + γ(x 0 pk,U M,i , i -x b pk,U M,i , i ),

where s pk,U M,i , i $ ← Z p . This concludes the proof that G 4,i-1 ∼ c G 4,i .

Remark 28. Note that while we have to prove a symmetric variant of security, our IP-DDFE scheme instantiated with our constructions is not actually symmetric: the asymmetry of the AoNE layer prevents decrypting a lone ciphertext, even with knowledge of the public key. However, once enough queries have been made that a complete ciphertext is available, the AoNE layer can be removed, and the message can now be recovered, meaning the caveat of symmetric security is necessary.

  [a] = aP ∈ G as the implicit representation of a in G. More generally, for a matrix A = (a ij ) ∈ Z n×m p we define [A] as the implicit representation of A in G: [A] :=   a 11 P ... a 1m P a n1 P ... a nm P   ∈ G n×m

  where the probability is taken over (msk, mpk) ← Setup(λ), ct ← Encrypt(msk, m), and dk f ← DKeyGen(msk, f ).Indistinguishability. The security notion is defined by a classical indistinguishability game:Definition 17 (IND-Security Game for FE). Let FE be a functional encryption scheme. No adversary A should be able to win the following security game:-Initialize: runs (msk, mpk) ← Setup(λ), choose a random bit b $ ← {0, 1} and returns mpk to A.-QLeftRight(m 0 , m 1 ): on input two messages (m 0 , m 1 ), returns Enc(msk, m b ).-QDKeyGen(f ): on input a function f ∈ F, returns DKeyGen(msk, f ).-Finalize: from the guess b of A on the bit b, it outputs the bit β = (b = b) unless some f was queried to QDKeyGen and (m 0 , m 1 ) was queried to QLeftRight such that f (m 0 ) = f (m 1 ), in which case it outputs a uniformly random bit β.

  Setup(λ): Run NIKE.pp ← NIKE.Setup(λ), AoNE.pp ← AoNE.Setup(λ), and output pp = (NIKE.pp, AoNE.pp); -KeyGen(): Run the KeyGen algorithms from the NIKE and the AoNE: (NIKE.pk, NIKE.sk pk ) ← NIKE.KeyGen(), (AoNE.pk, AoNE.sk pk ) ← AoNE.KeyGen(), and output the key pair (pk, sk pk ) = ((NIKE.pk, AoNE.pk), (NIKE.sk pk , AoNE.sk pk ));

  Generate a full domain hash function H : {0, 1} * → G. Compute AoNE.pp ← AoNE.Setup(λ) and DSum.pp ← DSum.Setup(λ). Return: pp = (G, H, NIKE.pp, AoNE.pp). -KeyGen(): Sample the keys • a PRF key K, • IP-FE keys (IP-FE.pk, IP-FE.sk pk ) ← IP-FE.KeyGen(G, d),

G 4

 4 ∼ c G 5 : For any complete query (pk, (x 0 pk , U M , ), (x 1 pk , U M , )) to QLeftRight, we switch the value c pk from c pk = IP-FE.Encrypt(IP-FE.pk, [x b pk + s pk,U M h ]) to c pk = IP-FE.Encrypt(IP-FE.pk, [x b pk + x 0 pk,U M ,x b

$←

  Z p . This transition is justified by the DDH assumption in G, which states that([h i ], [γ], [γh i ]) ∼ c ([h i ], [γ], [ω i ]), where ω i $ ← Z p . The leftmost distribution corresponds to G 4,i-1,1 , whereas the rightmost distribution corresponds to G 4,i-1,2 .

  Participant creation queries QNewHonest(): the challenger C runs the KeyGen algorithm (pk, sk pk ) ← KeyGen() to simulate a new participant, stores the association (pk, sk pk ) in the set H of honest keys, and returns pk to the adversary; -Reveal queries QReveal(pk, pk ): Requires that at least one of pk and pk be in H. Without loss of generality assume it is pk. The challenger returns SharedKey(pk , sk pk ); -Test queries QTest(pk, pk ): Requires that both pk and pk were generated via QNewHonest.

Definition 15 (Security Game for NIKE). Let us consider a NIKE scheme. No adversary A should be able to win the following security game against a challenger C, with unlimited and adaptive access to the oracles QNewHonest, QReveal, QTest, and QCorrupt described below: -Initialize: the challenger C runs the setup algorithm pp ← Setup(λ) and chooses a random bit b $ ← {0, 1}. It initializes the set H of honest participants to ∅. It provides pp to the adversary A; -

  p and d pk,k = DSum.Encrypt(DSum.sk pk , (y T pk s pk,U K , (DSum.pk ) pk ∈U K , k)).

	Compute d pk,k = IP-FE.DKeyGen(IP-FE.sk

pk , y pk ) and d pk,k ← AoNE.Encrypt(AoNE.sk pk , (d pk,k , (AoNE.pk ) pk ∈U K , "key"||k)) and return dk pk,k = (d pk,k , d pk,k ); -Decrypt((dk pk ,k pk

  there is no such k return ⊥. Parse dk pk,k as (d pk,k , d pk,k ) for all pk ∈ U. Get (c pk ) pk∈U = AoNE.Decrypt( , (ct pk ) pk∈U ) and (d pk,k ) pk∈U = AoNE.Decrypt( , (d pk,k ) pk∈U ).

Note that this was not true for MCFE as originally defined in [GGG+ 14], as that definition had strictly increasing timestamps for labels. But followup works on MCFE have usually allowed any bitstring to be used as a label, opening the primitive to the possibility of repetitions.

Depending on the details of NIKE and AoNE it may be necessary to explicitly include pk in sk pk to ensure the following check can be performed.

Of course, our DSum and our IP-DDFE themselves use AoNE, which may rely on pairings if instantiated with our construction from Section 5.

Note that here there are two ways for pk to be dishonest: either the adversary has the challenger create pk via QNewHonest and later corrupts it via QCorrupt, or the adversary generates pk on its own.

Note that here, and in subsequent proofs, we implicitly ignore the very real possibility that the adversary sends a query for a set UM for which a later query to QNewHonest generates a pk ∈ UM . Because this happens with negligible probability it is safe to abort when this situation materializes.

Note that here there are two ways for pk to be dishonest: either the adversary has the challenger create pk via QNewHonest and later corrupts it via QCorrupt, or the adversary generates pk on its own.

Acknowledgments.

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud), the European Community's Horizon 2020 Project FENTEC (Grant Agreement no. 780108), the Google PhD fellowship, and the French FUI ANBLIC Project. This work was partially done while the third author was visiting ENS, Paris, and UC Berkeley, California.

Proof. Let q r , q p , and q c denote (polynomial) upper bounds on the number of unique queries sent by the adversary to the Random Oracle (both directly and indirectly through queries to QEncrypt or QLeftRight), the QNewHonest oracle, and the challenge oracle QLeftRight, respectively. We define the following games for i ∈ [q r ]:

Game G i,0 : The challenger plays as does the challenger in Definition 3, except for queries to QLeftRight. Queries to QLeftRight take as arguments a public key pk and two messages m 0 = (x 0 , U M,0 , 0 ) and m 1 = (x 1 , U M,1 , 1 ). Note that by functionality and by description of the scheme, the response reveals U M,b , b , so if the adversary wants to avoid the Finalize condition ignoring its guess, it must have 0 = 1 = and U M,0 = U M,1 = U M . Now let j be such that (U M , ) is the jth unique query to the random oracle. In G i,0 , the challenger will respond to QLeftRight queries by encrypting m 0 if i ≤ j and m 1 otherwise.

Game G i,1 : This game is similar to G i,0 , except for the fact that, using (U M , ) to denote the ith unique query to the Random Oracle, in all QLeftRight queries for (U M , ) such that x 0 = x 1 , the challenger uses an ephemeral random value K to compute c pk = SEnc(K, x 0 ) instead of using K pk,U M , as described in Encrypt.

Game G i,2 : This game is similar to G i,1 , except for the fact that, using (U M , ) to denote the ith unique query to the Random Oracle, in all QLeftRight queries for (U M , ), the challenger will encrypt the right message: c pk = SEnc(K, x 1 ) when x 0 = x 1 and c pk = SEnc(K pk,U M , , x 1 ) otherwise.

Game G i,3 : This game is similar to G i,2 , except for the fact that, using (U M , ) to denote the ith unique query to the Random Oracle, in all QLeftRight queries for (U M , ), the challenger goes back to using an honestly computed K pk,U M , .

Note that in G 1,0 , all challenge ciphertexts contain the left message, while in G qr,3 all challenge ciphertexts contain the right message, and G i,3 = G i+1,0 , for i ∈ [q r -1]. Thus, we need only prove that G 1,0 is computationally indistinguishable from G qr,3 which we do by showing that G i,0 is computationally indistinguishable from G i,3 for all i ∈ [q r ], and then using the Hybrid Lemma. We want to show that

First, G i,1 ∼ c G i,2 follows immediately from the One-Time Security of our symmetric encryption scheme. The challenge is in proving G i,0 ∼ c G i,1 and G i,2 ∼ c G i,3 . The problems are basically the same: they consist in switching between an honestly computed key K pk,U M , and a random key K in one direction or the other, so without loss of generality we focus on proving G i,0 ∼ c G i,1 .

G i,0 ∼ c G i,1 : We proceed by contradiction, and, from a PPT adversary A which can distinguish between G i,0 and G i,1 with noticeable advantage, we construct a PPT algorithm B which breaks the q r -fold DBDH assumption with noticeable advantage. By Lemma 13 this is enough to show that our scheme is secure under DBDH. The core idea of the reduction is to embed the q r -fold DBDH tuple

) in the view of the adversary as follows: [a] 1 will serve as the random oracle response to a query for U M || , [b] 2 will be the public key of a participant in U M , and the c i 's will be the randomnesses used in the encryption (denoted by r pk in our construction).

We need to choose the participant whose public key will be [b] 2 carefully, because its S pk,U M , on a query to QEncrypt or QLeftRight with (U M , ) will be [ab] 1 , which we are unable to compute from the Q-fold DBDH tuple (otherwise we could pair it with [c i ] 2 and trivially break the assumption). The key is to notice that if the adversary is going to distinguish between G i,0 and G i,1 , the two need to be different, meaning the adversary A needs to make at least one query to QLeftRight on (U M , ) with x 0 = x 1 with noticeable probability, and that, conditioned on that event, A retains noticeable advantage. We can thus safely assume that A will make such a query, and abort otherwise. From then on, if it were the case that for every pk ∈ U M , the adversary either makes a QEncrypt or QLeftRight query on (U M , ) or pk is eventually not honest 6 , then the condition in the Finalize part of the security game

B.4 Theorem 26 (sel-sym-IND-Security of our IP-DDFE)

The Inner-Product DDFE scheme described in Section 7.2 is sel-sym-IND-secure (as per Definition 5) under the DDH assumption, assuming IP-FE is sel-IND secure, the AoNE scheme is sel-sym-IND-secure, the DSum scheme is sel-sym-IND-secure, and (F K ) K is a secure PRF family.

Proof. We define the following games:

Game G 0 : The challenger plays as in the sel-sym-IND security game for DDFE.

Game G 1 : In this game, the challenger changes the way s pk,U M and s pk,U K are computed in QEncrypt, QLeftRight and QDKeyGen: they are now sampled uniformly at random from Z d p , and stored for consistency (across subsequent calls to QEncrypt, QLeftRight and QDKeyGen), instead of using the PRF.

Game G 2 : In this game, the challenger changes the way it computes d pk,k when responding to QDKeyGen queries. Writing k = (y pk , pk ) pk ∈U K , the challenger keeps track of which pk ∈ U K have been queried for k, and responds to queries (pk, k) for pk ∈ U K as follows:

-If pk is not the last honest participant in U K for which a query remains to be made for k, then the challenger responds with:

DSum.Encrypt(DSum.sk pk , (0, (DSum.pk ) pk ∈U K , k)).

-Otherwise, if pk is the last honest participant in U K to be queried for k, then, let HS denote the subset of honest participants of U K , compute:

and respond with DSum.Encrypt(DSum.sk pk , (hc, (DSum.pk ) pk ∈U K , k)).

For each k, the challenger will need to memorize the last honest participant in U K queried on k so it can provide consistent responses to later queries.

Game G 3 : In this game, we change the way incomplete queries (pk, k = (y pk , pk ) pk ∈U K ) to QDKeyGen are answered. Such a query is called incomplete if not every pk ∈ U K is part of a query containing k to QDKeyGen. For these queries, QDKeyGen uses the value d pk,k = 0 instead of d pk,k = IP-FE.DKeyGen(IP-FE.sk pk , y pk ).

Game G 4 : In this game, we change the way incomplete queries pk, ([x 0 pk ], U M , ), ([x 1 pk ], U M , ) to QLeftRight are answered. A query is called incomplete if not every pk ∈ U M is part of a query containing (U M , ) to QEncrypt or QLeftRight. In that case QLeftRight uses 0 instead of c pk in the call to AoNE.Encrypt.

Game G 5 : In this game, we change the way complete queries pk, ([x 0 pk ], U M , ), ([x 1 pk ], U M , ) to QLeftRight are answered. A query is called complete if it is not incomplete. We consider repeated complete queries to the same pk, U M , . We denote by [x 0 pk,U M , ], [x 1 pk,U M , ] the pair of vectors used for the first complete query containing pk, U M , . For any complete repeated query pk, ([

pk +s pk,U M h ]) when making the call to AoNE.Encrypt.

Game G 6 : In this game, we change the way complete queries pk, ([x 0 pk ], U M , ), ([x 1 pk ], U M , ) to QLeftRight are answered. For these, QLeftRight uses c pk = IP-FE.Encrypt(IP-FE.sk pk , [x 0 pk +s pk,U M h ]) instead of c pk = IP-FE.Encrypt(IP-FE.sk pk , [x b pk +x 0 pk,U M , -x b pk,U M , +s pk,U M h ]) in the call to AoNE.Encrypt. Note that in this game, the adversary's view does not depend on b anymore.

We now show how to transition from each of those games to the next.

being computed from IP-FE.Encrypt(IP-FE.sk pk ,

, one pk at a time, using a series of hybrid games. Recall that ([x 0 pk,U M , ], [x 1 pk,U M , ]) is the pair of vectors contained in the first complete query to QLeftRight that contains pk, U M , . Let q p denote the number of queries made to QNewHonest. For i ∈ [q p + 1], we define H i as follows: all ciphertexts for pk with index j < i are generated using IP-FE.Encrypt(IP-FE.sk pk , [x b pk + x 0 pk,U M , -x b pk,U M , + s pk,U M h ]), all those for j ≥ i are generated using IP-FE.Encrypt(IP-FE.sk pk , [x 0 pk + s pk,U M h ]). Now we simply need to show that H i ∼ c H i+1 , and we proceed by contradiction. From a PPT adversary A which distinguishes between the current hybrid game and the next one with noticeable probability, we build B which wins the IND security game of IP-FE (see Definition 17). Let pk i denote the participant whose ciphertexts are being switched in this transition. First, note that when a query to QCorrupt is made for pk i , the constraints from the symmetric security game sym-IND (see Definition 4) impose that x 0 pk i ,U M , = x 1 pk i ,U M , and x 0

and the adversary's view does not depend on the game. Thus for A to distinguish between H i and H i+1 with noticeable advantage, it must be that, with noticeable probability, A does not corrupt pk i , and, conditioned on that event, A retains noticeable advantage. B can thus safely assume that A will not corrupt pk i , abort and guess at random otherwise. Now proceed as follows: use the oracles of the IP-FE challenger to naturally handle all IP-FE related operations in the IP-DDFE challenger for participant with public key pk i . The exceptions are QLeftRight queries. For these, write lq

and rq = x 0 pk i -x 0 pk i ,U M , . Then the reduction makes a query to IP-FE.QLeftRight with left ciphertext lq and right ciphertext rq, upon which it receives the ciphertext c pk i . The reduction B computes

The reduction B's queries to its oracle will not trigger the Finalize to output a random bit in the security game for IP-FE, as long as, for any y pk i that is part of a complete query (pk i , k = (y pk , U K = U M ) pk ∈U K ) to QDKeyGen on pk i , we have:

pk i -x b pk i ,U M , ) = y pk i (x 0 pk i -x 0 pk i ,U M , ).

Since (pk i , (x 0 pk i , U M , ), (x 1 pk i , U M , )) is a complete query, we have for all pk ∈ HS \ {pk i }, a query of the form (pk , (x 0 pk , U M , ), (x 1 pk , U M , )) to QLeftRight, or a query of the form (pk , (x 0 pk = x 1 pk , U M , )) to QEncrypt. Thus, the Finalize procedure of the IP-DDFE security game outputs a random bit unless the following holds:

y pk x 0 pk = y pk i x 1 pk i + pk ∈HS\{pk i } y pk x 1 pk , and y pk i x 0 pk i ,U M , + pk ∈HS\{pk i } y pk x 0 pk = y pk i x 1 pk i ,U M , + pk ∈HS\{pk i } y pk x 1 pk , which together imply that y pk i (x b pk i -x b pk i ,U M , ) = y pk i (x 0 pk i -x 0 pk i ,U M , ).

Lemma 27. For all i ∈ [q c + 1], we have G 4,i-1 ∼ c G 4,i .