Michele Et Michele

Celine

Anca Razvan

Jérémy Enfin

Remercie Philippe

Julien Tristan

Keywords: Key Encapsulation Mechanism cryptographie, chiffrement fonctionnel, délégation, multi-utilisateur, décentralisation cryptography, functional encryption, delegation, multi-client, decentralization

Functional encryption is a recent paradigm that generalizes the classical public key encryption. This formalization aims to finely manage both the access control to the encrypted data, and the information revealed by the decryption. This thesis studies possibilities of delegation through these two sides.

First, we deal with a multi-client context: several users provide each one an encryption of personal data, and an entity wishes to extract information from the aggregate of those inputs. Our contribution in this environment consists to provide these clients the possibility to give, or refuse, their consent for such an extraction. To this aim, we describe constructions of multi-client functional encryption. We then formalize several levels of security and provide methods to reach them. Eventually, we decentralize the construction of the functional decryption key, so that one needs the agreement of all clients to get a functional decryption key. All this, in a practical way.

Second, we consider a more specific case where a video content provider wishes to delegate the distribution of his creation, but without revealing it. Our solution is a key encapsulation mechanism, derived from attribute-based encryption, with a particular property. The provider uses it to encapsulate the key of the encrypted stream under several attributes, and provides the encapsulations to the distributor. This "content manager" can then use the property to combine the encapsulations and make a new one under the access policy of his choice.

iii

Résumé

Le chiffrement fonctionnel est un paradigme récent qui généralise le chiffrement à clef publique classique. Cette formalisation a pour objectif de réguler plus finement le contrôle d'accès aux données chiffrées, ainsi que l'information dévoilée par le déchiffrement. Cette thèse étudie des possibilités de délégation au travers de ces deux aspects.

Dans un premier temps, nous travaillons dans un contexte multi-client: plusieurs utilisateurs fournissent chacun une donnée personnelle chiffrée, et une entité souhaite extraire de l'information de ces données. Notre contribution consiste à permettre à ces utilisateurs de donner, ou refuser, leur accord à cette extraction. Pour ce faire, nous décrivons des constructions de chiffrement fonctionnel multi-utilisateur, puis nous definissons plusieurs niveaux de sécurité et fournissons des méthodes pour les atteindre. Enfin, principal objectif de ces travaux, nous décentralisons la fabrication de la clef de déchiffrement, pour qu'une personne souhaitant une clef de déchiffrement ait besoin de l'accord de tous pour l'obtenir. Toutes les instantiations proposées dans ces travaux sont utilisables en pratique.

Dans second temps, nous considérons une autre problématique dans laquelle un producteur de contenu vidéo cherche à déléguer la distribution de sa création, sans la révéler. Notre solution est un mécanisme d'encapsulation de clef, dérivé du chiffrement par attributs, avec une propriété particulière. Ce producteur l'utilise pour encapsuler la clef du flux vidéo sous plusieurs attributs, et fournit les encapsulations au distributeur. Celui-ci peut alors utiliser la propriété pour combiner les encapsulations et en définir les conditions d'accès à sa guise. v vi Nombre de personnes autour de moi ont dû fournir des efforts conséquents pour me supporter ces dernières années. A chacune d'entre elles, j'aimerais prendre le temps d'exprimer mes sincères remerciements pour avoir fait ce qu'ont été ces années de doctorat. Cependant, je me rends compte en écrivant ses lignes du nombre de personnes que cela représente, ma thèse s'étant effectuée à la fois à Paris et Limoges. Aussi, si vous êtes l'une d'entre elles mais que votre nom ne figure pas dans ces pages, je vous prie de m'en excuser.

Mes premiers remerciements vont naturellement à mes deux encadrants, Duong Hieu Phan et David Pointcheval, pour les opportunitées qu'ils m'ont offert au travers de cette thèse, comme celle de travailler sur un thème de recherche que j'ai beaucoup apprécié, l'occasion de rencontrer des gens très intéressants (même si je ne suis pas connu pour ma langue déliée), ou encore d'assister à des conférences à l'étranger. Je les remercie aussi pour leur disponibilité malgré toutes leurs responsabilités, pour leur patience et surtout pour toute l'aide qu'ils m'ont fourni sur bien des plans.

Je remercie Dario Catalano et Benoit Libert pour la relecture de ce mémoire. J'espère que le sujet vous a intéressé, et que la lecture du mémoire n'a pas été trop fastidieuse. Je remercie également Sébastien Canard, Caroline Fontaine et Michel Abdalla d'avoir accepté le rôle d'examinateur pour la soutenance. Et merci aussi Michel pour les remarques de dernière minute, mon anglais reste encore très approximatif malgré ces trois ans de thèse.

Je tiens à remercier toute l'équipe du département informatique de l'ENS, qui m'a très bien accueilli pendant mon stage, et au sein de laquelle j'ai passé quelques moments mémorables durant toute la durée de mon doctorat. Au cours de ces années, cette équipe a beaucoup évolué, mais heureusement, la moitié du temps de travail d'un doctorant consistant à boire du café, la cuisine a très bien rempli le rôle de catalyseur social. Ainsi, je vous remercie pour ces instants caféinés, même si je ne bois personnellement jamais de café.

Introduction

A brief crypto story

Information is the key behind any decision, and it is primordial for conflicting entities to hide it from each other. From the Antiquity, cryptography was used to this aim, mainly to allow several beings, knowing each other, to communicate safely. Thus, most of the techniques used then relate to what we call today symmetric cryptography, a protocol where two trusted parties must share a same secret to communicate each other.

In the nineteenth-twentieth century, with the rise of long distance communication devices, and on the strength of new mathematical tools, military research interest in this science grew up. Among the scientific projections, August Kerchkoffs enunciated the famous principle, which states that the secrecy of an encryption scheme must not depend on the knowledge of the algorithm. The one-time pad was formalized, rotor machines were used in the first world war, their cryptanalysis followed... However, the main goal was still to build complex systems to hide a stream between two entities sharing a secret. Furthermore, the reliability of these systems was not dependent of complex mathematical problems, leaving open the possibility of a potential cryptanalysis.

Our recent era saw the development of an international network that allows real-time communication between the smallest cells of any human organization, the human himself. But in a context where even adversaries are directly connected, how can one really trust someone else? The establishment of this situation created new needs in numerical security, like proven authentication, the possibility to start a secure communication with a totally unknown individual, or the insurance that transmitted messages are not modified. This is where the modern cryptography started to develop, principally through the formalization of public key cryptography.

Public key cryptography regroups protocols that require to publish a key to encrypt/prove/share something. Few examples are the public key encryption, signature and key exchange. Usually, public key encryption is illustrated by a user that provides a second one an open lock while he keeps the key. This lock acts has a public key: the second user utilizes it to hide a message in a box that can be open by the first user only. A signature is a trace of a message that cannot be falsified, but can be verified publicly. And the key exchange allows two individuals to share a common key after several public interactions.

The first practical schemes for these protocols were described after the mid-seventies: the first key exchange in [START_REF] Diffie | New directions in cryptography[END_REF], then signature and public key encryption in [START_REF] Rivest | A method for obtaining digital signature and public-key cryptosystems[END_REF]. They relied on mathematical problems from number theory the authors believed to be hard to break. However, there was no proof that one needs to solve those mathematical problems to violate the security supposedly given by the scheme.

The way for a new methodology of proven security was opened by Shafi Goldwasser and Silvio Micalli in [START_REF] Goldwasser | Probabilistic encryption[END_REF], which proposed a new public key encryption scheme associated to an original proof system for a formalized security model. More generally, it is now a standard that new cryptosystems come with an associated proof, stating that breaking the system implies solving an allegedly hard mathematical problem.

Our context

The Internet is now an exchange surface that allows a free circulation of information. The direct access to different services helps enterprises and institutions to better structure and delegate their tasks and needs. Consequently, new services related to informatics have emerged: some enterprises now rent computational power and storage space. This leads to a situation where clients willingly provide their information to untrusted organisms. This business model was democratized, and the use of external servers for storage or computational work is now referred as Cloud computing. The problem here is, when a source provides personal data, he technically loses control of it, so this "cloudy" context seemingly leaves no place for the user's privacy. The recent history has proven this suspicion was justified. We now know that private and governmental organizations have recorded, shared, sold data without the source's consent for statistics, advertising, spying or political purposes.

These circumstances call for new cryptographic solutions to protect an user unwilling to divulge his data, but also to permit the extraction of information if he allows it. A recent and promising candidate that partially solve this problematic is the fully homomorphic encryption. This primitive is an encryption protocol that allows two operations on the ciphertexts, which acts homomorphically on the corresponding plaintexts; a first instantiation was described in [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. It fits with our problematic in the sense that the server can work on the ciphertext without learning anything on the content. However, the original formalism of fully homomorphic encryption does not permit the server to extract information from the ciphertext after the computation. Also, while it aims to apply generic functions on the input, it is currently not efficient in most of the cases. In this thesis, we focus on an alternative primitive that reformulates the public key encryption: the functional encryption.

Functional encryption

Functional encryption is comparable to public key encryption, except that the key is associated to a function f : for any function f from a class F, a functional decryption key dk f can be computed such that, given any ciphertext c with underlying plaintext x, using dk f , a user can efficiently compute f (x), but does not get any additional information about x.

Mentioned for the first time in [AL10, LOS + 10, OT10], functional encryption was originally aimed to generalize the description of access control in public key encryption, gathering together protocols like Identity-Based Encryption, Inner Product Encryption or Broadcast Encryption. At that time, the definition focused on "all-or-nothing" protocols, where the decryption returns f (x) = x when the user is authorized to decrypt and ⊥ otherwise, and the first constructions considered were attribute-based encryption schemes.

Attribute-based encryption

Attribute-based encryption (ABE) was introduced by Sahai and Waters [START_REF] Sahai | Fuzzy identity-based encryption[END_REF], it is a generalization of some advanced primitives such as identity-based encryption [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF][START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] and broadcast encryption [START_REF] Fiat | Broadcast encryption[END_REF]. It gives a flexible way to define the target group of people who can receive the message: encryption and decryption can be based on the user's attributes. This primitive was further developed by Goyal et al. [START_REF] Goyal | Attributebased encryption for fine-grained access control of encrypted data[END_REF] who introduced two categories of ABE: "ciphertext-policy" attribute-based encryption (CP-ABE) and "key-policy" attribute-based encryption (KP-ABE). In a CP-ABE scheme, the secret key is associated with a set of attributes and the ciphertext is associated with an access policy over the universe of attributes: a user can decrypt a given ciphertext if he holds the attributes that satisfy the access policy underlying the ciphertext. KP-ABE is the dual to CP-ABE in the sense that an access policy is encoded into the users secret key, and a ciphertext is computed with respect to a set of attributes: the ciphertext is decryptable by a user only if the attributes in the ciphertext satisfy the user's access policy.

Over the last few years, there has been a lot of progress in constructing secure and efficient ABE schemes from different assumptions and for different settings [SW05, GPSW06, OSW07, GJPS08, HLR10, ALdP11, OT12, RW13, CCL + 13, GVW13, YAHK14, BGG + 14, KW19], to name a few.

Other classes of function

In parallel, through the articles [O'N10,[START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF], the authors supposed other classes of functions than "all-or-nothing", and generic constructions came with [GVW12,GKP + 13b,GKP + 13a,Wat15,ABSV15,GGG + 14,BGJS16,BKS16]. Unfortunately, they all rely on non standard cryptographic assumptions (indistinguishability obfuscation, multi-linear maps), or offer black-box contributions where the ciphertext's size somehow depends of the number of queried keys. It is more important in practice, and it is an interesting challenge, to build functional encryption for restricted (but concrete) classes of functions, satisfying standard security definitions, under well-understood assumptions.

This was achieved in 2015, with the inner product function family. Abdalla, Bourse, De Caro, and Pointcheval [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] considered the question of building functional encryption for inner product functions. In their paper, they show that inner product functional encryption can be efficiently realized under standard assumptions like the decisional Diffie-Hellman and learning-with-errors assumptions [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], but in a weak security model, named "selective security". Later, Agrawal, Libert and Stehlé [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF] considered "adaptive security" for inner product functional encryption and proposed constructions whose security is based on decisional Diffie-Hellman, learning-with-errors or Paillier's decisional composite residuosity [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] assumptions. Finally, [START_REF] Gay | Functional encryption for quadratic functions, and applications to predicate encryption[END_REF][START_REF] Elisabetta | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF] recently achieved single input functional encryption for quadratic functions. Their work proposes several schemes based either on matrix decisional Diffie Hellman group assumption or on an idealized model called the generic group model.

Multi-user context

Note however that all the above works consider functional encryption schemes on an input from a single source. Whereas the input can be large, like a high-dimensional vector, the basic definition of functional encryption implies that the input data comes from only one party: all the coordinates of the vector are provided by one party, and all are encrypted at the same time. In many practical applications, the data are an aggregation of information coming from different parties that may not trust each other. Especially, in the cloud context, a server stores data from several independent sources (Fig. 1.1).

• • •

Figure 1.1: Clients trustfully leaving their data on a server which can perform analysis. This situation is possible through functional encryption. In this case, the clients provided encrypted data, and the server uses a key that leaks a precise function of the data, and no more.

To handle this, Gordon, Goldwasser et al. [GKL + 13, GGG + 14] introduced both the notions of multi-input and multi-client functional encryption which break down a single input x into an input vector (x 1 , . . . , x n ) where the components are independent. In those primitives, anyone owning a functional decryption key dk f , for an n-ary function f and multiple ciphertexts c 1 = Encrypt(ek 1 , x 1 ), . . . , c n = Encrypt(ek n , x n ) (Encrypt(ek i , x i , i, ) in the multi-client case), can compute f (x 1 , . . . , x n ) but nothing else about the individual x i 's. Multi-input and multi-client functional encryption are similar except that the former presents no notion of ciphertext index or label: an user i can enter x i and encrypt it as c i = Encrypt(ek i , x i ). This means that in the latter, combination of ciphertexts generated for different labels does not give a valid global ciphertext and the adversary learns nothing from it. This little difference has important consequences in the control of the possible evaluations. To give an example, we consider a multi-client protocol where an user possesses one decryption key dk f , and is given two encrypted vectors c 1 , c 2 hiding the values x 1 , x 2 under the labels 1, 2. This user can recover two values f (x 1 ), f (x 2 ) and no more. If we repeat this situation in a multi-input protocol (without labels involved), the user can compute f (x) for any mix x of any coordinate from x 1 , x 2 , respecting the users indexes. We can thus count up to 2 n possible pairs (x, f (x)), n being the size of the vectors. Such an amount of informations can totally reveal the plaintext hidden in c 1 , c 2 , making this simple example a potential and trivial attack. Hence, the adversary is strongly limited on the encryption and key queries it is allowed to ask in the case of multi-input functional encryption.

Numerous applications of multi-input functional encryption have been given in detail in [GGG + 14]. Like the single-input version, multi-input and multi-client schemes first relied on indistinguishability obfuscation or multilinear maps, which we currently do not know how to instantiate under standard cryptographic assumptions. Extending inner product functional encryption to the multi-input setting has proved technically challenging. [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF] builds the first multi-input inner product functional encryption, that is, each input slot encrypts a vector x i ∈ Z m p for some dimension m, each functional decryption key is associated with a vector y, and decryption recovers x, y where x := (

x i • • • x n ), y ∈ Z n•m
p , and n denotes the number of slots, which can be set up arbitrarily. They prove their construction secure under standard assumptions in bilinear groups. Concurrently, [START_REF] Lee | Two-input functional encryption for inner products from bilinear maps[END_REF] build a two-input (i.e. n = 2) functional encryption using similar assumptions in bilinear groups. Very recently, [DOT18, ACF + 18] gave a "function-hiding" multi-input functional encryption for inner products, where the functional decryption keys do not reveal their underlying functions. [ACF + 18] also gives a generic transformation from single to multi-input for inner product functional encryption, which gives the first multi-input constructions whose security rely on decisional Diffie-Hellman, learning-with-errors or decisional composite residuosity.

These works allow extraction of information from the aggregation of data from independent sources. However, they all suppose an entity centralizing all the secrets, at least to make functional decryption keys, leaving users powerless regarding the distribution of such keys, and defenseless against the corruption of this entity. On an other side, they potentially require interactions between the users to set-up the protocol, which is hardly possible in a practical situation involving a large number of users unaware of each other. Also, while it was considered in the original work [GGG + 14], no one seems to handle with the user corruption. Finally, only multi-input functional encryption schemes were proposed to this point, leaving the open challenge to include a time-stamp system present in the multi-client version. All these points were studied in our article [CDG + 18a].

First contribution

For the reason previously detailed about the difference between multi-input and multi-client functional encryption, our work [CDG + 18a] focuses on the multi-client protocol. It introduces the notion of decentralized multi-client functional encryption, in which we decentralize the generation of functional decryption keys among the same clients as the ones that generate the ciphertexts.

A naive way to distribute the ciphertext generation could be to take a functional encryption scheme and to have a trusted party handling the setup and the key generation phases, while the encryption procedure would be left to many clients to execute by secure multi-party computation. This construction has two obvious weaknesses. First, generating any ciphertext potentially requires heavy interactions, with everybody simultaneously online, and the full ciphertext has to be generated at once, with all the components being known at the same time, which is impossible if an user does not answer at the moment. Secondly, the trusted third party reserves the power to recover every client's private data and the choice of the decryption keys to provide, which completely goes against our main goal.

Another idea, which is the one behind our method, is the use of a multi-input/client functional encryption (multi-client in our case) scheme with multi-party computation to build the decryption key. Again, while multi-party computation often requires several interactions, our target is a non-interactive generation of the functional decryption keys (in the Inner-Product case). We avoid this problem, in [CDG + 18a], by using an other multi-client scheme to assemble the key. The encryption of this second scheme then corresponds to the key construction of the first, and necessitates no interaction between the users.

The resulting schemes are the first practical instantiations of multi-client functional encryption scheme, with a label system allowing a finer control of the possible evaluations than the multi-input setting. They are highly practical as their efficiency is comparable to that of the decisional Diffie Hellman based inner product functional encryption scheme from [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF]: a value x i is encrypted as one or two group elements C i , depending of the security level needed. The setup phase, key generation and decryption all take time linear in the number of participants, and encryption takes time linear in the size of its input. Regarding security, two of the three schemes (Section 4.2.3, Section 5.2.1) are adaptive under classical assumptions either in prime order groups or pairing groups, and the last one (Section 4.2.1) is selective.

In addition, we successfully address corruptions of clients, even adaptive ones in the centralized multi-client setting, exploring what Goldwasser et al. [GGG + 14] highlighted as an "interesting direction". Finally, concerning the interactivity, the decentralized multi-client functional encryption scheme we present in Section 5.2 has a key generation protocol that does not require communications between the users. However, those constructions present some restrictions that we briefly describe here. First, when we succeed in decentralizing the decryption key generation, the set-up lose this property, which clearly goes against our objective. Also, the decentralization needs to introduce pairings because of a discrete logarithm computation. A alternative multi-party computation scheme could potentially remove this restriction. Another point is that our schemes do not capture the multi-input case, while the original definition described the multi-client functional encryption as a "multi-input with labels". Last cited, but not the least, the security level is at most an IND * derivative. This means that the schemes are not secure against the event where not all the users provide a encrypted value. Actually there is even a proof that our schemes are vulnerable in such a situation. Since this event is highly probable in a real-life context, we considered this limitation as a major problem.

Scheme Non Interactive SetUp

Non Interactive Encrypt

Non Interactive KeyGen

Second contribution

Our recent work [CDG + 18b] solves most of the previously evoked points. We first deal with the limitation in the security model from [CDG + 18a], that requires complete ciphertexts. Our solution is generic, as this is an additional layer, that is applied to the ciphertexts so that, unless the ciphertext is complete (with all the encrypted components), no information leaks about the individual ciphertexts, and thus on each components. This technique relies on a linear secret sharing scheme, hence the name "secret sharing encapsulation" (Section 6.1). It can also be seen as a decentralized version of "all-or-nothing transforms" from [Riv97, Boy99, CDH + 00]. We propose a concrete instantiation in pairing-friendly groups, under the decisional bilinear Diffie-Hellman problem, in the random oracle model. We stress that this conversion transforms "any" IND * -secure multi-client functional encryption (not necessarily for inner products) into an IND equivalent at constant cost, meaning that it now manages the case where ciphertexts are missing. Our conversion just adds two group elements to individual ciphertexts.

A second part of this contribution deals with the number of encryptions under a same label. In the inner product multi-client functional encryption from [CDG + 18a], the definition only allows to send a unique scalar (vector if we extend the key). Yet, when vectors are input, it makes sense to allow mix-and-match between the inputs. In addition, requiring a unique component per label for each client, while under his responsibility, is a strong limitation. What happens when the client makes a mistake? The Section 6.2 provides a solution specifically for the group based schemes from [CDG + 18a]. Briefly explained, each user adds an inner product functional encryption layer on his encrypted vector. This permits to combine the vectors from different users on one label with respect to the coordinates, and it finally achieves the multi-input mix-and-match functionality on this label.

In Section 5.1, we also propose an efficient decentralized algorithm to generate a sum of private inputs, hence called distributed sum, which can convert an inner product multi-client functional encryption into a decentralized one: this technique is inspired from [START_REF] Kursawe | Privacyfriendly aggregation for the smart-grid[END_REF], and only applies to the functional decryption key generation algorithm, so it is compatible with the other conversions (Fig. 1.3). Namely, this improves on the decentralization from [CDG + 18a] since it does not require pairings, and because no interactions are needed in its set-up, achieving thus a fully decentralized multi-client functional encryption (Fig. 1.2).

Eventually, to maximize the security level, we show how to prove security against chosen ciphertext attacks (noted CCA) generically, simply by adding signatures to ciphertexts for each slot (Section 6.3). This transformation applies to any multi-client scheme that reaches the IND-security level (the ideal one), and is not limited to the inner product functionality. Even though security against chosen ciphertext attacks is the de facto security notion for encryption, the only way to obtain a multi-client functional encryption secure against chosen ciphertext attacks prior to our work consists of applying the generic Naor Yung paradigm [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF], that requires extra assumptions (simulation-sound non interactive zero knowledge arguments), and doubles the ciphertext size. This is true even assuming the random oracle model. In particular, the seminal Fujisaki Okamoto transform [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] is of no help for functional encryption, where decryption only recovers partial information of the plaintext. Here, wtr stands for: "without repetitions", CCA for: "chosen ciphertexts attacks" and IND * is a security level that does not manage the case where an user does not provide a ciphertext, IND being the natural one.

IP-DMCFE

(IND * ) IP-DMCFE (IND) IP-MCFE (IND * ) IP-MCFE (
All the above conversions preserve the efficiency of the underlying multi-client functional encryption. While the secret sharing encapsulation techniques introduce pairings, the two others do not: they only rely on the decisional or even computational Diffie Hellman assumptions, in the standard or random oracle models. But we also stress that our secret sharing encapsulation techniques is constant-size. A concurrent and independent work [ABKW19] also proposes a compiler from IND * -security to IND-security, without pairings, but ciphertext size becomes linear in the number of clients.

To sum up those two works, we develop a practical solution to give someone a right of refusal regarding the exploitation of his data, in a context of mass storage on external platform. These results adequately answer the problematic described in Fig. 1.1 if a server aims to compute weighted means over an aggregated database.

Third contribution

The last work presented in this thesis considers a different question: is it possible to encrypt data such that someone else can choose the final target without seeing the contents? Our article [START_REF] Chotard | Homomorphic-policy attribute-based key encapsulation mechanisms[END_REF] answers this problem positively using the attributebased encryption.

Before explaining our scenario, we recall that attribute-based encryption can be qualified either ciphertext-policy or key-policy (we will note ABE, CP-ABE and KP-ABE), and both consider different situations. In KP-ABE, the encryptor has no control over who has access to the data he encrypts. This is the key-issuer who generates and controls the appropriate keys to grant or deny access to the users. In contrast, in CP-ABE, the encryptor is able to decide who should or should not have access to the data that he encrypts. In the applications we target such as pay-TV, this would mean that the access control is either dynamically managed by the encryptor (with a CP-ABE) or statically managed by the key-issuer (with a KP-ABE), while in real-life a third-party could be in charge of a dynamic policy.

In KP-ABE, the access policy is controlled at the key generation phase, while in CP-ABE, the access policy is controlled at the message encryption phase. We go a step further in this consideration by postponing the management of the access policy to a later phase and show how one can manage the access policies without knowing any secret nor the content of message.

Previous works on CP-ABE consider classical encryption: the encryptor, taking as input an access policy and a message, produces a corresponding ciphertext. The encryptor thus manages both the access policy and the encryption of the original message. This scenario is unavoidable when limiting the access policy as a single atomic attribute characterizing a user's identity (e.g., identity-based encryption) or a target group of users (e.g., identity-based broadcast encryption) because the encryptor needs to know the message to encrypt with the single attribute. However, in the general case, where the access policy is composed from sub-policies via AND and OR operators, the encryption of a message for the whole access policy can be computed from the ciphertexts of the sub-policies, without the knowledge of the original message.

Aiming to this scenario, where a combiner should manage the access policy without knowledge of the original message, we need an additional property in ABE: the homomorphic-policy. This property weakens the security of an ABE when the combiner colludes with legitimate users. However, in our practical application, there is no incentive for the combiner to break the scheme. The combiner is indeed involved in the protocol to improve on the flexibility of the access control, and even if it is corrupted, there is no harm for the system, comparing to the scenario where there is no combiner and everything is managed by a unique authority.

Considering Pay-TV, we can now separate the roles of the content provider and of the manager of the access policies (see Fig. 1.4): the content provider (C) encapsulates the same session key K under each attribute, encrypts the content under this session key K, and provides the encapsulation together with the encrypted content to the manager of the access policies (M ). The latter broadcasts the encrypted content, but according to the access policy, it combines the appropriate encapsulations to produce a unique encapsulation, to be broadcast to the users (the recipients (R)). Each authorized user can decrypt this encapsulation (by owning attributes satisfying the access policy) and get the session key to decrypt the content. All secrets and keys are provided by a security manager (S), a trusted, incorruptible entity. His role is not considered in our work, or is implicitly played by the content provider (C). We can also envisage another case where the entities (C) and (M ) are totally independent. To illustrate this, let us assume the manager (M ) is a service of video conferencing (again referring to Fig. 1.4), and the content provider (C) is a client that asks (A) to organize a meeting with the participants (R). The authorized participants are identified by several attributes. At the moment of the meeting, (C) secretly gives (M ) the encapsulations of the session key K, under the various attributes, so that it can publicly distribute it according to the appropriate policy to the participants. Only the authorized participants get access to the session K and can participate to the meeting. The manager (M ) does not learn any secret information, and cannot eavesdrop the meeting.

As explained in the above context, the homomorphic-policy property is compatible for key encapsulation rather than for encryption. Technically, we thus need to define attribute-based key encapsulation mechanisms (ABKEM) which encapsulate a session key for an access policy. Then, the combination of two encapsulations of the same session key under two sub-policies into an encapsulation for the composed access policy is completed via the homomorphic-policy property: if we have encapsulations of a session key K under two policies p 1 and p 2 , we will be able to produce an encapsulation of the same session key K for the policies p 1 ∨ p 2 and p 1 ∧ p 2 . The achievement of an homomorphic-policy ABKEM is the main contribution of this chapter. But of course, this is important to keep all the initial properties of an ABE scheme, and namely the collusion-resistance of the final encapsulation.

As explained above, our main contribution is the definition and construction of homomorphic-policy attribute-based key encapsulation mechanisms (HP-ABKEM). To this aim, we define properly the homomorphic policy property and ABKEM. We exploit special properties of LSSS for AND and OR operations and transforms them in an efficient way of combining the corresponding encapsulations. We also propose an efficient randomization method for making any ciphertext (possibly obtained from the above combinations) statistically indistinguishable from a fresh ciphertext targeting the same policy, this part is important for the security of the system. Finally, we describe a construction of ABKEM that relies on the Lewko-Waters ABE scheme [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF], which security holds in the random-oracle model. Putting altogether, our final result gives an HP-ABKEM which is as efficient as the Lewko-Waters ABE system. It is interesting that we get the homomorphic-policy property without paying an extra cost. Actually, the final encapsulation after several combinations turns out to be the same as the one the Lewko-Waters sender would have produced, hence the same security level, and namely the collusion-resistance (in the random-oracle model).

Organisation of this thesis

In addition to this introduction, this work is organized in six technical chapters plus the conclusion.

In Chapter 2 we specify some notations used all along this thesis, and we provide classical definitions and mathematical hypothesis needed for the proofs.

Chapter 3 chapter describes precisely the definitions of (decentralized) multi-client functional encryption, and the associated security notions.

Chapter 4 provides several constructions for the previously defined primitive, one theoretical and two others practical. The two last are parts of the results presented in [CDG + 18a].

Chapter 5 describes two constructions of decentralized multi-client functional encryption. The first, generic, is taken from [CDG + 18b], and the second from

[CDG + 18a].
In Chapter 6 we explain how to enhance, in several ways, the security of the schemes described in the previous chapters. All the material of this part are results from the article [CDG + 18b] Chapter 7 is the last technical chapter. It defines and provides a construction of homomorphic-policy attribute-based key encapsulation mechanism. This part gather the contributions of [START_REF] Chotard | Homomorphic-policy attribute-based key encapsulation mechanisms[END_REF].

Finally, the conclusion sum up some open questions, principally about the multiclient functional encryption.

Preliminaries

In this chapter we introduce, in this order, notations, standard cryptographic notions, and the mathematical assumptions needed for our work.

Notations and mathematical notions

Basics

We define the usual sets N, Z and Z N as the natural numbers, integers and the integers modulo N . We denote the vector notation x = (x i ) i . We denote Pr[X = x] the probability for a random variable X to be equal to x, and U n the uniform distribution over {0, 1} n . For any set S, we denote s $ ← S a random element uniformly picked in S. The abbreviation PPT stands for Probabilistic Polynomial Time. A PPT algorithm is running in polynomial time with respect to the input, meaning that it is asymptotically efficient. An oracle is an ideal algorithm which answers any given query, in a black-box way. A random oracle associates and returns uniform randomness to any input. An adversary Adv is an entity that tries to extract informations he is not allowed to get. In security proofs he is formalized as an algorithm, usually PPT. A security parameter, designated by λ in this work, is a value used to adapt the parameters of a cryptographic protocol to the supposed computational power of an adversary.

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

Pairing group

We also use a pairing-friendly group generator PGGen, a PPT algorithm that on input 1 λ returns a description PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) of asymmetric pairing 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 (non-degenerate) 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 , [a] 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 .

Generic cryptography notions

About randomness

Randomness is a crucial element in cryptography for keys, nonces, passwords... However, true randomness is not possible to produce with deterministic algorithms, making it a valuable resource.

Pseudo-random function

This justifies the use of pseudo-randomness, a source indistinguishable from true uniform randomness. In this work (Section 4.1 and Section 5.1.4) we use a pseudo-random function [START_REF] Goldreich | How to construct random functions[END_REF], indistinguishable from a randomly chosen function, because of its reproducibility.

Definition 2.1: Pseudo-Random Function family

Let be F : K × X → Y a family of efficiently computable functions used in the following security game:

• SetUp(λ): takes as input a security parameter λ. The challenger C picks a random bit b $ ← {0, 1}, a random key k $ ← K, and defines f :

x → F (k, x) if b = 0 or f $ ← F X →Y if b = 1.
• Query(x): the adversary A submits a request x to C, who computes and returns the value f (x). A can use this algorithm any polynomial number of time.

• Guess: A concludes this security game by sending C his guess b for the bit b.

A such function family is called Pseudo-Random Function (PRF) family if the following quantity is negligible:

Adv A PRF = P (b = 0|b = 0) -P (b = 0|b = 1)
Among the different possible properties of a pseudo-random function stands the key homomorphism. This property, defined in [START_REF] Boneh | Key homomorphic PRFs and their applications[END_REF], describes the conservation of a structure between the key and output spaces. This property is the main mechanism behind the scheme from Section 4.1.

Definition 2.2: Key-Homomorphic Pseudo-Random Function family

We call Key-Homomorphic Pseudo-Random Function (KH-PRF) family a set of functions F : K × X → Y, where (K, ⊕) and (Y, ⊗) are two groups, with the two following properties:

• F is a PRF. • F (k 1 , x) ⊗ F (k 2 , x) = F (k 1 ⊕ k 2 , x) for all keys k 1 , k 2 ∈ K and values x ∈ X .
Since the Key-Homomorphism only appears as an additional property, the security definition remains the same as the original PRF.

Leftover hash lemma

Another way to produce randomness is through randomness extractors. Those algorithms, given a "low quality" randomness, output a something "statically close" to the uniform distribution. Here is the formal definition of those notions:

• behind the named quality is the min-entropy, defined as the value ME(X) := -log(max x Pr(X = x)), where is X a random variable.

• the statistical distance between two random variables is, given two random variables X, Y , the value SD(X,

Y ) := 1 2 x | Pr[X = x] -Pr[Y = x]| Definition 2

.3: Randomness Extractor

A function Ext : X × {0, 1} n → {0, 1} v is an (m, )-extractor (for space X ), if for all (X, Z) such that X is distributed over X and ME(X|Z) ≥ m, we get SD(Ext(X, S), U v |(S, Z)) ≤ where S ∼ U n denotes the seed of Ext.

The main difference with the usual pseudo-randomness described above is the proximity to real randomness, the statistical distance offered by extractors being stronger than the computational indistinguishability of pseudo-random generators.

The proof of the scheme Section 5.1.5 requires a practical randomness extractor, and mentions the use of the leftover hash lemma. This result from [ILL89, HILL99] mainly states that specific hash functions, the universal hash functions, can be used as randomness extractors:

Definition 2.4: ρ-Universal Hashing

A family H of (deterministic) functions h : X → {0, 1} n is called a ρ-universal hash family (on X ), if for any

x 1 = x 2 ∈ X we have Pr h $ ←H [h(x 1 ) = h(x 2 )] ≤ ρ.
And finally, we recall the Leftover Hash Lemma, following the description from [BDK + 11]:

Theorem 2.1: Leftover Hash Lemma

Assume that the family H of functions h : X → {0, 1} n is a 1+γ 2 n -universal hash family. Then a function Ext(x, h) := h(x), where h $ ← H, is an (m, )-extractor, where = 1 2 γ + 1 2 m-n .

Basic primitives

Symmetric key encryption

Symmetric encryption is one of the most basic cryptographic primitive. It uses the same key for the encryption and the decryption. Since symmetric encryption is a pseudo-random permutation, without an included key derivation algorithm the encryption key can be used only once.

Definition 2.5: Symmetric Key Encryption scheme

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, output a plaintext.

The following must hold:

Correctness. For all m in the message space, Pr[SDec(K, SEnc(K, m)) = m] = 1, where the probability is taken over K $ ← K.

One time security is a formalization of what offers the classical one time pad. It consists of an unique message sent between two parties sharing a same key.

Definition 2.6: One Time Security

For any PPT adversary A, the following advantage is negligible:

Adv OT SKE (A) = 2 × Pr   b = b : (m 0 , m 1 ) ← A(1 λ ) K $ ← K, b $ ← {0, 1}, ct = SEnc(K, m b ) b ← A(ct)    -1 .
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 pseudorandom generator can stretch the key to the right length.

Signature

A signature scheme ensures authenticity and integrity of a message. The signer makes a trace of a message using a secret, which can be publicly verified. Signature schemes may offer several properties (homomorphism, group signature...) and security levels. In this work (more precisely in Section 6.1.4), we use a standard signature scheme, but with a quite strong security: strong unforgeability. Here we provide the definitions of both signature scheme and strong unforgeability: Definition 2.7: Signature Scheme A signature scheme on M is defined by four algorithms:

• SetUp(λ): takes as input the security parameter λ, and outputs the public parameters pp;

• KeyGen(pp): takes as input the public parameters and outputs a pair of signing and verification keys (sk, vk);

• Sign(sk, m): takes as input a signing key sk and a message m ∈ M, and outputs a signature s;

• Verif(vk, m, s): takes as input the verification key vk, a message m and a signature s, and returns either 1 or 0, whether the signature is valid or not.

Strong unforgeability ensures an adversary cannot create a new pair (message, signature) from a set of pairs of his choice. The difference with the weaker existential notion is that it prevents the adversary to make a new signature from a previously queried message, when it originally was considered as a trivial attack.

Definition 2.8: Strong Unforgeability

Let us consider a signature scheme, no adversary A should be able to win the following security game against a challenger C:

• Initialize: the challenger C runs the setup algorithm pp ← SetUp(λ) as well as the key generation algorithm (sk, vk) ← KeyGen(pp), and provides vk to the adversary A;

• Signature queries QSign(m): A has unlimited and adaptive access to the signing oracle, and receives the signature s ← Sign(sk, m). One appends (m, s) to the list Queries;

• Finalize: A provides a pair (m, s). A wins if Verif(vk, m, s) when (m, s) / ∈ Queries.

We say Sign is strongly unforgeable if for any adversary A, the following value is negligible

Adv SUF Sign (A) = Pr    (m, s) ← A QSign , (m, s) / ∈ Queries, Verif(pp, m, s) = 1
• Decaps(sk, E): takes as input a decryption key and an encapsulation E, to output the encapsulated key K or ⊥.

Correctness. For any (sk, pk) ← SetUp(λ) and (K, E) ← Encaps(pk, p), Decaps(sk, E) = K.

Indistinguishability. Security notion very similar to the indisguishability of public key encryption, but here the adversary cannot distinguish between two encapsulated keys instead of messages.

Definition 2.10: IND-security game for KEM

Let us consider an KEM. No adversary A should be able to break the following security game against a challenger:

• Initialization: the challenger runs the setup algorithm to get (msk, pk) ← SetUp(λ), and provides pk to the adversary A;

• Challenge: the challenger runs (K, E) ← Encaps(pk, p), and sets K b ← K and K 1-b as a random key, for a random bit b. It provides (E, K 0 , K 1 ) to the adversary;

• Finalize: the adversary A outputs its guess b on the bit b.

We then define Adv ind (A) = |2 × Pr[b = b] -1|, and say that an KEM is (t, ε)adaptively secure if no adversary A running within time t can get Adv ind (A) ≥ ε.

Secret sharing schemes

For any application with limited access, one needs to define the access structure, which precises which combinations of conditions grant access to the data or to the system.

Definition 2.11: Access Structure

Let P = {P 1 , P 2 , . . . , P m } be a set of parties (human players or attributes). An access structure in P is a collection A ⊆ 2 P \{∅}. The sets in A are called the authorized sets, while the others are called unauthorized sets.

When some minimal sets of parties are required to access the system (but any superset is good too), only monotone access structures make sense, since one can always ignore any supplementary party.

Definition 2.12: Monotone Access Structure

Let P = {P 1 , P 2 , . . . , P m } be a set of parties and A an access structure in P. A is said monotone if, for any subsets

B, C ⊆ P, if B ⊆ C, when B ∈ A then C ∈ A.
In order to control access rights according to a monotone access structure, the use of a secret sharing scheme that spreads the secret key among several players is a classical technique. One must use a secret sharing scheme that just allows authorized sets to reconstruct the secret key. This is even better if the secret key is never fully reconstructed, but just in a virtual way to run the restricted process (such as signature or decryption).

Definition 2.13: Secret Sharing Scheme

A secret sharing scheme over a set of parties P, for an access structure A over P, allows to share a secret s among the players, with shares ν 1 , . . . , ν m such that:

• any set of parties in A can efficiently reconstruct the secret s from their shares;

• any set of parties not in A has no information about the secret s from their shares.

A linear secret sharing scheme is quite appropriate to share a secret key in order to run the restricted process in a distributed way, since many cryptographic primitives have such linear properties.

Definition 2.14: Linear Secret Sharing Scheme

A Linear Secret Sharing Scheme (LSSS) over a field K and a set of parties P is defined by a share-generating matrix A ∈ K m×n and a labeling map ρ : {1, . . . , m} → P according to the access policy A: for any I ⊂ {1, . . . , m}, anyone can efficiently find a vector c ∈ K m with support I such that c t • A = (1, 0, . . . , 0) if and only if ρ(I) ∈ A.

Functional encryption

Functional encryption is the core of this work. In this section we provide its original definition, which we need to understand the scheme from [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] cited in the introduction, and used in Section 6.2. We then give the multi-input version to understand the differences with the multi-client Definition 3.2, also cited in the introduction. And finally we describe the attribute-based encryption, needed for Chapter 7.

The original functional encryption

As mentioned in the introduction, functional encryption originally aims to generalize the public key encryption, covering encryption schemes with different access control, or computation over encrypted data. It works like public key encryption, but returns a function of the key and the message. Public key encryption is thus a specific instantiation of functional encryption with a functionality that returns ⊥ or the message depending of the validity of the key.

Definition 2.15: Functional Encryption

A private-key, single input Functional Encryption (FE) for a family F consists of the following PPT algorithms:

• SetUp(λ): on input a security parameter, it outputs a master secret key msk and a public key mpk. The latter is implicitly input of all other algorithms.

• Encrypt(msk, x): on input the master secret key and a message x, it 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 f (x), if ct is a valid encryption of x, or ⊥ otherwise.

Correctness and security, as defined below, must hold:

Correctness. For any message x, and any function f in the family F, we have:

Pr[Dec(ct, dk f ) = f (x)] = 1
, where the probability is taken over (msk, mpk) ← SetUp(λ), ct ← Encrypt(msk, x), and dk f ← DKeyGen(msk, f ).

Indistinguishability. The security notion is defined by an indistinguishability game. Like the classical public key encryption, the goal is to distinguish the bit hidden in a ciphertext. However, the adversary now is allowed to compute a functionality with functional decryption keys, so this functionality must not trivially reveal this bit:

Definition 2.16: 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(x 0 , x 1 ): on input two messages (x 0 , x 1 ), returns Enc(msk, x b ).

• QDKeyGen(f ): on input a function f ∈ F, returns DKeyGen(msk, f ).

• Finalize: it outputs the guess b of A on the bit b, unless some f was queried to QDKeyGen and (x 0 , x 1 ) was queried to QLeftRight such that f (x 0 ) = f (x 1 ), in which case it outputs a uniformly random bit, independent of A's guess.

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 INDsecure if for any adversary A,

Adv IND FE (A) = | Pr[b = 1|b = 1] -Pr[b = 1|b = 0]| is negligible.

Multi-input functional encryption

Multi-input functional encryption is the first attempt to extend the functional encryption setting to multi-party computation. This protocol, like the original functional encryption, allows the computation of a function over an encrypted input, the difference is that this ciphertext is now an aggregation from several independent sources. In that respect, multi-input functional encryption and multi-client functional encryption (Section 3.1) are very close. Roughly speaking, the latter can be considered as an extension of the former that allows re-usability through labels.

Definition 2.17: Multi-Input Functional Encryption

A private-key, Multi-Input Functional Encryption (MIFE) for a family F over n users consists of the following PPT algorithms:

• SetUp(λ): on input a security parameter, it outputs a master secret key msk, encryption keys (ek i ) i and a public key mpk. The latter is implicitly input of all other algorithms.

• Encrypt(ek i , x i ): on input an encryption key ek i and a message x i , it 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 i ) i∈[n] , dk f ): deterministic algorithm that returns f ( x), if (ct i ) i∈[n] is a valid encryption of x = (x i ) i ∈ M n , or ⊥ otherwise.
Correctness and security, as defined below, must hold:

Correctness. For any vector of messages x, and any function f in the family F, we have:

Pr[Dec((ct i ) i∈[n] , dk f ) = f ( x)] = 1
, where the probability is taken over (msk, (ek i ) i , mpk) ← SetUp(λ), ct ← Encrypt(ek i , x i ), and dk f ← DKeyGen(msk, f ).

Indistinguishability. The security notion is quite the same as functional encryption. But since the ciphertext now comes from several sources, the finalize only considers function of full vectors, and thus incomplete ciphertext must not reveal anything to the adversary. This point makes this definition comparable to our IND-security, defined in Section 6.1.

Definition 2.18: IND-security game for MIFE

Let MIFE be a multi-input 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(x 0 i , x 1 i ): on input two messages (x 0 i , x 1 i ), returns Enc(ek i , x b i ).

• QDKeyGen(f ): on input a function f ∈ F, returns DKeyGen(msk, f ).

• Finalize: it outputs the guess b of A on the bit b, unless some f was queried to QDKeyGen and ( x 0 , x 1 ) was queried to QLeftRight such that f ( x 0 ) = f ( x 1 ), in which case it outputs a uniformly random bit, independent of A's guess.

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 INDsecure if for any adversary A,

Adv IND FE (A) = | Pr[b = 1|b = 1] -Pr[b = 1|b = 0]| is negligible.

Attribute-based encryption

Finally, the last part of our work focuses on a specific use of attribute-based encryption. Like the original public key encryption, it is an all-or-nothing functionality, meaning that the decryption returns either ⊥ or the original message. The specificity here is in the access control management; a predicate P , corresponding to the access policy, and attributes a ∈ A are encoded somewhere in the ciphertext or in the key, and the decryption returns the original message if and only if

P (a 1 , • • • , a k ) = 1.
When the predicate is encoded in the ciphertext and the attributes in the keys, it is called Ciphertext Policy attribute-based encryption. In the opposite case, it is called Key Policy attribute-based encryption, but our work only considers the first case:

Definition 2.19: Ciphertext-Policy Attribute-Based Encryption

An Ciphertext-Policy Attribute-Based Encryption (CP-ABE) scheme over an attribute space A is defined by four algorithms:

• SetUp(λ): takes as input the security parameter, and outputs the master secret key msk and the public key pk;

• KeyGen(msk, A): takes as input the master secret key msk and a set of attributes A, to output the private decryption key dk A ;

• Encrypt(pk, p, m): takes as input the public key, a policy p, and a message m, to output the encryption C p = (ct, p); • Initialization: the challenger runs the setup algorithm to get the values (msk, pk) ← SetUp(λ), and provides pk to the adversary A;

• Key Queries QKeyGen: the adversary A can ask KeyGen-queries, for any attribute set A of its choice to get dk A ;

• Challenge Challenge: the adversary A provides a policy p and two messages m 0 , m 1 to the challenger that picks a random bit b and runs C p ← Encrypt(pk, p, m b ). It provides C p to the adversary;

• Key Queries QKeyGen: the adversary A can again ask KeyGen-queries of its choice;

• Finalize: the adversary A outputs its guess b on the bit b.

We also define the event Cheat, which means that a user owns a set of attributes A that satisfies p: in such a case, the adversary can trivially guess b. Hence, we only allow adversaries such that Pr[Cheat] = 0. We then define

Adv ind (A) = |2 × Pr[b = b] -1|
, and say that an CP-ABE is (t, ε)-adaptively secure if no adversary A running within time t can get Adv ind (A) ≥ ε.

Assumptions

In this part we define the mathematical assumptions used in this work. They are all related to groups, and count among the most classical assumptions in group-based cryptography.

Prime order group assumptions

This first one states that given two random elements from the group, no one can compute their product, which is the basic idea behind every group assumptions.

Definition 2.21: Computational Diffie-Hellman assumption

The Computational Diffie-Hellman (CDH) assumption states that, in a primeorder 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 ].
The second is the decisional problem associated to the first one, given two random elements from the group, no one can distinguish between the product a third random element.

Definition 2.22: Decisional Diffie-Hellman assumption

The Decisional Diffie-Hellman (DDH) assumption states that, in a prime-order 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]
) . We can extend this second assumption in a vector of random elements with the help of the following proposition:

Proposition 2.1
For any distinguisher A running within time t, the best advantage A can get in distinguishing

D m = {(X, (Y j , Z j = CDH(X, Y j )) j ) | X, Y j $ ← G, j = 1, . . . , m} D m = {(X, (Y j , Z j ) j ) | X, Y j , Z j $ ← G, j = 1, . . . , m}. is bounded by Adv ddh (t + 4m × t G )
, where t G is the time for an exponentiation in G.

Proof

One can first note that the best advantage one can get, within time t, between

D = {(X, Y, Z = CDH(X, Y )) | X, Y $ ← G} D = {(X, Y, Z) | X, Y, Z $ ← G}.
is bounded by Adv ddh (t). This is actually the DDH assumption. One can note that D m and D m can be rewritten as

D m ={(X, (Y j = g u j Y v j , Z j = X u j • CDH(X, Y ) v j ) j ) | X, Y $ ← G, u j , v j $ ← Z p } D m ={(X, (Y j = g u j Y v j , Z j = X u j • Z v j ) j ) | X, Y, Z $ ← G, u j , v j $ ← Z p }
Since, from (X, Y, Z), the m tuples require 4 additional exponentiations per index j, one get the expected bound.

Pairing group assumptions

These assumptions, also considered classical, concerns the kind of groups we refer to in Section 2.1. The main difference with prime order groups is that the group G T now allows one multiplication.

This first assumption relies with the original group assumptions, presuming that DDH holds in both G 1 and G 2 .

Definition 2.23: Symmetric eXternal Diffie-Hellman assumption

The Symmetric eXternal Diffie-Hellman (SXDH) assumption states that, in a pairing group PG $ ← PGGen(1 λ ), the DDH assumption holds in both G 1 and G 2 .

The second really exploits the potential offered by the pairing. Three random elements from G 1 or G 2 are given, and the goal is to distinguish between the product of those three elements in G T or a random element from G T .

Definition 2.24: Decisional Bilinear Diffie Hellman assumption

The Decisional Bilinear Diffie Hellman (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 )]|.
Once again it can be extended in a vector of elements in the Q-fold DBDH assumption:

Proposition 2.2: 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] )]|.
And this lemma prove that Q-fold DBDH assumption is equivalent to classical DBDH assumption:

Lemma 2.1: 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 the values α i , c i $ ← Z p computes [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.

Multi-client functional encryption

This section is devoted to formalize multi-client functional encryption, decentralized multi-client functional encryption and their security models. We also discuss about the links and differences between several security level.

Multi-client functional encryption

We now define a private-key MCFE as in [CDG + 18b], which is a variant of the definition from [GGG + 14, GKL + 13, CDG + 18a]. The difference is, since we consider the symmetric setting, we allow users to decrypt using their own keys, to get back their component plaintexts at least when the ciphertexts were fully generated.

Definition

An MCFE scheme encrypts vectors of data from several senders i using personal encryption keys ek i , and it allows the controlled computation of functions f on these heterogeneous data with a functional decryption key dk f . In this work, we consider the symmetric-key setting, where the encryption key ek i can also serve to decrypt individual ciphertext for slot i ∈ [n], using the Decrypt algorithm. It works like the functional decryption algorithm FDecrypt, they both take as input a complete vector of individual ciphertexts, but the former uses ek i to decrypt an individual ciphertext, while the latter uses dk f to evaluate f on the global plaintext. The algorithm Decrypt will be used when proving CCA security in Section 6.3. We can thus define the MCFE definition as follows.

Definition 3.1: Multi-Client Functional Encryption

A multi-client functional encryption (MCFE) on M over a set of n senders is defined by five algorithms:

• SetUp(λ): takes as input the security parameter λ, and outputs the public parameters mpk, the master secret key msk and the n private encryption keys ek i ;

• Encrypt(ek i , x i , ): takes as input a user encryption key ek i , a value x i to encrypt, and a label , and outputs the ciphertext C ,i ;

• DKeyGen(msk, f ): takes as input the master secret key msk and a function f : M n → R, and outputs a functional decryption key dk f ;

• FDecrypt(dk f , , C): takes as input a functional decryption key dk f , a label , and an n-vector ciphertext C, and outputs

f ( x), if C is a valid encryption of x = (x i ) i ∈ M n for the label , or ⊥ otherwise.
• Decrypt(ek i , , C): takes as input a label , a user encryption key ek i and an n-vector ciphertext C, and outputs a value

x i , if C is a valid encryption of x = (x i ) i ∈ M n for the label , or ⊥ otherwise.
We will assume public parameters being implicitly included in the keys.

Correctness. Given (mpk, msk, (ek i ) i ) ← SetUp(λ), for any label , any function f : M n → R, and any vector

x = (x i ) i ∈ M n , if C ,i ← Encrypt(ek i , x i , ), for i ∈ {1, . . . , n}, and dk f ← DKeyGen(msk, f ), then FDecrypt(dk f , , C = (C ,i ) i ) = f ( x = (x i ) i ) and Decrypt(ek i , , C ) = x i .

Relation MIFE-MCFE

One can notice this definition makes MCFE very close to the MIFE described in Definition 2.17. In MIFE, every ciphertext for every slot can be combined with any other ciphertext for any other slot, and used with functional decryption keys to decrypt an exponential number of values, as soon as there are more than one ciphertext per slot. This "mix-and-match" feature is crucial for some of the applications of MIFE, such as building indistinguishability obfuscation [GGG + 14]. However, it also means the information leaked about the underlying plaintext is enormous, and in many applications, the security guarantees simply become void, especially when many functional decryption keys are queried. In the case of inner product, as soon as m wellchosen functional decryption keys are queried (i.e. for linearly independent vectors), the plaintexts are completely revealed. In the multi-client setting however, since only ciphertexts with the same label can be combined for decryption, information leakage of the plaintext is much controled.

Also we remark that, for both MIFE and MCFE, private-key is more relevant than their public-key counterparts. Essentially, in a public-key MCFE, an encryption of unknown plaintext x i , for some label , can be used together with encryptions of arbitrarily chosen values x j for each slot j ∈ [n] (for the same label ) and a functional decryption key for some function f , to obtain the value f

(x 1 , • • • , x i 1 , x i , x i+1 , • • • , x n ).
Since the values x j for j = i are arbitrarily chosen, this reveals typically too much information on x i for practical uses. In the case of inner product, that means that, from Enc(i, x i , ), dk y , and the public key, one can efficiently extract the values x i y i + j =i x j y j for chosen x j , which exactly reveals the partial inner product x i y i (see [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF] for more details on the limitations of public-key IP-FE in the multi-input setting). In order to prevent the adversary from a trivial win, one should make the restriction that the adversary is only allowed to ask functional decryption keys dk f for functions f that satisfy f

(x 0 1 , •, . . . , •) = f (x 1 1 , •, . . . , •), f (•, x 0 2 , . . . , •) = f (•, x 1 2 , . . . , •), . . . , f (•, •, . . . , x 0 n ) = f (•, •, . . . , x 1 n ).
This would essentially exclude any function. A private-key encryption solves this issue, and is still well-suited for practical applications.

Security

The security model is the usual left-or-right indistinguishability [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF], but where the adversary should not be able to get functional decryption keys that trivially help distinguish the encrypted vectors. Also, as explained in [GGG + 14, GKL + 13, CDG + 18a], one has to consider corruptions, since the senders do not trust each other, and they can collude and give their secret keys to the adversary who will play on their behalf.

IND * and IND

The reader will notice this definition describes two different versions, a weaker called IND * , and a stronger, IND. The former is given in [CDG + 18a] (more precisely wtr-IND * without QEncrypt, see Section 3.1.2 and Section 4.2.2). In this one there is the additional restriction on incomplete ciphertexts which formerly says that a challenge on a partial encryption of a vector over a label is considerate illegitimate. This constraint may seem artificial, but the construction given in [CDG + 18a] was vulnerable to this kind of attack. The latter is an improvement, and appears in [CDG + 18b]. This article fixes the shortcomings of the security achieved in [CDG + 18a], principally by allowing the adversary to query the left-or-right encryption oracle for some honest users, but not necessarily all of them, leading to incomplete ciphertexts.

We highlight the differences with the security definition from [CDG + 18a] and the one from [CDG + 18b]. Namely, the extra requirements in gray corresponds to the IND * -security and the framed to the IND one. Eventually, we note that the IND notion implicitly achieves CPA security. So we also consider CCA security, with additional functional decryption queries (dotted).

Definition 3.2: IND * , IND -CCA -Security Game for MCFE

Let us consider MCFE, a scheme over a set of n senders. No adversary A should be able to win the following security game against a challenger C, with unlimited and adaptive access to the oracles QEncrypt, QLeftRight, QFDecrypt, QDKeyGen, and QCorrupt described below:

• Initialize: the challenger C runs the setup algorithm (mpk, msk, (ek i ) i ) ← SetUp(λ) and chooses a random bit b $ ← {0, 1}. It provides mpk to the adversary A;

• Encryption queries QEncrypt(i, x, ): outputs the ciphertext C ,i ← Encrypt(ek i , x, ); • Challenge queries QLeftRight(i, x 0 , x 1 , ): outputs the ciphertext C ,i ← Encrypt(ek i , x b , );
• Functional decryption queries QFDecrypt(f, , C): the oracle first asks for the functional decryption key dk f , and then outputs FDecrypt(dk f , , C).

• Functional decryption key queries QDKeyGen(f ): outputs the functional decryption key dk f ← DKeyGen(msk, f );

• Corruption queries QCorrupt(i): outputs the encryption key ek i ;

• 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 CS is the set of corrupted senders (the set of indexes i input to QCorrupt during the whole game), and HS the set of honest (non-corrupted) senders. We set the output to β ← b , unless one of the cases below is true, in which case we set β $ ← {0, 1}:

1. some QLeftRight(i, x 0 i , x 1 i , )-query has been asked for an index i ∈ CS with x 0 i = x 1 i when encryption queries have been asked for all i ∈ HS;

2. for some label and for some function f asked to QDKeyGen, there exists a pair of vectors

( x 0 = (x 0 i ) i , x 1 = (x 1 i ) i ) such that f ( x 0 ) = f ( x 1 ), when • x 0 i = x 1 i , for all i ∈ CS; • QLeftRight(i, x 0 i , x 1 i , )-queries (or QEncrypt(i, x i , )-queries if x i = x 0 i = x 1 i
) have been asked for all i ∈ HS;

3. for some label , a challenge query QLeftRight(i, x 0 i , x 1 i , ) has been asked for some i ∈ HS, but challenge queries QLeftRight(j, x 0 j , x 1 j , ) or encryption queries QEncrypt(j, x j , ) have not all been asked for all j ∈ HS.

for some QFDecrypt(f, , C = (C i ) i )-query, we have 4.

• the answer was not ⊥;

• there exist two vectors x 0 and x 1 such that for all i ∈ CS: x 0 i = x 1 i , for all i ∈ HS: either there is a query QLeftRight(i,

x 0 i , x 1 i , ) that led to C i , or x 0 i = x 1 i = x i
and there is a query QEncrypt(i, x i , ) that led to C i .

• the above vectors x 0 and x 1 satisfy f

( x 0 ) = f ( x 1 ). We say MCFE is IND-secure if for any adversary A, Adv IND MCFE (A) = | Pr[β = 1|b = 1] -Pr[β = 1|b = 0]| is negligible.

About the finalize

The two first excluded cases are situations where the adversary could trivially distinguish the encrypted vectors, they are thus considered illegitimate attacks:

1. since we are dealing with symmetric-key encryption, where the encryption key and the decryption key are the same, a QLeftRight(i, x 0 i , x 1 i , )-query with x 0 i = x 1 i , for i ∈ CS leaks b (either at the QLeftRight-query time or at the corruption-time). In our stronger security model, this criteria is less restrictive, applying only when honest encryption are all queried; 2. for any functional decryption key, all the possible evaluations should not trivially allow the adversary to distinguish the ciphertexts generated through QLeftRightqueries (on honest components), only when ciphertexts are complete;

And the last condition is classical, in the CCA-setting, and here in the functional encryption context, as we consider illegitimate functional decryption queries on challenge ciphertexts that could result in a different values depending on the value of b. For such illegitimate attacks, the guess of the adversary is not considered (a random bit β is output). Otherwise, this is a legitimate attack, and the guess b of the adversary is output.

Other variants

We also define several variants of the security game:

• where the adversary must announce in advance the corruption (QCorrupt) queries: static security (sta-IND * /sta-IND);

• where the adversary must announce in advance the challenge (QLeftRight) queries: selective security (sel-IND * /sel-IND);

• where the adversary is limited to one encryption/challenge query on each (i, ) (later queries with the same i and will be ignored by QEncrypt and QLeftRight):

without-repetition security (wtr-IND * /wtr-IND). It was a problematic characteristic of the security definition of [CDG + 18a] fixed in [CDG + 18b], the resulting construction is described in Section 6.2;

• where the adversary is limited to challenge queries on one particular label: 1-Label-IND * -security. The 1-Label-IND * security is exactly the same security notion as IND * where the challenge QLeftRight oracle can only be queried with the same label. Hence, as above, the index ρ of the target label * is provided by the adversary, at the beginning, and so we can assume that all the encryption queries for * = ρ are asked to the QLeftRight oracle, while the other encryption queries are asked to the QEncrypt oracle. It is known that 1-Label-IND * and IND * are equivalent [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF], but the former is more convenient in the CCA security proof in Section 6.3;

About the oracle QEncrypt

Note that in the IND security game, the oracle QEncrypt can be simulated by QLeftRight, queried on input x 0 i = x 1 i . However, in the IND * , this oracle gives more power to the adversary: it is not possible for the adversary to query QLeftRight on some but not all input slots, for a given label (this is the condition 3. from Finalize), but it can query QEncrypt on incomplete ciphertexts, without triggering Finalize to output a random bit. This will be helpful when going from IND * to IND security, in Section 6.1.

Decentralization

Here, we define decentralized multi-client functional encryption (DMCFE), where the generation of functional decryption key is decentralized, and only requires individual secret keys, instead of the master secret key.

Definition of decentralized multi-client functional encryption

In MCFE, an authority owns a master secret key msk to generate the functional decryption keys. We would like to avoid such a powerful authority, and make the scheme totally decentralized among the owners of the data (the senders). We thus define DMCFE, for decentralized multi-client functional encryption. In this context, there are n senders (S i ) i , for i = 1, . . . , n, who will play the role of both the encrypting players and the functional decryption key generators, for a functional decryptor FD. Of course, the senders do not trust each other and they want to control the functional decryption keys that will be generated. There may be several functional decryptors, but since they could collude and combine all the functional decryption keys, in the description below, and in the security model, we will consider only one functional decryptor FD. We could simply use the definition of MCFE [GGG + 14, GKL + 13], where the setup and the functional decryption key algorithms are replaced by MPC protocols among the clients. But this could lead to a quite interactive process. We thus focus on efficient one-round key generation protocols DKeyGen that can be split in a first step DKeyGenShare that generates partial keys and the combining algorithm DKeyComb that combines partial keys into the functional decryption key.

Definition 3.3: Decentralized Multi-Client Functional Encryption

A decentralized multi-client functional encryption (DMCFE) on M between a set of n senders (S i ) i , for i = 1, . . . , n, and a functional decrypter FD is defined by the setup protocol and four algorithms:

• SetUp(λ): this is a protocol between the senders (S i ) i that generate their own secret keys sk i and encryption keys ek i , and eventually output the public parameters mpk;

• Encrypt(ek i , x i , ): takes as input a user encryption key ek i , a value x i to encrypt, and a label , and outputs the ciphertext C ,i ;

• DKeyGenShare(sk i , f ): takes as input a user secret key sk i and a label f , and outputs the partial functional decryption key dk f,i for a function f : M n → R that is described in f ;

• DKeyComb((dk f,i ) i , f ): takes as input the partial functional decryption keys and eventually outputs the functional decryption key dk f ;

• FDecrypt(dk f , , C): takes as input a functional decryption key dk f , a label , and an n-vector ciphertext C, and outputs f ( x), if C is a valid encryption of x = (x i ) i ∈ M n for the label , or ⊥ otherwise;

• Decrypt(ek i , , C): takes as input an encryption key ek i , a label , and an n-vector ciphertext C, and outputs x i , if C is a valid encryption of x i ∈ M for the label , or ⊥ otherwise;

We make the assumption that mpk is included in all the secret and encryption keys, as well as the (partial) functional decryption keys. Similarly, the function f might be included in the (partial) functional decryption keys.

Correctness. Given (mpk, (sk i ) i , (ek i ) i ) ← SetUp(λ), for any label , any function f : M n → R, and any vector

x = (x i ) i ∈ M n , if C ,i ← Encrypt(ek i , x i , ), for i ∈ {1, . . . , n}, and dk f ← DKeyComb((DKeyGenShare(sk i , f )) i , f ), then we have FDecrypt(dk f , , C = (C ,i ) i ) = f ( x = (x i ) i ).
The correctness property essentially states the combined key corresponds to the functional decryption key.

Security of DMCFE

The IND-security model is quite similar to the previous one for MCFE (see Definition 3.2), the differences occur on the three following points.

First, for the DKeyGen protocol: the adversary has access to transcripts of the communications, thus modeled by a query QDKeyGen(i, f ) that generates a part of the key through DKeyGenShare(sk i , f ), where f is a description of f . Consequently, the QDKeyGen takes the user i as input.

• Functional decryption key queries QDKeyGen(i, f ): A has unlimited and adaptive access to the (non-corrupted) senders running the DKeyGenShare(sk i , f ) algorithm for any input function f of its choice. It is given back the partial functional decryption key dk f,i ;

Secondly, corruption queries additionally reveal the secret keys sk i used in the DKeyGenShare algorithm:

• Corruptions queries QCorrupt(i): A can make an unlimited number of adaptive corruption queries on input index i, to get the secret and encryption keys (sk i , ek i ) of any sender i of its choice.

Last point, the Finalize procedure ignores incomplete functional decryption keys: for condition (2), only functions f for which all the honest key-shares have been asked are considered: 1. some QLeftRight(i, x 0 i , x 1 i , )-query has been asked for an index i ∈ CS with x 0 i = x 1 i when encryption queries have been asked for all i ∈ HS;

2. for some label and for some function f asked to QDKeyGen, there exists a pair of vectors

( x 0 = (x 0 i ) i , x 1 = (x 1 i ) i ) such that f ( x 0 ) = f ( x 1 ), when • x 0 i = x 1 i , for all i ∈ CS; • QLeftRight(i, x 0 i , x 1 i , )-queries (or QEncrypt(i, x i , )-queries if x i = x 0 i = x 1
i ) have been asked for all i ∈ HS; • QKeyGen(i, f )-queries have been asked for all i ∈ HS The critical point is the last one: the distributed key generation must guarantee that without all the shares, no information is known about the functional decryption key. In addition, the protocol must be efficient.

Construction of MCFE

In this section we present several constructions of inner product MCFE (IP-MCFE). The first one is generic, using a KH-PRF, and is proven sel-wtr-IND * -secure. The two others are group-based schemes, and were described in [CDG + 18a]. One can be considered as the direct instantiation of the first construction, and the security level remains the same. The other is an improvement that reaches the wtr-IND * -security against adaptive queries and corruptions.

IP-MCFE from key-homomorphic PRF

Here we describe how to build an IP-MCFE from a KH-PRF in a black-box way.

Overview

The main idea is the same as the inner product FE (IP-FE) from [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], which consists to mask linearly the x ,i with some secret r ,i . The decryption processes by computing i (x ,i + r ,i ) • y i and then removing the value i r ,i • y i with a decryption key dk y . There are essentially two constraints on the r ,i to satisfy when building such a scheme. First, these values must be indistinguishable from uniform randomness to ensure statistical security of x ,i . Secondly, they must be correlated with a same label to correctly decrypt with a same key dk y . Eventually, they must be uncorrelated between the different labels to avoid mix-and-match attacks. A KH-PRF F fulfills these conditions if we consider the label as the input, and a user key ek i as the key:

r ,i = F (ek i , ).

Description

Our construction, using additive notation:

• SetUp(λ): outputs a KH-PRF F : K × X -→ Y as public parameter pp, and a personal encryption key ek i

$ ← K for each users i ∈ [n]. We note msk = (ek i ) i .
• Encrypt(x i , ek i , ): takes as input a value x i to encrypt, a personal encryption key ek i , a label , and outputs the ciphertext

C ,i = F (ek i , ) + x i .
• DKeyGen(msk, y): takes as input msk, the vector y that characterizes the function f y ( x) = x, y and provides dk y = ( y, msk, y ) = ( y, (ek i ) i , y ).

• FDecrypt(dk f , , C = (C ,j ) j ): takes as input a decryption key dk f , a label , and a ciphertext C to compute the value: C , y -F (dk y , ).

• Decrypt(ek i , , C = (C ,j ) j ): takes as input a decryption key dk f , a label , and a ciphertext C to compute the value:

C ,i -F (ek i , ).
Correctness. If the scalar dk in the functional decryption key dk y = ( y, dk) is indeed dk = (ek i ) i , y , then:

C , y -F (dk y , ) = (F (ek i , ) + x i ) i , y -F (dk y , ) = F ( (ek i ) i , y , ) + x, y -F (dk y , ) = x, y

Security analysis

Sadly, the security level guaranteed by this construction is inversely proportional to its simplicity: only selective in encryption queries, limited to one encryption under the pair (i, ), and overall it is not secure if we suppose that the adversary can ask partial ciphertexts only. The MCFE protocol described above (see Section 4.1) is sel-wtr-IND * secure if the function F is a PRF. More precisely, we have

Adv IND (A) ≤ 2Q • Adv(t) PRF KH-PRF ,
for any adversary A running in time t, where Q is the number of labels.

The proof of this theorem consists in a sequence of hybrid games on the labels, from

G 0 = G 1,1,0 to G 2 = G 1,Q ,5
where Q is the number of labels. The idea is to pick a part of the key as a vector of x 0 -x b , then inject randomness through the KH-PRF. The following Fig. 4.1 summarizes this proof.

Games G 1,q,0 , G 1,q,1 , G 1,q,2 , G 1,q,3 , G 1,q,4 state, ( j , z j,i ) i∈[n],j∈[Q] ← A(1 λ , 1 n ) where each z j,i = (x 0 j,i , x 1 j,i ) ∈ Z 2 p , or z j,i = ⊥, which stands for no query. Initialize PRFO: pick µ $ ← K Initialize PRFO as RF . For all i ∈ [n], s i $ ← K, pick µ $ ← K, , and generate a KH-PRF F : K × X -→ Y. ek i := s i , ek i := s i + µ(x 0 i, q -x b i, q ) , msk := (ek i ) i , mpk := F . When z j,i = (x 0 j,i , x 1 j,i ), then C j,i = QLeftRight(i, x 0 j,i , x 1 j,i , j ) for i ∈ [n], j ∈ [Q ]. b ← A QDKeyGen(•),QCorrupt(•) (mpk, state). Run Finalize on b . QLeftRight(i, x 0 i , x 1 i , ): // {G 1,q,j } j=0,1 , G 1,q,2 ,G 1,q,3 , G 1,q,4
For b j = 0 when j < q, j ≤ q , b else.

C i := F (ek i , j ) + x b j i . C i := F (ek i , j ) + (x 0 i, q -x b i, q )PRFO( ) + x b j i . Return [c i ]. QEncrypt(i, x i , ): // {G 1,q,j } j=0•••4 Return QLeftRight(i, x i , x i , ). PRFO( ): // G 1,q,2 , {G 1,q,j } j=3,4
Return F (µ, ), RF( ) . QDKeyGen( y): Game G 1,q,0 : this game is characterized by the encryption:

// {G 1,q,j } j=0•••4 Return s, y . QCorrupt(i): // {G 1,q,j } j=0•••4 Return s i .
• for queries j where j < q, encrypts x 0

• for queries j where j ≥ q, encrypts x b

Game G 1,q,1 : this game only changes the generation of msk: C chooses msk = µ( x 0 q -x 1 q ) + s where µ $ ← K and s $ ← K n , and the ek i used in the encryption are now ek i : s i + µ(x 0 i, q -x 1 i, q ). Note that the decryption keys are dk y = (ek i ) i , y = s, y .

Game G 1,q,2 : now C only chooses the s part of the key in the SetUp. To prepare the QLeftRight queries, he asks an oracle PRFO the values F (µ, j ) for any query j and returns:

• C i = F (s i , j ) + (x 0 i, q -x 1 i, q )F (µ, j ) + x 0 i, j when j < q • C i = F (s i , j ) + (x 0 i, q -x 1 i, q )F (µ, j ) + x b i, j when j ≥ q
Also, C can still answer other queries: for QDKeyGen he computes and sends s, y , and for QCorrupt he answers s i .

Game G 1,q,3 : same as previously except that the oracle PRFO now answers RF( ) for any query , where RF : X -→ Y was randomly chosen at the initialization of PRFO.

Game G 1,q,4 : this game switches the bit used in the encryption into 0 for the label q .

Game G 1,q,5 = G 1,q+1,0 : in this game, the SetUp turns back to the original description of G 1,q,0 to start a new iteration, and we have G 1,q,5 = G 1,q+1,0 .

Game G 2 : same game as G 0 except that the bit used for encryption is 0.

The advantages for A are the same in G 1,q,0 , G 1,q,1 and G 1,q,2 since the distributions of both ciphertexts and keys are not modified. The PRF makes it hard to distinguish between G 1,q,2 and G 1,q,3 , |Adv ,2 -Adv ,3 | = Adv PRF KH-PRF (B), where B is an adversary playing against PRFO. The step between G 1,q,3 and G 1,q,4 is statistically secure, since PRFO has the same probability to use a function RF( ) or RF q ( ) where RF q ( ) = RF( ) + δ q ( ). In the last game G 1,q,5 , the challenger comes back to the use of a PRF, repeating the PRF security game. Thus, the final advantage is

Adv IND * MCFE (A) ≤ 2Q × Adv PRF KH-PRF
, where Q is the number of labels.

Remark 1. Note that, because of the first finalize condition, the extra value (x 0 i, q -x 1 i, q )F (µ, j ) is null for corrupted users, so their ciphertexts are not modified in a valid simulation.

Remark 2. Also, the QEncrypt(i, x i , ) can here be answered with the value QLeftRight(i, x i , x i , ). As explained in remark Section 3.1.2, the only difference between these two values is that QEncrypt allows the adversary to make incomplete ciphertext queries, not QLeftRight. In the security proof, the challenge ciphertexts output by QLeftRight are switched from an encryption of x b i to encryption of x 0 i , introducing a delta terms in the functional decryption keys. This delta term cancels out thanks to the conditions given in the Finalize procedure (for which we need complete ciphertexts). For QEncrypt queries, x b i = x 0 i = x 1 i , which means the delta term is zero, and doesn't show up in any of the functional decryption key even for incomplete ciphertexts.

Limitations

Following the KH-PRF definition, for such a function F , we have that αF (k, ) = F (αk, ) for any α ∈ Z p . Thus, the discrete logarithm problem must hold in the image space, else F cannot be a PRF. Consequently, two problems appear here:

• if the decryption need to solve a discrete logarithm to recover the value x, y , it limits the size of the outputs and decreases the efficiency of the scheme. However, we can avoid this by working on groups with subgroups that allow discrete logarithm computation.

• the group instantiation seems to be the only one for this precise construction. Such a PRF exists, since our scheme from [CDG + 18a] proposes one:

F (k, ) = H( ) k
, where H : {0, 1} * -→ G is an hash function onto the group G. However, this PRF has the drawback to be secure in the random oracle model only.

Another assumption

There exists a family of "almost key-homomorphic" PRF which allows an operation with a bounded error. Since the method described here presents a bounded number of operations (n additions and scalar multiplications in the decryption), we can imagine to manage this noise. This PRF was first described in the paper [START_REF] Boneh | Key homomorphic PRFs and their applications[END_REF], under an assumption derived from Learning With Errors, in the standard model. It was then re-developed in the paper [START_REF] Banerjee | New and improved keyhomomorphic pseudorandom functions[END_REF] under the standard Learning With Errors problem, still in standard model. Finally, a recent work, [START_REF] Libert | Multi-client functional encryption for linear functions in the standard model from lwe[END_REF], achieved a MCFE scheme from an "almost key-homomorphic" PRF family derived from these works. Their scheme is secure under the Learning With Errors assumption in the standard model. However, it loses in efficiency comparatively to the group instantiation, since this PRF uses techniques from fully homomorphic encryption.

Another interesting work from the same conference, [START_REF] Abdalla | From singleinput to multi-client inner-product funtional encryption[END_REF], builds (Decentralized) IP-MCFE from single-input IP-FE and a simple PRF in a black-box way. However, this construction mainly aims to be generic, and makes a trade-off on the size of the ciphertext, which is linear in the size of users.

IP-MCFE from groups

In this section we describe two MCFE schemes based on groups. While the first can now be seen as an instantiation of the generic construction, it was originally inspired by Abdalla et al. in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF]. The second improves the security from selective to adaptive, achieving the wtr-IND * security using a similar technique as [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF].

Overview

This section describes two secret-key MCFE schemes initially built up from the public-key FE scheme introduced by Abdalla et al. [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] (itself a selectivelysecure scheme). Mainly, we replace the global randomness with a hash function (modeled as a random oracle for the security analysis), in order to make the generation of the ciphertexts independent for each client. The comparison is illustrated in Figure Fig. 4.2. Note that for the final decryption to be possible, one needs the function evaluation α to be small enough, within this discrete logarithm setting. This is one limitation, which is still reasonable for real-world applications that use concrete numbers, that are not of cryptographic size.

From Section 4.2.1 MCFE ABDP15 [ABDP15] SetUp Pick (s i ) i∈[n] at random Pick (s i ) i∈[n] at random and set V i = [s i ] Encrypt Each client i, on input (x i , s i , ), return [c i ] = [x i ] + s i • H( ) On input ((x i ) i , (v i ) i ), pick r $ ← Z p , return ([c 0 ] = [r], ([c i ] = [x i ] + r • V i ) i ) DKeyGen On input ((y i ) i , (s i ) i ), return dk y = i y i s i On input ((y i ) i , (s i ) i ), return dk y = i y i s i Decrypt Discrete logarithm on [α] = i y i • [c i ] -dk y • H( ) Discrete logarithm on [α] = i y i • [c i ] -dk y • [c 0 ]
c i ] = [x i ] + s i • [c 0 ] for i ∈ [n]
in both cases. In the public-key scheme from [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], s i was private, and only V i = [s i ] was known to the encryptor. Since we are now dealing with private encryption, the encryptor can use s i . Correctness then follows from

[α] = i y i • [c i ] -dk y • [c 0 ] = i y i • ([x i ] + s i • [c 0 ]) -dk y • [c 0 ] = i [x i y i ] + ( i s i y i ) • [c 0 ] -dk y • [c 0 ] = [ x, y ]
We now describe this MCFE scheme and prove it selectively secure under the DDH assumption.

Description of selective version

• SetUp(λ): takes as input the security parameter, and generates a group G of prime order p ≈ 2 λ , g ∈ G a generator, and H a full-domain hash function onto G. It also generates the encryption keys s i $ ← Z p , for i = 1, . . . , n, and sets s = (s i ) i . The public parameters mpk consist of (G, p, g, H), while the master secret key is msk = s and the encryption keys are ek i = s i for i = 1, . . . , n (in addition to mpk, which is omitted).

• Encrypt(ek i , x i , ): takes as input the value x i to encrypt, under the key ek i = s i and the label . It computes [u ] := H( ) ∈ G, and outputs the ciphertext

[c i ] = [u s i + x i ] ∈ G.
• DKeyGen(msk, y): takes as input msk = (s i ) i and an inner product function defined by y as f y ( x) = x, y , and outputs the functional decryption key

dk y = ( y, i s i y i ) ∈ Z n p × Z p .
• FDecrypt(dk y , , ([c i ]) i∈ [n] ): takes as input a decryption key dk y = ( y, d), a label . It computes

[u ] := H( ), [α] = i y i • [c i ] -d • [u ],
and eventually solves the discrete logarithm to extract and return α.

• Decrypt(ek i , , ([c j ]) j∈ [n] ): takes as input an encryption key

ek i = s i , a label . It computes [u ] := H( ), [α] = [c j ] -ek i • [u ],
and eventually solves the discrete logarithm to extract and return α.

Correctness. If the scalar dk in the functional decryption key dk y = ( y, dk) is indeed dk = s, y , then:

[α] = i y i • [c i ] -d • [u ] = i y i • [u s i + x i ] -[u ] • i s i y i = [u ] • i s i y i + [ i x i y i ] -[u ] • i s i y i = [ i x i y i ].

Security analysis

Like Abdalla et al.'s original scheme [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], this protocol can only be proven secure in the weaker security model, sel-wtr-IND * in the MCFE context, where the adversary has to commit in advance to all of the pairs of messages for the left-or-right encryption oracle (QLeftRight-queries), and can only make one encryption per label. However, it can adaptively ask for functional decryption keys (QDKeyGen-queries) and encryption keys (QCorrupt-queries). Concretely, the challenger is provided (plaintext,label) pairs:

(x b j,i , j ) b∈{0,1},i∈[n],j∈[Q] ,
where Q is the number of query to QLeftRight(i, •, •, j ), each one for a different label j (note that in the security model, we assume each slots are queried the same number of time, on different labels). The challenge ciphertexts C i,j = Encrypt(ek i , x b j,i , j ), for the random bit b, are returned to the adversary. The adversary committing to challenge ciphertexts also limits its ability to corrupt users during the game: it must corrupt clients for which it didn't ask a ciphertext and cannot corrupt any client from which it asked a ciphertext for x 0 j,i = x 1 j,i .

About the security in [CDG + 18a]

Note that the security notion proven in [CDG + 18a] slightly differs from the sel-wtr-IND * security notion we use here, in that it does not give the adversary access to a QEncrypt oracle, but only QLeftRight (see Section 3.1.2 on the role of the oracle QEncrypt, and why it generally cannot be simulated by QLeftRight in the IND * security game). For the same reason as in 4.1, it follows from inspection of the security proof of [CDG + 18a] that it can actually achieve the IND * security notion defined here.

Games G 0 , G 1 , (G 2.q ) q∈[Q+1] state, ( j , z j,i ) i∈[n],j∈[Q] ← A(1 λ , 1 n ) where each z j,i = (x 0 j,i , x 1 j,i ) ∈ Z 2 p , or z j,i = ⊥, which stands for no query. G ← GGen(1 λ ), for all i ∈ [n], s i $ ← Z p ,ek i := s i , msk := (s i ) i , mpk := (G, p, g). C j,i = QLeftRight(i, x 0 j,i , x 1 j,i , j ) for i ∈ [n], j ∈ [Q] such that z j,i = (x 0 j,i , x 1 j,i ). b ← A QDKeyGen(•),QCorrupt(•),RO(•) (mpk, state). Run Finalize on b . RO( ): // G 0 , G 1 , G 2.q [u ] := H( ) , [u ] := RF( ) . Return [u ]. QLeftRight(i, x 0 i , x 1 i , ): // G 0 , G 1 , G 2.q [u ] := RO( ), [c i ] := [u ] • s i + [x b i ] If = j with j < q: [c i ] := [u s i + x 0 i ] Return [c i ]. QEncrypt(i, x i , ): // G 0 , {G 1,q,j } j=0•••4 Return QLeftRight(i, x i , x i , ).

QDKeyGen( y):

// G 0 , G 1 , G 2.q Return i y i s i .

QCorrupt(i): // G 0 , G 1 , G 2.q Return s i . Figure 4.3: Games G 0 , G 1 , (G 2. ) q∈[Q+1]
, for the proof of Theorem 4.2. Here, RF is a random function onto G, that is computed on the fly. Note that QLeftRight is only used as a subroutine of the initialization of the game and is not accessible to the adversary. In each procedure, the components inside a solid frame are only present in the games marked by a solid frame.

We proceed using hybrid games, summarized in Fig. 4.3, in a similar method as the KH-PRF-based construction: we play on the space defined by the vectors x 0 -x b to inject randomness and switch the bit.

Proof

Game G 0 : this is the sel-wtr-IND * security game as given in Definition 3.2 (see the paragraph about weaker models), with all the encryption queries being sent first: they are stored in z j,i = (x 0 j,i , x 1 j,i ), for j ∈ [Q] and i ∈ [n], where j is for the j-th H-query that specifies the label j and i is for the index of the sender. If the query is not asked, we have z j,i = ⊥. Note that the hash function H is modeled as a random oracle RO onto G. This is used to generate [u ] = H( ).

Game G 1 : we simulate the answers to any new RO query by computing a truly random element of G, on the fly. The simulation remains perfect, so

Adv 0 = Adv 1 .
Game G 2 : we simulate every encryption as the encryption of x 0 i instead of x b i . While it is clear that in this last game the advantage of any adversary is exactly 0 since b does not appear anywhere, the gap between G 1 and G 2 will be proven using an hybrid argument on the RO-queries. We thus index the following games by q, where q = 1, . . . , Q. Note that only distinct RO-queries are counted, since a second similar query is answered as the first one.

G 2.1 : this is exactly game G 1 . Thus, Adv 1 = Adv 2.1 . G 2.q
G 2.q+1 : we change the generation of the ciphertexts from

[c q,i ] := [u q s i + x b q,i ] to [c q,i ] := [u q s i + x 0 q,i ].
We proceed in three steps:

Step 1. We use the fact that the two following distributions are identical, for any choice of γ:

(s i ) i∈[n],z q,i =(x 0 q,i ,x b q,i ) and s i + γ(x 0 q,i -x b q,i ) i∈[n],z q,i =(x 0 q,i ,x 1 q,i )
,

where s i $ ← Z p , for all i ∈ [n]
. This is true since the s i are independent of the z q,i (we are in a selective setting, so the s i 's are generated after the z q,i 's have been chosen). Thus, we can re-write s i into s i + γ(x 0 q,i -x b q,i ) without changing the distribution of the game.

Note that when Finalize does not output a random bit β $ ← {0, 1} independent of the guess b , γ does not appear in the outputs of QCorrupt(i), since it must be that x 0 i = x 1 i or z q,i = ⊥, and it does not appear in the output of QDKeyGen( y) either, since i s i • y i + i γ(x 0 q,i -x b q,i )y i , where the gray term equals zero by Definition 3.1. The fact that γ does not appear in the outputs of these oracles will be crucial for step 2, which applies DDH on [γ].

Step 2. We use the DDH assumption to replace the [u q γ] that appear in the output of the q-th query to QLeftRight queries with [r q + 1] with r q $ ← Z p . This is possible since the rest of the adversary view can be generated only from [γ] and [r q + 1]. This increases the adversary's advantage by no more than Adv ddh G (t). We now have:

[c q,i ] :=[u q s i + (x 0 q,i -x b q,i )(r q + 1) + x b q,i ] =[u q s i + r q (x 0 q,i -x b q,i ) + x 0 q,i -x b q,i + x b q,i ] =[u q s i + r q (x 0 q,i -x b q,i ) + x 0 q,i ].
Step 3. We switch [r q ] in the output of the q-query to QLeftRight back to [u q γ], using the DDH assumption again. This is possible since the adversary's view is simulatable solely from [γ], [u q ], and [r q ]. We finally undo the distribution change on the s i , which brings us to G 2.q+1 .

As a conclusion, since

G 2.Q+1 = G 2 , we have Adv 1 -Adv 2 ≤ 2Q • Adv ddh G (t).
In addition, Adv 2 = 0, which concludes the proof.

Description of adaptative version

After the selective construction from [CDG + 18a], we propose another construction of MCFE for inner product from the same article, adapted from the Agrawal et al. [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF] scheme in the same manner. The main contribution of this construction is re-uses a technique from this article to achieve the adaptive wtr-IND * -security. Roughly speaking, it consists to double the size of the keys.

• SetUp(λ): takes as input the security parameter, and generates prime-order group G := (G, p, P ) $ ← GGen(1 λ ), and H a full-domain hash function onto G 2 . It also generates the encryption keys s i $ ← Z 2 p , for i = 1, . . . , n. The public parameters mpk consist of (G, p, g, H), while the encryption keys are ek i = s i for i = 1, . . . , n, and the master secret key is msk = ((ek i ) i ), (in addition to mpk, which is omitted).

• Encrypt(ek i , x i , ): takes as input the value x i to encrypt, under the key ek i = s i and the label . It computes [ u ] := H( ) ∈ G 2 , and outputs the ciphertext

[c i ] = [ u s i + x i ] ∈ G.
• DKeyGen(msk, y): takes as input msk = ( s i ) i and an inner product function defined by y as f y ( x) = x, y , and outputs the functional decryption key

dk y = ( y, i s i • y i ) ∈ Z n p × Z 2 p .
• FDecrypt(dk y , , ([c i ]) i∈ [n] ): takes as input a functional decryption key dk y = ( y, d), a label , and ciphertexts. It computes

[ u ] := H( ), [α] = i [c i ] • y i - [ u ]
• d, and eventually solves the discrete logarithm to extract and return α.

• Decrypt(ek i , , ([c j ]) j∈ [n] ): takes as input an encryption key

ek i = (s 1 , s 2 ), a label . It computes [ u ] := H( ), [α] = [c j ] -ek i • [ u ],
and eventually solves the discrete logarithm to extract and return α.

Correctness. If the scalar d in the functional decryption key dk y = ( y, d) is indeed d = ( s 1 , y , s 2 , y ), then:

[α] = i [c i ] • y i -[ u ] • d = i [ u s i + x i ] • y i -[ u ] • i y i s i = i [ u ] • s i y i + i [x i ] • y i -[ u ] • i y i s i = [ i x i y i ].

Security Analysis

We stress that the following theorem supports both adaptive encryption queries and adaptive corruptions.

Theorem 4.3: wtr-IND * -Security

The above MCFE protocol (see Section 4.2.3) is wtr-IND * -secure under the DDH assumption, in the random oracle model. More precisely, we have

Adv IND (A) ≤ 2Q • Adv ddh G (t) + Adv ddh G (t + 4Q × t G ) + 2Q p ,
for any adversary A, running within time t, where Q is the number of (direct and indirect -asked by QEncrypt-queries-) queries to H (modeled as a random oracle), and t G is the time for an exponentiation in G.

To obtain adaptive security, we use a technique that consists of first proving perfect security in the selective variant of the involved games, then, using a guessing (a.k.a. complexity leveraging) argument, which incurs an exponential security loss, we obtain the same security guarantees in the adaptive games. Since the security in the selective game is perfect (the advantage of any adversary is exactly zero), the exponential security loss is multiplied by a zero term, and the overall adaptive security is preserved. This technique has been used before in [START_REF] Wee | Dual system encryption via predicate encodings[END_REF] in the context of attribute-based encryption, or more recently, in [AGRW17,ACF + 18] in the context of multi-input IP-FE. We defer to [Wee14, Remark 1] and [AGRW17, Remark 5] for more details on this proof technique. We proceed using hybrid games, described in Fig. 4.4.

Proof

Let A be a PPT adversary. For any game G index , we denote by

Adv index := | Pr[G index (A)|b = 1] -Pr[G index (A)|b = 0]|,
where the probability is taken over the random coins of G index and A. Also, by event G index (A), or just G index when there is no ambiguity, we mean that the Finalize procedure in game G index (defined as in Definition 3.2) returns β = 1 from the adversary's answer b when interacting with A.

Game G 0 : this is the IND-security game as given in Definition 3.2. Note that the hash function H is modeled as a random oracle RO onto G 2 . This is essentially used to generate

[ u ] = H( ).
Game G 1 : we simulate the answers to any new RO-query by a truly random pair in G 2 , on the fly. The simulation remains perfect, and so Adv 0 = Adv 1 .

Game G 2 : we simulate the answers to any new RO-query by a truly random pair in the span of [ a] for a := ( 1 a ) , with a $ ← Z p . This uses the Multi-DDH assumption, which tightly reduces to the DDH assumption using the random-self reducibility (see Lemma Proposition 2.1):

Adv 1 -Adv 2 ≤ Adv ddh G (t + 4Q × t G )
, where Q is the number of RO-queries and t G the time for an exponentiation.

Game G 3 : we simulate any QEncrypt query as the encryption of x 0 i instead of x b i and go back for the answers to any new RO query by a truly random pair in G 2 .

While it is clear that in this last game the advantage of any adversary is exactly 0 since b does not appear anywhere, the gap between G 2 and G 3 will be proven using a hybrid technique on the RO-queries. We thus index the following games by q, where q = 1, . . . , Q. Note that only distinct RO-queries are counted, since a second similar query is answered as the first one. We detail this proof because the technique is important (Fig. 4.5). G 3.1.1 : this is exactly game G 2 . Thus, Adv 2 = Adv 3.1.1 . G 3.q.1 G 3.q.2 : we first change the distribution of the output of the q-th ROquery, from uniformly random in the span of [ a] to uniformly random over G 2 , using the DDH assumption. Then, we use the basis

(( 1 a ) ,( -a 1 ) ) of Z 2
p , to write a uniformly random vector over

Z 2 p as u 1 • a + u 2 • a ⊥ , where u 1 , u 2 $ ← Z p . Finally, we switch to u 1 • a + u 2 • a ⊥ where u 1 $ ← Z p , and u 2 $ ← Z *
p , which only changes the adversary view by a statistical distance of 1/p: Adv 3.q.1 -Adv 3.q.2 ≤ Adv ddh G (t) + 1/p. The last step with u 2 ∈ Z * p will be important to guarantee that u a ⊥ = 0.

G 3.q.2 G 3.q.3 : we now change the generation of the ciphertext

[c i ] := [ u ] • s i + [x b i ] by [c i ] := [ u ] • s i + [x 0 i ],
where [ u ] corresponds to the q-th RO-query. We then prove this does not change the adversary's view.

Note that if the output of the q-th RO-query is not used by QEncryptqueries, then the games G 3.q.2 and G 3.q.3 are identical. But we can show this is true too when there are RO-queries that are really involved in QEncrypt-queries, and show that Adv 3.q.2 = Adv 3.q.3 in that case too, in two steps. In Step 1, we show that there exists a PPT adversary B such that Adv 3.q.t = (p 2 + 1) n • Adv 3.q.t (B ), for t = 2, 3, where the games G 3.q.2 and G 3.q.3 are selective variants of games G 3.q.2 and G 3.q.3 respectively (see Fig. 4.5), where QCorrupt queries are asked before the initialization phase. In Step 2, we show that for all PPT adversaries B , we have Adv 3.q.2 (B ) = Adv 3.q.3 (B ). This will conclude the two steps.

Step 1. We build a PPT adversary B playing against G 3.q.t for t = 2, 3, such that Adv 3.q.t = (p 2 + 1) n • Adv 3.q.t (B ).

Adversary B first guesses for all i ∈ [n], z i $ ← Z 2
p ∪ {⊥}, which it sends to its selective game G 3.q.t . That is, each guess z i is either a pair of values (x 0 i , x 1 i ) queried to QEncrypt, or ⊥, which means no query to QEncrypt. Then, it simulates A's view using its own oracles. When B guesses successfully (call E that event), it simulates A's view exactly as in G 3.q.t . If the guess was not successful, then B stops the simulation and outputs a random bit β. Since event E happens with probability (p 2 + 1) -n and is independent of the view of adversary A: Adv 3.q.t (B ) is equal to

Pr[G 3.q.t |b = 0, E] • Pr[E] + Pr[¬E] 2 -Pr[G 3.q.t |b = 1, E] • Pr[E] - Pr[¬E] 2 = Pr[E] • | Pr[G 3.q.t |b = 0, E] -Pr[G 3.q.t |b = 1, E]| = (p 2 + 1) -n • Adv 3.q.t .
Step 2. We assume the values (z i ) i∈ [n] sent by B are consistent, that is, they don't make the game end and return a random bit, and Finalize on b does not return a random bit independent of b (call E this event).

We show that games G 3.q.2 and G 3.q.3 are identically distributed, conditioned on E . To prove it, we use the fact that the two following distributions are identical, for any choice of γ:

( s i ) i∈[n],z i =(x 0 i ,x 1 i ) and s i + a ⊥ • γ(x b i -x 0 i ) i∈[n],z i =(x 0 i ,x 1 i )
, where a ⊥ := ( -a 1 ) ∈ Z 2 p and s i $ ← Z 2 p , for all i = 1, . . . , n. This is true since the s i are independent of the z i (note that this is true because we are in a selective setting, while this would not necessarily be true with adaptive QEncrypt-queries). Thus, we can re-write s i into s i + a ⊥ •γ(x b i -x 0 i ) without changing the distribution of the game.

We now take a look at where the extra terms a ⊥ • γ(x b i -x 0 i ) actually appear in the adversary's view:

• they do not appear in the output of QCorrupt, because we assume event E holds, which implies that if z i = ⊥, then i is not queried to QCorrupt or x 1 i = x 0 i . • they might appear in QDKeyGen( y) as

dk y = i∈[n] s i • y i + a ⊥ • γ i:z i =(x 0 i ,x 1 i ) y i (x b i -x 0 i ) .
But the gray term equals 0 by the constraints for E in Definition 3.2: for all i ∈ HS,

z i = ⊥; if i ∈ CS and z i = ⊥, x 1 i = x 0 i ; and f ( x 0 ) = f ( x 1 ), hence i:z i =(x 0 i ,x 1 i ) y i (x b i -x 0 i ) = 0.
• eventually, they appear in the output of the QEncrypt-queries which use [ u ] computed on the q-th RO-query, since for all others, the vector [ u ] lies in the span of [ a], and a a ⊥ = 0. We thus have

[c i ] := [ u ] • s i + (x b i -x 0 i )γ[ u ] a ⊥ + [x b i ].
Since u a ⊥ = 0, we can choose γ = -1/ u a ⊥ mod p, and then

[c i ] = [ u ] • s i + [x 0 i ],
which is the encryption of x 0 i . We stress that γ is independent of the index i, and so this simultaneously converts all the encryptions of x b i into encryptions of x 0 i . Finally, reverting these statistically perfect changes, we obtain that

[c i ] is identically distributed to [ u ] • s i + [x 0 i ],
as in game G 3.q.3 . Thus, when event E happens, the games are identically distributed. When ¬E happens, the games both return β $ ← {0, 1}: Adv 3.q.2 (B ) = Adv 3.q.3 (B ). As a conclusion, we get Adv 3.q.2 = Adv 3.q.3 . G 3.q.3 G 3.q+1.1 : this transition is the reverse of G 3.q.1 G 3.q.2 , namely, we use the DDH assumption to switch back the distribution of [ u ] computed on the q-th RO-query from uniformly random over G 2 (conditioned on the fact that u a ⊥ = 0) to uniformly random in the span of [ a]: Adv 3.q.3 -Adv 3.q+1.1 ≤ Adv ddh G (t) + 1/p. As a conclusion, since G 3.Q+1.1 = G 3 , we have Adv 2 -Adv 3 ≤ 2Q(Adv ddh G (t)+1/p). In addition, Adv 3 = 0, which concludes the proof.

Games G 0 , G 1 , G 2 , (G 3.q.1 ) q∈[Q+1] , (G 3.q.2 , G 3.q.3 ) q∈[Q] G ← GGen(1 λ ), for all i ∈ [n], s i $ ← Z 2 p , ek i := s i , msk := ( s i ) i , mpk := (G, p, g). a $ ← Z p , a := ( 1 a ) , a ⊥ := ( -a 1 ) Sample a full-domain hash function H onto G 2 , and a bit b $ ← {0, 1}. b ← A QEncrypt(•,•,•,•),QDKeyGen(•),QCorrupt(•),RO(•) (mpk). Run Finalize on b . RO( ): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 [ u ] := H( ), [ u ] := RF( ) , [ u ] := [ a • r ], with r := RF ( )
On the q'th (fresh) query:

[ u ] := RF ( ) • a + RF ( ) • a ⊥ Return [ u ]. QEncrypt(i, x 0 i , x 1 i , ): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 [ u ] := RO( ), [c i ] := [ u ] • s i + [x b i ] If [ u ] is computed on the j RO-query, for j < q: [c i ] := [ u ] • s i + [x 0 i ] If [ u ] is computed on the q-th RO-query: [c i ] := [ u ] • s i + [x 0 i ] Return [c i ] QEncrypt(i, x i , ): // G 0 , {G 1,q,j } j=0•••4 Return QLeftRight(i, x i , x i , ).

QDKeyGen( y):

Return i y i s i . //G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 QCorrupt(i): Return s i . // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3
Figure 4.4: Games for the proof of Theorem 4.3. Here, RF, RF , RF are random functions onto G 2 , Z p , and Z * p , respectively, that are computed on the fly. In each procedure, the components inside a solid (dotted, gray) frame are only present in the games marked by a solid (dotted, gray) frame. The Finalize procedure is defined as in Definition 3.2.

Games (G 3.q.2 , G 3.q.3 ) q∈[Q] : state, (z i ∈ Z 2 p ∪ {⊥}) i∈[n] ← A(1 λ , 1 n ) G ← GGen(1 λ ), for all i ∈ [n], s i $ ← Z 2 p , ek i := s i , msk := ( s i ) i , mpk := (G, p, g). a $ ← Z p , a := ( 1 a ) , a ⊥ := ( -a 1 ) , b $ ← {0, 1}. b ← A QEncrypt(•,•,•,•),QDKeyGen(•),QCorrupt(•),RO(•) (mpk, state).
Run Finalize on b .

RO( ):

// G 3.q.2 , G 3.q.3 [ u ] := [ a • r ], with r := RF ( ) On the q'th (fresh) query:

[ u ] := [RF ( ) • a + RF ( ) • a ⊥ ] Return [ u ]. QEncrypt(i, x 0 i , x 1 i , ): // G 3.q.2 , G 3.q.3 [ u ] := RO( ), [c i ] := [ u ] • s i + [x b i ] If [ u ] is computed on the j-th RO-query with j < q: [c i ] := [ u ] • s i + [x 0 i ]. If [ u ] is computed on the q-th RO-query, then: • if (x 0 i , x 1 i ) = z i , the game ends and returns β $ ← {0, 1}. • otherwise, [c i ] := [ u ] • s i +[x b i ] +[x 0 i ] , S := S ∪ {i}. Return [c i ].

QEncrypt(i, x i , ):

// G 0 , {G 1,q,j } j=0•••4 Return QLeftRight(i, x i , x i , ).

QDKeyGen( y):

Return i y i s i . //G 3.q.2 , G 3.q.3 QCorrupt(i): // G 3.q.2 , G 3.q.3 If z i = (x 0 i , x 1 i ) with x 0 i = x 1
i , the game ends, and returns β $ ← {0, 1}. Return s i . Figure 4.5: Games G 3.q.2 and G 3.q.3 , with q ∈ [Q], for the proof of Theorem 4.3. Here, RF, RF are random functions onto G 2 , and Z p , respectively, that are computed on the fly. In each procedure, the components inside a solid (gray) frame are only present in the games marked by a solid (gray frame.

IP-DMCFE from multi-party computation

In this section, we convert an IP-MCFE into IP-DMCFE using a layer of multi-party computation (MPC). We first describe it and its characteristics then we provide a construction from [START_REF] Kursawe | Privacyfriendly aggregation for the smart-grid[END_REF] and a derivative. Finally, we explain how to apply this layer of a MCFE.

Distributed sum

In order to convert an MCFE scheme into a DMCFE, one needs to allow efficient distributed computation of the functional decryption key. In the case of our IP-MCFE, this can be seen as a particular MCFE for the unique sum function on the contributions of all the clients, since the key is dk y = ( y, i y i • s i ), and namely one has to compute i x i = i y i • s i , where the x i 's can be computed by each client. This primitive can also be considered as a two rounds secure MPC for the sum, called Private Stream Aggregation (PSA). This notion is an old primitive introduced by Shi et al. [SCR + 11]. It is quite similar to our target DMCFE scheme, however PSA does not consider the possibility of adaptively generating different keys for different inner product evaluations, but only enables the aggregator to compute the sum of the client's data for each time period. PSA also typically involves a Differential Privacy component, which has yet to be studied in the larger setting of DMCFE. Further research on PSA has focused on achieving new properties or better efficiency [CSS12, Emu17, JL13, LC13, LC12, BJL16] but not on enabling new functionalities.

Definition 5.1: Distributed Sum

A Distributed Sum (DSum) on a group G among n senders is defined by three algorithms:

• DSum.SetUp(λ): Takes as input the security parameter λ. Generates the public parameters pp and the personal secret keys sk i for i = 1 • • • n.

• DSum.Encode(x i , , sk i ): Takes the x i value to encode, a label and the personal secret key sk i of the user i. Returns the share M ,i .

• DSum.Combine( M ): Takes as input a vector M = (M ,i ) i of shares. Returns the value i M ,i .

Correctness. For any label , we want

Pr[DSum.Combine( M ) = i x i ] = 1,
where the probability is taken over

M ,i ← DSum.Encode(x i , , sk i ) for all i ∈ [n],
and (pp, (sk i ) i ) ← DSum.SetUp(λ) .

Security notion. This protocol must guarantee the privacy of the x i 's, their sum possibly excepted when all the shares are known. This is the classical security notion for MPC, where the security proof is performed by simulating the view of the adversary from the output of the result: nothing when not all the shares are asked, and just the sum of the inputs when all the shares are queried. We also have to deal with the corruptions, which give the users' secret keys.

DSum protocol in the random oracle model

The protocol below is similar to [START_REF] Kursawe | Privacyfriendly aggregation for the smart-grid[END_REF], with a hash function. We provide a new security analysis, which relies on the CDH problem in the Random Oracle Model.

• DSum.SetUp(λ): takes as input the security parameter λ and generates a group G of prime order p, with a generator g, were the CDH assumption holds. It also generates a hash function H : {0, 1} * → G, for any group G, denoted additively. Each user i, picks t i $ ← Z p . The public parameters pp are (G, p, g, H, ([t i ]) i ) and the personal secret keys sk i = t i for i = 1 • • • n (with the public parameters).

• DSum.Encode(x i , , sk i ): takes the x i value to encode, a label and the personal secret key sk i = t i of the user i, it returns M ,i computed as below, where

h ,i,j = H([t min{i,j} ], [t max{i,j} ], t i • [t j ], ) = h ,j,i : M ,i = x i -j<i h ,i,j + j>i h ,i,j .
• DSum.Combine( M = (M ,i ) i ): takes as input a vector M of shares. Computes and return the value i M ,i .

Correctness. The correctness should show that the sum of the shares is equal to the sum of the x i 's: the former is equal to

i   x i - j<i h ,i,j + j>i h ,i,j   = i x i - i j<i h ,i,j + i j>i h ,j,i = i x i - i j<i h ,i,j + j i<j h ,j,i = i x i

Security analysis

We now provide the proof of security for the DSum variant described above, under CDH assumption in the Random Oracle Model. We will prove that there exists a simulator that generates the view of the adversary from the output only. In this proof, we will assume static corruptions (the set CS of the corrupted clients is known from the beginning) and the hardness of the CDH problem. However, this construction will only tolerate up to n -2 corruptions, so that there are at least 2 honest users. But this is also the case for the MCFE. Proof W.l.o.g., we can assume that HS = {1, . . . , n-c} and CS = {n-c+1, . . . , n}, by simply reordering the clients, when CS is known. We will gradually modify the behavior of the simulator, with less and less powerful queries. At the beginning, the DSum.Encode-query takes all the same inputs as in the real game, including the secret keys. At the end, it should just take the sum (when all the queries have been asked), as well as the corrupted x j 's.

Game G 0 : the simulator runs as in the real game, with known CS.

Game G 1 : the simulator is given a group G with a generator g and a random pair (X = [t]; Y = [t 2 ]).

• DSum.SetUp: the simulator randomly chooses α i $ ← Z p , for i = 1, . . . , n -c, and defines

X i ← X + [α i ]. This sets t i = t + α i . It can also set Y i,j = CDH(X i , X j ) = Y + (α i + α j ) • X + [α i α j ], for i, j ≤ n -c. It then randomly choses t i ← Z p for i > n -c and sets X i = [t i ].
It can also generate all the other Y i,j = CDH(X i , X j )'s, using the known t i 's. It sends the X i 's as the pp, and the secret keys t i of the corrupted users.

• DSum.Encode(x i , ): the simulator generates all the required h ,i,j using the X j 's and Y i,j 's, querying the hash function, and returns

M ,i = x i -j<i h ,i,j + j>i h ,i,j .
Game G 2 : the simulator does as above, but just uses a random Y $ ← G instead of Y , to answer the DSum.Encode-queries.

This can make a difference for the adversary if the latter asks for the hash function on some tuple (X min{i,j} , X max{i,j} , CDH(X i , X j ), ), for i, j ≤ n -c, as this will not be the value h ,i,j , which has been computed using Y i,j = CDH(X i , X j ). In such a case, one can find CDH(X i , X

j ) = Y + [α i + α j ] • X + [α i α j ]
in the list of the hash queries, and thus extract Y = CDH(X, X). As a consequence, under the hardness of the square Diffie-Hellman problem (which is equivalent to the CDH problem), this simulation is indistinguishable from the previous one.

Game G 3 : the simulator does as above except for the DSum.Encode-queries.

If this is not the last-honest query under label , the simulator returns M ,i = -j<i h ,i,j + j>i h ,i,j ; for the last honest query, it returns

M ,i = S H -j<i h ,i,j + j>i h ,i,j
, where S H = j∈HS x j .

Actually, for a label , if we denote i the index of the honest player involved in the last query, the view of the adversary is exactly the same as if, for every i = i , we have replaced h ,i,i by h ,i,i + x i (if i > i) or by h ,i,i -x i (if i < i). We thus replace uniformly distributed variables by other uniformly distributed variables: this simulation is perfectly indistinguishable from the previous one.

Game G 4 : the simulator now ignores the values h ,i,j for honest i, j. But for each label, it knows the corrupted x j 's, and can thus compute the values M ,j for the corrupted users, using the corrupted x j 's and secret keys. If this is not the last honest query, it returns a random M ,i . For the last honest query, knowing S = j x j , it outputs M ,i = Sj =i M ,j .

As in the previous analysis, if one first sets all the h ,i,j , for j = i , this corresponds to define h ,i,i from M ,i , for i = i .

DSum protocol in the standard model

A variant of the protocol from Section 5.1.2 can also be described with a randomness extractor and a PRF. We then provide the security analysis under the DDH assumption and the PRF indistinguishability. More precisely, for the randomness extractor, we can use the Leftover-Hash-Lemma (see Theorem 2.1), with a random seed k in the common reference string to extract random keys K for a PRF (F K ) K , with a universal hash function (H k ) k :

• DSum.SetUp(λ): takes as input the security parameter λ and generates a group G of prime order p, with a generator g. From a family of universal hash functions (H k ) k and a random key k, this define the randomness extractor E(•) = H k (•), later used to generate the keys K of a PRF (F K ) K . Each user i, picks t i $ ← Z p . The public parameters pp are (G, p, g, E, (F K ) K , ([t i ]) i ) and the personal secret keys sk i = t i for i = 1 • • • n (with the public parameters).

• DSum.Encode(x i , , sk i ): takes the x i value to encode, a label and the personal secret key sk i = t i of the user i, it returns M ,i computed as below, where

h ,i,j = F K i,j ( ) with K i,j = E(t i • [t j ]): M ,i = x i -j<i h ,i,j + j>i h ,i,j .
• DSum.Combine( M = (M ,i ) i ): takes as input a vector M of shares. Computes and return the value i M ,i .

The correctness is the same as in Section 5.1.2, since it just makes use of h ,i,j . The security however requires the DDH assumption, in order to guarantee the randomness of all the Diffie-Hellman values [t i • t j ]. The Left-over-Hash Lemma thereafter ensures the uniform and independent distributions of the K i,j 's which then make the h ,i,j 's unpredictable for all the honest i, j.

Security analysis

In the section Section 5.1.3, we observe that we do not exploit programmability of the random oracle, and can actually use the Decisional Diffie-Hellman assumption to prove it in the standard model. The key used K i,j for F is E([t i t j ]), where E is a randomness extractor, and the input is .

Proof

We still assume that HS = {1, . . . , n -c}.

Game G 0 : the simulator runs as in the real game, with known CS (assumed to be {n -c + 1, . . . , n}, without loss of generality, since we are in the static corruption setting).

Game G 1 : the simulator does as above, but just uses a random value Y i,j $ ← G instead of the key [t i t j ], when both i = j ∈ HS, to generate the K i,j 's to answer the DSum.Encode-queries. After the hybrid sequence described below, the advantage for the adversary is:

|Adv G 0 (A) -Adv G 1 (A)| ≤ (n -c) 2 2 • Adv ddh (B),
for some adversary B running with a similar time as A.

Game G 2 : the simulator now uses random keys K i,j 's in the cases i < j are both honest, and K j,i = K i,j . Because of the entropy on the Y i,j 's, the Left-over-Hash Lemma guarantees a statistical indistinguishability with the previous game.

Game G 3 : The simulator now chooses random h ,i,j for any , in the cases i < j are both honest, and h ,j,i = h ,i,j . Under the indistinguishability of the PRF with random keys, this game is indistinguishable from G 2 . Now, the rest of the proof is similar to the previous one, with a final simulation as in above game G 4 .

Hybrid Sequence:

Here we present the hybrid games H i,j,k between G 0 and G 1 . An iteration of this sequence describes how to replace the value [t i * t j * ] used in the setup phasis, for honest i * < j * , by random Y i * ,j * $ ← G. The progression follows the lexicographical order on the pairs (i, j) ∈ HS where i < j, and Succ(i, j) denotes the next pair. It will be clear that G 0 = H 1,2,0 and G 1 = H n-c-1,n-c,3 . In addition, for all (1, 2) ≤ (i * , j * ) < (n -c -1, n -c), H i * ,j * ,3 = H Succ(i * ,j * ),0 . We indeed insist that K i,i is never used, so only Diffie-Hellman values for two different keys are used.

Game H i * ,j * ,0 : the simulator runs the real game, except that it additionally initializes Y i,j in the DSum.SetUp, used for the extracted keys K i,j = E(Y i,j ) during the DSum.Encode, either correctly as [t i t j ] or at random:

• DSum.SetUp: after having generated the group G of prime order p, with a generator g, the randomness extractor E(•), and the PRF (F K ) K , the simulator generates the secret keys t i $ ← Z p and sets X i ← [t i ], for all i. Then it defines:

for (i, j) < (i * , j * ), where i < j are both honest, pick a random element Y i,j $ ← G for (i, j) ≥ (i * , j * ), where i < j are both honest, set Y i,j ← [t i t j ] -for (i, j) where i < j and some of them is corrupted, set Y i,j ← [t i t j ] -for (i, j) where i > j, set Y i,j ← Y j,i It sends the X i 's as the pp, and the secret keys t i of the corrupted users.

Game H i * ,j * ,1 : for i * < j * , the simulator is given a group G with a generator g and a random Diffie-Hellman tuple

(X = [x], Y = [y], Z = [xy]).
• DSum.SetUp: it uses the above group G and generator g, and generates E and (F K ) K . For the indices i * , j * , the simulator defines

X i * ← X and X j * ← Y . This sets t i * ← x and t j * ← y. It can also set Y i * ,j * = CDH(X i * , X j * ) = Z. It then randomly chooses t i $ ← Z p for i = i * , j * and sets X i ← [t i ].
It can also generate Y i,j = CDH(X i , X j ), using the known t i , for (i, j) > (i * , j * ) and i < j. The cases (i, j) < (i * , j * ) for i < j and the cases i > j remain unchanged. It sends the X i 's as the pp, and the secret keys t i of the corrupted users.

The view of the adversary remains the same.

Game H i * ,j * ,2 : for i * < j * , the simulator is given a random tuple (X =

[x], Y = [y], Z $ ← G), and does as above. Under the hardness of the Decisional Diffie-Hellman problem, this simulation is indistinguishable from the previous one.

Game H i * ,j * ,3 : this is quite similar to game H i * ,j * ,0 , but with difference for (i, j) = (i * , j * ):

• DSum.SetUp: after having generated the group G of prime order p, with a generator g, the randomness extractor E(•), and the PRF (F K ) K , the simulator generates the secret keys t i $ ← Z p and sets X i ← [t i ], for all i. Then it defines:

for (i, j) ≤ (i * , j * ), where i < j are both honest, pick a random element Y i,j $ ← G for (i, j) > (i * , j * ), where i < j are both honest, set Y i,j ← [t i t j ] -for (i, j) where i < j and some of them is corrupted, set

Y i,j ← [t i t j ] -for (i, j) where i > j, set Y i,j ← Y j,i
The view of the adversary does not change.

Starting from (1, 2) up to (n -c -1, n -c), there are (n -c)(n -c -1)/2 cases with i * < j * which involve the DDH assumption, hence the conclusion.

Application to IP-DMCFE

Finally, one can generically convert an IP-MCFE into an IP-DMCFE, when dk y = y, d y , where d y = i x i , with the x i 's computed by each client, as x i ← y i • s i in [CDG + 18a], by letting the clients generating the DSum secret keys at the setup time, and the label is the vector y:

• SetUp(λ): runs the set-up of the IP-MCFE scheme plus DSum.SetUp(λ).

• DKeyGenShare(sk i , y): outputs M y,i ← DSum.Encode(x i , y, sk i ).

• DKeyComb((M y,i ) i , y): outputs the functional decryption key dk y = y, d y , where d y is publicly computed as DSum.Combine((M y,i ) i ).

In the last simulated game, we can now show that all the DKeyGenShare(sk i , y)-queries are simulated at random, excepted the last query that requires a DKeyGen-query to the IP-MCFE scheme to get the sum and program the output. Hence, unless all the queries are asked, the functional decryption key is unknown. However, this proof system forces statical security in the final DMCFE, meaning that the adversary decides the set of corrupted users on the beginning of the security game (Definition 3.2).

Remark : This technique is in the same vein as the idea introduced in a recent independent work [ACF + 19]. In that work, the SetUp is fully decentralized by definition, and their construction uses a two-round MPC scheme in a same way as we do with the DSum: one round in the SetUp to output public parameters and another in the decryption key generation to compute the key. This potentially generalizes our method to several other functionalities.

IP-DMCFE from pairings

While the transformation using DSum is quite generic, our original decentralized scheme from [CDG + 18a] relies on pairing groups. The idea, however, remains the same: using an existing MCFE, but making the decryption key with a MPC scheme. In this section, the decryption key is build with another MCFE scheme.

Overview

Our construction from Section 4.2.1 (or Section 4.2.3 if we double s i ) uses functional decryption keys dk y = ( y, i s i y i ) = ( y, dk), where dk = s, y = i s i y i = t, 1 , with t i = s i y i , for i = 1, . . . , n, and 1 = (1, . . . , 1). Hence, one can split msk = s into msk i = s i and define F ( t) = t, 1 . We could thus wish to use one of the MCFE constructions for inner product from Section 4.2 to describe a DMCFE for inner product. However, this is not straightforward as those schemes only allow small results for the function evaluations, since a discrete logarithm has to be computed. While, for real-life applications, it might be reasonable to assume the plaintexts and any evaluations on them are small enough, it is impossible to recover such a large scalar as dk = s, y , which comes up when we use our scheme to encrypt encryption keys. Nevertheless, following this idea we can overcome the concern above with pairings: one can only recover [dk], but using a pairing e : G 1 × G 2 → G T , one can use our MCFE in both G 1 and G 2 . This allows us to compute the functional decryption in G T , to get [ x, y ] T , which is decryptable as x, y is small enough.

Construction

Let us describe the new construction, using an asymmetric pairing group, as in Section 2.1.

• SetUp(λ): generates PG := (G 1 , G 2 , p, P 1 , P 2 , e) $ ← PGGen(1 λ ). Samples two full-domain hash functions H 1 and H 2 onto G 2 1 and G 2 2 respectively. Each sender

S i generates s i $ ← Z 2 p for all i ∈ [n],
and interactively generates

T i $ ← Z 2×2 p such that i∈[n] T i = 0.
One then sets mpk ← (PG, H 1 , H 2 ), and for i = 1, . . . , n, ek i = s i , sk i = ( s i , T i ).

• Encrypt(ek i , x i , ): takes as input the value x i to encrypt, under the key ek i = s i and the label . It computes

[ u ] 1 := H 1 ( ) ∈ G 2 1 ,

and outputs the ciphertext

[c i ] 1 = [ u s i + x i ] 1 ∈ G 1 .
• DKeyGenShare(sk i , y): on input y ∈ Z n p that defines the function f y ( x) = x, y , and the secret key

sk i = ( s i , T i ), it computes [ v y ] 2 := H 2 ( y) ∈ G 2 2 , [ d i ] 2 := [y i • s i + T i v y ] 2 ,
and returns the partial decryption key as dk y,i := ([

d i ] 2 ). • DKeyComb((dk y,i ) i∈[n] , y): the partial decryption keys dk y,i = ([ d i ] 2 ) i∈[n] , lead to dk y := ( y, [ d] 2 ), where [ d] 2 = i∈[n] [ d i ] 2 .
• Decrypt(dk y , , ([c i ] 1 ) i∈ [n] ): on input the decryption key dk y = [ d] 2 , the label , and ciphertexts

([c i ] 1 ) i∈[n] , it computes [α] T := i∈[n] e([c i ] 1 , [y i ] 2 )-e([ u ] 1 , [ d] 2 ),
and eventually solve the discrete logarithm in basis [1] T to extract and return α.

Correctness: Let x, y ∈ Z n p , we have:

[ d] 2 = i∈[n] [ d i ] 2 = i∈[n] [y i • s i + T i v y ] 2 = [ i∈[n] y i • s i ] 2 + [ v y ] 2 • i∈[n] T i = [ i∈[n] y i • s i ] 2 .
Thus:

[α] T := i∈[n] e([c i ] 1 , [y i ] 2 ) -e([ u ] 1 , [ d] 2 ) = i [( u s i + x i )y i ] T -[ i∈[n] y i u s i ] T = [ i x i y i ] T .

Compatibility

Our constructions from Section 4.2 use a prime-order group, while this one uses pairing groups. Since the latter use the former as a building block, we must use groups that are compatible with each other. Notice that one can generate a prime-order group either with G := (G, p, P ) $ ← GGen(1 λ ), but also using PG := (G 1 , G 2 , p, P 1 , P 2 , e) $ ← PGGen(1 λ ), and setting G := G 1 . This is possible here because we use asymmetric pairings and rely on the SXDH assumption in the pairing group, which is DDH in G 1 and G 2 (see Section 2.3).

Security analysis Theorem 5.1: sta-wtr-IND * -Security

The above DMCFE protocol (see Section 5.2.1) is sta-wtr-IND * -secure under the SXDH assumption, in the random oracle model. Namely, for any PPT adversary A, there exist PPT adversaries B 1 and B 2 such that:

Adv IND (A) ≤ 2Q 1 • Adv ddh G 1 (t) + 2Q 2 • Adv ddh G 2 (t) + 2Q 1 + 2Q 2 p + Adv ddh G 1 (t + 4Q 1 × t G 1 ) + 2 • Adv ddh G 2 (t + 4Q 2 × t G 2 ),
where Q 1 and Q 2 are the number of (direct and indirect) queries to H 1 and H 2 respectively (modeled as random oracles). The former being asked by QLeftRight-queries and the latter being asked by QDKeyGen-queries.

We stress that the above Theorem supports adaptive encryption queries, but static corruptions only. To prove it, we proceed using hybrid games, described in Fig. 5.1.

Proof

Game G 0 : this is the sta-wtr-IND * -security game as given in Section 3.2.2, but with the set CS of corrupted senders known from the beginning. Note that the hash functions H 1 and H 2 are modeled as random oracles. The former is used to generate

[ u ] 1 := H 1 ( ) ∈ G 2 1 and the latter [ v y ] 2 := H 2 ( y) ∈ G 2 2 .
Game G 1 : we replace the hash function H 2 by a random oracle RO 2 that generates random pairs from G 2 2 on the fly. In addition, for any QDKeyGenquery on a corrupted index i ∈ CS, one generates the partial functional decryption key by itself, without explicitly querying QDKeyGen. Hence, we can assume that A does not query QCorrupt and QDKeyGen on the same indices i ∈ [n]. The simulation remains perfect, and so Adv 0 = Adv 1 .

Game G 2 : now, the outputs of RO 2 are uniformly random in the span of

[ b] 2 for b := ( 1 a ) , with a $ ← Z p . As in the previous proof, we have

Adv 1 -Adv 2 ≤ Adv ddh G 2 (t + 4Q 2 × t G 2 )
, where Q 2 is the number of RO 2queries and t G 2 the time for an exponentiation.

Game G 3 : we replace all the partial key decryption answers by dk y,i :

= [y i • s i + w i • ( b ⊥ ) v y + T i v y ] 2 , for new w i $ ← Z 2
p , such that i w i = 0, for each y. This sum being among the honest clients, we need to know the last queried honest client to set this sum to zero. Hence the requirement to know the set of honest clients, and thus just security against static corruptions. We show below that Adv 2 = Adv 3 .

Game G 4 : we switch back the distribution of all the vectors [ v y ] 2 output by RO 2 , from uniformly random in the span of [ b] 2 , to uniformly random over G 2 2 , thus back to H 2 ( y). This transition is reverse to the two first transitions of this proof:

Adv 3 -Adv 4 ≤ Adv ddh G 2 (t + 4Q 2 × t G 2 ).
In order to prove the gap between G 2 and G 3 , we do a new hybrid proof:

Game G 3.1.1 : this is exactly game G 2 . Thus, Adv 2 = Adv 3.1.1 . G 3.q.1
G 3.q.2 : as in the previous proof, we first change the distribution of the output of the q-th RO 2 -query, from uniformly random in the span of [ b] to uniformly random over G 2 , using the DDH assumption. Then, we use the basis (( 1 a ) ,( -a 1 ) ) of Z 2 p , to write a uniformly random vector over

Z 2 p as v 1 • b + v 2 • b ⊥ , where v 1 , v 2 $ ← Z p . Finally, we switch to v 1 • b + v 2 • b ⊥ where v 1 $ ← Z p , and v 2 $ ← Z *
p , which only changes the adversary view by a statistical distance of 1/p: Adv 3.q.1 -Adv 3.q.2 ≤ Adv ddh G (t) + 1/p. The last step with v 2 ∈ Z * p will be important to guarantee that v y b ⊥ = 0.

G 3.q.2 G 3.q.3 : we now change the simulation of dk y,i from dk

y,i = [y i • s i +T i v y ] 2 to dk y,i = [y i • s i + RF i ( y) + T i v y ] 2 ,
with some RF i functions onto Z 2 p such that i RF i ( y) = 0 for any input y. We prove Adv 3.q.2 = Adv 3.q.3 .

To this aim, we use the fact that the two following distributions are identical, for any choice of w i $ ← Z 2 p , such that i w i = 0:

(T i ) i∈HS and (T i + w i ( b ⊥ ) ) i∈HS ,
where for all i ∈

[n], T i $ ← Z 2×2 p such that i T i = 0,
i • s i + w i • ( b ⊥ ) v y + T i v y ] 2 . Since v y is such that v y b ⊥ = 0, ( b ⊥ ) v y = 0. In that case, the vectors w i • ( b ⊥ ) v y are uniformly random over Z 2 p such that i w i • ( b ⊥ ) v y = 0, which is as in G 3.q.3 , by setting RF i ( y) := w i • ( b ⊥ ) v y . G 3.q.3
G 3.q+1.1 : this transition is the reverse of G 3.q.1 G 3.q.2 , namely, we use the DDH assumption to switch back the distribution of

[ v y ] 2 to uniformly random in the span of [ b] 2 : Adv 3.q.3 -Adv 3.q+1.1 ≤ Adv ddh G 2 (t) + 1/p.
Then one can note that

G 3.Q 2 +1.1 = G 3 , but
:= i s i • y i ∈ Z 2 p , computes [ v y ] 2 := H 2 ( y)
, and returns dk y,i := [dk y + RF i ( y) + T i v y ] 2 to A. Otherwise, it computes [ v y ] 2 := H 2 ( y), and returns dk y,i := [RF i ( y)+T i v y ] 2 to A. The random functions RF i are computed on the fly, such that their sum is the zero function.

We stress that this last simulation requires to know CS and HS, hence static corruptions only. From this reduction, one gets

Adv 4 ≤ 2Q 1 • Adv ddh G 1 (t) + Adv ddh G 1 (t + 4Q 1 × t G 1 ) + 2Q 1 p ,
where Q 1 denotes the number of calls to RO 1 , t G 1 denotes the time to compute an exponentiation in G 1 . This concludes the proof.

Games G 0 , G 1 , G 2 , (G 3.q.1 ) q∈[Q dk +1] , (G 3.q.2 , G 3.q.3 ) q∈[Q dk ] , G 4 PG ← PGGen(1 λ ), ∀i ∈ [n]: s i $ ← Z 2 p , T i $ ← Z 2×2 p , such that i∈[n] T i = 0 ek i := s i , sk i := ( s i , T i ), mpk := (G, p, g). a $ ← Z p , b := ( 1 a ) Sample full-domain hash functions H 1 onto G 2 1 and H 2 onto G 2 2 . Sample a bit b $ ← {0, 1}. b ← A QEncrypt(•,•,•,•),QDKeyGen(•,•),QCorrupt(•),RO 1 (•),RO 2 (•) (mpk). Run Finalize on b . RO 1 ( ): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 Return H 1 ( ). RO 2 ( y): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 , G 4 [ v y ] 2 := H 2 ( y), [ v y ] 2 := RF( y) , [ v y ] 2 := [ b • t y ] 2 , with t y := RF ( y).
On the q-th RO 2 -query:

[ v y ] 2 := RF( y). Return [ v y ] 2 . QLeftRight(i, x 0 i , x 1 i , ): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 , G 4 [ u ] 1 := RO 1 ( ). [c i ] 1 := [ u ] 1 • s i + [x b i ] 1 . Return [c i ]. QEncrypt(i, x i , ): // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 , G 4 [c i ] 1 := QLeftRight(i, x i , x i , ) Return [c i ] QDKeyGen( y, i): //G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 , G 4 Compute [ v y ] 2 := RO 2 ( y), dk y,i := [y i • s i + T i v y ] 2 , set S := S ∪ {i}. If [ v y ] 2 is computed on the j-th RO 2 -query, for j < q: dk y,i := [y i • s i + RF i ( y) + T i v y ] 2 . If [ v y ] 2 is computed on the q-th RO 2 -query: dk y,i := [y i • s i + RF i ( y) + T i v y ] 2 . dk y,i := [y i • s i + RF i ( y) + T i v y ] 2 .
Return dk y,i .

QCorrupt(i): Return ( s i , T i ). // G 0 , G 1 , G 2 , G 3.q.1 , G 3.q.2 , G 3.q.3 , G 4 Figure 5
.1: Games for the proof of Theorem 5.1. Here, RF, RF are random functions onto G 2 2 and Z p , respectively, that are computed on the fly. The RF i are random functions conditioned on the fact that i∈[n] RF i is the zero function. In each procedure, the components inside a solid (dotted, gray) frame are only present in the games marked by a solid (dotted, gray) frame. The Finalize procedure is defined as in Section 3.2.2.

From IND* to IND with secret sharing encapsulation

As explained in Section 3.1.2, the main difference between the IND notion and the IND * , is that incomplete ciphertexts were considered illegitimate. This was with the intuition that no adversary should use it since this leaks no information. But actually, an adversary could exploit that in the real-life, especially in the scheme from [CDG + 18a] which use homomorphic properties. The IND notion requires the scheme to actually leak nothing in such a case.

In this section, we present a generic layer, called the secret sharing encapsulation (SSE), that we will use to encapsulate ciphertexts from a MCFE scheme. It allows a user to recover the ciphertexts from the n senders only when he gets the contributions of all the servers. That is, if one sender did not send anything, the user cannot get any information from any of the ciphertexts of the other senders. More concretely, a share of a key S ,i is generated for each user i ∈ [n] and each label . Unless all the shares S i, have been generated, the encapsulation keys are random and mask all the ciphertexts.

After giving the definition of SSE, we provide a construction whose security is based on the DBDH assumption, and we show how to apply it on any MCFE scheme.

Definitions for secret sharing encapsulation Definition 6.1: Secret Sharing Encapsulation

A Secret Sharing Encapsulation (SSE) on K over a set of n senders is defined by four algorithms:

• SSE.SetUp(λ): on input a security parameter λ, generates the public parameters pk sse and the personal encryption keys are ek sse,i for all i ∈ [n].

• SSE.Encaps(pk sse , ): on input pk sse and the label , outputs a ciphertext C and an encapsulation key K ∈ K.

• SSE.Share(ek sse,i , ): on input ek sse,i and the label , outputs the share S ,i .

• SSE.Decaps(pk sse , (S ,i ) i∈[n] , , C ): on input all the shares S ,i for all i ∈ [n], a label , and a ciphertext C , outputs the encapsulation key K .

Correctness. For any label , we have: Indistinguishability. We want to show that the encapsulated keys are indistinguishable from random if not all the shares are known to the adversary. We could define a Real-or-Random security game [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF] for all the masks. Instead, we limit the Real-or-Random queries to one label only, and for all the other labels, the adversary can do the encapsulation by itself, since it just uses a public key. This is well-known that a hybrid proof among the label indices (the order they appear in the game)

Pr[SSE.Decaps(pk sse , (S ,i ) i∈[n] , , C ) = K ] = 1,
• SSE.Decaps(pk sse , (S ,i ) i∈[n] , , C ): takes as input all the shares S ,i for all i ∈ [n], a label and a ciphertext C , and outputs an encapsulation key

K = e j S ,j , C .
We stress here that K is not unique for each label : whereas S ,i deterministically depends on and the client i, K is randomized by the random coins r in C . Hence, with all the shares, using a specific C , one can recover the associated K .

Correctness. It follows from the fact that the above decapsulated key K is equal to:

e j t j H sse ( ), [r] 2 = e H sse ( ), [r • j t j ] 2 ,
where the pair (C , K ) has been generated by SSE.Encaps(pk sse , ) with random r.

Security analysis

The intuition for the security is that given all the S ,i = t i • H sse ( ) for a label , one can recover the masks K = e(H sse ( ), [r j t j ] 2 ) using C = [r] 2 . However if S ,i is missing for one slot i, then all the encapsulation keys K are pseudo-random, from the DBDH assumption.

Theorem 6.1

Let A be a PPT adversary against the security of the above SSE. We can build a PPT adversary B against the q r -fold DBDH such that:

Adv 1-Label-IND SSE (A) ≤ (1 + q h ) • Adv qr-DBDH PG (B),
where q h denotes the number of H sse queries (explicit or implicit) and q r the number of challenge-queries to the QRealRandom oracle.

Applying Lemma Lemma 2.1, one can reduce the security to the DBDH assumption. Here we describe the construction of such an adversary:

Proof B receives a q r -fold DBDH challenge PG, [a] 1 , [b] 1 , [b] 2 , {[c i ] 2 , [s i ] T } i∈[qr]
, where q r denotes the number of queries of A to its oracle QRealRandom, and receives

i ∈ [n] from A.
Then, B guesses ρ $ ← {0, . . . , q h }. Intuitively, ρ is a guess on when the random oracle is going to be queried on , the first label used as input to QRealRandom (without loss of generality, we can assume QRealRandom is queried at least once by A, otherwise the security is trivially satisfied), with ρ = 0 indicating that the adversary never queries H sse on before querying QRealRandom.

Then, B samples t i $ ← Z p and sets ek sse,i := t i for all i ∈ [n], i = i , and sets

[t i ] 2 = [b] 2 . It returns pk sse = (PG, [ t] 2 ) to A.
For any query QCorrupt(i): if i = i , B returns ek sse,i , otherwise B stops simulating the experiment for A and returns 0 to its own experiment.

For any query to the random oracle H sse , if this the ρ'th new query, then B sets H sse ( ρ ) := [a] 1 . For others queries, B outputs [h] 1 for a random h $ ← Z p . B keeps track of the queries and outputs to the random oracle H sse , so that it answers two identical queries with the same output.

For any query to QRealRandom( ): if has never been queried to the random oracle H sse before (directly, or indirectly via QShare) and ρ = 0, then B sets H sse ( ) := [a] 1 ; if was queried to random oracle as the ρ'th new query (again, we consider direct and indirect queries to H sse , the latter coming from QShare), then we already have

H sse ( ) = [a] 1 . In both cases, B sets C ← [c j ] 2 , for the next index j in the q r -fold DBDH instance, computes K ← [s j ] T + e([a] 1 , ( i =i t i ) • [c j ] 2 ),
and returns (C , K ) to A. Otherwise, the guess ρ was incorrect: B stops simulating the experiment for A, and returns 0 to its own experiment. Moreover, if A ever calls QRealRandom on different labels , then B stops simulating this experiment for A and returns 0 to its own experiment.

For any query to QShare(i, ): if the random has been called on , then B uses the already computed input H sse ( ); otherwise, it computes H sse ( ) for the first time as explained above. If i = i and = ρ , then B stops simulating the experiment for A and returns 0 to its own experiment. Otherwise, that means either i = i , in which case B knows t i ∈ Z p , or = ρ , in which case B the discrete logarithm of H sse ( ). In both cases, B can compute

S ,i := t i • H sse ( ) ∈ G 1 , which it returns to A.
At the end of the experiment, B receives the output α from A. If its guess ρ was correct, B outputs α to its own experiment, otherwise, it ignores α and returns 0.

When B's guess is incorrect, it returns 0 to its experiment. Otherwise, when it is given as input a real q r -fold DBDH challenge, that is s j = abc j for all indices j ∈ [q r ], then B simulates the 1-Label-IND security game with b = 0. Indeed, since b = t i , for the j-th query to QRealRandom, we have:

K = [s j ] T + e([a] 1 , ( i =i t i ) • [c j ] 2 ) = [abc j ] T + e([a] 1 , ( i =i t i ) • [c j ] 2 ) = e([a] 1 , [bc j ] 2 ) + e([a] 1 , ( i =i t i ) • [c j ] 2 ) = e([a] 1 , [bc j ] 2 + ( i =i t i ) • [c j ] 2 ) = e([a] 1 , (b + i =i t i ) • [c j ] 2 ) = e([a] 1 , i t i • [c j ] 2 ) = e(H sse ( ), i t i • [c j ] 2 )
where C = [c j ] 2 . When given as input a random q r -fold DBDH challenge, the simulation corresponds to the case b = 1. Finally, we conclude using the fact that the guess ρ is correct with probability exactly 1 q h +1 .

Generic construction of IND-secure MCFE

We now show how we can enhance the security of any MCFE using a SSE as defined in Definition 6.1. Namely, we show that the following construction is IND secure if the underlying MCFE is IND * -secure, thereby removing the complete-ciphertext restriction, as incomplete ciphertexts do not leak any information thanks to the SSE layer.

Let MCFE = (SetUp, Encrypt, DKeyGen, FDecrypt, Decrypt) be a MCFE scheme, SSE = (SSE.SetUp, SSE.Encaps, SSE.Decaps) be a SSE scheme, and SKE = (SEnc, SDec) be a Symmetric Key Encryption scheme (Definition 2.5) with same key space as SSE, and whose message space is the ciphertext space of MCFE. We define MCFE = (SetUp , Encrypt , DKeyGen , FDecrypt , Decrypt ) as follows:

• SetUp (λ): it executes (mpk, msk, (ek i ) i ) ← SetUp(λ) and (pk sse , (ek sse,i ) i ) ← SSE.SetUp(λ). The public parameters mpk consist of mpk ∪ pk sse , while the encryption keys are ek i = ek i ∪ ek sse,i for i = 1, . . . , n, and the master secret key is msk = msk.

• Encrypt (ek i , x i , ): it parses the encryption key ek i as ek i ∪ ek sse,i , runs C ,i ← Encrypt(ek i , x i , ), executes (D ,i , K ,i ) ← SSE.Encaps(pk sse , ), and S ,i ← SSE.Share(ek sse,i , ). The ciphertext C ,i is then set to the tuple (E ,i = SEnc(K ,i , C ,i ), D ,i , S ,i ).

• DKeyGen (msk , f ): with msk = msk , it runs dk f = DKeyGen(msk, f ).

• FDecrypt (dk f , , (C ,i ) i∈ [n] ): takes as input a functional decryption key dk f , a label , and ciphertexts ).

(C ,i = (E ,i , D ,i , S ,i )) i∈[n] . It
Remark : Because the DSum protocol (described in Section 5.1), the SSE (described in Section 6.1) and the original MCFE from [CDG + 18a] (recalled in Section 4.2.3) all have a decentralized setup, the resulting scheme also enjoys the same property, thereby completely getting rid of the need for a trusted party generating the private keys.

Security analysis

We show that this generic construction MCFE achieves IND-security, assuming the underlying MCFE is IND * -secure (see Definition 3.2), SSE is 1-Label-IND-secure (see Definition 6.2), and the symmetric encryption is one-time secure (see definition in Definition 2.6). More precisely, we can state the following security result: Theorem 6.2 For any adversary A running within time t, against the IND-security of the above MCFE',

Adv IND MCFE (A) ≤ (n + 1) • L × Adv IND * MCFE (t) + 2 • Adv 1-Label-IND SSE (t ) +q e • Adv OT SKE (t )
, with t and t quite close to t, where L is the total number of labels queried to the oracle QLeftRight , and q e is the maximum number of queries to QLeftRight

Proof

Actually, two cases can happen between games G ρ-1 and G ρ , for each ρ ∈ {1, . . . , L}: either all the honest components of the ciphertext are generated under ρ or not all of them. We first make the guess, and then deal with the two cases: if they are all generated (for honest clients), this is the simple IND * security game for the underlying MCFE, otherwise there is an honest index i * for which the ciphertext has not been generated, and the SSE scheme will help, together with the symmetric encryption scheme:

Guess of the case for the ρ : We define a new sequence of hybrid games G * ρ for all ρ = 0, . . . , n, which is exactly as above, except that a guess for the missing honest-client ciphertext i * under ρ is performed (i * = 0 means that all the honest-client ciphertexts are expected to be generated under ρ ):

• Initialize: it first makes a guess for i * $ ← {0, . . . , n}, and then does as in G ρ .

• QEncrypt (i, x, j ), QLeftRight (i, x 0 , x 1 , j ), QDKeyGen (f ), QCorrupt (i),
as in G ρ .

• Finalize: as in G ρ , except if i * = 0, but not all the honest ciphertexts under ρ have been asked.

i * = 0, but client i * is corrupted.

i * = 0, but the i * -th client ciphertext has been asked under ρ .

in which cases a random bit is output.

Since G * ρ and G ρ are the same when the guess incorrect, which happens with probability exactly 1/(n+1), for any adversary A:

Adv Gρ (A) = (n+1)•Adv G * ρ (A).
All the ciphertexts are generated under ρ : Under the condition that A asks for all the honest ciphertexts under ρ , which means the correct guess is i * = 0, we build a PPT adversary B ρ against the

IND * security of MCFE such that |Adv G * ρ-1 (A ∧ i * = 0) -Adv G * ρ (A ∧ i * = 0)| ≤ Adv IND * MCFE (B ρ ).
B ρ simulates the IND-adversary A's view as follows:

• Initialize: it obtains mpk from its own IND * -security game for MCFE, samples (pk sse , (ek sse,i ) i∈[n] ) ← SSE.SetUp(λ) and returns mpk = mpk ∪ pk sse to the adversary A.

• QEncrypt (i, x, j ): it uses its own encryption oracle QEncrypt to get C j ,i ← QEncrypt(i, x, j ). Then, it computes (D j ,i , K j ,i ) ← SSE.Encaps(pk sse , j ), and S j ,i ← SSE.Share(ek sse,i , j ). Eventually, it computes and returns the ciphertext (E j ,i = SEnc(K j ,i , C j ,i ), D j , S j ,i ).

• QLeftRight (i, x 0 , x 1 , j ):

if j < ρ, it uses its own encryption oracle QEncrypt to get the ciphertext C j ,i ← QEncrypt(i, x 1 , j ).

if j > ρ, it uses its own encryption oracle QEncrypt to get the ciphertext C j ,i ← QEncrypt(i, x 0 , j ).

if j = ρ, then it uses its own left-or-right encryption oracle to get the ciphertext C j ,i ← QLeftRight(i, x 0 , x 1 , ρ ).

Then, it computes the encapsulation (D j ,i , K j ,i ) ← SSE.Encaps(pk sse , j ) and the share S j ,i ← SSE.Share(ek sse,i , j ). Eventually, it returns the ciphertext (E j ,i = SEnc(K j ,i , C j ,i ), D j ,i , S j ,i ).

• QCorrupt (i): it uses its own corruption oracle to get ek i ← QCorrupt(i), and returns ek i = ek i ∪ ek sse,i .

• Finalize: B ρ checks whether all the honest ciphertexts under ρ have been asked. If not, it ignores A's guess and sends a uniformly random bit β $ ← {0, 1}. Otherwise, it forwards A's guess to the Finalize procedure of the IND * -security game.

When the guess i * = 0 is correct, the queries B ρ makes to its QLeftRight oracle are valid, i.e. they don't make the Finalize procedure output a uniformly random bit (independent of B ρ 's guess). Indeed, if QLeftRight(i, •, •, ρ ) is queried for some i ∈ [n], then for all slots j ∈ HS, QLeftRight(j, •, •, ρ ) is also queried. Thus, we can use the IND * security of MCFE to switch Encrypt (ek i , x 0 , ρ ) as in game G * ρ-1 to Encrypt (ek i , x 1 , ρ ) as in game G * ρ . Some ciphertexts are missing under ρ : For β ∈ {0, 1}, we define the game H ρ,β as G * ρ , except that when i * = 0, QEncrypt (i, x, ρ ) encrypts x and QLeftRight (i, x 0 , x 1 , ρ ) encrypts x β in C ρ,i , then they both generate the encapsulation (D ρ,i , K ρ,i ) ← SSE.Encaps(pk sse , ρ ) and the share S ρ,i ← SSE.Share(ek sse,i , ρ ), sample a fresh key K ρ,i $ ← K at random in the key space, and return the ciphertext

(E ρ,i = SEnc(K ρ,i , C ρ,i ), D ρ,i , S ρ,i ).
Now, we build PPT adversaries B ρ,0 and B ρ,1 against the 1-Label-INDsecurity of the SSE such that

|Adv G * ρ-1 (A ∧ i * = 0) -Adv H ρ,0 (A ∧ i * = 0)| ≤ Adv 1-Label-IND SSE (B ρ,0 ) and |Adv G * ρ (A ∧ i * = 0) -Adv H ρ,1 (A ∧ i * = 0)| ≤ Adv 1-Label-IND SSE (B ρ,1 ).
Let β ∈ {0, 1}. We proceed to describe B ρ,β . First, B ρ,β samples the guess i * $ ← {0, . . . , n}. If i * = 0, then B ρ,β behaves exactly as the challenger in the game G * ρ-1+β . Otherwise, it does the following, using the 1-Label-IND-security game against SSE:

• Initialize: it generates (mpk, msk, (ek i ) i∈ [n] ) ← SetUp(λ), and sends i * to receive pk sse from its own 1-Label-IND challenger for SSE. It returns mpk = mpk ∪ pk sse to the adversary A.

• QEncrypt (i, x, j ): it can compute C j ,i ← Encrypt(ek i , x, j ). Then, it call its own oracle to get S j ,i ← QShare(i, j ).

If j = ρ, it computes (D j ,i , K j ,i ) ← SSE.Encaps(pk sse , j ); if j = ρ, it calls (D ρ,i , K ρ,i ) ← QRealRandom( ρ ).
Eventually, it returns the ciphertext

E j ,i = (SEnc(K j ,i , C j ,i ), D j ,i , S j ,i ) • QLeftRight (i, x 0 , x 1 , j ): if j < ρ, it computes C j ,i = Encrypt(ek i , x 1 , j ); if j > ρ, it computes C j ,i = Encrypt(ek i , x 0 , j ); and if j = ρ, it computes C j ,i = Encrypt(ek i , x β , j ).
Then it calls its own oracle to get S j ,i = QShare(i, j ). If j = ρ, it computes (D j ,i , K j ,i ) ← SSE.Encaps(pk sse , j );

if j = ρ, it calls (D ρ,i , K ρ,i ) ← QRealRandom( ρ ).
Eventually, it returns the ciphertext (E j ,i = SEnc(K j ,i , C j ,i ), D j ,i , S j ,i ).

• QDKeyGen (f ): it runs and returns DKeyGen(msk, f ).

• QCorrupt (i): it uses its own corruption oracle to get ek sse,i ← QCorrupt(i), and returns ek i = ek i ∪ ek sse,i .

• Finalize: B ρ,β checks whether the ciphertext for the i * -th client has been asked under ρ , or corrupted. If so, it ignores A's guess and sends a uniformly random bit β $ ← {0, 1}. Otherwise, it forwards A's guess to the Finalize procedure of the IND * -security game.

Game G ρ , which encrypts x 1 under ρ , just differs from H ρ,1 with real vs. random keys K ρ , as emulated by B ρ,1 , according to the real-or-random behavior of the 1-Label-IND game for SSE. Game G ρ-1 , which encrypts x 0 under ρ , just differs from H ρ,0 with real vs. random keys K ρ , as emulated by B ρ,0 , according to the real-or-random behavior of the 1-Label-IND game for SSE. Note that if adversary A makes queries that satisfy the conditions required by the Finalize procedure from the game IND * of MCFE , and that the guess i * = 0 is correct, then the queries of B ρ,β satisfy the conditions required by the 1-Label-IND security game for SSE, namely, QRealRandom is only queried on one label ρ , QCorrupt is never queried on i * , and QShare is never queried on (i * , ρ ).

Note that in the case the guess i * = 0 is correct, in the IND-security game, the adversary can ask QLeftRight queries on users i ∈ CS for the label ρ , which was not allowed in the original IND * -security game (and would lead to a random output). The reason is that security here relies on the 1-Label-IND security of the SSE for the label ρ . In the simulation, no matter what is encrypted in C ρ,i under the label ρ , the QRealRandom algorithm provides randomness and makes the ciphertexts C ρ,i impossible to recover.

Since the encapsulation keys K ρ are uniformly random in games H ρ,0 and H ρ,1 , we can use the one-time security of SKE, for each ciphertext for the label ρ , to obtain a PPT adversary B ρ such that:

|Adv H ρ,0 (A ∧ i * = 0) -Adv H ρ,1 (A ∧ i * = 0)| ≤ q e • Adv OT SKE (B ρ ),
where q e denotes maximum number of ciphertexts generated by the QLeftRight oracle for a given label.

Putting everything together, for the case i * = 0, we obtain PPT adversaries B ρ and B ρ such that:

|Adv G * ρ-1 (A ∧ i * = 0) -Adv G * ρ (A ∧ i * = 0)| is upper- bounded by 2 • Adv 1-Label-IND SSE (B ρ ) + q e • Adv OT SKE (B ρ )).
Since for any game G and any adversary A, Adv G (A) = Adv G (A ∧ i * = 0) + Adv G (A ∧ i * = 0), this concludes the proof of Lemma 6.1.

Bridge between MIFE and MCFE

In this section, we add a layer of IP-FE on top of the IP-MCFE from Section 4.2.3, to remove the restriction of having a unique challenge ciphertext per client and per label. This way, our IP-MCFE really captures the MIFE formalism on one label (see Section 3.1.1) in the case of the inner product functionality.

Overview

Our construction works for any IP-FE that is compatible with the IP-MCFE from Section 4.2.3, namely, an IP-FE whose message space is the ciphertext space of the IP-MCFE.

For correctness, we exploit the fact that decryption of the IP-MCFE computes the inner product of the ciphertext together with the decryption keys. Also, we make use of the fact that the encryption algorithm can act on vectors of group elements, in G m , where G is a prime-order group, as opposed to vectors over Z. Decryption recovers the inner product in the group G, without any restriction on the size of the input of the encryption and decryption key generation algorithms. Namely, the message space of IP-FE is G m , for some dimension m, its decryption key space is Z m p , where p is the order of G, and for any [ x] ∈ G m , y ∈ Z m p , IP.Dec(ct, dk y ) = [ x y] with probability one, where ct ← IP.Encrypt(IP.msk, [ x]), dk y ← IP.DKeyGen(IP.msk, y), and (IP.mpk, IP.msk) ← IP.SetUp(λ)

For security, we exploit the fact that this IP-MCFE is linearly homomorphic, in the sense that given an input x, one can publicly maul an encryption of x into an encryption of x + x . This is used to bootstrap the security from one to many challenge ciphertexts per (user,label) pair, similarly to [AGRW17, ACF + 18] in the context of multi-input IP-FE. In fact, [ACF + 18] uses a one-time secure MIFE as inner layer, and a single-input IP-FE as outer layer, while we use an IP-MCFE as inner layer, and an IP-FE as outer layer. The main technical challenge is to handle the case of (adaptive) corruptions, which are not considered in [AGRW17, ACF + 18] (even in the static case where corruptions are known beforehand).

Remark. Notice finally that using the IP-FE from [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF], the IP-MCFE from Section 4.2.3, and adding the SSE scheme from Section 6.1.2, one gets an IP-MCFE that is IND-secure, with repetitions and with adaptive corruptions.

Extension of IP-MCFE to vectors

We first extend the IP-MCFE from Section 4.2.3 to handle vectors as inputs of the encryption algorithm for each client, instead of just scalars.

• SetUp(λ): samples G := (G, p, P ) $ ← GGen(1 λ ), a full-domain hash function H onto G 2 , S i $ ← Z m×2 p , for i = 1, . . . , n. Returns the public key mpk := (G, H), encryption keys ek i = S i for i = 1, . . . , n, and the master secret key msk = ((S i ) i ), (in addition to mpk, which is omitted).

• Encrypt(ek i , x i , ): Takes as input the value x i ∈ Z m p to encrypt, under the key ek i = S i and the label . It computes [ u ] := H( ) ∈ G 2 , and outputs the ciphertext

[ c i ] = [S i u + x i ] ∈ G m .
• DKeyGen(msk, y): Takes as input msk = (S i ) i and an inner product function defined by y ∈ Z m•n p as f y ( x) = x, y ,where x = ( x 1 • • • x n ) ∈ Z nm p , and outputs the functional decryption key dk y = y, i S i y i ∈ Z mn p × Z 2 p .

• Correctness. One can check that:

[α] = i [ c i ] y i -[ u ] d = i [S i u + x i ] y i -[ u ] i S i y i = i [S i u ] y i + [ x i ] y i - i [S i u ] y i = i [ x i ] y i = [ x y] = [ x, y ].
For security, we will use the two following properties of the IP-MCFE from Section 4.2.3:

• Linear Homomorphism of ciphertexts: for any i ∈ [n], x i , x i ∈ Z p , and any label , we have

[ c i ] + [ x i ] = Encrypt(ek i , x i + x i , ), where [ c i ] = Encrypt(ek i , x i , ).
• Deterministic Encryption: in particular, together with the linear homomorphism of ciphertexts, this implies that for any x i , x i ∈ Z m p and any label , we have:

Encrypt(ek i , x i , ) -Encrypt(ek i , x i , ) = [ x i -x i ].

Construction of IND-secure IP-MCFE with repetitions

We now give our generic construction to obtain security with repetitions. Let MCFE = (SetUp, Encrypt, DKeyGen, FDecrypt, Decrypt) be the above IP-MCFE scheme and IP-FE = (IP.SetUp, IP.Encrypt, IP.DKeyGen, IP.Dec) be a single-input IP-FE (as defined in Definition 2.15) whose message space is the ciphertext space of MCFE. We define a new MCFE = (SetUp , Encrypt , DKeyGen , Decrypt ) as follows:

• SetUp (λ): it executes (mpk, msk, (ek i ) i ) ← SetUp(λ) as well as, for i = 1, . . . , n, (IP.mpk i , IP.msk i ) ← IP.SetUp(λ). The encryption keys are ek i = (ek i , IP.msk i ) for all i = 1, . . . , n, the public key is mpk := (mpk, {IP.mpk i } i ), and the master secret key is msk = (msk, {IP.msk i } i ).

• Encrypt (ek i , x i , ): it parses the encryption key ek i as (ek i , IP.msk i ), runs [ c i, ] ← Encrypt(ek i , x i , ), and returns C ,i := IP.Encrypt(IP.msk i , [ c i, ]).

• DKeyGen (msk , y): on input y := ( y 1 • • • y n ) ∈ Z nm p , it computes dk y = DKeyGen(msk, y), and for all i ∈ [n]: dk y i = IP.DKeyGen(IP.msk i , y i ). It returns dk y = dk y , {dk

y i } i∈[n] .
The three above algorithms are enough to show the security (as proven below), which holds with respect to any IP-MCFE that satisfies the Linearly Homomorphism of ciphertexts, and deterministic encryption, as defined above. However, correctness only holds for the particular IP-MCFE from Section 4.2.3, where decryption computes the inner product between ciphertexts and decryption keys. That prevents from a generic transformation. We now prove correctness when using the IP-MCFE from Section 4.2.3 in MCFE':

• FDecrypt (dk y , , (C ,i ) i∈ [n] ): takes as input a functional decryption key dk y = dk y , {dk y i } i∈ [n] , where dk y = ( y, d = i S i y i ), a label , and ciphertexts

(C ,i ) i∈[n] . First, it computes [d i, ] = IP.Dec(dk y i , C ,i ) for i = 1 • • • n. Then it computes [ u ] = H( ), and computes [α] = [ i d i, ] -d [ u ].
Finally, it returns the discrete logarithm α ∈ Z p .

• Decrypt (ek i , , (C ,i ) i∈ [n] ): takes as input an encryption key ek i = (ek i , IP.msk i ), a label , and ciphertexts (C ,i ) i∈ [n] . For k ∈ [m], computes dk k = IP.DKeyGen(IP.msk i , (δ k,j ) j ), then [c i ] = IP.Dec(dk k , C ,i ), and finally

x i = Decrypt(ek i , , [ c i ]).
Correctness. By correctness of the IP-FE, we have for all i ∈ [n], and any label :

[d i, ] = [ y i , x i + S i u ] = [ y i , x i ] + y i , S i • [ u ]. Thus, i [d i, ] = [ y, x ] + ( i y i S i ) • [ u ]. Since d = i S i y i , we have i [d i, ] = [ y, x ] + d [ u ], hence α = x, y .

Security analysis

In this section, we provide the proof that the MCFE described above achieves 1-Label-IND * -security (Section 3.1.2), using the wtr-IND * -security of the MCFE from Section 4.2.3, assuming the IP-FE is IND-secure (concrete instances of which are given in [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF]). We can state the following security result:

Theorem 6.3

For any adversary A, against the 1-Label-IND * -security of the above MCFE ,

Adv 1-Label-IND * MCFE (A) ≤ Adv wtr-IND * MCFE (t ) + n • Adv IND IP-FE (t ),
where both t and t are close to the running time t of A.

We prove how the scheme from Section 6.2.2 achieves the 1-Label-IND * -security. As explained in Definition 3.2, the 1-Label-IND * -security game for MCFE is exactly the IND * -security game where only one label * is allowed in the challenge QLeftRight oracle, defined by its index ρ, at the initialization step. We assume that all the other encryption queries are asked to the QEncrypt. The proof uses a series of hybrid games, defined below:

Proof

For any game G, we denote Adv G (A) the advantage of A in the game G, that is, the probability that the procedure Finalize in the game G outputs 1. For any user i ∈ [n], we denote by Q i the number of queries to the oracle QLeftRight containing the user i, that is, of the form: QLeftRight (i, x k,0 i , x k,1 i , ), for k ∈ {1, . . . , Q i }. When all the Q i 's are 1, there is no repetition, but here we are dealing with repetitions. The counter k numbers the repetitions.

Game G β : For any β ∈ {0, 1}, we define the following game, where multiple plaintexts can be queried for the same user i and the same label. We use a counter k, which starts at 1 to number the queries ( x k,0 i , x k,1 i ), under the label * = ρ . We do not keep track of the queries under other labels (as in previous definitions).

• Initialize(ρ): it generates (mpk, msk, (ek i ) i∈ [n] ) ← SetUp(λ), and for all i ∈ [n], (IP.mpk i , IP.msk i ) ← IP.SetUp(λ). It returns mpk := (mpk, (IP.mpk i ) i∈ [n] ) to the adversary A.

• QEncrypt (i, x i , j ): it first computes [ c i ] ← Encrypt(ek i , x i , j ), and returns IP.Enc(msk i , [ c i ]).

• QLeftRight (i,

x k,0 i , x k,1 i , ρ ): it computes [ c k i ] ← Encrypt(ek i , x k,β i , ρ ), and returns IP.Enc(msk i , [ c k i ]). • QDKeyGen ( y): on input y := ( y 1 • • • y n ) ∈ Z nm
p , it first computes dk y = DKeyGen(msk, y), and then, for all i ∈ [n]: dk y i = IP.DKeyGen(msk i , y i ). It returns dk y = dk y , {dk y i } i∈ [n] .

• QCorrupt (i): on input a user i ∈ [n], it returns (ek i , IP.msk i ).

• Finalize: as in Definition 3.2.

Note that:

Adv 1-Label-IND * MCFE (A) = |Adv G 0 (A) -Adv G 1 (A)|.
Game H 0 : Now we consider the game H 0 defined exactly as G 0 , except in

QLeftRight (i, x k,0 i , x k,1 i , ρ ), one computes [ c k i ] ← Encrypt(ek i , x k,0 i + x 1,1 i - x 1,0 i , ρ ).
Then it returns IP.Enc(IP.msk i , [ c k i ]). The transition from G 0 and H 0 uses 1-Label-IND * security and the linear homomorphism of the ciphertexts of MCFE. Namely, we build a PPT adversary B against the 1-Label-IND * security of MCFE such that:

|Adv G 0 (A) -Adv H 0 (A)| ≤ Adv 1-Label-IND * MCFE (B).
B simulates the view of the 1-Label-IND * -adversary A against MCFE as follows:

• Initialize(ρ): after having sent ρ, it gets mpk from its 1-Label-IND * challenger. For all i ∈ [n], (IP.mpk i , IP.msk i ) ← IP.SetUp(λ), and it returns mpk := (mpk, (IP.mpk i ) i∈ [n] ) to the adversary A.

• QEncrypt (i, x i , j ): it first computes [ c i ] ← QEncrypt(i, x i , j ), and returns IP.Enc(msk i , [ c i ]).

• QLeftRight (i, x k,0 i , x k,1 i , ρ ): for k = 1, i.e. the first query for user i, B queries its own QLeftRight oracle to get the value [

c 1 i ] = QLeftRight(i, x k,0 i , x k,1 i , ρ ), otherwise it computes [ c k i ] := [ c 1 i ] + [ x k,0 i - x 1,0 i ]. It then returns IP.Encrypt(IP.msk i , [ c k i ]) to A.
• QDKeyGen ( y): on input y := ( y 1 • • • y n ) ∈ Z nm p , it first computes dk y = DKeyGen(msk, y), and then, for all i ∈ [n]: dk y i = IP.DKeyGen(msk i , y i ). It returns dk y = dk y , {dk y i } i∈ [n] .

• QCorrupt (i): B queries its own oracle to obtain ek i ← QCorrupt(i), and returns (ek i , IP.msk i ) to A.

• Finalize: B verifies that the conditions in Definition 3.2 are satisfied; if they are, it forwards the guess b of A, otherwise, it sends a random bit to its own Finalize oracle.

Note that the constraints B has to verify in the finalize procedure, and namely for condition (2), might look exponential for general functionalities. But in the case of inner product, one just has to look at spanned vector subspaces. Namely, all queries (i,

x k i ,0 i , x k i ,1 i , ρ ) i∈[n],k i ∈[Q i ]
to QLeftRight and all queries y := (

y 1 • • • y n ) to QDKeyGen must satisfy: i x k i ,0 i , y i = i x k i ,1
i , y i . This is an exponential number of linear equations, but, as noted in [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF], it suffices to verify the linearly independent equations, of which there can be at most n • m. This can be done efficiently given the queries.

One can note that, for the label ρ = * , [ c 1 i ] received by B is actually

[ c 1 i ] = Encrypt(ek i , x 1,b i , * )
, where b is the random bit chosen by the 1-Label-IND * security game for MCFE that B is interacting with. By linear homomorphism of the ciphertexts of MCFE, for all k ∈ [Q i ], we have:

[ c k i ] = Encrypt(ek i , x 1,b i , * ) + [ x k,0 i -x 1,0 i ] = Encrypt(ek i , x k,0 i + x 1,b i -x 1,0 i , * ). So, when b = 0, B simulates G 0 , while it simulates H 0 when b = 1, which proves |Adv G 0 (A) -Adv H 0 (A)| ≤ Adv 1-Label-IND * MCFE (B).
We define the following hybrid games H r , for all r ∈ [n], as H 0 , except for QLeftRight (i, x k,0 i , x k,1 i , ρ ): for all i ≤ r, it sets

[ c k i ] ← Encrypt(ek i , x k,1 i , ρ ), instead of [ c k i ] ← Encrypt(ek i , x k,0 i + x 1,1 i -x 1,0 i , k )
, and returns IP.Enc(msk i , [ c k i ]). Note that this definition is compatible with H 0 defined previously, and H n is G 1 . Thus, it suffices to build a PPT adversary B r for all r ∈ [n], against the IND-security of the IP-FE, such that:

|Adv H r-1 (A) -Adv Hr (A)| ≤ Adv IND IP-FE (B r ).
We distinguish two cases. The first case occurs when A queries the user r to its oracle QCorrupt . Then, conditioned on the event that Finalize doesn't output a random bit, it must be the case that for all k ∈ [Q r ], x k,0 r = x k,1 r . If we call E this first case, we have:

Adv H r-1 (A ∧ E) = Adv Hr (A ∧ E).
The second case corresponds to the event ¬E: A does not query QCorrupt on r. We build a PPT adversary B such that

|Adv H r-1 (A|¬E)-Adv Hr (A|¬E) ≤ Adv IND IP-FE (B r ), which implies that |Adv H r-1 (A ∧ ¬E) -Adv Hr (A ∧ ¬E) ≤ Adv IND
IP-FE (B r ). We conclude using the fact that for any game G and event E:

Adv G (A) = Adv G (A ∧ E) + Adv G (A ∧ ¬E).
We now proceed to describe B r , which simulates the view of the 1-Label-IND * adversary A against MCFE as follows:

• Initialize(ρ): B r obtains IP.mpk r from its own Initialize oracle, and generates (IP.mpk i , IP.msk i ) ← IP.SetUp(λ) for all i = r, (mpk, msk, (ek i ) i ) ← SetUp(λ) and returns mpk := (mpk, (IP.mpk i ) i ) to A.

• QEncrypt (i,

x i , j ): it computes [ c i ] ← Encrypt(ek i , x i , j ). If i = r, it returns IP.Enc(msk i , [ c i ]); if i = r, it returns QLeftRight([ c i ], [ c i ]). • QLeftRight (i, x k,0 i , x k,1 i , ρ ): B computes [ c k,0 i ] = Encrypt(ek i , x k,1 i , ρ ) and [ c k,1 i ] = Encrypt(ek i , x k,0 i + x 1,1 i -x 1,0 i , ρ )
, and uses its own QLeftRight oracle to output the ciphertext to A

-if i < r, it outputs IP.Enc(msk i , [ c k,0 i ]). -if i > r, it outputs IP.Enc(msk i , [ c k,1 i ]). -if i = r, it outputs QLeftRight([ c k,0 i ], [ c k,1 i ]). • QDKeyGen ( y): on input y := ( y 1 • • • y n ) ∈ Z nm
p , B r computes dk y = DKeyGen(msk, y), for all i = r: it computes dk y i = IP.DKeyGen(msk i , y i ), and it queries its QDKeyGen oracle to obtain QDKeyGen( y r ). It returns dk y = dk y , {dk y i } i∈ [n] to A.

• QCorrupt(i): if i = r, B aborts the simulation and sends a random bit to its Finalize oracle. Otherwise, it returns IP.msk i .

• Finalize: B r verifies that the conditions in Definition 3.2 are satisfied; if they are, it forwards the guess b of A, otherwise, it sends a random bit to its own Finalize oracle.

Note that when the random bit b used by the IND-security game of IP-FE that B r is interacting with is equal to 0, then, B r simulates the game H r to A; otherwise, it simulates the game H r-1 . In particular, the condition of the Finalize from Definition 3.2 implies that for all queries (i,

x k i ,0 i , x k i ,1 i , ρ ) to QLeftRight , we have: i x k i ,0 i , y i = i x k i ,1 i , y i for all k i ∈ [Q i ]
. Thus, we have in particular, for all k ∈ [Q r ]:

x k,0 r -x 1,0 ρ , y r = x k,1 r -x 1,1 ρ , y r ⇒ x k,0 r + x 1,1 r -x 1,0 ρ , y r = x k,1 r + x 1,1 r -x 1,1 ρ , y r ⇒ c k,0 r , y r = c k,1 r , y r , where [ c k,0 r ] = Encrypt(ek r , ( x k,0 r + x 1,1 r -x 1,0 r ), ρ ) and [ c k,1 r ] = Encrypt(ek r , ( x k,1 r + x 1,1 r -x 1,1 r ), ρ ).
The last implication uses the structural properties of the IP-MCFE scheme, namely, the property of linear homomorphism, and deterministic encryption. The last equality corresponds exactly to the condition to prevent the Finalize oracle from the IND security game of the IP-FE from outputting a random bit (see Definition 2.16).

This proves |Adv

H r-1 (A) -Adv Hr (A)| ≤ Adv IND
IP-FE (B r ), and concludes the security proof.

CCA security from signatures

In this section we briefly describe how to achieve Chosen-Ciphertext (CCA) security in a black-box way, where the adversary may have access to functional decryption queries, without learning the functional decryption key, but just the result. Indeed, while using public-key cryptography techniques, MCFE remains a symmetric-key primitive, where the client encryption key not only allows encryption, but decryption. Using the additional decryption algorithm, we show that adding a signature (Definition 2.7) simply provides CCA-security. MCFE.DKeyGen remains the same as MCFE.DKeyGen. In the following section we provide the full security proof.

Description

Security analysis

Here we formally prove the scheme described in Section 6.3 to achieve the IND-CCA security level using the strong unforgeability (see Definition 2.8) property of the signature. The proof consists of a sequence of games starting from G 0 , playing the real security game described as above, to G 2 where we are back to the basic IND-security game, without decryption queries.

Proof

Game G 0 : the real security game.

• Initialize: C runs both the algorithms MCFE.SetUp(λ) and S.SetUp(λ), to get respectively (msk, (ek i ) i , pp) and (S.key i , S.pp i ) i . Finally, C chooses a bit b $ ← {0, 1} and provides A the public parameters mpk = (pp, (S.pp i ) i ).

• Encryption queries QEncrypt(i, x i , ): for each encryption query, C computes A ,i ← MCFE.Encrypt(ek i , x i , ) and the signature S ,i ← S.Sign(S.key i , (A ,i , )) to return A the value C ,i = (A ,i , S ,i ).

• Challenge queries QLeftRight(i, x 0 i , x 1 i , ): for each encryption query, C computes A ,i ← MCFE.Encrypt(ek i , x b i , ) and the signature S ,i ← S.Sign(S.key i , (A ,i , )) to return A the value C ,i = (A ,i , S ,i ).

• Functional decryption key queries QDKeyGen(f ): for each functional key query, C returns dk f ← MCFE.QDKeyGen(msk, f ).

• Corruption queries QCorrupt(i): for each corruption query, C returns ek i = (ek i , S.key i ).

• Functional decryption queries QFDecrypt( C, , f ): for each functional decryption query, C first checks the validity of the signatures parts S i of C i . If all the signatures are valid, recovers the decryption function key dk f and runs MCFE.FDecrypt(dk f , , C).

Game G 1 : in this game, C does as above, but rejects (outputting ⊥) upon a query QFDecrypt(f, , C) for which there is i ∈ HS, and C i is not the output of QEncrypt or QLeftRight on previous queries. This makes a difference with game G 0 only if such C i contains a valid signature, which would be a forgery. By simply guessing which client will be impersonated (which is correct with probability greater than 1/n), one can output a forgery as soon as a difference happens:

|Adv G 1 (A) -Adv G 0 (A)| ≤ n × Adv SUF S (t).
Now we build a PPT adversary B such that:

Adv G 1 (A) ≤ Adv IND MCFE (B)
, that is, we rely on the IND-CPA security of the underlying MCFE to conclude the CCA security proof. B samples the signature parameters (S.key i , S.pp i ) i ← S.SetUp(λ) for all i ∈ [n], and uses its own oracle to simulate the oracles QEncrypt, QLeftRight, QDKeyGen and QCorrupt. It answers queries QFDecrypt(f, , C) as follows. If for some i ∈ HS, C i is not the output of QEncrypt or QLeftRight on previous queries, then output ⊥. Otherwise, that means that for all i ∈ HS, either C i is the output of QEncrypt(i, x i , ), in which case B sets x i := x i ; either C i is the output of QLeftRight(i, x 0 i , x 1 i , ), in which case B sets x i := x 0 i . For all corrupted slots i ∈ [n] \ HS, B computes x i ← Decrypt(ek i , , C), which it can do since it knows ek i , and C is a complete valid ciphertext. It finally outputs f ( x = ( x i ) i ) to A, which is correctly simulated, since the Finalize procedure imposes that the function f doesn't distinguish between x 0 i and x 1 i queried to QLeftRight, that is, it doesn't matter whether we choose x i := x 0 i or x i := x 1 i . This allows B to properly simulate the oracle QFDecrypt without knowing which bit b is chosen by QLeftRight in its own experiment.

Preliminaries

In this part we derive a key encapsulation mechanism from the usual attributebased encryption, we define the homomorphic-policy property and the associated security notions, and we explain how schemes based on this formalism can solve the access control delegation problem described in the introduction.

Attribute-based key encapsulation mechanism

We first extend ABE to attribute-based key encapsulation mechanism (ABKEM), where the ciphertext encapsulates a session key, later used to encrypt the message, in a symmetric way.

Definition 7.1: ABKEM

An attribute-based key encapsulation mechanism (ABKEM) over an attribute space A is defined by four algorithms:

• SetUp(λ): takes as input the security parameter, and outputs the master secret key msk and the public key pk.

• KeyGen(msk, id, a): takes as input the master secret key msk, the identity id of a player, and an attribute a ∈ A, to output the private decryption key dk a id for this attribute a.

• Encaps(pk, p): takes as input the public key pk and a policy p, to output a key K and an encapsulation E of this key.

• Decaps(dk, E): takes as input a decryption key and an encapsulation E, to output the encapsulated key K or ⊥.

Correctness. For any (msk, pk) ← SetUp(λ), dk a id ← KeyGen(msk, id, a) for a ∈ A, and (K, E) ← Encaps(pk, p), Decaps(dk id , E) = K if A satisfies the policy p.

Note that the decryption key will indifferently mean a key dk a id for a specific user id and a specific attribute a, or a set dk A id of keys specific to a user id, but for many attributes a ∈ A ⊂ A.

Indistinguishability.

The main security property is the usual indistinguishability (IND), which should prevent collusions of adaptively chosen players, that can also get decryption keys for adaptively chosen attributes:

Definition 7.2: IND for ABKEM

Let us consider an ABKEM over an attribute space A. No adversary A should be able to break the following security game against a challenger:

• Initialization: the challenger runs the setup (msk, pk) ← SetUp(λ), and provides pk to the adversary A.

• Key Queries QKeyGen: the adversary A can ask KeyGen-queries, for any id and any attribute a of its choice to get dk a id .

• Challenge Challenge: the adversary A provides a policy p to the challenger that runs (K, E) ← Encaps(pk, p), and sets K b ← K and K 1-b as a random key, for a random bit b. It provides (E, K 0 , K 1 ) to the adversary.

• Key Queries QKeyGen: the adversary A can again ask KeyGen-queries of its choice.

• Finalize: the adversary A outputs its guess b on the bit b.

We also define the event Cheat, which means that a user (with some identity id) owns a set of attributes A (the set of all the attributes a asked to a Key Query for id) that satisfies p: in such a case, the adversary can trivially guess b. Hence, we only allow adversaries such that Pr[Cheat] = 0. We then define We stress that everything is adaptive in this definition: the identities and the attributes asked to the key queries, and the policy asked for the challenge query. However, we are in the chosen-plaintext scenario, without access to any decryption/decapsulation oracle.

Adv ind (A) = |2 × Pr[b = b] -1|,

Homomorphic-policy

While CP-ABE allows to specify the policy at the encryption time, which is also the case for our definition of ABKEM, the sender may not be aware of the policy yet. We thus suggest to exploit an homomorphic property on the policy: we would like to allow the derivation of an encapsulation of K under a combination p = p 1 ∧ p 2 or p = p 1 ∨ p 2 from the encapsulations of K under the policies p 1 and p 2 on the attributes in A, without knowing K (which has already been used to encrypt the payload).

∨ (→ E p ) ∧ ∨ ∨ ∧ ∧ E a 8 E 1 E 2 E 3 E 4 ∨ E 7 E 5 E 6
= ((a 1 ∨ a 2 ) ∧ (a 3 ∧ a 4 )) ∨ (((a 5 ∨ a 6 ) ∧ a 7 ) ∨ a 8 )
With such an homomorphism on the policies, from the encapsulations of a common key K under all the attributes a ∈ A, one could publicly generate an encapsulation of

∨ ∧ ∨ ∨ ∧ ∧ a 8 a 1 a 2 a 3 a 4 ∨ a 7 a 5 a 6 ∨ ∧ ∨ ∨ ∧ ∧ a 8 a 1 a 2 a 3 a 4 ∨ a 7

Security

As explained in the Pay-TV scenario in the introduction, we have three players: the content provider (or the sender), the manager of the access policy (or the combiner) and the receiver. We recall that we do not consider the security manager here since it is a necessary trusted party, potentially played by the sender. We thus expect the sender to encapsulate a key K under each attribute, and to encrypt the payload under K; the combiner then generates the encapsulation of K under the appropriate policy; so that only the legitimate receivers can decapsulate and decrypt the payload.

When the adversary plays the role of the receivers, the required security notion is exactly the previous indistinguishability: given several keys for various attributes, and even several identities (to model collusions), an adversary should not be able to get any information about a key encapsulated under a policy that is not satisfies by any of the users under its control. We stress that this indistinguishability game (IND) models the resistance against the collusion of receivers. But both the sender and the combiner are considered honest.

On the other hand, the sender may not totally trust the combiner and may want to limit the risk in case the combiner would be corrupted: while the former sends K encapsulated under many attributes (or more generally many policies), the latter should not be able to distinguish K from a random key, in order to guarantee to privacy of the content encrypted under K. Hence the new indistinguishability game with multiple encapsulations (m-IND), but without being able to get any decryption key, hence the no-key attack (NKA). Since the adversary does not have access to any decryption key, this security scenario does not allow the combiner to collude with anybody, and namely not with any receiver.

Definition 7.4: m-IND-NKA for ABKEM

Let us consider an ABKEM over an attribute space A. No adversary A should be able to break the following security game against a challenger:

• Initialization: the challenger runs the setup (msk, pk) ← SetUp(λ) and provides pk to the adversary A;

• Challenge: the challenger runs (K, (E i ) i ) ← Encaps(pk, A), and sets K b ← K and K 1-b as a random key, for a random bit b. It provides ((E i ) i , K 0 , K 1 ) to the adversary;

• Finalize: the adversary A outputs its guess b on the bit b.

We then define Adv m-ind-nka (A) = |2 × Pr[b = b] -1|, and say that an ABKEM is (t, ε)-m-IND if no adversary A running within time t can get Adv m-ind-nka (A) ≥ ε.

We stress that now, nothing is adaptive, since the adversary cannot get decryption keys, but gets the encapsulations of the same key K under all the individual attributes. We also remain in the chosen-plaintext scenario, without access to any decryption/decapsulation oracle. In addition, since the adversary is the combiner that receives the key K encapsulated under every attribute, we do not allow any collusion with a user: any attribute would be enough to get K and break the security game.

On can note that in the real-life, such a combiner would not be a critical party since it does not know any long-term secret. Of course, it will learn ephemeral encapsulations that would allow any receiver (with attributes that satisfy the final policy or not) to decapsulate the session key and to decrypt the content. But a short-term corruption will just leak the content during a short period, and not for ever.

An appropriate LSSS construction

The ABKEM we aim to build with the homomorphic policy functionality allows a very fine grained access control. The classical method to realize a such control used in ABE is the monotone span program (Definition 2.12), achieved by a linear secret sharing scheme (Definition 2.14).

Linear secret sharing is a secret sharing (Definition 2.13) defined with a matrix. In order to share s ∈ K, one chooses v 2 , . . . , v n $ ← K and sets v ← (s, v 2 , . . . , v n ) t , then the share-vector is ν ← A • v. One would like to be able to reconstruct s from a few coordinates of this share-vector is ν. Being able to find such a vector c with support I is equivalent to reconstruct s for the players satisfying ρ(I) only:

i∈I c i • ν i = m i=1 c i • ν i = c t • ν = c t • A • v = (1, 0, . . . , 0) • v = s.

Lewko-Waters LSSS construction

To give an example, we can refer to the LSSS proposed by Lewko-Waters [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF]. It generates the matrix A and the map ρ from any monotone policy p that is encoded as a boolean tree, with binary AND and OR gates. One does not need to handle NOT gates, since one only considers monotone policies. We recall in Fig. 7.3 this construction from a predicate: let p be a predicate, we build the corresponding binary tree and we apply the following algorithm to build the share-generating matrix A.

However, this chapter aims to describe another way to build such a LSSS matrix, more adapted to the homomorphic policy functionality. This one assemble several independents LSSS into one. More precisely, we detail a construction of the LSSS, from a boolean tree (with only OR and AND gates), in an iterative way. Figure 7.4: Lewko-Waters's construction applied on the policy p, using the method exposed in Fig. 7.3. The indexes represent the state of the run in the tree, and the resulting vectors are the leaves which are then filled with zeros to make the matrix. Also, we denote 1 := -1 for the sake of clarity.

a 1 : [1] a 2 : [1] a 3 : [1] a 4 : [1] a 5 : [1] a 6 : [1] a 7 : [1] a 8 : [1] ∨ : 1 1 ∧ : 1 1 0 -1 ∨ : 1 1 ∧ :      1 1 0 1 1 0 0 -1 -1 0 0 1      ∧ :    1 1 1 1 0 -1    ∨ :     

Practical example

Finally, we provide an example that details the application of the iterative LSSS construction on an ABKEM to achieve homomorphic policy property. To this aim, we need an ABKEM scheme allowing linear combinations on the shares ν i (where ν = A • v) encoded in the encapsulations; it is necessary to make use of the LSSS properties. Thus, we present here a revised version of a CP-ABE scheme from [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF]. First, for the sake of simplicity, we do not exploit the decentralized version and so all the attributes are managed by the same entity (but we could keep the decentralized version). Second, for the homomorphic property, we consider a KEM instead of an encryption scheme, which just encaps a session key. However, we still use an LSSS to realize the access policy and pairing techniques to ensure collusion resistance. More precisely, we use a symmetric pairing e : G × G -→ G T , where the groups G and G T will be of composite order N = q 1 q 2 q 3 , with three large prime integers q 1 , q 2 , and q 3 . Let us describe our variant of ABKEM.

Description

• SetUp(λ): one first generates symmetric pairing groups (G, G T , [g], N, e) ← PGGen(λ) of composite order N = q 1 q 2 q 3 . One also generates a generator [g 1 ] of the subgroup G 1 ⊂ G of order q 1 and a hash function

H : {0, 1} * -→ G. We also denote G = e([g 1 ], [g 1 ]) = [g 2 1 ] T ∈ G T .
Then, for each attribute a, the authority specifies the pair of secret/public keys, respectively sk a = (α a , y a ) and

pk a = (G a = α a • G, [g a ] = y a • [g 1 ])
. The master secret key msk is the concatenation of the sk a 's, and the public key pk contains N , [g 1 ] and H, together with the concatenation of the pk a 's.

• KeyGen(msk, id, a): from msk = {sk a }, id and a, the authority outputs dk a id = α a • [g 1 ] + y a • H(id).

• Encaps(pk, P ): from the public key pk and a set P of policies, one first chooses some random s $ ← Z N and sets the symmetric encapsulated key K ← s • G. Then, for each p ∈ P , we process the following encapsulation: from the LSSS matrix A ∈ K m×n and the associated labeling map ρ onto the attributes describing the access structure defined by the policy p, we set v = (s, v 2 , . . . , v n ) and w = (0, w 2 , . . . , w n ), with v k , w k $ ← Z N for k = 2, . . . , n and r $ ← Z m N . We build the share vectors ν = A • v and ω = A • w. Eventually, for each line x ∈ {1, . . . , m} of the matrix A, we construct the encapsulation using the keys pk ρ(x) = (G ρ(x) , [g ρ(x) ]) associated to the attribute a x = ρ(x) involved in the policy p:

E 1,x = ν x • G + r x • G ρ(x) E 2,x = r x • [g 1 ] E 3,x = ω x • [g 1 ] + r x • [g ρ(x) ]
The algorithm returns E p = {(E 1,x , E 2,x , E 3,x )} x for each p ∈ P .

• Decaps(dk id , E p ), where dk id = (dk a id ) for the attributes owned by id: first, the user must find a vector c ∈ K m such that c t • A = (1, 0, . . . , 0) and the support I of the non-zero components of c links to a set of attributes owned by the user. Then, for each x ∈ I, the user computes

F x = E 1,x + e(H(id), E 3,x ) -e(dk ρ(x)
id , E 2,x ). He finally gets K by combining with the vector c: K

← x∈I c x • F x .
Correctness. The latter reconstruction works since:

x∈I c x • ν x = m x=1 c x • ν x = c, ν = c t • A • v = (1, 0, . . . , 0) • v = s x∈I c x • ω x = m x=1 c x • ω x = c, ω = c t • A • w = (1, 0, . . . , 0) • w = 0
In addition, for each x ∈ I,

F x = E 1,x + e(H(id), E 3,x ) -e(dk ρ(x) id , E 2,x ) = ν x • G + ω x • e(H(id), [g 1 ]).
And so, the final combination leads to

x∈I c x • F x = x∈I c x • (ν x • G + ω x • e(H(id), [g 1 ])) = c, ν • G + c, ω • e(H(id), [g 1 ]) = s • G.
Note that this scheme produces ciphertexts decryptable when at least k attributes overlapped between a ciphertext and a private key. While they showed that this primitive is useful for error-tolerant encryption with biometrics, the lack of expressibility limits its applicability when more general policy are required. Consequently, the map ρ needs to be an injection. In practice, this is not a real issue, since one can simply duplicate the attributes and provide multiple keys to users.

Security analysis

In [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF], Lewko and Waters proved their ABE scheme to be indistinguishable under several assumptions in the composite-order pairing setting recalled here (Section 7.3.2), and the condition that ρ is injective. This easily leads to the IND security for the above variant of ABKEM, even for adaptive KeyGen-queries. Hence, this ABKEM construction achieves the IND security level. We now show that, the m-IND-NKA security of the modified ABKEM can also be based on the IND security of Lewko-Waters scheme.

Theorem 7.1

The IND security level of Lewko-Waters implies the m-IND-NKA security of the modified ABKEM.

Proof

As highlighted in Fig. 7.6, the two security games are quite similar, the main differences appear in the challenge phase, and the lack of key-queries in the latter. If one looks at the above construction of the LSSS-matrix, for p = a 1 ∨ . . . ∨ a k , then A = (1, . . . , 1) t and ν = (s, . . . , s) t : from an encapsulation E of the key K = s • G under the policy p, one can easily extract the encapsulations E i of the same K, under the policies p i = (a i ) respectively: indeed, each triple

(E 1,x , E 2,x , E 3,x ) is a simple encapsulation of K under a x = ρ(x).
This remark is true for every conjunction p f = p i where the policies p i 's do not share any attribute. Note that the triples (E 1,x , E 2,x , E 3,x ) involved in the decryption of a policy p i are those associated to the attributes which appears in this policy. The choice of these triples is given by the vector c. QKeyGen(id i , a i ) : dk a i id i ← KeyGen(msk, id i , a i ) none

Challenge(p) : p = p i p = (p j ) j (K, E) ← Encaps(pk, p) (K, (E j ) j ) ← Encaps(pk, (p j ) j )

K b ← K, K 1-b $ ← K K b ← K, K 1-b $ ← K (E, K 0 , K 1 )
((E j ) j , K 0 , K 1 )

QKeyGen(id i , a i ) : dk a i id i ← KeyGen(msk, id i , a i ) none Remark. As already noted, Lewko and Waters [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF] assume a one-use restriction on attributes throughout the proof: this means that the row-labeling map ρ of the challenge ciphertext access matrix (A, ρ) must be injective. The reason is that, if an attribute is used twice in the access matrix, then there will appear an implicit relation between the randomnesses associated to the corresponding two lines of the matrix and the proof does not go through anymore. To overcome this issue, Lewko and Waters suggested to associate k independent attributes to any attribute a, where k is an upper-bound on the number of repetitions of an attribute in a policy. Thus, it is important to note our ABKEM derivation inherently has the same limitation.

Composite group assumptions

While we do not recall the proof of the original CP-ABE scheme from [LW11], we describe the assumptions used. Unlike the other work presented in this thesis, this scheme uses non standard assumptions, based on pairing groups with an order N = p 1 p 2 p 3 where the p i are primes.

Definition 7.5: Composite group assumption 1

Given a group generator G, let be the following distribution:

G = (N = p 1 p 2 p 3 , e : G × G → G T ) $ ← G g 1 $ ← G p 1 D = (G, g 1 ) T 0 $ ← G, T 1 $ ← G p 1
This assumption says that with the distribution D but without the knowledge of the factorization of N , we can't decide if T β $ ← {T 0 , T 1 } is in G or G p 1 .

Definition 7.6: Composite group assumption 2

Given a group generator G, let be the following distribution:

G = (N = p 1 p 2 p 3 , e : G × G → G T ) $ ← G g 1 , X 1 $ ← G p 1 , X 2 $ ← G p 2 , g 3 $ ← G p 3 D = (G, g 1 , g 3 , X 1 X 2 ) T 0 $ ← G p 1 , T 1 $ ← G p 1 p 2
This assumption says that with the distribution D but without the knowledge of the factorization of N , we can't decide if T β $ ← {T 0 , T 1 } is in G p 1 or G p 1 p 2 .

Definition 7.7: Composite group assumption 3

Given a group generator G, let be the following distribution:

G = (N = p 1 p 2 p 3 , e : G × G → G T ) $ ← G g 1 , X 1 $ ← G p 1 , Y 2 $ ← G p 2 , X 3 , Y 3 $ ← G p 3 D = (G, g 1 , X 1 X 3 , Y 2 Y 3 ) T 0 $ ← G p 1 p 2 , T 1 $ ← G p 1 p 3
This assumption says that with the distribution D but without the knowledge of the factorization of N , we can't decide if T β $ ← {T 0 , T 1 } is in G p 1 p 2 or G p 1 p 3 .

Definition 7.8: Composite group assumption 4

Given a group generator G, let be the following distribution:

G = (N = p 1 p 2 p 3 , e : G × G → G T ) $ ← G g 1 , X 1 $ ← G p 1 , g 2 $ ← G p 2 , g 3 $ ← G p 3 , (a, b, c, d) $ ← Z N D = (G, g 1 , g 2 , g 3 , g a 1 , g b 1 g b 3 , g c 1 , g ac 1 g d 3 ) T 0 = e(g 1 , g 1 ) abc , T 1 $ ← G T
This assumption says that with the distribution D but without the knowledge of the factorization of N , we can't decide if T β $ ← {T 0 , T 1 } is in the G T or a subgroup of G T generated by e(g 1 , g 1 ).

Achieving homomorphic policy

Eventually, we now show how the iterative construction of the LSSS can be exploited in our ABKEM (Section 7.3.1) to fulfill the homomorphic-policy property.

We recall that in this scheme, ν = A • v is a secret sharing of a random scalar s, while ω = A • w is a secret sharing of 0, the components ν x and ω x being hidden in E 1,x and E 3,x by G rx ρ(x) and g rx ρ(x) respectively. Also, note that the encapsulated key is not exactly s but s • G.

Shares combinations

We first describe the share combinations that are needed to achieve our goal; because of the linear property of the LSSS, by concatenating or by adding the shares, we either obtain the OR or the AND policies of two encapsulations E (1) and E (2) :

Share-Vectors Encapsulations ν 1 ν 2 ←→ E (1) ∪ E (2) ν 1 + ν 2 ←→ E (1) + E (2)
Of course, the same applies on the shares ω of 0, but we focus on the shares ν of the random s

One secret under two policies. Let us be given two encapsulations E (1) and E (2) of the same secret value K = s • G under the policies p 1 and p 2 , represented by the LSSS (A 1 , ρ 1 ) and (A 2 , ρ 2 ). The construction thus used the share-vectors ν i = (ν i,1 , . . . , ν i,m i ) = A i • v i , with v i = (s, v i,2 , . . . , v i,n i ) t , for i = 1, 2. Using

A ∨ = A 1 1 A * 1 0 A 1 2 0 A * 2
and v = (s, v 1,2 , . . . , v 1,n 1 , v 2,2 , . . . , v 2,n 2 ) t , one gets ν = ν 1 ν 2 . From attributes satisfying p i , under the LSSS property, one can efficiently find a vector c i = (c i,1 , . . . , c i,m i ) t ∈ K m such that c t i • A i = (1, 0, . . . , 0). By multiplying this vector on the appropriate half of ν, one can get s:

(c 1,1 , . . . , c 1,m 1 , 0, . . . , 0) • ν = c t 1 • ν 1 = s (0, . . . , 0, c 2,1 , . . . , c 2,m 2 ) • ν = c t 2 • ν 2 = s. It will be used for the disjunction of policies in Section 7.3.3. Two secrets under different policies. Let us be given two encapsulations E (1) and E (2) of two secret values K 1 = s 1 • G and K 2 = s 2 • G under the policies p 1 and p 2 , represented by the LSSS (A 1 , ρ 1 ) and (A 2 , ρ 2 ). The construction thus used the share-vectors ν i = (ν i,1 , . . . , ν i,m i ) = A i • v i , with v i = (s i , v i,2 , . . . , v i,n i ) t , for i = 1, 2. Using

A ∧ = A 1 1 A 1 1 A * 1 0 0 -A 1 2 0 -A * 2
and v = (s 1 + s 2 , -s 2 , v 1,2 , . . . , v 1,n 1 , v 2,2 , . . . , v 2,n 2 ) t , one gets again ν = ν 1 ν 2 . This combination will be used for the conjunction of policies in Section 7.3.3, but only with the same secret. Note that the produced encapsulation Randomization. If one looks in details the description of the Encaps algorithm, there are 4 kinds of randomness:

• s, that defined the encapsulated key K = s • G;

• v k , w k $ ← Z N for k = 2, . . . , n, to define v and w;

• r $ ← Z m N .

Let us start from any encapsulation E (1) of K under a policy p, with

E (1) 1,x = ν (1) x • G + r (1) x • G ρ(x) E (1) 2,x = r (1) x • [g 1 ] E (1) 3,x = ω (1) x • [g 1 ] + r (1) x • [g ρ(x) ]
for each a x = ρ(x) involved in the policy p, where ν (1) = A • v (1) and ω (1) = A • w (1) . We now define a new fresh encapsulation E (2) :

E (2) 1,x = ν (2) x • G + r (2) x • G ρ(x) E (2) 2,x = r (2) x • [g 1 ] E (2) 3,x = ω (2) x • [g 1 ] + r (2) x • [g ρ(x) ]
where ν (2) = A • v (2) and ω (2) = A • w (2) , for v (2) = (0, v 2 , . . . , v n ) t and w (2) = (0, w 2 , . . . , w n ) t , with v k , w k $ ← Z N for k = 2, . . . , n, and r (2) $ ← Z m N . This is actually a fresh random encapsulation of K (2) = e([g], [g]) = [1] T under the policy p. It can be computed from the public key pk that contains N , [g 1 ], and the keys pk a = (G a , [g a ]), for all the attributes, as would be generated a fresh encapsulation of K = [1] T . Eventually, the new encapsulation E = {(E (2) 3,x )} x is a truly random encapsulation of the same K under the policy p, and so looks like a fresh encapsulation.

Conclusion

This thesis presented two ways to delegate the access control to encrypted data, both based on functional encryption.

The first chapters describe how to allow a distributed control of data analysis with the decentralization of multi-client functional encryption; after defining the main definitions and security notions in Chapter 3, we provide practical schemes in Chapter 4. Finally, we describe black-box combinations or generic ideas to achieve a non-interactive decentralized construction and improve security, respectively in Chapter 6 and Chapter 5. All this, with standard assumptions in the random oracle model.

The last chapter (Chapter 7) describes a contribution on a different delegation problem. It allows to separate the roles of the sender and the access right manager. This is a quite useful property for the Pay-TV context, since the access right manager does not have access anymore to the content payload. The distribution to the subscribers can be performed by a weakly trusted party.

Open questions. Through MCFE, we aim to build analysis tools for aggregated data. Our work makes an important step towards this goal, but also left open several questions:

• A first point is the security. Our work is based on groups, uses pairings, and is only proven secure in the random oracle model. It would be interesting to know if we can generalize the ideas presented in this thesis to other assumptions, especially lattices-based. Getting rid of the random oracle model also seems to be an important gap to pass.

In Section 4.1.2 we cite an ongoing work [START_REF] Libert | Multi-client functional encryption for linear functions in the standard model from lwe[END_REF] that deals with these two points. This article describes a scheme built with something close to a KH-PRF, based on Learning With Errors, and is proven secure in the standard model. However, it implies an heavy trade-off on the practicability.

• As noticed in the Section 4.1.2, our IP-MCFE constructions are based on groups where the discrete logarithm problem holds, and the size of the numbers we encrypt is limited by the necessity to solve one in the decryption. At first sight, this constraint may not be problematic for financial or marketing applications, where they work on relatively little values. However it is a real limitation for cryptographic applications since one can not re-use the functionality as a black-box.

A solution to re-use the framework described in this thesis could be using groups that allow discrete logarithm on sub-groups. Thus, the use of groups from Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] (Z/N 2 Z) * seems legitimate. More recently, another recent work [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF] uses specific kind of groups with this property in an IP-FE context.

• A problem not tackled in this work is the dynamic setting. In a practical application, an external user could manifest his wish to join the protocol. This case involves several problems, the first being the creation of the secrets for this new user. A joining algorithm is equivalent to a personal set-up, and must not concern the other participants, so we must imagine a fully decentralized, non-interactive set-up from the beginning. Note that our work offers this possibility. Also, it is the goal of the recent paper [ACF + 19] in the MIFE context.

Another point related to the dynamic setting is the forward secrecy. When a new user is added to an existing group, should he be able to apply a decryption key on the old ciphertexts. In the other way, should we allow a user with an old decryption key to work on a ciphertext from a more recent set of participants? We could add the group as input to the decryption key generation and encryption algorithms to handle these questions, or maybe pair the MCFE with a finer grained access control, similarly to [START_REF] Dufour | Unbounded inner-product functional encryption, with succinct keys[END_REF].

• Another functionality to study is the function-hiding. Briefly explained, we can suppose a case where a user is given a decryption key that does not leak the function encoded inside. This is already possible with the MIFE through the paper [ACF + 18], and the technique seems applicable to MCFE. However it remains a problem in the decentralized context.

In the case of the DMCFE, even if the users do not know the precise function when they make the decryption key, they must use a common time stamp to forbid combination of pieces from different keys. Consequently, no one is fully aware of the function, the key requester only knows the time stamp, and the senders know this time stamp and their personal values encoded in their key parts.

• Last point, but not the least, is about the others function we could potentially describe through MCFE. In this work we described a framework principally aiming inner product functionality, and a natural extension would be higher degree polynomials. We know today, since the paper [START_REF] Lin | Indistinguishability obfuscation from trilinear maps and block-wise local PRGs[END_REF], that trilinear maps would imply strong theoretical results in cryptography. Furthermore, functional encryption for quadratic functions is now known possible for single input functional encryption through the work [START_REF] Elisabetta | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF], a scheme that relies on the use of pairings. Therefore, the important question is to know if quadratic functionality is possible in a (decentralized) multi-client context.

In an attempt to answer positively, an idea to explore is to re-use an additive mask c = x + s , apply the function A: c • A • c and use function-hiding to remove the x • A • s terms, while we take away s A s using a key, analogously to IP-FE schemes.

Finally, on homomorphic-policy, we leave open the question of a generalization of the method used in [START_REF] Chotard | Homomorphic-policy attribute-based key encapsulation mechanisms[END_REF] to others ABE schemes with more standard assumptions.

Figure list

Résumé

Le chiffrement fonctionnel est un paradigme récent qui généralise le chiffrement à clef publique classique. Cette formalisation a pour objectif de réguler plus finement le contrôle d'accès aux données chiffrées, ainsi que l'information dévoilée par le déchiffrement. Cette thèse étudie des possibilités de délégation au travers de ces deux aspects.

Dans un premier temps, nous travaillons dans un contexte multi-client : plusieurs utilisateurs fournissent chacun une donnée personnelle chiffrée, et une entité souhaite extraire de l'information de ces données. Notre contribution consiste à permettre à ces utilisateurs de donner, ou refuser, leur accord à cette extraction. Pour ce faire, nous décrivons des constructions de chiffrement fonctionnel multi-utilisateur, puis nous definissons plusieurs niveaux de sécurité et fournissons des méthodes pour les atteindre. Enfin, principal objectif de ces travaux, nous décentralisons la fabrication de la clef de déchiffrement, pour qu'une personne souhaitant une clef de déchiffrement ait besoin de l'accord de tous pour l'obtenir. Toutes les instantiations proposées dans ces travaux sont utilisables en pratique.

Dans second temps, nous considérons une autre problématique dans laquelle un producteur de contenu vidéo cherche à déléguer la distribution de sa création, sans la révéler. Notre solution est un mécanisme d'encapsulation de clef, dérivé du chiffrement par attributs, avec une propriété particulière. Ce producteur l'utilise pour encapsuler la clef du flux vidéo sous plusieurs attributs, et fournit les encapsulations au distributeur. Celuici peut alors utiliser la propriété pour combiner les encapsulations et en définir les conditions d'accès à sa guise.

Abstract

Functional encryption is a recent paradigm that generalizes the classical public key encryption. This formalization aims to finely manage both the access control to the encrypted data, and the information revealed by the decryption. This thesis studies possibilities of delegation through these two sides.

First, we deal with a multi-client context : several users provide each one an encryption of personal data, and an entity wishes to extract information from the aggregate of those inputs. Our contribution in this environment consists to provide these clients the possibility to give, or refuse, their consent for such an extraction. To this aim, we describe constructions of multi-client functional encryption. We then formalize several levels of security and provide methods to reach them. Eventually, we decentralize the construction of the functional decryption key, so that one needs the agreement of all clients to get a functional decryption key. All this, in a practical way.

Second, we consider a more specific case where a video content provider wishes to delegate the distribution of his creation, but without revealing it. Our solution is a key encapsulation mechanism, derived from attribute-based encryption, with a particular property. The provider uses it to encapsulate the key of the encrypted stream under several attributes, and provides the encapsulations to the distributor. This "content manager" can then use the property to combine the encapsulations and make a new one under the access policy of his choice.

DMCFE + DSum Section 5 .1. 6 Figure 1 . 2 :

 5612 Figure 1.2: Comparison of different cryptographic solutions to the problem of linearly aggregating private multi-client data.

Figure 1 . 3 :

 13 Figure1.3: Contributions and theorems. Here, wtr stands for: "without repetitions", CCA for: "chosen ciphertexts attacks" and IND * is a security level that does not manage the case where an user does not provide a ciphertext, IND being the natural one.

Figure 1 . 4 :

 14 Figure1.4: Separating the roles, the content provider (C) encapsulates the key K of his stream with the public key pk, and provides this encapsulation E(K) to the content manager (M ). This one chooses the target T and fixes the policy with the public key, and distributes the encapsulation E T (K) to the final receiver (R). (C) and (M ) can be totally independents, or not. Also, (C) can play the role of the security manager (S), or not.

a

  use implicit representation of group elements as introduced in [EHK + 13]. For a ∈ Z p , define [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: 11 P ... a 1m P a n1 P ... a nm P    ∈ G n×m 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.

Contents 3 . 1

 31 Multi-client functional encryption . . . . . . . . . . . . . . . . . . . 28 3.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Decentralization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Definition of decentralized multi-client functional encryption 32 3.2.2 Security of DMCFE . . . . . . . . . . . . . . . . . . . . . . 33

  Contents 4.1 IP-MCFE from key-homomorphic PRF . . . . . . . . . . . . . . . . 36 4.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1.2 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 IP-MCFE from groups . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.1 Description of selective version . . . . . . . . . . . . . . . . 40 4.2.2 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.3 Description of adaptative version . . . . . . . . . . . . . . . 44 4.2.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 45

  Theorem 4.1: sel-wtr-IND * Security

Figure 4

 4 Figure 4.1: Summary of the hybrid-games proof system of the Theorem 4.1. On this description, PRFO plays the role of the challenger of the PRF security game, and appears only in three games.

Figure 4 . 2 :

 42 Figure 4.2: Comparison of the IP-FE scheme from Abdalla et al. [ABDP15] and a similar MCFE obtained by introducing a hash function H.

Theorem 4. 2 :

 2 sel-wtr-IND * Security The MCFE protocol described above (see Section 4.2.1) is sel-wtr-IND * secure under the DDH assumption, in the random oracle model. More precisely, we have Adv IND (A) ≤ 2Q • Adv ddh G (t), for any adversary A, running within time t, where Q is the number of encryption queries per slot.

  and b ⊥ := ( -a 1 ) . The extra terms ( w i ( b ⊥ ) ) i∈HS only appear in the output of the queries to QDKeyGen which use the vector [ v y ] 2 computed on the q-th RO 2 -query (if there are such queries), because for all other queries, [ v y ] 2 lies in the span of [ b] 2 , and b b ⊥ = 0. We thus have dk y,i := [y

  FDecrypt(dk y , , ([ c i ]) i∈[n] ): Takes as input a functional decryption key dk y = ( y, d), a label , and ciphertexts. It computes [ u ] := H( ) and returns [α] = i [ c i ] y i -[ u ] d. • Decrypt(ek i , , ([ c i ]) i∈[n] ): Takes as input the encryption key ek i = S i , a label , and ciphertexts. It computes [ u ] := H( ) and returns [ x ,i ] = [ c i ] -[S i u ].

Figure 7 . 1 :

 71 Figure 7.1: Derivation of E p from a set of encapsulations {E i }, for the policy p = ((a 1 ∨ a 2 ) ∧ (a 3 ∧ a 4 )) ∨ (((a 5 ∨ a 6 ) ∧ a 7 ) ∨ a 8 )

Figure 7 . 2 :

 72 Figure 7.2: Randomization process in combination

Figure 7 . 5 :

 75 Figure 7.5: Matrix-based iterative construction of p, following the method described in Proposition 7.1.

  Consequently, we can easily convert the challenger's answer from one game to another by concatenating/separating the ciphertext(s) by following this policy decomposition. Because of the lack of key-queries in the m-IND-NKA security game, we can just build an adversary B for the IND game from an adversary A of the m-IND-NKA game. More precisely, if an adversary A has an advantage Adv m-ind-nka (A) = ε in the m-IND-NKA game for the policies (p j ) j , one can construct an adversary B with the same advantage Adv ind (B) = ε in the IND game for the policy p f = p i . IND game m-IND-NKA game SetUp(λ) : (msk, pk) ← SetUp(λ) (msk, pk) ← SetUp(λ)

Figure 7 . 6 :

 76 Figure 7.6: Comparison between the original IND security game for ABKEM and the m-IND-NKA game. The p i 's are different policies that do not share any attribute, and K is the key space.

Fig. 1

 1 Fig. 1.1: Illustration of MCFE context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 1

 1 Fig. 1.2: Comparison of interactions between several schemes . . . . . . . . . . . . . . . . . .

Fig. 1

 1 Fig. 1.3: Relations between the different security models of MCFE . . . . . . . . . . . . .

Fig. 1

 1 Fig. 1.4: Illustration of ABKEM context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 4

 4 Fig. 4.1: Summary of the proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 4

 4 Fig. 4.2: Comparison of the schemes from Section 4.2.1 and [ABDP15] . . . . . . . .

Fig. 4

 4 Fig. 4.3: Summary of the proof of Theorem 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 4

 4 Fig. 4.4: Summary of the proof of Theorem 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 4. 5 :

 5 Fig. 4.5: Summary of hybrid games from the proof of Theorem 4.3 . . . . . . . . . . . .50 Fig. 5.1: Summary of the proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 7 .

 7 Fig. 7.1: Illustration of the HP property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fig. 7.2: Illustration of the randomization process . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fig. 7.3: Lewko-Waters LSSS algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 7 .

 7 Fig. 7.4: Illustration of Lewko-Waters LSSS algorithm on an example . . . . . . . . .

Fig. 7 . 5 :

 75 Fig. 7.5: Illustration of our LSSS algorithm on an example . . . . . . . . . . . . . . . . . . . .

Fig. 7 . 6 :

 76 Fig. 7.6: Comparison between IND and NKA security games . . . . . . . . . . . . . . . . . . . .

  Contents 2.1 Notations and mathematical notions . . . . . . . . . . . . . . . . . 13 2.2 Generic cryptography notions . . . . . . . . . . . . . . . . . . . . . 14 2.2.1 About randomness . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Basic primitives . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.3 Functional encryption . . . . . . . . . . . . . . . . . . . . . 19

2.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Prime order group assumptions . . . . . . . . . . . . . . . . 23 2.3.2 Pairing group assumptions . . . . . . . . . . . . . . . . . . 24

  also that in Game G 4 , all the dk y,i output by QDKeyGen can be computed only knowing i∈[n] s i • y i , which is exactly the functional decryption key dk y from our MCFE in Section 4.2.3. This follows from the fact that the values RF i ( y) perfectly mask the vectors s i • y i , up to revealing i∈[n] s i • y i (as the RF i must sum up to the zero function). Thus, we can reduce to the IND-security of the MCFE from Section 4.2.3 (or even sta-IND-security) by designing an adversary B against the MCFE from Section 4.2.3: Adversary B first samples T i It sends CS given by A (set of static corruptions), then it receives mpk from the MCFE security game, as well as the secret keys s i for i ∈ CS. It forwards mpk as well as ( s i , T i ) for i ∈ CS to A. Then • B answers oracle calls to RO 1 , RO 2 and QEncrypt from A using its own oracles.

$ ← Z 2×2 p for all i ∈ [n], such that i∈[n] T i = 0.

• To answer QDKeyGen(i, y): if i is the last non-corrupted index for y, B queries its own QDKeyGen oracle on y, to get dk y

  where the probability is taken over pk sse , (ek sse,i ) i∈[n] ← SSE.SetUp(λ), (C , K ) ← SSE.Encaps(pk sse , ), and S ,i ← SSE.Share(ek sse,i , ) for all i ∈ [n].

  operates in two steps; first it applies SSE.Decaps sse (pk sse , (S ,j ) j∈[n] , , D ,i ) on all the ciphertexts D ,i to get all the encapsulation keys K ,i 's and thus all the plaintexts C ,i 's using SDec on E ,i . Then it runs FDecrypt(dk f , , (C ,i ) i∈[n] ).

• Decrypt (ek i , , (C ,i ) i∈

[n]

): takes as input an encryption key ek i , a label , and ciphertexts

(C ,i = (E ,i , D ,i , S ,i )) i∈[n] . It

operates in two steps; first it applies SSE.Decaps sse (pk sse , (S ,j ) j∈[n] , , D ,i ) on all the ciphertexts D ,i to get all the encapsulation keys K ,i 's and thus all the plaintexts C ,i 's using SDec on E ,i . Then it runs Decrypt(ek i , , (C ,i ) i∈[n]

  More precisely, given an IND-secure MCFE scheme MCFE = (MCFE.SetUp, MCFE.Encrypt, MCFE.KeyGen, MCFE.FDecrypt, MCFE.Decrypt), a strongly unforgeable signature (S.SetUp, S.Sign, S.Verif), we generically build an IND-CCA-secure scheme MCFE, where the changes are as follows:• MCFE.SetUp(λ): executes (msk, (ek i ) i , pp) ← MCFE.SetUp(λ)and, for any i ∈ [n], sets the signature parameters (S.key i , S.pp i ) ← S.SetUp(λ) for each user i. msk = (msk, (S.key i ) i ), for all i sets ek i = (ek i , S.key i ), and finally pp = (pp, (S.pp i ) i ). • MCFE.Encrypt( ek i , x i , ): computes A ,i ← MCFE.Encrypt(ek i , x i , ) and the signature S ,i ← S.Sign(S.key i , (A ,i , )) to return C ,i = (A ,i , S ,i ). • MCFE.FDecrypt(dk f , , C): given a ciphertext C = (A i , S i ) i , computes the values S.Verif(S.pp i , (A i , ), S i ) for any user i. If all the signatures are valid, returns α ← MCFE.FDecrypt(dk f , , (A i ) i ), otherwise, returns ⊥. • MCFE.Decrypt( ek i , , C): given a ciphertext C = (A i , S i ) i , computes the values S.Verif(S.pp i , (A i , ), S i ) for any user i. If all the signatures are valid, returns x i ← MCFE.Decrypt(ek i , , (A i ) i ), otherwise, returns ⊥.

  and say that an ABKEM is (t, ε)-adaptively secure if no adversary A running within time t can get Adv ind (A) ≥ ε.

Remerciements

shows that the One-Label security is equivalent to the Many-Label security. The One-Label definition will be enough for our applications.

Definition 6.2: 1-Label-IND-security game for SSE

Let us consider an SSE scheme over a set of n senders. We define the following security game against a challenger C, where the adversary has unlimited and adaptive access to the oracles QRealRandom, QShare, and QCorrupt described below.

• Initialize(i * ): the adversary announces an index i * [n]. The challenger C runs the setup algorithm (pk sse , (ek sse,i ) i∈ [n] ) ← SetUp(λ) and chooses a random bit b $ ← {0, 1}. It provides pk sse to the adversary A.

• Challenge queries QRealRandom( ): outputs a ciphertext C , together with an encapsulation key K b , where (C , K 0 ) ← SSE.Encaps(pk sse , ), and K 1 $ ← K, where K is the encapsulation key space.

• Sharing queries QShare(i, ): outputs S ,i ← SSE.Share(ek sse,i , ).

• Corruption queries QCorrupt(i): outputs the encapsulation key ek sse,i .

• Finalize: A provides its guess b on the bit b, and this procedure outputs this β ← b if the following condition is satisfied: QRealRandom is only queried on at most one label * and i * was not queried to QCorrupt and (i * , * ) was not queried to QShare. If this condition is not satisfied, Finalize outputs a random bit β.

We say this SSE is 1-Label-IND-secure if for any PPT adversary A, its advantage Adv We can also define the weaker static variant, where corruptions are known from the beginning.

Construction

Let us exhibit a concrete construct for our main tool SSE, in the random oracle model, under the DBDH assumption.

• SSE.SetUp(λ): takes as input a security parameter λ and generates

The public parameters pk sse consist of (PG, H sse , [ t] 2 ), and the personal encapsulation keys are ek sse,i = t i , the i-th coordinate of t.

• SSE.Share(ek sse,i , ): takes as input the key ek sse,i = t i and the label and outputs the share

• SSE.Encaps(pk sse , ): takes as input the public key pk sse = (PG, H sse , [ t] 2 ) and the label , samples r $ ← Z p , and outputs the ciphertext C and the encapsulation key K defined as:

for a given label. In addition Adv(t), for any security notion, is the maximum advantage an algorithm can get within time t.

We stress that this security result keeps all the properties of the basic MCFE and the SSE schemes:

• if MCFE and SSE are both secure against adaptive corruptions, MCFE' is also IND against adaptive corruptions;

• if MCFE is secure with repetitions (see Section 6.2), MCFE' is also IND with repetitions.

The proof uses a hybrid argument that goes over all the labels 1 , . . . , L used as input to the queries A makes to the QLeftRight oracle.

Proof

We define the following hybrid games, for all ρ = 0, . . . , L: Game G ρ : This hybrid game outputs right answers for the QLeftRight -queries involving the first ρ labels, and left answers for the other labels, to the INDadversary A, as follows:

• Initialize: it gets the global parameters (mpk, msk,

(pk sse , (ek sse,i ) i∈[n] ) ← SSE.SetUp(λ) and it returns the public ones mpk = mpk ∪ pk sse to the adversary A.

• QEncrypt (i, x, j ): it returns Encrypt (ek i , x, j ).

• QLeftRight (i, x 0 , x 1 , j ): if j ≤ ρ, it returns Encrypt (ek i , x 1 , j ), if j > ρ, it returns Encrypt (ek i , x 0 , j ).

• QDKeyGen (f ): it returns DKeyGen (msk, f ).

• QCorrupt (i): it returns ek i = ek i ∪ ek sse,i ;

• Finalize: as in Definition 3.2, for IND-security.

For any hybrid game G ρ , we denote by Adv Gρ (A) := Pr[β = 1], where β is the output of Finalize. Note that

Lemma 6.1

For any adversary A against the IND-security of the above MCFE , for all ρ ∈ [L], there exist PPT adversaries B ρ , B ρ , and B ρ such that :

7 Delegation of access control

In this last chapter, we describe how to delegate the access control through functional encryption, the material from this chapter comes from the work [START_REF] Chotard | Homomorphic-policy attribute-based key encapsulation mechanisms[END_REF].

In a first part, we define the attribute-based key encapsulation mechanism primitive, a mix of CP-ABE and KEM (see Definition 2.19 and Definition 2.9 respectively), and the homomorphic policy property. We discuss about the security behind those notions.

In the second part, we discuss about a construction of a new LSSS (Definition 2.14) from two independent LSSS, following combinations of their shares.

In the last part, we provide an example with an adaptation of the Lewko-Waters scheme from [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF], and we explain how to exploit homomorphic policy property using the LSSS techniques from the second part.

Contents

K under any policy on A: as illustrated above on Fig. 7.1, from the encapsulations {E i } i of K for the attributes A = {a i }, one can derive the encapsulation E p of K under any policy p, encoded as a binary tree with AND (∧) and OR (∨) gates. Again, we only consider monotone policies, hence the absence of NOT gates. On attributes, if one wants to consider the negation (or absence) of some attribute a, one has to define a second attribute a that is exclusive with a, so that, if p = (a), then ¬p = (a ).

To achieve this goal, we just need to be able to combine two encapsulations of K under p 1 and p 2 in order to derive the encapsulation of K under p ∨ = p 1 ∨ p 2 and under p ∧ = p 1 ∧ p 2 . The global encapsulation under a more general policy can then be recursively built.

Definition 7.3: Homomorphic-Policy ABKEM

An Homomorphic-Policy Attribute-Based Key Encapsulation Mechanism (denoted HP-ABKEM) over an attribute space A is an ABKEM (see Definition 7.1), with a more specific encapsulation algorithm and two additional algorithms for the homomorphism:

• Encaps(pk, P ): takes as input the public key pk, a list of policies P = (p i ) i , to output a key K and the encapsulations E i of this key under the policies p i 's.

• Combine(pk, gate, E 1 , E 2 ): takes as input the public key pk as well as two encapsulations E 1 and E 2 , and a gate gate ∈ {∧, ∨}, to output an encapsulation under the combination of the initial policies for E 1 and E 2 .

• Rand(pk, E): takes as input the public key pk as well as an encapsulation, to output a new encapsulation (of the same key under the same policy).

The intuition behind the new Encaps algorithm is that we want to be able to encapsulate the same key K under various policies. We thus opt for an encapsulation algorithm that takes as input all the policies that will be combined later.

Correctness. The correctness properties are:

• if (E i ) i ← Encaps(pk, (p i ) i ) are common encapsulations of a key K under the p i 's, then for any i, j, E ← Combine(pk, gate, E i , E j ) is an encapsulation of the same key K, but under the policy p = p i gate p j .

• for any encapsulation E of some key K under a policy p, E ← Rand(pk, E) follows the same distribution as a fresh encapsulation of K under the policy p.

Note that we do not expect the combination to hide the structure of the initial encapsulations. The randomization will do this work, but there is no need to do it at each step, hence the separation of the two processes: one will iteratively combine the encapsulations in order to obtain the encapsulation under the appropriate policy, and then the randomization will finalize the process. Fig. 7.2 illustrates this fact: combining and randomizing at each step leads to exactly the same distribution of the root encapsulation as combining at each step and randomizing at the last step only.

Iterative LSSS construction

First, we have to start from an LSSS for a simple policy p = (a i ), for some i (i.e., a unique attribute): A i = (1) and ρ(1) = i. Then we explain how to combine two policies p 1 and p 2 , represented by the LSSS's (A 1 , ρ 1 ) and (A 2 , ρ 2 ) respectively, into the policies p ∧ = p 1 ∧ p 2 and p ∨ = p 1 ∨ p 2 with LSSS's (A ∧ , ρ ∧ ) and (A ∨ , ρ ∨ ) respectively.

In the following, for any A, we denote A 1 the first column et A * the matrix A without the first column (i.e., A = A 1 A * ).

Proposition 7.1

Let (A 1 , ρ 1 ) and (A 2 , ρ 2 ) be two LSSS's for the policies p 1 and p 2 . Then we can build the LSSS's (A ∧ , ρ ∧ ) and (A ∨ , ρ ∨ ) for the policies p ∧ = p 1 ∧ p 2 and p ∨ = p 1 ∨ p 2 as follows

If we label the rows of the matrices from 1 to m 1 + m 2 , where A 1 ∈ K m 1 ×n 1 and A 2 ∈ K m 2 ×n 2 , we have

This construction is not really new, since it was described in [START_REF] Nikov | New monotone span programs from old[END_REF] in a more generic way. But we need this explicit description for the security analysis of our ABKEM. The correctness of this LSSS construction is provided in the following proof. Up to a re-ordering of the rows and columns of the matrices, this is also the same construction obtained from the algorithm presented in Fig. 7.3 from [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF]. A brief comparison of the two methods is indeed proposed after the proof of Proposition 7.1.

Proof

Let us now prove the combinations of LSSS lead to LSSS for the combined policies.

First, let us remark that with the initialization A = (1) and ρ(1) = i for a simple policy p = (a i ), this is indeed an LSSS:

• ν 1 = s, where ν 1 is the share of the player i (or with attribute a i ). The secret s can be revocered;

• Without ν 1 , no information is leaked about s.

Disjunctions. We assume that for some attributes A, there is I such that ρ(I) ⊂ A satisfies the policy p 1 ∨ p 2 . This also means there is I ⊆ I such that ρ(I ) ⊂ A satisfies the policy p b , for b = 1 or b = 2: from the LSSS (A b , ρ b ), there is c b with support I such that c t b • A b = (1, 0, . . . , 0). Let us take the other vector c t 3-b ← (0, . . . , 0) t and build:

This vector also has the same support andc

The last block of n 2 -1 components is also also (0, . . . , 0).

In the other direction, in order to be able to distinguish s from a random value, given the coordinates of ν in I, one must be able to find c such that

As a consequence,

Let us assume this is the first one, and it is equal to α ∈ K * : the vector

, 0, . . . , 0). This vector has a support I ⊆ I, and thus (from the LSSS property) ρ(I ) must satisfy the policy p 1 , and so does ρ(I) because of the monotonicity.

Conjunctions. We assume that for some attributes A, there is I such that ρ(I) ⊂ A satisfies the policy p 1 ∧ p 2 . This also means there is

This vector c has a support I 1 ∪ I 2 ⊆ I.

In the other direction, in order to be able to distinguish s from a random value, given the coordinates of ν in I, one must be able to find c such that

) and the supports of c 1 and c 2 are I 1 and I 2 included in I. From the LSSS property ρ(I b ) must satisfy the policy p b , for b = 1, 2, and so does ρ(I) because of the monotonicity. As a consequence, ρ(I) satisfies the policy p 1 ∧ p 2 .

About the two constructions

To summarize, we illustrate here these methods to construct the LSSS for the policy p = ((a 1 ∨ a 2 ) ∧ (a 3 ∧ a 4 )) ∨ (((a 5 ∨ a 6 ) ∧ a 7 ) ∨ a 8 ).

Using Lewko-Waters' algorithm, we get the tree and the matrix described on Fig. 7.4. This algorithm explores the tree following nodes corresponding to binary gates (i) and associates vectors with values in {-1, 0, 1} to the child nodes. The vectors linked to leaves form the final matrix. Using our combination of matrices, starting from the leaves, associated to the matrix [1], and going go back to the root, we obtain the construction on Fig. 7.5.

The matrices obtained are equivalent: columns can just differ with the sign. Indeed, if there exists c such that c t • A = (1, 0, . . . , 0), changing the sign of a column of A does not impact the support of c: changing the sign of the first column needs changing the sign of c, while changing the sign of the other columns does not impact c at all. The matrices also have the same size: m rows for n + 1 columns where m is the numbers of literals in the predicate p and n is the number of AND gates. If this is well known for the matrices made from Lewko-Waters's method, it is easy to see it with our method too, by induction. Let A 1 and A 2 be two LSSS matrices, with respectively n 1 and n 2 columns, for the policies p 1 and p 2 , with respectively n 1 and n 2 AND gates. Following our construction, the new LSSS matrices A ∨ and A ∧ have respectively n 1 + n 2 and n 1 + n 2 + 1 columns, and their associated policies p 1 ∨ p 2 and p 1 ∧ p 2 respectively have n 1 + n 2 and n 1 + n 2 + 1 AND gates. Note that we start must be randomized to perform the new policy, otherwise there is a colluding attack: with independent keys for each policy, two players can independently get s 1 and s 2 , and can then combine them to get s 1 + s 2 .

Two secrets under the same policy. Let us be given two encapsulations E (1) and E (2) of two secret values K 1 = s 1 • G and K 2 = s 2 • G under the same policy p, represented by the LSSS (A, ρ). The construction thus used the share-vectors ν 1 and ν 2 of the random scalars s 1 and s 2 respectively under the same policy p. Then, one can see ν = ν 1 + ν 2 as a share-vector of s = s 1 + s 2 under the policy p, since ν = A • ( v 1 + v 2 ). Indeed, from attributes satisfying p, one can efficiently find a vector c ∈ K m such that c t • A = (1, 0, . . . , 0):

This combination will be used for the randomization in Section 7.3.3, with s 2 = 0.

Encapsulations combinations

Let us now see how this impacts on the encapsulations, when one wants to do disjunctions and conjunctions of policies.

Disjunctions. Let us be given two encapsulations E (1) and E (2) of the same key K = s • G under the policies p 1 and p 2 , represented by the LSSS (A 1 , ρ 1 ) and (A 2 , ρ 2 ). We want to make an encapsulation of K under the policy p 1 ∨ p 2 . Using the construction of the share-vectors from Section 7.3.3, which applies on both ν 1 , ν 2 and ω 1 , ω 2 , we know that the resulting encapsulation should use

Therefore, the resulting encapsulation is

Conjunctions. Let us be given two encapsulations E (1) and E (2) of the same key K = s • G under the policies p 1 and p 2 , represented by the LSSS (A 1 , ρ 1 ) and (A 2 , ρ 2 ). We want to make an encapsulation of K under the policy p 1 ∧ p 2 . Using the construction of the share-vectors from Section 7.3.3, which applies on both ν 1 , ν 2 and ω 1 , ω 2 , we know that the resulting encapsulation should use

However, this will contain the key 2 • K = 2s • G. We thus have to halve: the resulting encapsulation is E p 1 ∧p 2 = {(( 1 2 • E

(1) j,x ), ( 1 2 • E

(2) j,x )) j=1,2,3 } x∈A . Note that even if in the Lewko-Waters' construction there is a modulus N = q 1 q 2 q 3 that is hard to factor, this is the order of the group. Hence 1 2 • [g] = α • [g] where α = (N + 1)/2. As already noted, collusion is possible. But this is even worse in this case since we are using s = s 1 = s 2 : just satisfying one of the two policies, one can recover 1 2 • K = s 2 • G, which thereafter easily leads to K. We thus need to randomize the encapsulation, in order to glue together the policies.

Abbreviations