Keywords: cryptography, functional encryption, inner-product, provable security, generic constructions, projective hash functions

Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d'effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c'est-à-dire du chiffrement fonctionnel qui permet l'évaluation de n'importe quel circuit. Ces contributions délaissent souvent l'efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n'est proche d'être pratique. Le but de cette thèse est d'attaquer ce défi sous un autre angle: nous essayons de construire des schémas de chiffrement fonctionnel les plus expressifs que nous le pouvons en se basant sur des hypothèses classiques, tout en conservant la simplicité et l'efficacité des constructions. C'est pourquoi nous introduisons la notion de chiffrement fonctionnel pour l'évaluation de produits scalaires, où les messages sont des vecteurs #" x , et l'autorité peut transmettre des clés correspondants à des vecteurs #" y qui permettent l'évaluation du produit scalaire #" x , #" y . Cette fonctionnalité possède immédiatement des applications directes, et peut aussi être utilisée dans d'autres constructions plus théoriques, le produit scalaire étant une opération couramment utilisée. Enfin, nous présentons deux structures génériques pour construire des schémas de chiffrement fonctionnels pour le produit scalaire, ainsi que des instanciations concrètes dont la sécurité repose sur des hypothèses classiques, telles que DDH, DCR, et LWE. Nous comparons aussi les avantages et inconvénients de chacune d'entre elles.

Introduction

"All warfare is based on deception." -Sun Tzu, The Art of War Throughout history, many generals have noticed that information was the key to victory: whoever knows the most about the enemy often triumphs in battle. To this end, the use of spies was capital. However, what use is a spy of, if his information can be intercepted or, even worse, faked? This is the reason why cryptography was first invented: to protect -with secure encryption -to authenticate -with signatures -and to hide -with steganography techniques -the information obtained by a spy behind the enemy lines so that it can be safely used as a weapon. At this time, the use of symmetric cryptography was enough, because the spy could agree with his master upon a key before his departure. It was not until the advances of technology with the development of the Internet that public key cryptography was needed.

"With great power comes great responsibility."

-Uncle Ben, Spider-Man On the Internet, anyone is able to contact everybody. However, anybody can pretend to be anyone, and can read everything. It is really hard to protect users' privacy if this ability is not used with caution. Unlike the previous example of the spy, it is not possible for a search engine or an online encyclopedia for example to meet physically with all of its users, and agree about a key with each of them, and remember all the keys. This is where public key cryptography comes into play. For example, the use of a key exchange [START_REF] Diffie | New Directions in Cryptography[END_REF] allows the user and the server to share a secret key, which allows them to rely on previously known techniques. However, this has a flaw: how can the user know that he communicated with the server he wanted to speak to, and not to another user trying to trick him? This explains the need of public-key encryption and digital signatures [START_REF] Rivest | A Method for Obtaining Digital Signature and Public-Key Cryptosystems[END_REF], and authenticated variants of those primitives. Another aspect of the Internet, is that the technical knowledge can be shared amongst everybody, and it is very hard to restrict its spread. So security has to hold even if the eventual attackers know the algorithm used to encrypt or sign messages.

With the emergence of cloud computing, the Internet is now a place where everybody puts all data online, and have servers do the work instead of their own computers. This sounds like a dream world, where everybody would have equally easy access to a lot of computing power when they need it. However, on this gigantic web, it is very hard to trust anybody with your private information. Thus, this dream seems to be unreachable: since encryption shouldn't reveal anything about the message they contain, how could someone use those data to provide you with a service? In the recent years, this challenge hasn't remained untouched. There have been many proposals that aim at bringing this dream closer to reality. For example, secure multi-party computation [Yao82; Yao86; Yun84; GMW87] would allow different users to compute together some function of their data, while only learning the output of said function. Another approach is fully homomorphic encryption [Gen09; BV11b; GSW13; AP14], which would allow anybody to perform some computation on one user's encrypted data, which could then be decrypted by that user in order to reveal the result of the computation. The last example we give, but not the least, is the paradigm of functional encryption [BSW11; GVW12; BO13; AGVW13; BF13; GGH+13]. It all started with identity-based encryption [BF01; BB04; Wat09; ABB10a; ABB10b], an encryption scheme which allows all users to use the same public key, and have each a secret key associated to their identity. One can encrypt using the public key and an identity, and only the user with this identity can recover the message. Even if multiple adversaries possessing different secret keys collude, they cannot recover anything at all. Then started the generalization process. Identity-based encryption was generalized with fuzzy identity-based encryption [START_REF] Sahai | Fuzzy Identity-Based Encryption[END_REF][START_REF] Agrawal | Functional Encryption for Threshold Functions (or Fuzzy IBE) from Lattices[END_REF], where it is possible to encrypt a message for an identity, and decryption is possible for users whose identity is almost the same. This allows constructions of scheme where the sender can chose a set of recipients to its message, as in broadcast encryption [START_REF] Fiat | Broadcast Encryption[END_REF]. Then attribute-based encryption [GPSW06; OSW07; GJPS08; LOS+10; Wat11; GVW13; BV16] was developped as a generalization of fuzzy identity-based encryption, where the choice of recipients can be given by any predicate. The next step was to hide the actual set of recipient, by hiding the identities, or attributes, used to encrypt the message, in what we call predicate encryption [KSW08; KY09; OT09; GMW15; GVW15]. The problem with all these definition is that the decryption is always all-or-nothing. A secret key either recovers completely the message or learns nothing at all. Hence the generalization to functional encryption. In this encryption scheme, it is possible to derive secret keys for different functions, that allow for computation over the message. Then, with a secret key associated with a function, and a ciphertext, it is only possible to recover the result of this function on the encrypted message. Thus, it allows for computation on encrypted data, and to recover the result in clear. Achieving functional encryption for any computation would make our dream world come true. Some constructions have been proposed, but they are relying on existence of really complex primitives like indistinguishability obfuscation or multilinear maps. These construction are also extremely inefficient to the point where even a proof of concept seems to be infeasible for the moment. This is why this thesis will be focusing on designing efficient schemes for the special case of inner-product functional encryption [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF], one of the smallest and yet powerful example of functional encryption that is non-trivial (at least superpolynomial set of possible functions) and that is not all-or-nothing -it allows partial computation on the data.

Chapter 1

1.1 Personal Contributions 3 Functional Encryption for Inner-Product Evaluations. In an inner-product functional encryption scheme (IPFE), the messages are vectors, and it is possible to generate keys for vectors y such that given an encryption of x, the secret key only reveals the partial information x, y about the vector x. At first glance, this functionality might seem like a step back, from the previous definitions and constructions of identity-based encryption and attribute-based encryption. Indeed, inner-product functional encryption cannot be used to construct those kind of cryptosystems. However, neither can identity-based encryption nor attribute-based encryption be used to build IPFE. So this notion is completely separated from previous work, in that its expressivity is somewhat diminished, but the fact that it provides partial information and not all-or-nothing looks interesting. And in fact, IPFE directly finds many natural applications, in theory as well as in practice.

First, it can be used directly to compute hamming distances between two words, and more generally, the inner-product is already a distance for vectors of fixed norm. So this could find some application for example in biometric identification. IPFE could also be used in machine learning, where support vector machine evaluation can be just an inner-product between a test vector and the data. In this case, a secret key could allow classifying the data with regard to one criterion, and learn nothing about the rest of it. It also allows to make statistical analysis, like weighted means, or by encrypting the cross-products between the entries, it can even be used for variance computations or other degree 2 polynomial in the input.

Theoretically, the inner-product functionality is interesting because it allows for all computation in NC 0 by encrypting the powers of x, and using polynomial representation. Moreover, as stated in [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] and refined in [START_REF] Agrawal | Functional Encryption for Bounded Collusions, Revisited[END_REF], it can be used to construct bounded collusion resistant functional encryption for any function. Note that this line of work has the upside of building functional encryption with succint ciphertexts, which was not reached by previous approaches. Another line of work [LV16; Lin16a; Lin16b; LT17; AS17] shows that a slightly more expressive functional encryption scheme can be used to construct indistinguishability obfuscation and functional encryption for all functions. It has also been used to construct efficient public trace and revoke schemes [START_REF] Agrawal | Efficient Public Trace and Revoke from Standard Assumptions: Extended Abstract[END_REF]. All these reasons made the line of work very interesting and a lot of improvements have been made to the first proposal. For example, hiding the vector y in the secret key [BJK15; DDM16; TAO16], using multiple vectors x i to be concatenated as input [START_REF] Abdalla | Multi-input Inner-Product Functional Encryption from Pairings[END_REF] (we note that those parts of vectors could be encrypted separately), or using pairings to compute bilinear functions without having to increase the size of the vectors [START_REF] Elisabetta | Practical Functional Encryption for Quadratic Functions with Applications to Predicate Encryption[END_REF].

Personal Contributions

The detailed list of my personal publications with full names, authors, and conferences is given at the end of the introduction. Here we briefly describe the goal of each of these papers, as well as the results they achieve. [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF] In this paper, we introduce the notion of inner-product functional encryption.

Contributions in this Thesis

We give the first very simple construction from the DDH assumption, and develop a framework to generically construct IPFE schemes from public key encryption schemes.

Chapter 1 Introduction

We also include a lattice-based instantiation whose security relies on the LWE assumption. The details for the security proof of the lattice-based scheme can be found in the full version [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF]. All of the constructions of this paper reach selective security against chosen-plaintext attacks.

[ABCP16] In this paper, we refine the security of our previous construction in order to get security against adaptive adversaries. We also include a new instantiation based on the DCR assumption. As an added contribution, we also show the equivalence between nonadaptive simulation-based security and adaptive indistinguishability. This paper wasn't published in any conference because the independent concurrent work [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] was accepted before, and therefore our paper was of little interest (the contributions left are the genericity of our framework, and the comparison between simulation-based security and indistinguishability). [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] achieves slightly better parameters under the same assumptions and also presents a construction of functional encryption for any circuits secure against bounded collusions from their IPFE constructions by transforming their non-modular IPFE schemes into stateful modular IPFE schemes. This second result can be used together with our framework for building IPFE schemes.

[BBL17] In this paper, we further refine our construction to reach security against chosenciphertext attacks. In order to do so, we rely on another building block: projective hash functions. The downside of this technique is that it gives up on the lattice-based concrete constructions, but we are able to show CCA security of our scheme based on the plain DDH assumption, without the use of pairings, as well as a generalization to any MDDH assumption. We also give another instantiation based on the DCR assumption to avoid the problem of efficiency for the decryption.

Other Contributions [BPMW16]

In this paper, we look at the circuit privacy property for fully homomorphic encryption (FHE). This property states that computing over encrypting data using an FHE scheme shouldn't reveal anything about the computation that has been performed but the result. In this paper we show a new technique of noise analysis for lattice-based fully homomorphic encryption schemes (we show the result for one particular scheme, but we believe the same analysis could be valuable in many other instances) in order to reach this property basically for free, adding just a really small noise to the output of the computation. Our result also applies to somewhat homomorphic encryption schemes, as it removes the necessity of bootstrapping (read: homomorphically evaluating the decryption circuit on an encryption of the secret key) the ciphertext in order to have circuit privacy.

Organization of this Thesis

In Chapter 2, we first define the notations that will be used throughout the thesis, and recall preliminaries that will be necessary for proving the security of our constructions.

In Chapter 3, we formally define the notion of inner-product functional encryption and its security model. We also show alternative models of security and compare them. We also show a way to reach function hiding almost for free against bounded collusions of adversaries via

Chapter 1

1.2 Organization of this Thesis 5 partial function hiding inner-product functional encryption, which we think is an interesting security notion in itself.

In Chapter 4, we combine the results of [ABDP15b; ABCP16] that generically builds innerproduct functional encryption from public key encryption with additional properties that are defined in that chapter.

In Chapter 5, we present the construction of [START_REF] Benhamouda | CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions[END_REF] which uses projective hash functions in order to generically build IPFE schemes secure against chosen-ciphertext attacks.

We then proceed to present concrete instantiations of our generic constructions based on standard assumptions in Chapters 6, 7, and 8, where we show constructions from the decisional Diffie-Hellman assumption, the decisional composite residuosity assumption, and the learning with errors assumptions. Each of these constructions have their upsides and their downsides that are discussed. Finally, we conclude in Chapter 9 with a brief summary of what we achieved and open questions that remain to be answered after this work.

Personal Publications

Notation and Preliminaries

Mathematical Notions

Integers, Sets. We denote by N the set of natural numbers, by Z the set of integers, and by R the set of real numbers. The curly brackets {} denotes a set, and : is used as an abreviation for "such that". If n ∈ N, then [n] denotes the set {1, . . . , n} of positive integers up to n, spf(n) denotes its smallest prime factor. The size of an integer log n is the number of bits used to represent it, where log will be used to denote the base-2 logarithm. The logarithm in natural base will be denoted ln. {0, 1} n denotes the set of n-bit strings, and if x is a string then |x| denotes its length. More generally, if S is a set, then S n is the set of n-tuples of elements of S and |S| denotes the cardinality of S. We denote by U (S) the uniform distribution on S, and we use the notation x $ ← S to say that x is sampled uniformly at random from S. For any operation • (e.g., + or •), we extend it to sets in the following way: if t is an element and S is a set, t • S = {t • s : s ∈ S}.

Vectors and Matrices.

Let R be a commutative ring. We denote the set of d-dimensional column vectors over R by R d , the set of d-dimensional row vectors by R 1×d , and the set of × d matrices by R ×d . Unless explicitly said otherwise, each vector is a column vector. We denote vectors by using either boldface lower-case letters or lower-case letters with an arrow over it as in b and #" b . We denote matrices by using boldface upper-case letters like in A. We have two possible notations for vectors, as we sometimes need to consider vectors of vectors ( #" b ) and vectors of matrices ( #" A). We denote the concatenation of two vectors a and b by (a, b). The transpose of a matrix is denoted A , and the inner-product between two vectors by •, • . The ith coefficient of a vector b or #" b is denoted by b i , while the ith coefficient of a vector of vectors #" b is a vector and is denoted by b i . The jth coefficient of this latter vector is b i,j . The same convention is used with coefficients of matrices and coefficients of vectors of matrices. Unless otherwise stated, the norm • considered in this paper is the 2 norm.

Abelian Groups. We extensively use Abelian groups, especially when dealing with projective hash functions. In particular, in our concrete instantiations of PHFs in Chapters 6 and 7, we use prime-order cyclic groups over an elliptic curve or subgroups of the (multiplicative) group Z * N , for some positive integer N . We denote the elements of such groups by using the Fraktur script like in g or b. By extension, even in our generic constructions and definitions in Chapter 5, we also use this font to indicate values which, in our concrete instantiations, are group elements in such group G or vectors of such elements. However, we are also considering other Abelian groups (e.g., the group K of hashing keys of a key-homomorphic PHF in Definition 5.2.1) that are not related to cryptographic assumptions and for which group elements are not denoted using the Fraktur script.

Except if explicitly stated otherwise, we use additive notation for all our Abelian groups, even when this is not usual (as in the case of subgroups of Z * N ). Let G be an Abelian group. We recall that if g is a group element of order M , then we have a canonical monomorphism w ∈ Z M → w • g ∈ G. If G is a multiplicative group, this monomorphism corresponds to exponentiation. Hence, we denote the inverse of this monomorphism by log g . That is, if b = w • g, then log g b = w.

Furthermore, let R be R = Z or R = Z M with M being such that the order of any group element in G divides M . Then G can be seen as a R-module. This means that for any w ∈ R and g ∈ G, w • g is well defined. Importantly, by using additive notation, we can use the Chapter 2

2.1 Notation and Preliminaries 9 standard "matrix-vector" notation without prior explanation.

Asymptotic Behaviors. For two sequences of real numbers f = (f n ) n∈N , g = (g n ) n∈N we use the following notations:

• f = O(g) if ∃M > 0, n 0 ∈ N such that ∀n > n 0 , |f n | ≤ M |g n |; • f = o(g) if ∀ > 0, ∃n 0 ∈ N such that ∀n > n 0 , |f n | ≤ |g n |; • f = Ω(g) if g = O(f ); • f = ω(g) if g = o(f ).
We also often abuse the notation by writing directly an expression, for example f = O(n 2 ) instead of f = O(n → n 2 ), or using those notations as functions, for example we write f = n ω(1) if there exists a sequence g such that f = n g and g = ω(1). We say that a function is polynomial in n if it is O(n c ) for some constant c. We say that it is superpolynomial if it is n ω (1) . We say that it is constant if it is O(1).

Probability. If X is a probability distribution, we will write v $ ← X when v is sampled from the distribution X. Given two distributions X, Y over a finite or countable domain D, their statistical distance is defined as

∆(X, Y ) = 1 2 v∈D |X(v) -Y (v)|. (2.1)
When defining a probability distribution, we use the symbol ∝ to denote proportionality, the distribution can then be obtained by taking into account the normalizing factor. We will often implicitly use the following lemmas. Proof. In the sum in Equation 2.1, exactly 2|t| terms are non-zero: the ones corresponding to y in (S \ (S + t)) ∪ ((S + t) \ S). And these terms are equal to 1/|S|. Algorithms. Unless otherwise stated, all the algorithms considered in this paper are randomized, and thus A (x) the result of running algorithm A with input x can be seen as a probability distribution. We sometimes explicit the random tape of A : A (x; r) denotes running algorithm A on input x with randomness r. If A is an algorithm, we will write v $ ← A (x) to denote running A on input x and assigning the result to the variable v. We will instead write v ← A (x) if A is deterministic. We also use this definition for any computation, e.g., v ← x + y, thus we reserve the notation = for equality testing and definitions (or assignments without computation). An algorithm is called polynomial, or efficient if its running time is polynomial in the size of its inputs. We sometimes allow algorithms to have oracle access to probability distributions or other algorithms and write A O the fact that the algorithm A can use oracle O.

Provable Security

Security Parameter. In public key cryptography, any problem can be solved if given enough time and efforts. The goal of provable security is to measure the quantity of time and efforts required to solve a problem. To do so, we implicitely have a certain security parameter κ, and every integers, vectors, matrices, functions that we define will implicetely be defined with regard to that security parameter, and we often omit this in the definitions to make everything more readable. We explicitely remind this sometimes, for example our algorithms Setup will take as input the security parameter in unary representation 1 κ . The reason it is represented in unary is because we want the algorithm to run in a time that is polynomial in κ, so its input must have size κ. We usually state that an algorithm is efficient if its running time is polynomial in κ, and inefficient if not. Similarly, we say that a function f is negligible if it is o(1/κ c ) for any constant c ∈ N, and we say that a probability p is overwhelming if 1p is negligible. We consider a scheme secure if there is no efficient algorithm that has a non-negligible probability of "breaking the scheme". Given two distributions X, Y over a finite or countable domain D, we say that they are equal if their statistical distance ∆(X, Y ) is 0. We say that they are statistically indistinguishable if ∆(X, Y ) is negligible. We say that they are computationally indistinguishable if ∆(A X , A Y ) is negligible for all probabilistic polynomial time (i.e., efficient) algorithms A . As an analogy with the applications, we often call adversary an algorithm designed to attack the security of a scheme.

Code-Based Games. We use the code-based game-playing [START_REF] Bellare | The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs[END_REF] to define the security notions. In such games, there exist procedures for initialization (Initialize) and finalization (Finalize) and procedures to respond to adversary oracle queries. A game G is executed with an adversary A as follows. First, Initialize executes and its outputs are the inputs to A . Then A executes, its oracle queries being answered by the corresponding procedures of G. When A terminates, its output becomes the input to the Finalize procedure. The output of the latter, denoted G(A ), is called the output of the game, and "G(A ) = y" denotes the event that the output takes a value y. Boolean flags are assumed initialized to false. Games G i , G j are identical until bad if their code differs only in statements that follow the setting of bad to true.

Basic Cryptographic Primitives

One-Time Signature and Collision Resistant Hash Functions

One-Time Signatures. The purpose of a one-time signature is to prevent messages to be tampered with. Basically, it allows to sign a message and give out the verification key that guarantees that the message was generated as a whole, and that no parts of it has been replaced, added, or removed. Definition 2.2.1 (One-Time Signature). A one-time signature scheme is a tuple OT S = (Setup, Sign, Verify) of three probabilistic polynomial time algorithms:

• Setup(1 κ ) → (sk, vk). On input security parameter κ outputs a signing key sk and a verification key vk;

• Sign(sk, m) → (σ). On input signature key sk and message m returns a signature σ;

Chapter 2 This property is not only useful for cryptographic purposes, but it can also be used to check if two users have the same data for example, they just have to compare the fixed-length hash of their database.

Public Key Encryption

Some of our generic construction of inner-product functional encryption are using public key encryption scheme as building blocks. We state here the formal definition of PKE, as well as the security notion we require for our constructions.

Definition 2.2.4 (Public Key Encryption). A public key encryption (PKE) scheme E consists of 4 probabilistic polynomial time algorithms:

• Setup(1 κ ) → (pp, sk, pk). On input security parameter κ outputs public parameters pp, secret key sk, and public key pk;

• Encrypt(pp, pk, m) → ct. On input public parameter pp, public key pk, and plaintext m, outputs ciphertext ct;

• Decrypt(pp, sk, ct) → m or ⊥. On input public parameters pp, secret key sk, and ciphertext ct, outputs a message m or an error symbol ⊥. Definition 2.2.5 (Indistinguishability under Selective Chosen-Plaintext Attacks). For a PKE scheme E, we define selective security against chosen-plaintext attacks (s-IND-CPA security) via the security game depicted on Figure 2.1: we define the advantage of an adversary

A to be Adv s-ind-cpa E,κ (A ) = 2 • Pr[Exp s-ind-cpa-b E,κ (A ) = 1] -1 .
Then we say that E is secure against chosen-plaintext attacks

(s-IND-CPA secure) if Adv s-ind-cpa E,κ (A ) is negligible for all probabilistic polynomial time A . Game Exp s-ind-cpa-b E,κ (A ) proc Initialize(κ, m * 0 , m * 1 ) (pp, sk, pk) $ ← Setup(1 κ ) Return (pp, pk) proc Encrypt() ct $ ← Encrypt(pp, pk, m * b ) Return ct proc Finalize(b') Return (b = b) Figure 2.1: Game Exp s-ind-cpa-b E,κ (A ) defines s-IND-CPA security of E.
The more standard security notion would be adaptibe security against chosen-plaintext attacks, where the challenge messages m * 0 and m * 1 would be chosen when calling Encrypt. We chose to only use a selective notion because it is a weaker assumption, and it was sufficient for our construction.

Functional Encryption. Functional Encryption has been introduced to generalize the concept of public key encryption and identity-based encryption. We briefly recall the definition for completeness. We don't elaborate on the security definitions, since we will discuss that matter on the special case of inner-product functional encryption in Chapter 3.

A functionality F defined over (M y , M x ) is a function M y × M x → Σ ∪ {⊥}, where M y is a key space, M x is a message space, and Σ is an output space that does not contain the special symbol ⊥.

A functional encryption scheme for functionality F [ONe10; BSW11] is a tuple FE = (Setup, KeyDer, Encrypt, Decrypt) of four probabilistic polynomial time algorithms:

• Setup(1 κ ) → (pp, msk, mpk). On input security parameter κ outputs public parameters pp, master secret key msk, and master public key mpk;

• KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ M y , outputs user secret key sk y ;

• Encrypt(pp, mpk, x) → ct x . On input public parameter pp, master public key mpk, and plaintext x ∈ M x , outputs ciphertext ct x ;

• Decrypt(pp, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs a message m or an error symbol ⊥.

We say that a FE scheme is correct if m = F(y, x). The special case of inner-product functional encryption is F(y, x) = x, y .

Projective Hash Functions

Before being able to define projective hash functions, we have to define what is a subset membership problem, which will be used in the definition of PHF.

Chapter 2

2.3 Projective Hash Functions 13

Subset Membership Problems

Our framework uses subset membership problems, which were originally defined in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF].

Basically, a subset membership problem defines an NP language L ⊂ X , in which a random word in L is hard to distinguish from a random word in X \ L. In this thesis, we consider a slight extension, where we instead require a random word in L to be hard to distinguish from a random word in a given set L ⊆ X \ L. More formally, a subset membership problem P specifies an ensemble (I κ ) κ≥0 of distributions. For every value of a security parameter κ ≥ 0, I κ is a probability distribution of instance descriptions. An instance description Λ = Λ[X , L, W, , L] specifies the following: (a) finite, non-empty sets X , L, W, and L, such that L is a proper subset of X and L is a non-empty subset of X \ L, (b) a binary relation ⊂ X × W. For b ∈ X and w ∈ W, we say that w is a witness for b if (b, w) ∈ . We require that instance descriptions and elements of X and W can be uniquely encoded as bitstrings of length poly(κ).

A subset membership problem satisfies the following properties:

1. I κ is efficiently samplable, which means that there exists a probabilistic polynomial time instance sampling algorithm that on input 1 κ samples an instance Λ according to the distribution I κ ;

2. is efficiently samplable, which means that there exists a probabilistic polynomial time subset sampling algorithm that on input Λ outputs a random b ∈ L together with a witness w ∈ W for b; the distribution over implicitly defines a distribution over L;

3. L is efficiently samplable;

4. X is efficiently recognizable, which means that there exists a deterministic polynomial algorithm that on input (Λ, ζ) checks whether ζ is a valid binary encoding of an element of X ;

5. is efficiently recognizable;

6. (L, L)-indistinguishability: a sample from L is computationally indistinguishable from a sample from L.

We do not require the distributions over , L, and L to be uniform. However, when we do not specify these distributions, we implicitly use the uniform distributions.

Projective Hash Functions

We are now ready to state the formal definition of projective hash functions. Definition 2.3.1 (Projective Hash Function). Let P be a subset membership problem, specifying an ensemble (I κ ) κ of instance distributions. A projective hash function for P is a tuple PHF = (hashkg, projkg, hash, projhash) of four probabilistic polynomial time algorithms:

• hashkg(Λ) generates a hashing key hk in some set K for the instance Λ = Λ[X , L, W, ],

• projkg(hk) (deterministically) derives from the hashing key hk a projection key hp,

• hash(hk, b) (deterministically) computes the hash value H (in some efficiently recognizable set Π) of b ∈ X under hk ∈ K,

• projhash(hp, b, w) (deterministically) computes the projected hash value pH of b ∈ L using a witness w ∈ W.

A PHF must be complete, in the following sense:

• For any instance Λ, for any b ∈ X and w ∈ W, such that (b, w) ∈ , for any hashing key hk ∈ K, if hp ← projkg(hk), then hash(hk, b) = projhash(hp, b, w) .

The instance Λ is implicitly included in the hashing key hk and the projection key hp.

The standard statistical requirement for a projective hash function is to be smooth. The smoothness property essentially states that the hash of a word not in the language is close to uniform, and so unguessable. In our proof, we will require other properties that we define in the beginning Chapter 5.

Additional Preliminaries for Concrete Instantiations

We now recall some additional preliminaries that will be required for our concrete instantiations, starting with preliminaries that will be used for the instantiations based on DCR, and then ones that will be used for the instantiations based on LWE.

Basic Number Theory

Let N be a positive integer. Let ϕ(N ) be the Euler totient function. For any integer a and an odd prime q, the Legendre symbol a q is defined as

a q =        0
If a ≡ 0 (mod q) +1 If a ≡ 0 (mod q) and for some integer y, a ≡ y 2 (mod q) -1 If a ≡ 0 (mod q) and there is no such y For any integer a and any positive odd integer N , the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of N , a N := t i=1 a p i α i , where

N = t i=1 p α i i for distinct primes p i . Let J N = {a ∈ Z N : a N = 1}; clearly J N is a subgroup of Z * N .
The Jacobi symbol can be computed in polynomial time, given only a and N [JOA96, Algorithm 2.149].

Gaussians and Lattices

We first recall the definition of a lattice before defining discrete Gaussian distribution over a lattice. We also recall some lemmas that will be used in Chapter 8.

Lattices.

A m-dimensional lattice Λ is a discrete additive subgroup of R m (e.g., Z m ). For an integer k < m and a rank k matrix B ∈ R m×k , Λ(B) = {Bx ∈ R m : x ∈ Z k } is the lattice generated by the columns of B.

Gaussians. The n-dimensional Gaussian function

ρ : R n → [0, 1] is defined as ρ(x) = exp(-π • ||x|| 2 ) = exp(-π • x, x ) .
Chapter 2

Additional Preliminaries for Concrete Instantiations 15

Applying a linear transformation given by a (not necessarily square) matrix B with linearly independent columns yields the (possibly degenerate) Gaussian function

ρ B (x) = ρ(B -1 x) = exp(-π • x Σ -x) If x ∈ Span(B) = Span(Σ) 0 otherwise
where Σ = BB ≤ 0. Because ρ B is distinguished only up to Σ, we usually refer to it as

ρ √ Σ .
We say that a distribution D is subgaussian with parameter σ if there exists a constant

k ∈ R such that D(x) ≤ k • ρ σ (x).
Definition 2.4.1 (Smoothing parameter). For a lattice Λ ⊆ Z m and positive real > 0, the smoothing parameter η (Λ) is the smallest real σ > 0 such that ρ 1/σ (Λ * \ {0}) ≤ , where

Λ * = {x ∈ R m : x Λ ⊆ Z}.
The next result gives a bound on the smoothing parameter of a generic lattice.

Lemma 2.4.2 ([MR07, Lemma 3.3]). Let Λ be any rank-m lattice and be any positive real.

Then

η (Λ) ≤ λ m (Λ) • ln(2m(1 + 1/ )) π
where λ m (Λ) is the smallest R such that the ball B R centered in the origin and with radius R contains m linearly independent vectors of Λ.

Corollary 2.4.3.

η (Z ) ≤ ln(2 (1 + 1/ ))
π The following lemma gives a bound on values drawn from subgaussian distributions.

Lemma 2.4.4 ([AP14, Lemma 2.1]

). There exists a universal constant C > 0, such that

Pr x > Cσ √ m ≤ 2 -Ω(m)
where x is drawn from a subgaussian distribution over Z m with parameter σ.

Lemma 2.4.5. Let ρ √ Σ (x) be the probability that a gaussian random variables of covariance matrix Σ is equal to x. Then, for any invertible matrix β,

ρ √ Σ (β -1 x) = ρ β √ Σ (x) . Lemma 2.4.6. Let Λ ⊂ R n be a lattice. For any Σ ≥ 0 and c ∈ R n , we have ρ √ Σ (Λ + c) ≤ ρ √ Σ (Λ). Moreover, if √ Σ ≥ η (Λ) for some > 0 and c ∈ Span(Λ), then ρ √ Σ (Λ + c) ≥ 1- 1+ • ρ √ Σ (Λ).
Generalized Leftover Hash Lemma. The following text and lemma are taken verbatim from [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF]. The predictability of a random variable A is max a Pr[A = a], and its minentropy H ∞ (A) islog(max a Pr[A = a]). The min-entropy of a distribution tells us how many nearly uniform random bits can be extracted from it.

Chapter 2 Preliminaries

Consider now a pair of (possibly correlated) random variables A, B. If the adversary finds out the value b of B, then predictability of A becomes max a Pr[A = a|B = b]. On average, the adversary's chance of success in predicting A is then

E b $ ←B [max a Pr[A = a|B = b]].
Note that we are taking the average over B (which is not under adversarial control), but the worst case over A (because prediction of A is adversarial once b is known). Again, it is convenient to talk about security in log-scale, which is why we define the average min-entropy of A given B as simply the logarithm of the above:

H∞ (A|B) = -log E b $ ←B [max a Pr[A = a|B = b]] = -log E b $ ←B
I, ∆((H X (W ), X, I), (U , X, I)) ≤ 1 2 2 -H∞(W |I) 2 .
Chapter 3

Chapter 3

Inner-Product Functional Encryption

In this Chapter, we provide the formal definition of inner-product functional encryption and discuss the multiple ways to model its security, as well as the desirable properties it can have.

We start off with the definition as we introduced in [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF] and explain the functionality it provides together with the standard security notion that we will use: indistinguishability under chosen-plaintext attack.

Then we compare this model with the weaker model of selective security, and with the other intuitive way to model security: simulation-based security. We show that adaptive indistinguishability-based security is equivalent to the non-adaptive simulation-based security (result from our paper [START_REF] Abdalla | Better Security for Functional Encryption for Inner Product Evaluations[END_REF]). We also introduce the security against chosen-ciphertext attacks. We define the related tag-based inner-product functional encryption, which is a variant of IPFE that is easier to analyze in the case of CCA security, and we show how to translate it into a CCA secure standard inner-product functional encryption scheme, as done in our contribution [START_REF] Benhamouda | CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions[END_REF]. Finally, we discuss the function hiding hiding property, another desirable security property for an inner-product encryption scheme which means that a secret key doesn't reveal the computation it allows. We also show how to obtain weak versions of this property without any additional assumption. This work is exclusive to this thesis.

Contents

Definition and Security Model

Definition

The definition of an inner-product functional encryption scheme is best illustrated with an example of what it allows to do. A diagram showing the functionality provided by an IPFE scheme can be found on Figure 3.1. In this case, a user Bob transmits to another user Alice the inner product x, y between a vector x that he knows and any vector y for which Alice has a certified secret key:

• The trusted authority generates a pair (mpk, msk) of master public key and master secret key. The former can be made public and retrieved by Bob, while the later will be kept secret by the authority.

• Bob uses the master public key mpk to encrypt his vector x. He then makes public the resulting ciphertext ct x .

• Alice makes a request for a secret key sk y for her vector y, which the authority derives using the master secret key msk, and privately sends to Alice if she is entitled.

• Alice uses her key sk y to decrypt the ciphertext ct x that she received from Bob and receives the value x, y .

We say that an inner-product functional encryption scheme is correct if the result is indeed x, y . • Setup(1 κ , 1 ) → (pp, msk, mpk). On input security parameter κ and functionality parameter outputs public parameters pp, master secret key msk, and master public key mpk;

Setup

• KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ R , outputs user secret key sk y ;

• Encrypt(pp, mpk, x) → ct x . On input public parameter pp, master public key mpk, and plaintext x ∈ R , outputs ciphertext ct x ;

• Decrypt(pp, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs a message m ∈ R or an error symbol ⊥.

To lighten the notations, we sometimes omit the public parameters pp or assume they are included in the public key. We also sometimes implicitely assume that y is included in clear in the user secret key sk y . We will focus on the rings Z q for some prime number q (we also sometimes denote this prime number p to avoid confusions), and N. We will sometimes refer to the first case as modular inner-product functional encryption, and to the second as non-modular inner-product functional encryption. There are some major differences between the two: modular IPFE is more friendly for security analysis and also for applications. However, the only instantiations we know of requires the computation of a discrete logarithm in order to decrypt, which means that we can only decrypt inner-products in a fixed polynomial range, thus the whole plaintext space is not used. In the case of non-modular IPFE, the computation is usually done modulo some integer, but we require the inner-produt result to be smaller than the modulus for security issues. [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] describes a technique to build modular IPFE schemes from non-modular one, the downside being that the key generation algorithm KeyDer has to be stateful. The idea is to remember the queries that were answered, and change the queries that would allow a break into queries that give the same information without threatening the security of the scheme.

Correctness.

To account for the previous remarks, we allow the Decrypt algorithm to output ⊥ if x, y is outside of a polynomial sized set P fixed at setup. We also denote the plaintext space M x and the key space M y , and they may be smaller than the full ring R. Hence the following correctness property: An IPFE scheme is correct if for any x ∈ M x , y ∈ M y ,(pp, msk, mpk) $ ← Setup(1 κ , 1 ), sk y $ ← KeyDer(pp, msk, y), ct x $ ← Encrypt(pp, mpk, x). Then if x, y ∈ P, it holds that Decrypt(pp, sk y , ct x ) = x, y .

Indistinguishability-Based Security

We will use a left-or-right indistinguishability based definition of security also called security against chosen-plaintext attacks. Intuitively, it means that an eavesdropping adversary cannot tell appart between encryptions of messages of his chosing. For example, this implies that the scheme has no weak plaintexts, otherwise the adversary could choose to attack this particular message, and it also means that the scheme is non-deterministic, because this would lead to a trivial attack in the model. It has been used for many years in the context of public key encryption as well as symmetric key encryption, and has been adapted to identity-based encryption and functional encryption as the most intuitive security property. As for the definition of IPFE, we give an informal illustration of the security model for intuition on Figure 3.2. Here we only pictured a single challenge couple (x * 0 , x * 1 ) because as we show later, it is equivalent. Definition 3.1.2 (Indistinguishability under Chosen-Plaintext Attacks). For an innerproduct functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define security against chosen-plaintext attacks (IND-IPFE-CPA security) via the security game depicted on Figure 3.3: we define the advantage of an adversary A to be

Adv ind-ipfe-cpa F E,κ (A ) = 2 • Pr[Exp ind-ipfe-cpa-b F E,κ (A ) = 1] -1 .
Then we say that FE is secure against chosen-plaintext attacks

(IND-IPFE-CPA secure) if Adv ind-ipfe-cpa F E,κ (A ) is negligible for all probabilistic polynomial time A .
The event bad corresponds to the adversary making queries that trivially allows him to find b. Those are attack that we cannot be secure against, by definition of the functionality. The goal of the adversary is to find b without having access to those queries.

Game Exp ind-ipfe-cpa-b F E,κ (A ) proc Initialize(κ, ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V y ← ∅ V x ← ∅ Return (pp, mpk) proc KeyDer(y) V y ← V y ∪ {y} sk y $ ← KeyDer(pp, msk, y) Return sk y proc Encrypt(x 0 , x 1 ) V x ← V x ∪ {(x 0 , x 1 )} ct $ ← Encrypt(pp, mpk, x b ) Return ct proc Finalize(b') if bad then return false Return (b = b) Figure 3.3: Game Exp ind-ipfe-cpa-b F E,κ (A ) defines IND-IPFE-CPA security of FE. The event bad corresponds to ∃y ∈ V y , ∃(x 0 , x 1 ) ∈ V x , x 0 , y = x 1 , y .
Because we are dealing with public key encryption schemes, we can without loss of generality only consider the adversaries A that only makes one encryption query (x * 0 , x * 1 ). In particular, we have the following theorem: Chapter 3

Definition and Security Model 21

Theorem 3.1.3. For any adversary A making q encryption queries {(x j 0 , x j 1 )} j∈ [q] , there exists an adversary B making only 1 encryption query which runs in roughly the same time as A and such that Adv ind-ipfe-cpa

F E,κ (B) ≥ 1 q • Adv ind-ipfe-cpa F E,κ (A )
Proof. We prove this theorem by using a standard hybrid argument [START_REF] Goldwasser | Probabilistic Encryption[END_REF]. The adversary B is as follows: It first picks a random number i ∈ {0, . . . , q}. It forwards A 's queries to Initialize, KeyDer and Finalize. However, it behaves differently with Encrypt on input (x j 0 , y j 1 ):

• If i<j, it sets ct = Encrypt(pp, mpk, x 0 );

• If i=j, it invokes Encrypt;

• If i>j, it sets ct = Encrypt(pp, mpk, x 1 ). Now, to analyze the advantage of B, we define the following hybrid experiment:

Game H i proc Initialize(κ, ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V y ← ∅ V x ← ∅ Return (pp, mpk) proc KeyDer(y) V y ← V y ∪ {y} sk y $ ← KeyDer(pp, msk, y) Return sk y proc Encrypt(x 0 , x 1 ) if |V | < i then ct $ ← Encrypt(pp, mpk, x 0 ) if |V | ≥ i then ct $ ← Encrypt(pp, mpk, x 1 ) V x ← V x ∪ {(x 0 , x 1 )} Return ct proc Finalize(b') if bad then return false Return (b = b)
Notice that we have:

Adv ind-ipfe-cpa F E,κ (A ) = 2 • Pr[Exp ind-ipfe-cpa-b F E,κ (A ) = 1] -1 = Pr[Exp ind-ipfe-cpa-0 F E,κ (A ) = 1] + Pr[Exp ind-ipfe-cpa-1 F E,κ (A ) = 1] -1 = Pr[b = 1|b = 1] -Pr[b = 1|b = 0] = Pr H 1 [b = 1] -Pr H q+1 [b = 1] = i∈[q] Pr H i [b = 1] -Pr H i+1 [b = 1] ≤ i∈[q] Pr H i [b = 1] -Pr H i+1 [b = 1] = q • Adv ind-ipfe-cpa F E,κ (B)
Chapter 3 Inner-Product Functional Encryption Remark 3.1.4. We note that this reduction is not tight in the general case, but with most instantiations, one can use random self-reducibility of the underlying assumption to have a better reduction in the case of multiple encryption challenges. A good example would be the resulting scheme based on the decisional Diffie-Hellman assumption presented in Chapter 6.

In the rest of this chapter, we will present alternative security notions and discuss their relations with IND-IPFE-CPA security.

Alternative Security Models

Selectivity vs. Adaptivity

A natural weakening of IND-IPFE-CPA security is security against selective chosen-plaintext attacks. The difference with the previous definition is that in this new model, the adversary has to chose the challenge messages beforehand. It cannot see the public key or make any key query before he choses the messages. This means that the security will be easier to prove: for example, in the special case of IPFE, this means that the adversary has to chose the challenge vectors x * 0 and x * 1 , so that its queries are restricted to a known set (x * 1 -x * 0 ) ⊥ . To avoid ambiguity, we sometimes refer to IND-IPFE-CPA as adaptive security in contrast with selective security. We now define s-IND-IPFE-CPA security and compare it to IND-IPFE-CPA. We also show that a modular IPFE scheme that satisfy s-IND-IPFE-CPA security can be slightly modified to be IND-IPFE-CPA secure if it satisfies a very natural homomorphic property. Definition 3.2.1 (Indistinguishability under Selective Chosen-Plaintext Attacks). For an IPFE scheme FE, we define selective security against chosen-plaintext attacks (s-IND-IPFE-CPA security) via the security game depicted on Figure 3.4: we define the advantage of an adversary A to be

Adv s-ind-ipfe-cpa F E,κ (A ) = 2 • Pr[Exp s-ind-ipfe-cpa-b F E,κ (A ) = 1] -1 .
Then we say that FE is secure against chosen-plaintext attacks (s-IND-IPFE-CPA secure) if Adv s-ind-ipfe-cpa F E,κ (A ) is negligible for all probabilistic polynomial time A .

The following theorem states the relation between those two security notions. Basically, if the adversary is restricted in his queries, he can choose randomly beforehand, and abort if it decides it was not the query he wanted. Its advantage will drop by the probability of guessing correctly. This technique is called complexity leveraging, and is widely used when dealing with more complex tools such as functional encryption for all circuits, or indistinguishability obfuscation. Theorem 3.2.2. For any IPFE scheme FE with message space M x , if M x is polynomial in κ and FE is s-IND-IPFE-CPA secure, then it is also IND-IPFE-CPA secure. More precisely, for any adversary A , there exist an adversary B which runs in roughly the same time as A , and such that:

Adv s-ind-ipfe-cpa F E,κ (B) ≥ 1 |M x | 2 • Adv ind-ipfe-cpa F E,κ (A )
Chapter 3

Alternative Security Models 23

Game Exp s-ind-ipfe-cpa-b Proof. B just guesses the challenge messages x * 0 and x * 1 of A and does the same as A . If B guessed wrongly, it just aborts and output a uniformly random guess b , otherwise, he is correct when A is correct. The result follows from the fact that B guesses correctly with probability 1 |Mx| 2 . This implies that an IPFE scheme with polynomial message space is necessarily

F E,κ (A ) proc Initialize(κ, , x * 0 , x * 1 ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V y ← ∅ Return (pp, mpk) proc KeyDer(y) V y ← V y ∪ {y}
IND-IPFE-CPA secure if it is s-IND-IPFE-CPA secure.
Moreover, this is true if the message space is independent of, or logarithmic in the security parameter κ. However, this factor really impacts the concrete security of the scheme, which is why adaptive security is an appealing property. It has been shown that if a functional encryption scheme supports all polynomial functions, then one can use the functionality provided by the scheme to build a tightly adaptively secure scheme [START_REF] Ananth | From Selective to Adaptive Security in Functional Encryption[END_REF]. However, this is not as simple in the case of functional encryption limited to inner-product evaluations. We proceed to show a tight (independent of the size of the message space) reduction from IND-IPFE-CPA security to s-IND-IPFE-CPA security, which only works for certains modular IPFE but the same idea will be used in Chapter 4 to build directly IND-IPFE-CPA secure schemes. First, we need to define the additively homomorphic property that will be needed for this transformation. Definition 3.2.3 (Additive Homomorphism). We say that an inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) is additively homomorphic if it is possible to add encryptions: ∀(x 0 , x 1 ) ∈ M 2

x , (pp, msk, mpk)

$ ← Setup(1 κ , 1 ), Encrypt(pp, mpk, x 0 ) + Encrypt(pp, mpk, x 1 ) = Encrypt(pp, mpk, x 0 + x 1 )
for some operation + on the ciphertexts.

Note that we are talking about probability distributions. Moreover, we don't actually need rigorous equality for our reduction as computational inditinguishability would be enough. However, this definition makes the notations much simpler and the proof easier to read.

We now move onto the construction of our IND-IPFE-CPA scheme. We construct an IPFE scheme using another IPFE scheme, so for the sake of readability and simplicity, we add a Chapter 3 Inner-Product Functional Encryption prime to elements that corresponds to the new scheme and use notations without primes for the building block.

Adv s-ind-ipfe-cpa F E,κ (B) = 1 2 • Adv ind-ipfe-cpa F E ,κ (A )
Proof. We prove this theorem by showing such an adversary B. B first picks a random t $ ← R , and a random bit b * $ ← {0, 1}. Then, it acts as follows on A 's queries:

• Initialize (κ, ): B calls Initialize (κ, , 0, (t, 1));

• KeyDer(y): B appendst, y to y, and calls KeyDer((y, -t, y ));

• Encrypt(x * 0 , x * 1 ): B calls Encrypt() to get ct , and then sets and returns ct = ct + FE.Encrypt(pp, mpk, (x b * , 0));

• Finalize(b ): B checks if A has triggered the bad event, and trigger it in this case.

Otherwise, it calls Finalize(b = b * ).

Notice that in both experiments Exp s-ind-ipfe-cpa F E,κ (B) and Exp ind-ipfe-cpa F E ,κ (A ), bad is the same event because B never triggers it unless A did: for any y ∈ R , (t, 1), (y, -t, y ) = 0. We now analyze the advantage of B.

Chapter 3

3.2 Alternative Security Models 25

• If b = 0, then ct = FE.Encrypt(pp, mpk, 0), and A receives FE .Encrypt(pp, mpk, x * b ). This means that in this case, B wins whenever A wins.

• Now, if b = 1, then ct = FE.Encrypt(pp, mpk, (t, 1)), and thus A receives FE.Encrypt(pp, mpk, (x * b + t, 1)). We want to show that in this case, A cannot correctly guess b with probability more than 1 2 , because its view is independent of b. Indeed, we show that replacing t by t = t + x * 1-b -x * b yields the same keys sk y , while changing the message from x * b to x * 1-b . The important thing to notice is just that for any query y that doesn't trigger bad:

x * 0 , y = x * 1 , y =⇒ t , y = t, y .
Thus, the advantage of B is

Adv s-ind-ipfe-cpa F E,κ (B) = 1 2 • Adv ind-ipfe-cpa F E ,κ (A ).

Simulation-Based Security

Another very intuitive way to model the security is what we call simulation-based security. In this setting, in order to prove security, we show that it is possible to generate the same view (ciphertexts and keys), or at least a view that fools any adversary, only knowing the outputs of the functionality, and not the inputs. In our context, this means generating a ciphertext, as well as secret keys without knowing the underlying plaintext vector x, only using the results x, y . This is formalized by a simulator that generates a view given the inner-products values, and the adversary tries to tell apart if it's interacting with the simulator, or if it has been given normally generated keys and ciphertext. Simulation-based security is a very strong notion of security. Its relation to indistinguishabilitybased security has been well studied [ONe10; AGVW13; DIJ+13], and it has been shown to be impossible to reach in the case of functional encryption for very simple functionalities like IBE [START_REF] Boneh | Functional Encryption: Definitions and Challenges[END_REF], and even for any non-trivial functionality [START_REF] Bellare | Semantically-Secure Functional Encryption: Possibility Results, Impossibility Results and the Quest for a General Definition[END_REF]. It is easy to see that in general, simulation-based security implies indistinguishability-based security, because as the simulator doesn't know the plaintext, it yields the same view whether it was x * 0 or x * 1 , as long as the adversary only makes allowed queries. Definition 3.2.6 (Non-Adaptive Simulation-Based Security.). For an inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define non-adaptive simulation security (NA-SIM security, for short) via the security game depicted on Figure 3.5: we define the advantage of an adversary A to be

Adv na-sim-ipfe F E,κ (A ) = 2 • Pr[Exp na-sim-ipfe-b F E,κ (A , S ) = 1] -1 .
Then, we say that FE is simulation secure against non-adaptive adversaries (NA-SIM secure, for short) if there exists a probabilistic polynomial time simulator S such that

Adv na-sim-ipfe F E,κ (A , S
) is negligible for all probabilistic polynomial time A .

Chapter 3 Inner-Product Functional Encryption In this section, we compare the two a-priori incomparable security notions of NA-SIM security and IND-IPFE-CPA security. It is a known result that simulation security implies indistinguishability for any functionality. The next theorem shows that IND-IPFE-CPA security notion lies somewhere between SIM security and NA-SIM security for the innerproduct functionality. Although we prove this result from scratch for completeness, we remark that it follows from the work of [START_REF] Adam | Definitional Issues in Functional Encryption[END_REF], because the inner-product functionality is preimage sampleable, as noted in [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF]. Theorem 3.2.7. Let FE be any inner-product functional encryption scheme. If FE is

Game Exp na-sim-ipfe-b F E,κ (A , S ) proc Initialize(κ, ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V ← ∅ Return (pp, mpk) proc KeyDer(y) V ← V ∪ {y} sk y $ ← KeyDer(pp, msk, y) Return sk y proc Encrypt(x * ) ct * 0 $ ← Encrypt(mpk, x * ) ct * 1 $ ← S (mpk, { x * ,
IND-IPFE-CPA secure, then it is NA-SIM secure.
Proof. We prove this statement by exhibiting a simulator S and showing that if FE is IND-IPFE-CPA secure, then S satisfies the properties needed to prove NA-SIM security of FE. S is given as input mpk and the set of values { x, y , y} y∈V for some unknown x. It then finds a vector x such that x, y = x , y for all y ∈ V and encrypts it using mpk. S returns this new formed ciphertext. If an adversary A wins Game Exp na-sim-ipfe F E,κ (A , S ), it wins Game Exp ind-ipfe-cpa-b F E,κ (A , S ) with challenge messages x and x and without key queries after the challenge.

The next question is whether NA-SIM security implies IND-IPFE-CPA security or not. We answer this question in a non-black box manner: We require that the functional encryption scheme supports key delegation in order to prove equivalence of NA-SIM security and IND-IPFE-CPA security. Definition 3.2.8 (Key delegation). We say that an inner-product functional encryption scheme FE supports key delegation if sk y can be obtained from any set {sk z } z∈V where y ∈ Span(V ).

Note that with this definition, any functional encryption scheme for the inner-product functionality with a deterministic key derivation algorithm supports key delegation. Proof. If there weren't any secret key queries after the challenge ciphertext has been received, we could use the same argument as for proving that SIM security implies IND-IPFE-CPA security. This is a simple argument on games defining the security: the experiment

Exp ind-ipfe-cpa-0 F E,κ
(A ) with challenges x 0 and x 1 is the same experiment as Exp na-sim-ipfe-0

F E,κ (A , S )
with challenge x 0 , which is indistinguishable from the experiment Exp na-sim-ipfe-1

F E,κ
(A , S ) with challenge x 0 , which is exactly the same as Exp na-sim-ipfe-1

F E,κ (A , S ) with challenge x 1 , which is in turn indistinguishable from Exp na-sim-ipfe-0 F E,κ
(A , S ) with challenge x 1 , or equivalently

Exp ind-ipfe-cpa-1 F E,κ
(A ) with challenges x 0 and x 1 . From which IND-IPFE-CPA security follows. We now show that given x 0 and x 1 , one can compute a basis {z i } i∈[ ] of the orthogonal (x 1 -x 0 ) ⊥ . Given secret keys for this basis, key delegation allows to compute a secret key for any y such that x 0 , y = x 1 , y . This is easy for modular IPFE schemes where R = Z q because Z q is a field. For nonmodular IPFE schemes where R = Z, we want to find a basis {z i } i∈[ -1] of the lattice orthogonal to a given vector x. We construct one recursively: First, if the gcd of all coordinates of x is not 1, set x = 1 gcd(x i ) x.

• If = 2: z = (-x 2 , x 1 ) is a basis of (x 1 , x 2 ) ⊥ • If > 2: Let {z i } i∈[ -2] be a basis of (x 1 , • • • , x -1 ) ⊥ . We set z -1 = (-x × a 1 , -x × a 2 , . . . , -x × a -1 , gcd(x 1 , . . . , x -1 ))
where the a i 's come from Bezout's Identity.

This basis does not generate a sub-lattice of x ⊥ . Indeed, a vector y orthogonal to x has a last coordinate which is a multiple of gcd(x 1 , . . . , x -1 ), because

x y = -i∈[ -1] x i y i .
To conclude the proof, suppose there is an adversary A that breaks the IND-IPFE-CPA security. A simulator S can use this adversary to break the NA-SIM security: Upon reception of x 0 and x 1 , S queries secret keys for the z i before asking for a challenge ciphertext, thus avoiding the non-adaptive queries. S can still answer A 's adaptive queries using key delegation.

Indistinguishability under Chosen-Ciphertext Attack

Although IND-IPFE-CPA security is a very attractive notion, because it provides really strong security of the plaintext vectors, it only protects against passive attacks. In order to be secure against active adversaries, we need to consider a stronger notion of security: IND-IPFE-CCA security [BDPR98; Ble98](In this work, we only consider CCA2 security, not the weaker CCA1 security or security against lunchtime attacks). In this model, the adversary tries to attack a ciphertext while having access to a decryption oracle. IND-CCA security is nowadays the go-to security notion for public key encryption. It is thus very natural to extend it to functional encryption, as has been done in [START_REF] Nandi | Generic Conversions from CPA to CCA secure Functional Encryption[END_REF]. However, this result doesn't directly give any IPFE scheme secure against chosen-ciphertext attacks. As noted in [START_REF] Blömer | Subtleties in Security Definitions for Predicate Encryption with Public Index[END_REF], there are multiple possibilities to be considered for this decryption oracle for handling the private keys. However, since our schemes have deterministic key derivation,

Chapter 3 Inner-Product Functional Encryption Adversary Challenger (x * 0 ,x * 1 ) ct x * b KeyDer(msk, •) y sk y Decrypt(KeyDer(msk, •), •) (y,ct x )
x, y or ⊥

Adv ind-ipfe-cca F E,κ (A ) = 2 • Pr[Exp ind-ipfe-cca-b F E,κ (A ) = 1] -1 . Then we say that FE is secure against chosen-ciphertext attacks (IND-IPFE-CCA secure) if Adv ind-ipfe-cca F E,κ (A ) is negligible for all probabilistic polynomial time A .
As in the case of IND-IPFE-CPA security, we only consider the case of a single challenge vector pair (x * 0 , x * 1 ). This is without loss of generality, because the same hybrid argument proves security in the case of multiple challenge.

Remark 3.3.2. As in the case of public key encryption, if an inner-product functional encryption scheme is additively homomorphic as in Definition 3.2.3, it cannot be IND-IPFE-CCA

secure. This is because one can always add an encryption of 0 to change the ciphertext without changing the plaintext and submit this new ciphertext to the decryption oracle.

Tag-Based Inner-Product Functional Encryption

Tags are a really useful tool to construct schemes secure against active adversaries. The reason is that this tag can be anything from a hash value to verification keys for signature Chapter 3

3.3 Indistinguishability under Chosen-Ciphertext Attack 29 Game Exp ind-ipfe-cca-b F E,κ (A ) proc Initialize(κ, ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V y ← ∅ V ct ← ∅ Return (pp, mpk) proc Dec(ct, y) V ct ← V ct ∪ {ct} sk y $ ← KeyDer(pp, msk, y) m ← Decrypt(pp, sk y , ct) return m proc KeyDer(y) V y ← V y ∪ {y} sk y $ ← KeyDer(pp, msk, y) Return sk y proc Encrypt(x * 0 , x * 1 ) ct * $ ← Encrypt(pp, mpk, x b ) Return ct * proc Finalize(b') if bad then return false Return (b = b) Figure 3.7: Game Exp ind-ipfe-cca-b F E,κ (A ) defines IND-IPFE-CCA security of FE. The event bad corresponds to ∃y ∈ V y , x * 0 , y = x * 1 , y ∨ ct * ∈ V ct .
schemes. This allows the scheme to be protected against an adversary trying to tamper with the ciphertexts. The security in a tag-based scheme is only required as long as tags are differents. This allows for easier analysis and more elegant proofs. A very speaking example is the original IND-CCA secure scheme of Cramer and Shoup [START_REF] Cramer | A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack[END_REF], which use hashes of parts of the ciphertext as tags in order to ensure its authenticity. Our definition is an adaptation from the concept of tag-based encryption in [START_REF] Mackenzie | Alternatives to Nonmalleability: Definitions, Constructions, and Applications (Extended Abstract)[END_REF].

Basically, tags are bitstrings that we will denote τ and which will be added as inputs to

Encrypt and Decrypt. We denote the set of all possible tags T and assume that it is easy to sample one at random. In order to preserve correctness, the tag τ used to decrypt a ciphertext should match the one that has been used to encrypt it.

Definition 3.3.3 (Tag-Based Inner-Product Functional Encryption). Formally, a tag-based inner-product functional encryption (TBIPFE) scheme T BFE is defined with regard to a some ring R, and consists of 4 probabilistic polynomial time algorithms:

• Setup(1 κ , 1 ) → (pp, msk, mpk). On input security parameter κ and functionality parameter outputs public parameters pp, master secret key msk, and master public key mpk;

• KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ R , outputs user secret key sk y ;

• Encrypt(pp, τ, mpk, x) → ct x . On input public parameter pp, master public key mpk, and plaintext x ∈ R , outputs ciphertext ct x ;

• Decrypt(pp, τ, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs a message m ∈ R or an error symbol ⊥.

Chapter 3 We define our secret key inner-product functional encryption scheme FE as follows:

• Setup(1 κ , 1 ) → (pp, msk, mpk). On input security parameter κ and functionality parameter , samples (pp, msk, mpk)

$ ← T BF E.Setup(1 κ , 1 ), a key k $ ← K
, and outputs public parameters pp = (pp, k), master secret key msk, and master public key mpk;

• KeyDer(pp , msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ R , samples sk y $ ← T BF E.KeyDer(pp, msk, y) and outputs user secret key sk y ;

• Encrypt(pp , mpk, x) → ct x . On input public parameter pp, master public key mpk, and Correctness. The correctness of FE directly follows from the correctness of T BFE and the completeness of OT S.

plaintext x ∈ R , samples (sk, vk) $ ← OT S.Setup(1 κ ), τ ← H k (vk), ct x $ ← T BF E.Encrypt(pp, τ, mpk, x),
Security. We have the following security theorem.

Theorem 3.3.6. Let T BFE, OT S, (H k ) k∈K , and FE be defined as in Construction 3.3.5.

If T BFE is IND-TBIPFE-CCA secure, OT S is strongly unforgeable, and (H k ) k∈K is collision resistant, then FE is IND-IPFE-CCA secure.
Proof. If for any decryption query (y, (ct x , vk, σ)) made by the adversary A , H(vk) = H(vk * ) for the challenge vk * , and the check OT S.Verify(vk, ct x , σ) passes. Then either A found a collision of the hash function (if vk = vk * ), or it did a forgery σ for the message ct x . Otherwise, the security game of IND-TBIPFE-CCA security for T BFE ensures that the advantage of A is negligible.

Function Hiding

Although inner-product functional encryption provides the best possible security for the plaintext vector x, it doesn't protect the key vector y at all. This however might be desirable for many applications. For example, it prevents an adversary with many keys to learn the Chapter 3 Inner-Product Functional Encryption plaintext vector if it doesn't know the actual key vectors associated with its user secret keys. We call this property function hiding. In the following, we show that this property cannot be met in the public key setting, because the adversary can learn the key vectors by encrypting many different plaintexts and decrypting them with its keys. This is why many works have studied the function hiding property in the secret key setting. Function hiding has been previously studied in the case of functional encryption for larger class of functions [START_REF] Brakerski | Function-Private Functional Encryption in the Private-Key Setting[END_REF], where it is easy to use the functionality provided by the scheme in order to hide the computation allowed by the key. In the particular case of inner-product functional encryption, the first scheme was proposed by [START_REF] Bishop | Function-Hiding Inner Product Encryption[END_REF], but was only reaching a weak form of function hiding. This was later improved to reach the best possible security we can hope for [DDM16; TAO16; KLM+16; KKS17]. All these constructions use the same underlying ideas and require the use of pairings. In this work, we relax a bit the definition of function hiding property to show what we can achieve with modular IPFE schemes without additional assumptions, and show that it implies the standard function hiding security property if the adversary only has access to a bounded number of key queries.

Function Hiding in the Public Key Setting

In this section, we first define the function hiding property in the public key setting before showing its impossibility. The intuition behind the definition is that we adapt the IND-IPFE-CPA security experiment, but now the KeyDer procedure takes 2 inputs y 0 and y 1 , and it returns KeyDer(pp, msk, y b ). Notice that the hidden bit is shared with the Encrypt procedure.

Definition 3.4.1 (Function Hiding). For an inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define function hiding via the security game depicted on Figure 3.9: we define the advantage of an adversary A to be

Adv function-hiding-ipfe F E,κ (A ) = 2 • Pr[Exp function-hiding-ipfe-b F E,κ (A ) = 1] -1 .
Then we say that FE is function hiding if Adv function-hiding-ipfe

F E,κ (A ) is negligible for all proba- bilistic polynomial time A .
As usual, the event bad aims at removing queries that allows A to distinguish trivially between b = 0 and b = 1. However, in this case, it won't be enough, because the restriction is only on the inputs to Encrypt, and A can computes Encrypt directly using mpk.

Theorem 3.4.2. No public key inner-product functional encryption scheme is function hiding.

Proof. We exhibit an adversary A that guesses correctly b for any IPFE FE = (Setup, KeyDer, Encrypt, Decrypt):

• A calls Initialize (κ, 1) to receive pp and mpk.

• A calls KeyDer(0, 1) to receive sk.

• A computes ct $ ← Encrypt(pp, mpk, 1) and learns b = Decrypt(pp, ct, sk).

Notice that A didn't trigger bad because V x is empty. So A completely breaks the function hiding of FE.

Chapter 3

Function Hiding 33

Game Exp function-hiding-ipfe-b

F E,κ (A ) proc Initialize(κ, ) (pp, msk, mpk) $ ← Setup(1 κ , 1 ) V y ← ∅ V x ← ∅ Return (pp, mpk)
proc KeyDer(y 0 , y 1 )

V y ← V y ∪ {(y 0 , y 1 )} sk $ ← KeyDer(pp, msk, y b ) Return sk proc Encrypt(x 0 , x 1 ) V x ← V x ∪ {(x 0 , x 1 )} ct $ ← Encrypt(pp, mpk, x b ) Return ct proc Finalize(b') if bad then return false Return (b = b) Figure 3.9: Game Exp function-hiding-ipfe-b F E,κ (A ) defines function hiding of FE. The event bad corresponds to ∃(y 0 , y 1 ) ∈ V y , ∃(x 0 , x 1 ) ∈ V x , x 0 , y 0 = x 1 , y 1 .
Due to this impossibility result, in order to continue our discussion on function hiding, we are forced to switch to the context of secret key inner-product funtional encryption.

Secret Key Inner-Product Functional Encryption

This setting is almost the same as the standard IPFE setting we discussed previously, the only difference being that mpk doesn't exist anymore, and Encrypt takes as input msk instead. We start this section by the formal definition of secret key IPFE and the security model of function hiding, before comparing this new tool with standard modular IPFE. Definition 3.4.3 (Secret Key Inner-Product Functional Encryption). Formally, a secret key inner-product functional encryption (secret key IPFE) scheme FE is defined with regard to a some ring R, and consists of 4 probabilistic polynomial time algorithms:

• Setup(1 κ , 1 ) → (pp, msk). On input security parameter κ and functionality parameter outputs public parameters pp and master secret key msk;

• KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ R , outputs user secret key sk y ;

• Encrypt(pp, msk, x) → ct x . On input public parameter pp, master secret key msk, and plaintext x ∈ R , outputs ciphertext ct x ;

• Decrypt(pp, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs a message m ∈ R or an error symbol ⊥.

Correctness. As in the public key setting, we allow the Decrypt algorithm to output ⊥ if x, y is outside of a polynomial sized set P fixed at setup. We also denote the plaintext space M x and the key space M y , and they may be smaller than the full ring R. Hence the following correctness property:

An IPFE scheme is correct if for any x ∈ M x , y ∈ M y , (pp, msk) $ ← Setup(1 κ , 1 ), Chapter 3 Inner-Product Functional Encryption sk y $ ← KeyDer(pp, msk, y), ct x $ ← Encrypt(pp, msk, x).
Then if x, y ∈ P, it holds that Decrypt(pp, sk y , ct x ) = x, y .

Note that any IPFE scheme can be seen as a secret key IPFE scheme, by merging the master public key and the master secret key, but not the other way around. The security that we require for secret key IPFE is also stronger than what we ask in the public key setting. For example, we cannot just prove security for one challenge message because the hybrid argument presented in Section 3.1.2 doesn't hold anymore. Hence the following function hiding definition, which is similar to the one in the public key setting: Definition 3.4.4 (Function Hiding). For a secret key inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define function hiding via the security game depicted on Figure 3.10: we define the advantage of an adversary A to be

Adv function-hiding-ipfe F E,κ (A ) = 2 • Pr[Exp function-hiding-ipfe-b F E,κ (A ) = 1] -1 . Then we say that FE is function hiding if Adv function-hiding-ipfe F E,κ (A ) is negligible for all proba- bilistic polynomial time A . Game Exp function-hiding-ipfe-b F E,κ (A ) proc Initialize(κ, ) (pp, msk) $ ← Setup(1 κ , 1 ) V y ← ∅ V x ← ∅ Return pp proc KeyDer(y 0 , y 1 ) V y ← V y ∪ {(y 0 , y 1 )} sk $ ← KeyDer(pp, msk, y b ) Return sk proc Encrypt(x 0 , x 1 ) V x ← V x ∪ {(x 0 , x 1 )} ct $ ← Encrypt(pp, msk, x b ) Return ct proc Finalize(b') if bad then return false Return (b = b) Figure 3.10: Game Exp function-hiding-ipfe-b F E,κ (A ) defines function hiding of FE. The event bad corresponds to ∃(y 0 , y 1 ) ∈ V y , ∃(x 0 , x 1 ) ∈ V x , x 0 , y 0 = x 1 , y 1 .
Remark 3.4.5. If a secret key IPFE scheme FE = (Setup, KeyDer, Encrypt, Decrypt) is function hiding, then its dual FE = (Setup, Encrypt, KeyDer, Decrypt), obtained by switching plaintexts and keys is also function hiding, because of the symmetry in the definition. This implies that FE is IND-IPFE-CPA secure, which is a really strong property. In most applications, fewer user secret keys than ciphertexts are used, so the user secret keys shouldn't need the same security as the one provided to ciphertexts. It is with this idea in mind that we now define the partial function hiding property, which means that the leakage obtained when getting multiple user secret keys is equivalent to the linear relations between the keys.

Partial Function Hiding

For the remainder of this section, we will be focusing on secret key modular IPFE, that is the case where R = Z p for some prime number p. Note that all known constructions of Chapter 3

Function Hiding 35

function hiding IPFE are modular (for small message space). As explained previously, we feel that some applications don't need as strong a security for secret keys as the function hiding property. Notice that only learning the linear equations that the keys satisfy don't allow the adversary to learn the plaintext vector x of a ciphertext ct x even given user secret keys for independent unknown vectors (y i ) i∈[ ] . This is because in this scenario, the adversary only learns x up to a change of basis, even if he has multiple ciphertexts. Moreover, we observe that in some applications, no linearly dependent keys should be given, or the linear combinations don't really have a meaning. For example, if doing machine learning using support vector machine, the elements are embeded as vectors x, and to classify the elements, one simply separates them using another vector y: this separator defines two sets S + = {x : x, y ≥ 0} and S -= {x : x, y < 0}. In this case, adding two vectors y doesn't really have a meaning as a new separator. For example, if we have two separators that learned to distinguish men from women, and children from adults, adding them doesn't give a separator that distinguishes young boys from grown up women.

We first give the formal definition of this security property, then we show how to obtain such a security property from any public key modular IPFE, using an intermediate tool that we call vector one-time pad, then we will show that partial function hiding implies full function hiding against bounded collusions of adversaries. We now define our notion of partial function hiding. The only difference with function hiding resides in the definition of the event bad and thus, the set of queries the adversary is allowed in the security game. Definition 3.4.6 (Partial Function Hiding). For a secret key inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define partial function hiding via the security game depicted on Figure 3.11: we define the advantage of an adversary A to be

Adv pfh-ipfe F E,κ (A ) = 2 • Pr[Exp pfh-ipfe-b F E,κ (A ) = 1] -1 .
Then we say that FE is partially function hiding if Adv pfh-ipfe F E,κ (A ) is negligible for all probabilistic polynomial time A .

Notice that here we broke the symmetry between the secret keys and the ciphertexts. We also show an equivalent definition of bad (the first part stays the same):

∃λ 1 , . . . , λ j ∈ R, ∃(y 1 0 , y 1 1 ), . . . , (y j 0 , y j 1 ) ∈ V y , k∈[j] λ k y k 0 = 0 = k∈[j] λ k y k 1 ⇐⇒ M ∈ R × invertible s.t. ∀(y 0 , y 1 ) ∈ V y , y 0 = My 1 Remark 3.4.7.
We note that any adversary A that triggers the event bad in this experiment also triggers it in Exp function-hiding-ipfe-b F E,κ (A ). Thus, if a scheme is function hiding, then it is also partially function hiding.

Vector One-Time Pad.

We now present our tool that we call Vector One-Time Pad. It is a toy secret key innerproduct functional encryption scheme that is secure as long as it is used only for one key and one plaintext, like the well known one-time pad that is the way to information theoretically

Chapter 3 Inner-Product Functional Encryption Game Exp pfh-ipfe-b F E,κ (A ) proc Initialize(κ, ) (pp, msk) $ ← Setup(1 κ , 1 ) V y ← ∅ V x ← ∅ Return pp proc KeyDer(y 0 , y 1 ) V y ← V y ∪ {(y 0 , y 1 )} sk $ ← KeyDer(pp, msk, y b ) Return sk proc Encrypt(x 0 , x 1 ) V x ← V x ∪ {(x 0 , x 1 )} ct $ ← Encrypt(pp, msk, x b ) Return ct proc Finalize(b') if bad then return false Return (b = b) Figure 3.11: Game Exp pfh-ipfe-b F E,κ (A ) defines function hiding of FE. The event bad corre- sponds to ∃(y 0 , y 1 ) ∈ V y , ∃(x 0 , x 1 ) ∈ V x , x 0 , y 0 = x 1 , y 1 ∨ ∃λ 1 , . . . , λ j ∈ R, ∃(y 1 0 , y 1 1 ), . . . , (y j 0 , y j 1 ) ∈ V y , k∈[j] λ k y k 0 = 0 = k∈[j] λ k y k 1 .
hide a message with a key of same length. Here, the idea is to translate it to vectors by multiplying the plaintext vector by a random invertible matrix B. Then, the key will be multiplied by the transpose of the inverse B -t of B. Thus, these new vectors will totally hide the plaintext and the key, while their inner-product will keep the same value. Now, looking more closely at this scheme, the leakage coming from reusing the same matrix B for multiple plaintexts (x i ) will be exactly the linear relations between those vectors. And the same can be said about the key vectors. So the total leakage is the linear relations between plaintexts and keys, as well as the inner-product values between each pair of plaintext and key.

Construction 3.4.8 (Vector One-Time-Pad). We define our functional encryption scheme for the inner-product functionality VOT P = (Setup, KeyDer, Encrypt, Decrypt) as follows:

• Setup(1 κ , 1 ) → (pp, msk). On input security parameter κ and functionality parameter , samples a random invertible matrix B ∈ Z p outputs public parameters pp = (p, ) and master secret key msk = B;

• KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk = B, and key y ∈ Z p , outputs user secret key sk y = B -t y;

• Encrypt(pp, msk, x) → ct x . On input public parameter pp, master secret key msk = B, and plaintext x ∈ Z p , outputs ciphertext ct x = Bx;

• Decrypt(pp, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs ct x , sk y .

Correctness. For any

κ ∈ Z, ∈ Z, y ∈ Z p , x ∈ Z p , let (pp, msk) $ ← Setup(1 κ , 1
), sk y ← KeyDer(pp, msk, y), ct x ← Encrypt(pp, msk, x). We have:

ct x , sk y = ct x t sk y = x t B t B -t y = x, y .
Chapter 3

Function Hiding 37

Remark 3.4.9. All known function hiding IPFE use the same underlying idea of using a random invertible matrix to rerandomize plaintexts and keys. They do so by putting this new vector in the exponent in a group where the discrete logarithm is hard to compute, thus needing a pairing to compute the inner-product. This technique is also called dual pairing vector spaces [START_REF] Okamoto | Homomorphic Encryption and Signatures from Vector Decomposition[END_REF][START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF] This means that at the end of the decryption, a discrete logarithm has to be computed. The plaintext space and the key space should be restricted because of this, but it seems that this is inherent to all constructions based on the discrete logarithm problem.

Our way to proceed is to encrypt the resulting vectors with any modular IPFE, thus it could be used with IPFE schemes that supports bigger message spaces. For example the schemes in [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] based on the DCR and LWE assumptions with stateful key derivations algorithms. This is one of the reasons that makes this variant of function hiding appealing.

Generic Construction from Public Key Inner-Product Functional Encryption

We now present our generic construction from public key IPFE to partially function hiding secret key IPFE. The partial function hiding property of the resulting scheme will be inherited from the IND-IPFE-CPA security of the building block, and from the perfect security of the vector one-time pad.

Adv ind-ipfe-cpa F E,κ (B) = Adv pfh-ipfe F E ,κ (A )
Proof. Unless the event bad is triggered by A , there exists an invertible matrix M ∈ R × such that y 0 = My 1 for all key queries (y 0 , y 1 ). Because the distribution of B is uniform, we can multiply it by any invertible matrix without changing the view of the adversary. In particular, B can take A 's queries {(x 0 , x 1 )} and {(y 0 , y 1 )} and replace them by {Bx 0 , BM -t x 1 } and {B -t y 0 = B -t My 1 } and use those queries in Exp ind-ipfe-cpa-b B). The equality between their advantages follow.

F E,κ (

Function Hiding against Bounded Collusion.

In this section, we will compare our weakening on the function hiding with another intuitive weakening: function hiding against bounded collusions. We show that any partially function hiding IPFE scheme can be used to construct an IPFE scheme function hiding against bounded collusion for any bound q y on the user secret key queries made by the adversary. The idea is to concatenate a random vector at the end of each key vector before deriving the user secret key. We also append zeros to each plaintext vector so that the inner-product will cancel the uniform parts of the key. Those uniform vectors with correctly chosen length will be linearly independent with high probability, in which case the event bad won't be triggered, and we can use the advarsary breaking the function hiding against bounded collusions property in order to break the partial function hiding property. We let PH denote a partial function hiding IPFE. We also let q y be a parameter that will be used as a bound on the secret key queries. Construction 3.4.12 (Inner-Product Functional Encryption Function Hiding against Bounded Collusions). Let us assume the existence of a modular secret key IPFE scheme FE = (FE.Setup, FE.KeyDer, FE.Encrypt, FE.Decrypt). We define a new secret key IPFE scheme FE as follows:

• Setup(1 κ , 1 , 1 qy ) → (pp,
Adv pfh-ipfe F E,κ (B) = (1 - 1 p ) • Adv function-hiding-ipfe F E ,κ (A ).
We recall that p is the order of the message space.

Proof. Since the games are exactly the same, except the allowed queries, we only need to look at the probabilities of the two events bad in Exp pfh-ipfe-b

F E,κ (B) and Exp function-hiding-ipfe-b F E ,κ
(A ) that we will denote bad F E and bad F E It is easy to see that if A triggers bad, then B also does. That is, if a query is forbidden in the function hiding security game, then it is also forbidden in the partial function hiding security game. We now assume without loss of generality that A makes q y queries. Using an union bound, we can get the following bound on the probability P f ail = 1 -P ind that the vectors (r i ) i∈ [qy] are linearly dependent:

P f ail ≤ qy i=0 p i p qy+1 ≤ 1 p qy+1 • 1 -p qy 1 -p ≤ 1 p Thus, Pr[bad F E ] ≤ (1 - 1 p ) • Pr[bad F E ],
and the adversary B has advantage (1

-1 p ) • Adv function-hiding-ipfe F E ,κ
(A ) against the security of FE .

Remark 3.4.14. Even though we only look at bounded collusions, if an adversary makes more queries, the IND-IPFE-CPA security will still protect the plaintexts, and the scheme will still be partially function hiding. That is because we are using directly the previous scheme that has these security properties against unbounded collusions that we inherit.

Chapter 4

Chapter 4

Generic Construction from Public Key Encryption

The goal of this chapter is to generically build an inner-product functional encryption scheme FE from a basic public key encryption scheme E. It combines the generic construction we have done in [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF] and [START_REF] Abdalla | Better Security for Functional Encryption for Inner Product Evaluations[END_REF]. We start by explaining the ideas behind the construction, and the proof of security. Afterwards, we will define additional properties that the public key encryption scheme must have in order to continue with our construction: structural properties, but also homomorphic properties and security properties.

Then, we construct s-IND-IPFE-CPA secure inner-product functional encryption, and prove its correctness and security using the properties of E. Finally, we construct directly IND-IPFE-CPA secure schemes without requiring the generic techniques presented in Section 3.2.1, thus having a tighter reduction to the underlying assumption, and we explain the downside of this construction: it requires bigger parameters, which makes it slower, and sometimes rely on a stronger assumption, depending on the underlying scheme.

Contents

Overview

Before going into more details, we first give a high-level overview of the intuition behind the construction, and the ideas behind the proof of security for the simpler s-IND-IPFE-CPA security, as well as how to reach full IND-IPFE-CPA security.

Overview of the Construction. In order to build an inner-product functional encryption scheme, the first observation is the following: in order to compute an inner-product between two vectors x and y and knowing y, it is enough to do a weighted sum of the coordinates of x. So intuitively, if x is encrypted with a homomorphically additive scheme, we could derive an encryption of x, y using this property. However, this is not enough for our purpose, because we need to give a key that decrypts this new ciphertext. Moreover, we don't want this key to allow decryption of any other ciphertext. So, we need this additive homomorphism to change the secret key at the same time as the plaintext. Usually, when dealing with additively homomorphic public key encryption schemes, adding the ciphertexts usually adds up the plaintext as well as the randomness used for encryption, which is good because usually, we want the key to stay the same, and the randomness doesn't really matter. Here we are going to use a dual approach: we will see the randomness used to encrypt as a secret key, and the secret key as the encryption randomness. So in the end, we encrypt each coordinate of the vector x under the same randomness, and a different key. This will ensure that when adding the different parts of the ciphertext to compute x, y , the key will also be changed to sk, y .

Selective Security. The trick that makes this construction secure against collusion is that the leakage of information about the secret key is exactly the same as the leakage produced by the functionality, so combining user secret keys yields exactly the same result as combining results once decrypted. In fact, this means that our scheme supports key delegation as per Definition 3.2.8. The fact that our scheme allows to delegate user secret keys is very useful in order to prove its selective security. Once the challenge vectors x * 0 and x * 1 are set, the adversary is only allowed key queries y in the set (x * 1 -x * 0 ) ⊥ . This is crucial in the proof, because then all key queries can be simulated only knowing a basis of this set, which is either a vector space in the case of R = Z q , or a lattice in the case of R = Z. Then it is left to show that we can simulate all the adversary's view only using a challenge public key and ciphertext from the public key encryption, plus the user secret keys for (x * 1 -x * 0 ) ⊥ .

Adaptive Security. In order to reach full adaptive security for our schemes, we use the technique described in Section 3.2.1. However, this doesn't directly apply to non-modular IPFE schemes. In order to reach IND-IPFE-CPA security for all IPFE schemes, we use the same technique of sampling a random vector t to hide the message which will be stored in the master secret key. The downside is that we cannot use a uniform vector t in R to mask the plaintext x, so we have to sample t in a set superpolynomially bigger than M x in order to statistically hide x.

The underlying idea behind this transformation is to use a specific challenge message in the proof: (t, 0) against (0, 0). In order for the proof to follow, we just require x + t to hide x, Hence the choice of M t .

Chapter 4

Additional Properties of Public Key Encryption

Even if our generic constructions can be instantiated using many known public key encryption schemes, it doesn't work with all of them. We require a few additional properties, structural and homomorphic properties for the correctness of the inner-product functional encryption as well as security properties in order to protect the vector against collusions.

Structural Properties

We now define the structure that we need on E, its secret and public keys, its plaintexts and ciphertexts, and its Setup algorithm. These structural properties are mostly rewriting to explicit the randomness sampled by the algorithms in order to present the homomorphic properties we require more easily. The parameter τ that we introduce in the Setup algorithm is useful for schemes that allows multiple public keys to correspond to the same underlying secret key. For example, it will be useful for schemes based on the learning with error assumption that we will use in Chapter 8, where the public key is noisy: a small error is added to the correct computation to prevent adversaries to revert the secret key to public key computation. In this case, τ could be the parameters that sets this error distribution.

• The secret keys are elements of a group (G, +, 0 G ), for which we use an additive notation. We note that this group doesn't have to be public, as our proof only requires the operation + to be publicly available and efficiently computable.

• The public keys are elements of a group (H, •, 1 H ), for which we use a multiplicative notation.

• The message space is R or a subset of it. We require that the order of R is greater than x 1 -x 0 2 for all (x 0 , x 1 ) ∈ M 2 x .

• The ciphertexts can be splitted in two parts: 1. The first part ct 0 corresponds to some commitment C(r) of the randomness r used for the encryption.

2. The second part ct 1 is the encryption E(pk, x; r) of the message x under public key pk and randomness r. We require that this part is an element of a group (I, •, 1 I ) for which we use the multiplicative notation.

• The Setup can also be splitted in two parts: 1. SKGen(1 κ ) → sk. On input the security parameter κ samples and returns a secret key sk from the secret key space according to the same distribution induced by Setup. 2. PKGen(sk, τ ) → pk. On input a secret key sk and parameters τ , generates a public key pk corresponding to sk according to the distribution induced by τ . We will omit τ when it is clear from the context. Now that we defined the structure of E, we can define the homomorphic properties that we will use in order to prove the correctness of our inner-product functional encryption scheme.

Homomorphic Properties

In order for the decryption to be correct, we require two homomorphic properties. One on the public and secret keys of the scheme, as well as one on the second part of the ciphertexts E. The first one more or less states that PKGen is a group homomorphism from G to H. This would be exact if the parameter τ wasn't there. Instead, it states that a linear combination of secret keys is functional with regard to the same linear combination of corresponding public keys. Definition 4.2.1 (Linear Key Homomorphism.). We say that a PKE has linear key homomorphism (LKH, for short) if the following is true: for any two secret keys sk 1 , sk 2 ∈ G and any y 1 , y 2 ∈ Z, the component-wise G-linear combination formed by y 1 sk 1 + y 2 sk 2 can be computed efficiently only using public parameters, the secret keys sk 1 and sk 2 and the coefficients y 1 and y 2 . Moreover, this combination y 1 sk 1 + y 2 sk 2 also functions as a secret key for a public key that can be computed as pk

y 1 1 • pk y 2 2
, where pk 1 (resp. pk 2 ) is a public key corresponding to sk 1 (resp. sk 2 ): ∀x ∈ M x , (sk 1 , pk 1 ), (sk 2 , pk 2 )

$ ← Setup(1 ), y 1 , y 2 ∈ Z, Decrypt(y 1 sk 1 + y 2 sk 2 , Encrypt(pk y 1 1 • pk y 2 2 , x)) = x.
The second homomorphic property that we need for the correctness of our construction states that the second part E of the Encrypt algorithm is a group homomorphism from G × R to I for a fixed randomness r. That is, when multiplying two encryptions with same randomness, both the plaintexts and the public key undergo the same linear combination. Definition 4.2.2 (Linear Ciphertext Homomorphism under Shared Randomness.). We say that a PKE has linear ciphertext homomorphism under shared randomness (LCH, for short) if for any plaintexts x 1 , x 2 ∈ M x , any public keys pk 1 , pk 2 ∈ H, and any randomness r, it holds that E(pk 1 , x 1 ; r) • E(pk 2 , x 2 ; r) = E(pk 1 • pk 2 , x 1 + x 2 ; r).

Note the contrast with Definition 3.2.3: Here we fix the randomness, and both the public key and message change: the public keys get multiplied whereas the messages get added. In the previous case, the public key was fixed, while the messages were added. This is crucial for the security of our scheme, because if we were not changing the public key, a secret key allowing decryption would leak too much information about the plaintext. Our setting is close to the one of multi-key fully homomorphic encryption [CM15; MW16; BP16; CO17], which supports any computation on the ciphertexts, while the secret key used for decryption changes during computation, or to the one of fully key-homomorphic ABE [START_REF] Boneh | Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits[END_REF].

Remark 4.2.3. Combining both definitions, if a public key encryption scheme has both

linear key homomorphism and linear ciphertext homomorphism under shared randomness, it is possible to encrypt two messages x 1 and x 2 using the same randomness and different public keys pk 1 and pk 2 corresponding to sk 1 and sk 2 , multiply the encryptions E(pk 1 , x 1 ; r) and E(pk 2 , x 2 ; r) and decrypt it using sk 1 + sk 2 to recover x 1 + x 2 . We note that the plaintexts and the secret keys follow exactly the same computation.

We now move on to the definitions of the security properties we need beside s-IND-CPA security for E. They closely follow the homomorphic properties defined previously, but are not directly implied in the general case.

Chapter 4

ct y i i )).
The correctness of our scheme directly follows from the homomorphic properties defined in Section 4.2.2 and the correctness of the public key encryption scheme E.

ct y i i )) = E.Decrypt(sk y , (ct 0 , i∈[ ] E.E(pk i , x i ; r) y i )) = E.Decrypt(sk y , (ct 0 , E.Encrypt( i∈[ ] pk y i i , i∈[ ] y i x i ; r))) = i∈[ ] y i x i .
by the LCH property. Finally, note that the decryption is allowed because (sk y , i∈[ ] pk y i i ) is a valid key pair, due to the LKH property.

A Simpler Case: Randomness Reuse

As we want our constrution to be generic enough to encompass some lattice-based public key encryption schemes as building block, the proof might seem a bit complicated because we have to deal with a lot of approximate properties. However, in the special case where we have randomness reuse, which is basically the perfect version of ciphertext reproducibility, there is a very simple and elegant proof. Randomness reuse is also called reproducibility in [START_REF] Bellare | Randomness Re-use in Multi-recipient Encryption Schemeas[END_REF] and guarantees that it is secure to reuse randomness when encrypting under several independent public keys. The idea was first considered by [START_REF] Kurosawa | Multi-recipient Public-Key Encryption with Shortened Ciphertext[END_REF]. It is illustrated on This property is enough to replace both security properties defined in Section 4.2.3, hence the following theorem. Remark 4.3.4. For our security proof to work, it must hold that x 1 -x 0 2 = 0, where x 0 , x 1 are the challenge messages. The lower bound on the order of the message space ensures exactly this. We note that in some cases, like the instantiation based on DDH, a direct proof would avoid this issue. Proof. To prove the security of our scheme we will show that the s-IND-IPFE-CPA game is indistinguishable from a game where the challenge ciphertext encrypts a uniformly random linear combination of the challenge messages whose coefficients sum up to one. Thus, the challenge ciphertext decrypts to the expected values and information theoretically hides the challenge bit.

Given an adversary A that breaks the s-IND-IPFE-CPA security of our FE scheme with non-negligible probability ε, we construct an adversary B that breaks the s-IND-CPA security of the underlying PKE scheme E with comparable probability.

B starts by picking a random element a in the full message space of the underlying PKE E, and sends challenge messages 0 and a to the challenger C of PKE security game. C answers by sending an encryption ct = (ct 0 , ct 1 ) of either 0 or a and public key pk.

B then invokes A on input the security parameter and gets two different challenge messages in output, namely (x i = (x i,1 , . . . , x i, )) i∈{0,1} both in M .

Recall that, by the constraints of security game, the adversary can only issue secret key queries for vectors y such that x 0 , y = x 1 , y . Thus, we have that y, x 1 -x 0 = 0 meaning that y is in the vector space defined by (x 1 -x 0 ) ⊥ .

Then, B generates the view for A in the following way:

Public Key. To generate master public key mpk, B does the following. First, B finds a basis (z 1 , z 2 , . . . , z -1 ) of (x 1 -x 0 ) ⊥ . Then we can write the canonical vectors in the basis ((

x 1 -x 0 ), z 1 , z 2 , . . . , z -1 ): for i ∈ [ ], j ∈ [ -1],
there exist λ i,j ∈ R and α i ∈ R such that:

e i = α i (x 1 -x 0 ) + j∈[ -1] λ i,j z j . (4.1)
Then, for j ∈ [ -1], B sets (pk z j , sk z j ) = E.Setup(1 κ ), and for i ∈ [ ],

γ i = j∈[ -1] pk λ i,j z j and pk i = pk α i γ i . Eventually, B invokes A on input mpk = (pk i ) i∈[ ] .
Notice that, B is implicitly setting sk i = α i sk + j∈[ -1] λ i,j sk z j because of the LKH property, where sk is the secret key corresponding to pk, which is unknown to B.

Challenge Ciphertext. B computes the challenge ciphertext ct * as follows. B randomly picks b $ ← {0, 1}, computes E.E(γ i , 0; r) from ct 0 and j∈[ -1] λ i,j sk z j and E.E(1 H , x b,i ; r) from secret key 0 G and ct 0 , by randomness reuse. B then sets

ct * 0 = ct 0 and (ct * i = ct α i 1 • E.E(γ i , 0; r) • E.E(1 H , x b,i ; r)) i∈[ ] ,
Then the algorithm returns the challenge ciphertext ct * = (ct * 0 , (ct

* i ) i∈[ ] ).
Secret Keys. To generate a secret key for vector y, B computes sk y as

sk y = j∈[ -1]   i∈[ ] y i λ i,j   sk z j
At the end of the simulation, if A correctly guesses b, then B returns 0 (B guesses that C encrypted 0), else B returns 1 (B guesses that C encrypted a). This concludes the description of adversary B.

It remains to verify that B correctly simulates A 's environment.

First see that the master public key is well distributed, because we are just applying a change of basis to a well distributed master public key. Now it holds that

α i = x 1,i -x 0,i x 1 -x 0 2 because x 1,i -x 0,i = x 1 -x 0 , e i = α i x 1 -x 0 2 + j∈[ -1] λ i,j x 1 -x 0 , z j = α i x 1 -x 0 2 ,
where the e i are the vectors of the canonical basis.

To ensure that x 1 -x 0 2 is different from 0 modulo q, fixed the message space M = {0, . . . , B -1} ⊆ R, q needs to be set to be a prime larger then • B 2 . Now recall that a vector y satisfying the security game constraints is such that y, x 0 = y, x 1 , so

i∈[ ] y i α i = i∈[ ] y i x 1,i -x 0,i x 1 -x 0 2 = 0
which in turn implies that a secret key sk y for the vector y is distributed as

sk y = i∈[ ] y i sk i = i∈[ ] y i α i sk + i∈[ ] j∈[ -1] y i λ i,j sk z j = j∈[ -1]   i∈[ ] y i λ i,j   sk z j
On the other hand, if A asks for a secret key for some vector y / ∈ (x 1 -x 0 ) ⊥ , B would need to know sk in order to generate a correct secret key for y.

Now, we have to analyze the following two cases, depending on which message was encrypted by C in the challenge ciphertext:

1. C encrypted 0. Then, the challenge ciphertext ct * for message x b is distributed as

ct * 0 = ct 0 and ct * i = E.E(pk, 0; r) α i • E.E(γ i , x b,i ; r) = E.E(pk i , x b,i ; r) ,
thanks to the LCH property, and then as in the real game.

Thus, in this case, B generates a view identical to that A would see in the real game. Hence, the advantage of B in this game is ε, the same advantage as A against s-IND-IPFE-CPA of FE when 0 has been encrypted.

2. C encrypted a. First, in Equation 4.1, we have

α i = (x 1,i -x 0,i )/ x 1 -x 0 2 .
Let us analyze the distribution of the challenge ciphertext in this case. We have ct * 0 = ct 0 and

ct * i = E.E(pk, a; r) α i • E.E(γ i , x b,i ; r) = E.E(pk i , x b,i + α i a; r) = E.E(pk i , xi ; r), Chapter 4
4.3 Generic Selectively Secure Inner-Product Functional Encryption 51 thanks to the LCH property, where xi is defined as follows:

xi = x b,i + α i a = a x 1 -x 0 2 (x 1,i -x 0,i ) + x b,i = a x 1 -x 0 2 (x 1,i -x 0,i ) + x 0,i + b(x 1,i -x 0,i ).
Let us set u = a/ x 1 -x 0 2 + b, which is a random value in the full message space of E, given that a is random in the same space, then xi = ux 1,i + (1u)x 0,i . Then, the challenge ciphertext is a valid ciphertext for the message x = ux 1 + (1u)x 0 , which is a random linear combination of the vectors x 0 and x 1 whose coefficients sum up to one, as expected. Notice that b is information theoretically hidden because the distribution of u is independent from b. Hence, the advantage of B in this game is 0, when a random non-zero a has been encrypted.

Security in the General Case

If the underlying PKE scheme does not support randomness-reuse defined in the previous section then it is still possible to prove the security of Construction 4.3.1 using the security properties defined in Section 4.2.3. We have the following security theorem, similar to Theorem 4.3.3. Proof. The proof strategy is essentially the same as that of Theorem 4.3.3. For increased clarity and readability, we prove security via a sequence of hybrid experiments. We first describe a sequence of hybrid games and then show indistinguishability between adjacent hybrids, thus proving s-IND-IPFE-CPA security.

Hybrid H 1 : This is the s-IND-IPFE-CPA game. proc Initialize(κ, x 0 , x 1 ) (msk, mpk) $ ← Setup(1 κ ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} 1sk y $ ← KeyDer(msk, y) Return sk y proc Encrypt() ct * $ ← Encrypt(mpk, x b ) Return ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
Hybrid H 2 : This is like H 1 except that the master public key is generated by invoking the algorithm H 2 .Setup defined as follows:

H 2 .
Setup(1 κ , x 0 , x 1 ): The algorithm finds a basis (z 1 , z 2 , . . . , z -1 ) of (x 1 -x 0 ) ⊥ . Then, the canonical vectors can be rewritten in this basis as follows: for i ∈ [ ], j ∈ [ -1], there exist λ i,j ∈ R and α i ∈ R such that:

e i = α i (x 1 -x 0 ) ||x 1 -x 0 || 2 + j∈[ -1] λ i,j z j .
Then, the algorithms samples sk ← E.SKGen(1 κ ) and, for j ∈ [ ], PKE secret key sk z j ← E.SKGen(1 κ ). Finally, the algorithm sets:

sk i = α i • sk + λ i,j sk z j , pk i = E.PKGen(sk i , τ ) ,
where τ is the same used in the Setup algorithm. The algorithm returns msk = (sk i ) and mpk

= (pk i ) i∈[ ] .
proc Initialize(κ, x 0 , x 1 )

(msk, mpk) $ ← H 2 .Setup(1 κ , x 0 , x 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← KeyDer(msk, y) Return sk y proc Encrypt() Ct * $ ← Encrypt(mpk, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
Hybrid H 3 : This is like H 2 except that the master public key is generated by invoking the algorithm H 3 .Setup and the secret keys are generated by invoking the algorithm H 3 .KeyDer which are defined as follows.

Chapter 4

4.3 Generic Selectively Secure Inner-Product Functional Encryption 53

H 3 .Setup(1 κ , x 0 , x 1 ):
The algorithm finds a basis (z 1 , z 2 , . . . , z -1 ) of (x 1 -x 0 ) ⊥ . Then, the canonical vectors can be rewritten in this basis as follows: for i ∈ [ ], j ∈ [ -1], there exist λ i,j ∈ R and α i ∈ R such that:

e i = α i (x 1 -x 0 ) ||x 1 -x 0 || 2 + j∈[ -1] λ i,j z j .
Then, the algorithms first samples sk $ ← E.SKGen(1 κ ) and pk $ ← E.PKGen(sk, τ ). Then, for j ∈ [ -1], a PKE secret keys sk z j ← E.SKGen(1 κ ), sets t i = λ i,j sk z j , pk t i ← E.PKGen(t i , τ i ) and computes

pk i = pk α i • pk t i .
The algorithm returns mpk = (pk i ) i∈[ ] and msk = (pk, sk z j ).

H 3 .KeyDer(msk , y): The algorithm computes secret key for vector y in the following way:

sk y = i∈[ ] y i • t i . proc Initialize(κ, x 0 , x 1 ) (mpk, msk ) $ ← H 3 .Setup(1 κ , x 0 , x 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← H 3 .KeyDer(msk , k) Return sk y proc Encrypt() Ct * $ ← Encrypt(mpk, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
Hybrid H 4 : This is like H 3 except that the challenge ciphertext is generated by invoking the algorithm H 4 .Encrypt defined as follows: H 4 .Encrypt(msk , x): The algorithm computes the ciphertext for x in the following way:

ct 0 = E.C(r) and ct i = E.E(pk, 0; r) α i • E.E(pk t i , x i ; r) i∈[ ] ,
where r is some randomness in the random space of E.

proc Initialize(κ, x 0 , x 1 )

(mpk, msk ) $ ← H 3 .Setup(1 κ , x 0 , x 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← H 3 .KeyDer(msk , k) Return sk y proc Encrypt() Ct * $ ← H 4 .Encrypt(msk , x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
Hybrid H 5 : This is like H 4 except that the challenge ciphertext is generated by invoking the algorithm H 5 .Encrypt defined as follows: H 5 .Encrypt(msk , ct, x): Let ct = (ct 0 , ct 1 ), then, the algorithm computes the ciphertext for x in the following way:

ct 0 = ct 0 and ct i = ct α i 1 • E.E (t i , x i , ct 0 ; r) i∈[ ] ,
where r is some randomness shared among all the invocation of E.E.

proc Initialize(κ, x 0 , x 1 )

(mpk, msk ) $ ← H 3 .Setup(1 κ , x 0 , x 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← H 3 .KeyDer(msk , k) Return sk y proc Encrypt() ct = E.Encrypt(pk, 0) Ct * $ ← H 5 .Encrypt(msk , ct, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b) Hybrid H 6 : This is like H 5 except that ct encrypts a random value a ∈ Z p . proc Initialize(κ, x 0 , x 1 ) (mpk, msk ) $ ← H 3 .Setup(1 κ , x 0 , x 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← H 3 .KeyDer(msk , k) Return sk y proc Encrypt() ct = E.Encrypt(pk, a), a ← Z p Ct * $ ← H 5 .Encrypt(msk , ct, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
We now show that the relevant distinguishing probabilities between adjacent hybrids are negli-gible, which completes the proof.

Indistinguishability of H 1 and H 2 :

The distribution of the master public key in both the games is identically. This is because in H 2 a simple change of basis is applied to a well distributed master secret key and this change of basis can be computed due to the linear key-homomorphism of E, that tells us that the sk i 's as computed in H 2 are valid secret keys of E.

Chapter 4

4.3 Generic Selectively Secure Inner-Product Functional Encryption 55

Moreover, notice that, by our change of basis it holds that α i = x 1,ix 0,i because

x 1,i -x 0,i = x 1 -x 0 , e i = α i + j∈[ -1] λ i,j x 1 -x 0 , z j = α i .
Then, the change of basis implies that for all the vectors y = (y 1 , . . . , y ) satisfying the security game constraints, meaning that y ∈ (x 1 -x 0 ) ⊥ , it holds that i∈[ ] y i • α i = 0. Thus, to generate a well-distributed secret key for a y satisfying the security game constraints, sk is not required.

Indistinguishability of H 2 and H 3 : This holds under the -public-key-reproducibility of E for the distribution M induced by the challenge messages, defined as follows:

M x 0 ,x 1 (1 κ ): M finds a basis (z 1 , z 2 , . . . , z -1 ) of (x 1 -x 0 ) ⊥ .
Then, the canonical vectors can be rewritten in this basis as follows: for i ∈ [ ], j ∈ [ -1], there exist λ i,j ∈ R and

α i ∈ R such that: e i = α i (x 1 -x 0 ) ||x 1 -x 0 || 2 + j∈[ -1] λ i,j z j .
Then, M first samples sk

$ ← E.SKGen(1 κ ), then, for j ∈ [ -1], samples sk z j ← E.SKGen(1 κ ), sets t i = λ i,j sk z j and gives in output (sk, (α i , t i ) i∈[ ] ).
For the sake of completeness, suppose that there exists and adversary A that distinguishes with non-negligible advantage H 2 from H 3 . Then, we can construct an adversary B that uses A as a subroutine and breaks the -public-key-reproducibility of E.

B does the following. B invokes A to gets the challenge messages x 0 , x 1 . Then, B receives from the challenger of the -public-key-reproducibility experiment values (pk i , t i ) i∈[ ] on input the security parameter and distribution M x 0 ,x 1 . B sets master public key as mpk = (pk i ) i∈[ ] and gives it to A . Then B answers secret key queries by using the t i 's which are enough to generate secret keys for vectors satisfying the security game constraints.

B generates the challenge ciphertext by using mpk and uses A 's guess as its guess for the -public-key-reproducibility game.

Finally, notice that if B plays Exp -pk-rep-0

E,κ (B) (resp. Exp -pk-rep-1 E,κ (B)), then B perfectly simulates H 2 (resp. H 3 ).

Indistinguishability of H 3 and H

4 : By linear ciphertext-homomorphism of E, H 3 = H 4 .
In fact, notice that in both the games pk i = pk α • pk t i , then it holds that

E.E(pk α i • pk t i , x i ; r) = E.E(pk, 0; r) α i • E.E(pk t i , x i ; r) .
Indistinguishability of H 4 and H 5 : This holds under the -ciphertext-reproducibility of E for the distribution M, induced by the challenge messages, defined as follows: M x 0 ,x 1 (1 κ ): M finds a basis (z 1 , z 2 , . . . , z -1 ) of (x 1 -x 0 ) ⊥ . Then, the canonical vectors can be rewritten in this basis as follows: for i ∈ [ ], j ∈ [ -1], there exist λ i,j ∈ R and

α i ∈ R such that: e i = α i (x 1 -x 0 ) ||x 1 -x 0 || 2 + j∈[ -1] λ i,j z j .
56

Chapter 4 Generic Construction from Public Key Encryption Then, M samples, for j ∈ [ -1], secret keys sk z j ← E.SKGen(1 κ ).

Finally, M, for i ∈ [ ], sets t i = λ i,j sk z j and returns (0, (α i , x β,i , sk t i ) i∈[ ] ), where β is random bit.

For the sake of completeness, suppose that there exists and adversary A that distinguishes with non-negligible advantage H 4 from H 5 . Then, we can construct an adversary B that uses A as a subroutine and breaks the -ciphertext-reproducibility of E.

B does the following. B invokes A to gets the challenge messages x 0 , x 1 . Then, B receives from the challenger of the -ciphertext-reproducibility values (pk, (α i , pk t i , t i ) i∈[ ] , ct 0 , (ct i ) i∈[ ] ) on input the security parameter and distribution M x 0 ,x 1 . B sets master public key as mpk = (pk i = pk α i • pk t i ) i∈[ ] and gives it to A . Then B answers secret key queries by using the t i 's which are enough to generate secret keys for vectors satisfying the security game constraints. B uses as challenge ciphertext (ct 0 , (ct i ) i∈[ ] ) and uses A 's guess as its guess for the -ciphertext-reproducibility game.

Finally, notice that if B plays Exp -ct-rep-0

E,κ (B) (resp. Exp -ct-rep-1 E,κ (
B)), then B perfectly simulates H 4 (resp. H 5 ).

Indistinguishability of H 5 and H 6 :

The only difference between H 5 and H 6 is in the message that ct encrypts. In H 5 , ct is an encryption of 0 and H 5 , it is an encryption of a for a random a ∈ R. Moreover, notice that sk is never used. Therefore under the the IND-CPA security of E, H 5 is computational indistinguishable from H 6 .

Advantage of any adversary in H 6 . In this game, the challenge ciphertext is for message x = (x 1 , . . . , x ) defined as follows:

xi = x b,i + α i a = a(x 1,i -x 0,i ) + x b,i = a(x 1,i -x 0,i ) + x 0,i + b(x 1,i -x 0,i ).
Let us set u = a + b, which is a random value in Z p , then xi = ux 1,i + (1u)x 0,i . Then, the challenge ciphertext is a valid ciphertext for the message x = ux 1 + (1u)x 0 , which is a random linear combination of the vectors x 0 and x 1 whose coefficients sum up to one. Notice that b is information theoretically hidden because the distribution of u is independent from b. Hence, the advantage of any adversary in this game is 0.

Generic Adaptively Secure Inner-Product Functional Encryption

Now that we constructed a selectively secure inner-product functional encryption scheme, we want to improve it to reach full adaptive security against chosen-plaintext attacks. In the case of modular IPFE schemes, one can use the generic Construction 3.2.4. However, we want to stay as generic as possible and include the non-modular IPFE schemes to our framework.

Construction and Correctness

Our IND-IPFE-CPA secure scheme is very closely related to the two schemes of Construction 4.3.1 and Construction 3.2.4. It is essentially the latter construction applied to the former, but instead of sampling uniform vectors t to mask the vector in the proof, we sample it in some set T ⊂ Z. So the construction boils down to encrypting (x, 0) and decrypting with key (y, -t, y ) with the selectively secure scheme.

Chapter 4

ct y i 2,i • ct -sk y,1 1
)).

Correctness. Once again, the correctness follows from the homomorphic properties of the scheme E as well as its correctness. It is directly implied by the correctness of Construction 4.3.1 and Construction 3.2.4. It is easy to see that the plaintext computed by the homomorphic properties is the value of the inner product x, y , while the key required for decryption is

i∈[ ] y i (s i + t i sk) -i∈[ ] t i sk = sk y .
The main downside of this construction, is that T can be huge. This is a very slight problem for efficiency, but it can become a problem in security too, because it impacts the parameters we have to handle reproducibility for, and leads stronger assumption in the case of lattice-based schemes for example.

Adaptive Security

The security of Construction 4.4.1 is the same as the security of Construction 4.3.1, except that here we know exactly in advance the challenge vector to protect: 0 against (t, 1), as shown in the proof of Theorem 3.2.5, and at the end, our choice of T ensures that x is statistically hidden from the adversary. Hybrid H 2 : This is like H 1 except that the master public key is generated by invoking the algorithm H 2 .Setup defined as follows:

H 2 .Setup(1 κ , 1 ): The algorithm samples sk ← E.SKGen(1 κ ), for i ∈ [ ],
PKE secret key s i ← E.SKGen(1 κ ) and uniformly random scalar t i $ ← T . Finally, the algorithm sets:

pk = E.PKGen(sk, τ ) sk i = s i + t i • sk pk s i = E.PKGen(s i , τ i ) pk i = pk t i •
ct 0 = E.C(r) ct 1 = E.E(pk, 0; r) ct 2,i = ct t i 1 • E.E(pk s i , x i ; r)
where r is some randomness in the random space of E. proc Initialize(κ)

(mpk, msk) $ ← H 2 .Setup(1 κ , 1 ) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← KeyDer(msk, y) Return sk y proc Encrypt(x 0 , x 1 ) Ct * $ ← H 3 .Encrypt(msk, pk, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b) By linear ciphertext-homomorphism of E, H 2 = H 3 .
Hybrid H 4 : This is like H 3 except that the challenge ciphertext is generated by invoking the algorithm H 4 .Encrypt defined as follows: H 4 .Encrypt(msk, Ct, x): Let Ct = (ct 0 , ct 1 ). Then, the algorithm computes the ciphertext for x in the following way:

ct 0 = ct 0 ct 1 = ct 1 ct 2,i = ct t i 1 • E.E (s i , x i , ct 0 ; r)
where E.E is the alternative encryption algorithm defined in theciphertext-reproducibility game, r is some randomness shared among all the invocation of E.E .

Advantage of any Adversary in H

9 .
To analyze the advantage of an adversary in H 9 , let us define Hybrids H 9,0 and H 9,2 be the games corresponding to H 9 when b is fixed to 0 and 1 respectively. Then we construct H 9,1 from H 9,0 by replacing t by t and s by s defined as follows:

t = t + z, s i = s i -z i sk
The statistical distance between H 9,1 and H 9,0 is upper bounded by the probability Pr[t / ∈ T ∨ s / ∈ S]. If the secret key sk is chosen uniformly in a group, taking T /(2 M 2 x ) superpolynomial in κ is sufficient for the security to hold. If instead the secret key sk is chosen uniformly in an interval of N, say [S], we need to sample the s i from [S ] instead, where S /(2 M x S) is superpolynomial in κ. We now conclude by noticing that H 9,2 and H 9,1 are perfectly indistinguishable: if there is no abort and for any vector y satisfying the security game constraints, i.e. y, x 0 = y, x 1 , it holds that, since x 0 + t = x 1 + t ,

y i t i = i∈[ ] y i t i and i∈[ ] y i s i = i∈[ ] y i s i .
We note that we had to guess the value of the challenge ciphertext, because otherwise, the values of t and s wouldn't be defined at the beginning of the experiment. This guess only hinders the security in the last hybrid, on a statistical argument, so it doesn't make the underlying assumption weaker.

Remark 4.4.3.

The only constraint we have on T is that it must be that for any two vectors x 0 , x 1 in M x , for any vector t in T , with overwhelming probability, t + x 1 -x 0 or tx 1 + x 0 is in T . We conjecture that for M x = {0, . . . , M x } there exist a finite, non-empty set T for which this probability is 1; meaning that for any two vectors x 0 , x 1 in M x , for any vector t in T , either t + x 1 -x 0 is in T , or tx 1 + x 0 is in T . This set would be a discretized hypersphere (integral points inside an hypersphere) in dimension whose radius would only depend on M x . If this conjecture turned out to be true, our scheme wouldn't require T to be superpolynomial in the security parameter, resulting in a better assumption for the schemes presented in Chapter 8.

Chapter 5

Chapter 5

Generic Construction from Projective Hash Functions

In this chapter, we present the construction of IND-IPFE-CCA secure IPFE schemes from projective hash functions in our work [START_REF] Benhamouda | CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions[END_REF]. As a brief introduction, we first give an overview of the construction and explain the ideas behind the proofs. Then we will present our construction in two steps: first we construct an IND-IPFE-CPA secure scheme, and then we upgrade it to an IND-IPFE-CCA secure scheme. For each step we will present the properties that we require on the PHFs, before going on to the construction and finally the proof of security.

Overview

In order to reach security against chosen-ciphertext attacks, we give up a bit on the generality of the framework and instead of using a public key encryption scheme as our building block, we are going to use the stronger projective hash functions. Before presenting our construction, we give a quick informal introduction to projective hash functions and illustrate how to use them with a simple example. Then we will present the ideas behind the construction of a IND-IPFE-CPA secure inner-product functional encryption scheme, and how to improve it to reach IND-IPFE-CCA security.

Projective Hash Functions. Projective hash functions were defined by [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] in order to construct public key encryption schemes secure against chosen-plaintext attacks and even against chosen-ciphertext attacks. This concept has since found many other applications. Notably in password authenticated key exchange as in [GL03; CHK+05; KV09; KM14], but not only: [Kal05; ACP09; Wee12; BPV12; Wee16].

One of the most basic example use of projective hash functions is a zero knowledge proof of knowledge of a witness of a word in some NP language. In this example, Bob wants to prove to Alice that he knows a witness w that some word b is in a language. However, he does not want to reveal his witness to Alice. Here is how to solve this problem using projective hash functions as illustrated on Figure 5.1:

1. Alice calls the algorithm HashKg to create a hashing key hk.

2. Alice derives a projection key hp from her hashing key hk using ProjKg and sends it to Bob.

3. Bob computes a hash h of the word b using the algorithm ProjHash with inputs the witness w and the projection key hp. Then, Bob sends h to Alice 4. Alice computes the hash h' of the word b using the algorithm Hash with inputs the word b and the hashing key hk. She checks that h = h and is convinced that b is indeed in the language.

Why is Alice convinced? This is illustrated on Figure 5.2: if b is not in the language, Bob cannot know a witness w, and hence it is nearly impossible for him to guess correctly the value of the hash h. So alice knows that if Bob gives her the correct hash, he must know a witness, and thus b is in the language. Why is this proof zero knowledge? Well, Bob only gave Alice a value she already knew, which is computable with the knowledge of hk and b, so she doesn't gain any additional knowledge from this proof.

Overview of the Constructions. We note that the PHF could be used to construct a public key encryption that could be generically transformed into an IPFE scheme using the results from Chapter 4, but presenting the first construction helps giving intuition about how we are using PHF to build IPFE schemes, and it also avoid more cumbersome notations.

The Figures 3.1 and 5.1 illustrate very well the parallel between inner-product functional encryption and projective hash function. From these, it is easy to see the strategy to construct the former using the latter as a building block, by mapping each node of the diagram to a node on the other diagram. The secret key will be hashing keys, while the public key will be projection keys. To encrypt, we will sample a word b together with a witness w, and use the In red is Alice's view, and in blue is Bob's view. Here Bob cannot guess the value of h.

witness and the projection keys to derives hashes that will be used as a mask in order to hide the plaintext. Then to decrypt, we remove the mask using the hashing keys to hash the word b. As in Chapter 4, we will rely on additive homomorphism in order to ensure correctness, as well as security against collusions of our scheme. This technique gives an IND-IPFE-CPA secure IPFE scheme. This construction is simpler than the one from public key encryption. However, it cannot be applied to lattice-based schemes, for which we only know of approximate PHFs. We could maybe adapt the IND-IPFE-CPA secure scheme to include these schemes, but this would make the notation cumbersome and the PHFs wouldn't meet the requirements to build IND-IPFE-CCA secure schemes.

In order to reach IND-IPFE-CCA security, we need to ensure that the adversary cannot learn any information he shouldn't using the decryption oracle. To prevent leakage of information, our strategy is to ensure that ill-formed ciphertexts can be detected at decryption time. To do this, we use a second PHF with more statistical properties in order to ensure that the word is indeed inside the language, and that the adversary is not trying to get information Chapter 5 Generic Construction from Projective Hash Functions about the hashing keys by decrypting ciphertext for words outside the language. We also prevent malleability by using the technique already described in Section 3.3. In the end, our scheme is really close to parallel repetitions of the Cramer-Shoup encryption scheme [START_REF] Cramer | A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack[END_REF], but instead of using a hash of the witness as a tag, we use the standard approach based on one-time signatures because the former wouldn't yield an IND-IPFE-CCA secure scheme in our case.

Security Against Chosen-Plaintext Attacks. The strategy to prove IND-IPFE-CPA security of our first scheme is not very far from the strategy used in Chapter 4 and the one used in [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF]. The proof proceeds in two steps:

1. First, we replace the word of the challenge ciphertext to a word outside the language.

In order to generate the correct distribution for the ciphertext, we instead generate it using the hashing keys instead of the projection keys.

2. The second step is to use statistical properties of the projective hash functions to argue that the adversary cannot guess the challenge bit with non-negligible probability. The strategy here is to switch the hashing key for another hashing key that gives the same projection key, but a different hash for the word chosen in the challenge ciphertext.

In the second step, we will require to know the challenge messages, so we will guess them, as done in complexity leveraging. However, here we only guess the vectors in the second part of the proof, so the security loss doesn't apply to the computational argument which is used in the first step. In practice, this only impacts the size of the secret keys and doesn't weaken the hardness of the underlying assumption.

Security Against Chosen-Ciphertext Attacks. The core idea of our construction is similar to the one used in the Cramer-Shoup encryption scheme [CS98; CS02]: adding a hash value (from a 2-universal PHF) to ensure that the word b is in the language L, to our generic IND-IPFE-CPA construction in Section 5.3. Then, at least information-theoretically, the hash values hash(hk i , b) used to decrypt a ciphertext could be computed using only the projection keys hp i and do not leak any information about hk i . We can then conclude using the same ideas as in the IND-IPFE-CPA security proof of our generic construction. However, this does not work directly, as checking a 2-universal hash value require to know the corresponding hashing key hk † , and knowing this hashing key enables to fake these hash values. In other words, with the naive scheme described previously, an attacker knowing a secret key for any #" y could then generate a ciphertext with b / ∈ L, but a valid 2-universal hash values. This completely removes the usefulness of the 2-universal hash value.

Our new idea is the following: instead of using only one hash value, we use such values. The secret key sk #" y only enables to check that a linear combination (with coefficient #" y ) of these hash values is valid. This uses the key homomorphism property. Knowing sk #" y enables to generate hash values that would be accepted by the decryption oracle with #" y , and knowing sk #" y for multiple vectors #" y enables to generate hash values for any vector in the span of these #" y . But intuitively, this is not really an issue, as if the attacker already knows sk #" y , calling the decryption oracle for #" y is of no use to him, as he could decrypt the given ciphertext himself. The proof however is more subtle and requires a careful design of hybrid games to deal with adaptivity and the fact that we are working over a ring and not a field. In particular, we cannot directly rely on the notion of span of vectors.

Chapter 5

5.2 IPFE-CPA Friendly Projective Hash Functions 67

IPFE-CPA Friendly Projective Hash Functions

In this section we present the properties required by our first projective hash function in order to build an IND-IPFE-CPA secure inner-product functional encryption scheme that will be later improved to IND-IPFE-CCA security. We first define 3 new properties on the projective hash functions, that we will regroup under one property for the sake of readability later.

Key Homomorphism

For correctness of the IPFE we will need the following property. Like in the generic construction from public key encryption, we use an additive homomorphism to compute the result of the inner-product, while changing the key used for decryption. We give an illustration of this property on Figure 5.3, and the formal definition below.

Definition 5.2.1 (Key Homomorphism [BJL16]

). A projective hash function PHF = (hashkg, projkg, hash, projhash) for a subset membership problem P is key-homomorphic, if it satisfies the following additional properties:

1. the set K of hashing keys and the set Π of hash values are additive Abelian groups, with polynomial time group operations;

2. for any instance Λ, and any word b ∈ X , the function hk

∈ K → hash(hk, b) ∈ Π is a group homomorphism, that is, hash(hk, b) + hash(hk , b) = hash(hk + hk , b), for any hk, hk ∈ K.
We do not require K to be finite. For example, in the DCR construction in Chapter 7, K = Z. However, we require that each group element of K and Π has a unique representation as a bit-string.

# " hk

# " hk, #" y #" h #" h , #" y •, #" y •, #" y Hash(•,b) Hash(•,b)
Figure 5.3: Illustration of key homomorphism. We see that a linear combination of the hashing keys gives the same linear combination of the hash values for any word. This property is similar to the linear ciphertext homomorphism under shared randomness of Section 4.2.2. Here the shared randomness is the word b.

Projection Key Homomorphism

For our IND-IPFE-CCA secure construction, we do not only need key homomorphism, in the security proof, we also need to simulate projection key, so we are going to require another homomorphic property, projection key homomorphism. It is only required in Section 5.4.3 (for the CCA security), but we will introduce it already here to discuss some possible simplifications of the next properties.

Definition 5.2.2 (Projection Key Homomorphism). A projective hash function PHF = (hashkg, projkg, hash, projhash) for a subset membership problem P is projection-key-homomorphic if it satisfies the following additional properties:

1. the set K of hashing keys and the set K hp of projection keys are additive Abelian groups, with polynomial time group operations;

2. for any instance Λ, the function hk ∈ K → projkg(hk) ∈ K hp is a group homomorphism, that is, projkg(hk + hk ) = projkg(hk) + projkg(hk ), for any hk, hk ∈ K.

Strong Diversity

The second property we need for our PHFs is strong diversity. More precisely, we require that for each b there exists a (not necessarily efficiently computable) hashing key hk ⊥ (b), such that hk and hk + hk ⊥ (b) result in the same projection key, while the hash value of b under the key hk ⊥ (b) is equal to g ⊥ , where g ⊥ is a fixed efficiently computable group element.

Definition 5.2.3 (Strong diversity).

A key-homomorphic projective hash function PHF = (hashkg, projkg, hash, projhash) for a subset membership problem P is (hk ⊥ , g ⊥ , M ⊥ )-strongly diverse for a function hk ⊥ : L → Π, an element g ⊥ of Π, and a positive integer M ⊥ , if the following properties are satisfied:

1. g ⊥ and M ⊥ can be efficiently computed from Λ;

2. the group element g ⊥ has order M ⊥ , 3. for any hashing key hk ∈ K and any word b ∈ L:

projkg(hk + hk ⊥ (b)) = projkg(hk) , (5.1) hash(hk ⊥ (b), b) = g ⊥ . (5.2)
We do not require hk ⊥ to be efficiently computable, as we are only using it to bound statistical distance.

In what follows, we will use the following straightforward lemma.

Lemma 5.2.4. If a key-homomorphic PHF is also projection-key homomorphic, then Equation Equation (5.1) is true iff projkg(hk

⊥ (b)) = 0.
Relation with Diverse Groups. Diverse groups were introduced in [CS02] as a way to construct PHFs. They can be seen as key-homomorphic projection-key-homomorphic strongly diverse PHFs with the two following differences: L = X \ L (instead of L ⊆ X \ L), and for any hk ∈ K and any b ∈ L, it is only required that hash(hk

⊥ (b), b) = 0 instead of hash(hk ⊥ (b), b) = g ⊥ .
Nevertheless, all the diverse groups we currently know of are also strongly diverse for L = X \ L.

Chapter 5

5.3 Inner-Product Functional Encryption Secure Against Chosen-Plaintext Attacks 69

Translation Indistinguishability

We also require one last statistical property, translation indistinguishability. Informally it says that translating the hashing key of the PHF by a small multiple of hk ⊥ (b) cannot be detected with non-negligible probability. In the proof, we use this as a statistical argument to conclude after using the computational assumption.

Definition 5.2.5 (Translation indistinguishability).

A key-homomorphic projective hash function PHF = (hashkg, projkg, hash, projhash) is (hk ⊥ , M x , ε ti )-translation-indistinguishable for a function hk ⊥ : L → Π, a positive integer M x , and ε ti ∈ [0, 1], if for any integer x ∈ {-M x , . . . , M x } and for any b ∈ L,

∆(hashkg(Λ), hashkg(Λ) + x • hk ⊥ (b)) ≤ ε ti .
Important Particular Case: Key Uniformity. For many key-homomorphic PHFs, like the ones based on DDH and MDDH that we are going to use in Chapter 6, the output of hashkg is actually uniform over the group K. In this case, the PHF is automatically (•, •, 0)-translation-indistinguishable. More formally, we have the following lemma.

Lemma 5.2.6. Let PHF = (hashkg, projkg, hash, projhash) be a key-homomorphic PHF such that the distribution of hashkg(Λ) is uniform over K. Let L be a non-empty subset of X , hk ⊥ be a function from L to Π and M x be a positive integer. Then PHF is (hk ⊥ , M x , 0)translation-indistinguishable.

Proof. Both hashkg(Λ) and hashkg(Λ) + x • hk ⊥ (b) are uniform group elements in K.

IPFE-CPA Friendliness

In the following, we regroup all 3 properties we have defined under the IPFE-CPA friendliness property.

Definition 5.2.7 (IPFE-CPA Friendliness).

A projective hash function PHF = (hashkg, projkg, hash, projhash) is (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly for a function hk ⊥ from L to Π, an element g ⊥ of Π, and two positive integers M ⊥ and M x , if it is key-homomorphic, (hk ⊥ , g ⊥ , M ⊥ )-strongly diverse, and (hk ⊥ , M x , ε ti )-translation-indistinguishable.

We are now ready to show our construction of inner-product functional encryption from key homomorphic projective hash functions.

Inner-Product Functional Encryption Secure Against Chosen-Plaintext Attacks

We now define our generic construction for IND-IPFE-CPA secure IPFEs. Intuitively, we use PHFs in parallel, that are combined during decryption in order to only reveal a linear combination of the hashes, which implies that it only reveals this same linear combination of the messages. This restriction is enforced by the key generation algorithm, which only outputs linear combinations of the hashing keys.

Construction and Correctness

We first give an informal illustration of the construction and its correctness via an illustration on Figure 5.4. It is a very intuitive construction given the definitions of projective hash functions and the key homomorphism property. Then, we explicit more formally the construction and prove its correctness.

Setup Encrypt KeyGen

Decrypt We suppose that we have a (hk ⊥ , g ⊥ , M ⊥ , x, ε ti )-IPFE-CPA-friendly projective hash function PHF = (hashkg, projkg, hash, projhash) for a subset membership problem P. Let R be the ring Z or Z M ⊥ , let be a positive integer parameter corresponding to the length of the message and key vectors, and let M y and M x two subsets of R . We always suppose to be polynomial in the security parameter κ.

# " hp # " hk #" x #" y ( #" h + #" x , b) # " hk, #" y #" h + #" x , #" y -Hash( # " hk, #" y , b) = #" x , #" y Bob Alice
We suppose that the following condition is satisfied.

Condition 1. Using the above notation:

1. if R = Z M ⊥ , the order of any hashing key hk ∈ K divides M ⊥ ;

2. M y and M x are efficiently recognizable subsets of R ;

3. for any #" x ∈ M x and any i, x i ∈ {-M x , . . . , M x };

4. there exists a polynomial time algorithm (in the security parameter κ) that given as input ct #" y = #" y , #" x • g ⊥ for #" y ∈ M y and #" x ∈ M x , can compute log g ⊥ ct #" y = #" y , #" x ; 5. for any #" y ∈ M y and #" x ∈ M x , #" y , #" x is the same over R and over

Z M ⊥ (this condition is trivial when R = Z M ⊥ ).
The first subcondition implies that K is a R-module, which implies that, for any t ∈ R, t • hk is well defined. The second subcondition enables KeyDer and Encrypt to check in polynomial-time the validity of their arguments y and x respectively. The third subcondition Chapter 5

5.3 Inner-Product Functional Encryption Secure Against Chosen-Plaintext Attacks 71 is used in the proof to apply the (hk ⊥ , M x , ε ti )-translation indistinguishability property. The fourth subcondition ensures that decryption can be performed in polynomial time. The last subcondition is similar as the condition in the "over Z constructions in [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF]. If R = Z M ⊥ , then-as in [ALS16]-a simple way to guarantee that subconditions 3 and 5 hold is to assume that |y i |, |x i | < (M ⊥ / ) 1/2 for each #" y ∈ M y , #" x ∈ M x , and i ≤ . The fourth subcondition can potential restrict the values |y i | and |x i | even more. We are now ready to present our scheme and to prove its correctness.

Construction 5.3.1 (Inner-Product Functional Encryption secure against Chosen-Plaintext Attacks from Projective Hash Functions). Let P be a subset membership problem. Let PHF = (hashkg, projkg, hash, projhash) be a (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly PHF. We assume that Condition 1 is satisfied. We define our inner-product functional encryption scheme FE as follows.

• Setup(1 κ , 1 ) → (msk, mpk). On input security parameter κ and functionality parameter , samples

Λ $ ← I κ , sets pp = (κ, , Λ), computes for all i in [ ] hk i $ ← hashkg(Λ) , hp i ← projkg(hk i ) ,
and returns master secret key msk = (pp, # " hk) and master public key mpk = (pp, # " hp);

• KeyDer(msk, #" y ) → sk #" y . On input master secret key msk, and key #" y ∈ M y , computes

hk #" y ← #" y , # " hk ,
and outputs user secret key sk #" y = hk #" y ;

• Encrypt(mpk, #" x ) → ct #" x . On input master public key mpk, and plaintext #" x ∈ M x , samples a random pair (b, w) ∈ , computes for all i in [ ]

ct i ← projhash(hp i , b, w) + x i • g ⊥ ,
and outputs ciphertext ct #" x = (b, #" ct);

• Decrypt(sk #" y , ct #" x ) → m or ⊥. On input user secret key sk #" y , and ciphertext ct #" x , computes ct #" x , #" y ← #" y , #" cthash(hk #" y , b)

and returns log g ⊥ ct #" x , #" y .

Correctness. The correctness of our construction follows from the correctness and key homomorphism of the PHF, the fact that g ⊥ has order M ⊥ , and from Condition 1, as follows:

#" y , #" ct = i=1 y i • (projhash(hp i , b, w) + x i • g ⊥ ) = i=1 y i • hash(hk i , b) + i=1 y i • x i • g ⊥ = hash( i=1 y i • hk i , b) + #" y , #" x • g ⊥ = hash(hk #" y , b) + #" y , #" x • g ⊥ .
Now, because g ⊥ has order M ⊥ , and thanks to Condition 1, one can extract #" y , #" x over R. Since this equal to #" y , #" x over Z M ⊥ , we get that the completeness holds.

ε A ≤ 2 • ε B + • |∆M x | • ε ti .
Before going into the proof, we make the following remark on the precise advantage of the adversary in the reduction, and give a quick overview of the proof.

Remark 5.3.3. When ε ti = 0, there is an exponential loss in the security proof in the term |∆M x |ε ti . This term comes from the fact that at one point we guess the value of #" x 1 -#" x 0 . This is not complexity leveraging, as the reduction loss is with regards to a statistical property. In particular, we do not need to rely on subexponential computational assumptions. Concretely, in our instantiations with DCR, we just need to take this security loss into account in the parameter M defining the bound on the size of the hashing key (see Chapter 7). This approximately multiplies by log |∆M x | the size of the secret keys which would be obtained if this security loss was not taken into account.

We also remark that if we used a selective security notion, where the adversary announces #" x 0 and #" x 1 before obtaining the public key, we would not lose the factor |∆M x |. We could then use classical complexity leveraging to go from this selective notion to the adaptive one we are considering. But then, we would need to use sub-exponential (L, L)-indistinguishability (if is polynomial in the security parameter), and the size of the ciphertexts, of the secret and public keys, and of the public parameters (and not just of the secret keys) would be multiplied by |∆M x |.

For a quick overview of the proof, we illustrate the strategy on Figure 5.5. Let us now move to the formal proof of the theorem.

Proof. We process through a sequence of games Game 0 , . . . , Game 4 , at each game slightly modifying FE. We denote by Win[Game i ] the probability that the adversary wins Game i , and by

Adv[Game i ] = |2 • Win[Game i ] -1| its advantage. We then upper bound the ad- vantage Adv[∆ i ] = |Win[Game i ] -Win[Game i-1 ]| = |Adv[Game i ] -Adv[Game i-1 ]|/2,

Setup Encrypt KeyGen

# " hp # " hk ( #" x 0 , #" x 1 ) #" y In the first one, we change the way to compute the challenge ciphertext. In the second one, we change the word in the language. This last game is statistically unwinnable.

( #" h + #" x b , b) # " hk, #" y 2. Setup Encrypt KeyGen # " hp # " hk ( #" x 0 , #" x 1 ) #" y ( #" h + #" x b , b) # " hk, #" y 3. Setup Encrypt KeyGen # " hp # " hk ( #" x 0 , #" x 1 ) #" y ( #" h + #" x b , b) # " hk, #" y
In Game 1 , we change the way of computing the ciphertext. More precisely, we now compute ct i as follows using hk i instead of hp i and w:

ct i ← hash(hk i , b) + x i g ⊥ ,
which is perfectly indistinguishable thanks to the correctness of the PHF. Hence, Adv[∆ 1 ] = 0.

In Game 2 , we sample b from L instead of from L. Clearly, we can construct an attacker B that runs in approximately the same time as A such that Adv[∆ 2 ] ≤ ε B , where B is the advantage of B against (L, L)-indistinguishability.

In Game 3 , we pick a uniform random value x * ∈ ∆M x at the beginning and abort if #" x 1 -#" x 0 = x * and make the adversary win with probability 1 2 in that case. As x * is completely independent of everything else,

Adv[Game 2 ] = |∆M x | • Adv[Game 3 ] ,
since:

Adv[Game 3 ] = |2 • Win[Game 3 ] -1| = 2 • 1 |∆M x | • Win[Game 2 ] + |∆M x | -1 |∆M x | • 1 2 -1 = 1 |∆M x | • |2 • Win[Game 2 ] -1| = 1 |∆M x | • Adv[Game 2 ] .
In Game 4 , we also abort if the adversary queries a vector #" y ∈ M y to the key oracle such that #" y , x * = 0. This game is perfectly indistinguishable from the previous one, as the adversary cannot ask for a key for #" y ∈ M y such that #" y , #" x 0 = #" y , #" x 1 . Hence, Adv[∆ 4 ] = 0.

Let us now bound Adv[Game 4 ]. For that purpose, let Game 4,0 and Game 4,2 be the games corresponding to Game 4 when b is fixed to 0 and 1 respectively. We have:

Adv[Game 4 ] = | Pr[b A = 1 in Game 4,2 ] -Pr[b A = 1 in Game 4,0 ]| .
We then construct the game Game 4,1 from Game 4,0 by replacing # " hk by # " hk defined as follows:

# " hk ← # " hk + x * • hk ⊥ (b)
where hk i $ ← hashkg(Λ) for i = 1, . . . , . By translation indistinguishability, we have:

| Pr[b A = 1 in Game 4,1 ] -Pr[b A = 1 in Game 4,0 ]| ≤ ε ti .
We conclude by remarking that Game 4,1 and Game 4,2 are perfectly indistinguishable and that:

Pr

[b A = 1 in Game 4,2 ] = Pr[b A = 1 in Game 4,1 ] .
Indeed, in Game 4,1 , assuming no abort, we have x * = #" x 1 -#" x 0 and for any allowed query #" y to KeyDer msk :

projkg(hk i ) = projkg(hk i ) ct i = hashkg(Λ, hk i , b) + x 0,i g ⊥ = hashkg(Λ, hk i , b) + x * i g ⊥ + x 0,i g ⊥ = hashkg(Λ, hk i , b) + x 1,i g ⊥ hk #" y = #" y , # " hk = #" y , # " hk + #" y , x * hk ⊥ (b) = #" y ,
# " hk as #" y , x * = #" y , #" x 1 -#" y , #" x 0 = 0 . Finally, putting everything together, we get

ε A = Adv[Game 0 ] ≤ 2Adv[∆ 1 ] + 2Adv[∆ 2 ] + |∆M x | • Adv[Game 4 ] ≤ 2ε B + |∆M x |ε ti .

IPFE-CCA Friendly Projective Hash Functions

In order to achieve IND-IPFE-CCA security, we will require another kind of projective hash functions: tag-based projective hash functions [START_REF] Abdalla | Disjunctions for Hash Proof Systems: New Constructions and Applications[END_REF]. In this section, we first define this new tool, as well as the properties we need for our construction. As both a IPFE-CPAfriendly PHF and a IPFE-CCA-friendly PHF are used in our constructions of IND-IPFE-CCA inner-product functional encryption scheme in Section 5.5, we distinguish the two PHFs by adding a dagger to all the symbols defining the latter PHF. Both PHFs will be used on the same subset membership problem P.

Chapter 5

5.4 IPFE-CCA Friendly Projective Hash Functions 75

Tag-Based Projective Hash Function

A tag-based projective hash function [START_REF] Abdalla | Disjunctions for Hash Proof Systems: New Constructions and Applications[END_REF] is defined as a PHF, except that hash † and projhash † take an additional input (in some efficiently recognizable set T ) called a tag τ . We suppose that we can efficiently uniquely encode any 2κ-bit string as a tag τ , as a tag is usually the output of a collision-resistant hash-function. In our constructions, T is Z M for some large integer M . As for basic projective hash functions, we provide some intuition on how to use tag-based PHFs using a diagram on On the first illustration, we see the correctness property: if the same tag is used, then the same hash is derived. On the second illustration, we see the property that will be useful to prove the security against chosen-ciphertext attacks: if the tag is different, it is hard to guess the correct hash value.

Definition 5.4.1 (Tag-based Projective Hash Function [ABP15]

). Let P be a subset membership problem, specifying an ensemble (I ) ≥0 of instance distributions. A tag-based projective hash function for P is a tuple PHF † = (hashkg † , projkg † , hash † , projhash † ) of four probabilistic polynomial time algorithms:

• hashkg † (Λ) generates a hashing key hk † in a set K † for the instance Λ = Λ[X , L, W, ],
• projkg † (hk † ) (deterministically) derives from the hashing key hk † a projection key hp † from the set K hp of possible projection keys,

• hash † (hk † , b, τ ) (deterministically) computes the hash value H † (in some efficiently recognizable set Π), of b ∈ X under hk † ∈ K † , for the tag τ ∈ T ,

• projhash † (hp † , b, w, τ ) (deterministically) computes the projected hash value pH † of b ∈ L using a witness w ∈ W, for the tag τ ∈ T .

It has to satisfy the following correctness property:

• For any instance Λ, for any b ∈ X and w ∈ W, s.t. (b, w) ∈ , for any hashing key hk † ∈ K † , for any tag τ ∈ T , if hp † ← projkg † (hk † ), then:

hash † (hk † , b, τ ) = projhash † (hp † , b, w, τ ) .
The notion of key homomorphism can be adapted to tag-based PHFs in a straightforward way: it has to hold for any tag τ ∈ T .

In the sequel, we sometimes omit the term "tag-based" when it is clear from context.

2-Universality

We now recall the notion of 2-universality, first introduced by Cramer and Shoup in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF], in order to ensure non-malleability. This will not be directly required by the tag-based PHF we use in the construction, but by a slight modification on it that will be used during the proof. It will ensure that decryption queries made by the adversary do not leak too much information.

Definition 5.4.2 (2-universality). A key-homomorphic tag-based projective hash function

PHF † = (hashkg † , projkg † , hash † , projhash † ) for a subset membership problem P is ε † 2u -2universal if for any instance Λ, for any b ∈ X and b ∈ X \ L, for any distinct tags τ, τ ∈ T , for any hp † ∈ K hp , and for any H † ∈ Π, H † ∈ Π:

Pr hk † H † = hash † (hk † , b, τ ) ∧ H † = hash † (hk † , b , τ ) ∧ hp † = projkg † (hk † ) ≤ ε † 2u • Pr hk † H † = hash † (hk † , b, τ ) ∧ hp † = projkg † (hk † ) ,
where probabilities are taken over hk

† $ ← hashkg † (Λ). The PHF is 2-universal if it is ε † 2u (κ)- 2
-universal for some negligible function ε † 2u (κ). In our generic construction, we will not require the PHF used in the construction to be 2-universal, but a variant of it where hashkg † is replaced by some other (not necessarily polynomial time) algorithm.

Universal Translation Indistinguishability

We also need one last statistical property to conclude the proof, as in the IND-IPFE-CPA case: universal translation indistinguishability. It is a strengthening of the previous translation indistinguishability in the sense that the algorithm defining the translation has to be the same for all words.

Definition 5.4.3 (Universal translation indistinguishability). A key-homomorphic tag-based projective hash function PHF

† = (hashkg † , projkg † , hash † , projhash † ) is (hashkg † , M x , ε †
uti )universally-translation-indistinguishable for a (not necessarily polynomial time) algorithm hashkg † taking as input Λ and outputting a hashing key hk † in some set K * † ⊆ K, and for a positive integer M x , if for any integer x such that |x| ≤ M x ,

∆(hashkg † (Λ), hashkg † (Λ) + x • hashkg † (Λ)) ≤ ε † uti .
encryption scheme can then be obtained by Construction 3.3.5. This construction is an enhancement of the previous IND-IPFE-CPA secure scheme which uses also tag-based projective hash functions in order to ensure the non-malleability of the scheme.

Construction and Correctness

As our construction is closely related to the previous one, and the intuition is about the same, we first highlight the changes made to reach IND-IPFE-CCA security on Figure 5.7, before formally presenting the construction and the proof of its correctness. The idea is that the one-time signature prevents the use of the same tag for the challenge ciphertext, and a ciphertext generated by the adversary. Then, the security of the tag-based IPFE will convey to the tagless IPFE. Let us now define our construction of a IND-TBIPFE-CCA secure tag-based inner-product functional encryption scheme.

Encrypt b w # " hp ProjHash #" x #" h + #" x # " hp' #" h '
We suppose that we have a (hk ⊥ , g ⊥ , M ⊥ , x, ε ti )-IPFE-CPA-friendly projective hash function PHF = (hashkg, projkg, hash, projhash) and a (hashkg † , Σ † , ε † 2u , M x , ε † uti )-IPFE-CCA-friendly projective hash function PHF † = (hashkg † , projkg † , hash † , projhash † ) for the subset membership problem P. Let R be the ring Z or Z M ⊥ , let be a positive integer parameter corresponding to the length of the message and key vectors, and let M y and M x be two subsets of R . We always suppose to be polynomial in the security parameter κ.

We suppose that Condition 1 is satisfied, in addition to the following new condition.

Condition 2. Using the above notation:

1. if R = Z M ⊥ , the order of any hashing key hk ∈ K † divides M ⊥ ; and 2. for any #" y ∈ M y and #" x ∈ M x , #" y , #" x ∈ Σ † ∪ {0} ⊆ R.

Construction 5.5.1 (Tag-Based Inner-Product Functional Encryption secure against Chosen-Ciphertext Attacks from Projective Hash Functions). Let P be a subset membership problem.

Chapter 5

5.5 Inner-Product Functional Encryption Secure Against Chosen-Ciphertext Attacks 79

Let PHF = (hashkg, projkg, hash, projhash) be a (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly PHF, and PHF † = (hashkg † , projkg † , hash † , projhash † ) be a (hashkg † , Σ † , ε † 2u , M x , ε † uti )-IPFE-CCA-friendly tag-based PHF. We assume that Conditions 1 and 2 are satisfied. We define our tag-based inner-product functional encryption scheme T BFE as follows.

• Setup(1 κ , 1 ) → (msk, mpk). On input security parameter κ and functionality parameter , samples Λ $ ← I κ , sets pp = (κ, , Λ), computes for all i in [ ]

hk i $ ← hashkg(Λ) , hp i ← projkg(hk i ) , hk † i $ ← hashkg † (Λ) , hp † i ← projkg † (hk † i ) ,
and returns master secret key msk = (pp, # " hk, # " hk † ) and master public key mpk = (pp, # " hp, # " hp † );

• KeyDer(msk, #" y ) → sk #" y . On input master secret key msk, and key #" y ∈ M y , computes

hk #" y ← #" y , # " hk , hk † #" y ← #" y , # " hk † ,
and outputs user secret key sk #" y = (hk #" y , hk † #" y );

• Encrypt(τ, mpk, #" x ) → ct #" x . On input master public key mpk, and plaintext #" x ∈ M x , samples a random pair (b, w) ∈ , computes for all i in [ ]

ct i ← projhash(hp i , b, w) + x i • g ⊥ , ct † i ← projhash † (hp † i , b, w, τ ) ,
and outputs ciphertext ct #" x = (b, #" ct, #" ct †

);

• Decrypt(τ, sk #" y , ct #" x ) → m or ⊥. On input user secret key sk #" y , and ciphertext ct #" x , checks that #" y ,

#" ct † = hash † (hk † #" y , b, τ )
and returns ⊥ if it fails, otherwise computes

ct #" x , #" y ← #" y , #" ct -hash(hk #" y , b)
and returns log g ⊥ ct #" x , #" y .

Correctness. The correctness of our scheme follows from correctness and key homomorphism of both PHF and PHF † and from the fact that g ⊥ has order M ⊥ . The proof is similar to the one for Theorem 5.3.2 with the additional remark:

#" y , #" ct † = i=1 #" y i • (projhash † (hp † i , b, w, τ )) = i=1 #" y i • hash † (hk † i , b, τ ) = hash † ( i=1 #" y i • hk † i , b, τ ) = hash † (hk † #" y , b, τ ) .

Security Against Chosen-Ciphertext Attacks

We have the following security theorem.

Theorem 5.5.2. Let P be a subset membership problem. Let PHF = (hashkg, projkg, hash, projhash) be a (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly projective hash function, (hashkg † , Σ † , ε † 2u , M x , ε † uti )-IPFE-CCA-friendly tag-based projective hash function, and let T BFE be the tag-based inner-product functional encryption scheme defined in Construction 5.5.1. We assume that Conditions 1 and 2 are satisfied. Then T BFE is IND-TBIPFE-CCA secure.

More precisely, if there exists an adversary A = A T BF E that has advantage ε A in breaking the IND-TBIPFE-CCA security of T BFE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the (L, L)-indistinguishability, such that

ε A ≤ 2 • ε B + • |∆M x | • (ε ti + 2 • ε † uti ) + 2 • q dec • |∆M x | • ε † 2u ,
where q dec is the number of queries to the decryption oracle.

Before proving the theorem, we one again give a remark on the precise advantage of the adversary in the reduction.

Remark 5.5.3. In addition to the exponential loss

• |∆M x | • (ε ti + 2 • ε † uti
) similar to the one for the generic IND-IPFE-CPA construction (Theorem 5.3.2), there is an addition exponential loss in the security proof in the term 2q dec |∆M x |ε † 2u . We point out however that the resulting requirement that |∆M x |ε † 2u is negligible in the security parameter can easily be achieved: given a ε † 2u -2-universal PHF, we can get a (ε † 2u ) ν -2-universal PHF, by repeating it ν-times in parallel. This transformation preserves IPFE-CCA friendliness. We emphasize that the resulting key and ciphertext sizes remain polynomial in the security parameter κ, and that we do not rely on complexity leveraging nor subexponential assumptions (see Remark 5.3.3).

Furthermore, as for the IND-IPFE-CPA construction from translation-indistinguishable keyhomomorphic PHF in Section 5.3, if we only consider a selective version of IND-TBIPFE-CCA security where the adversary announces #" x 0 and #" x 1 before receiving the public key, then we would not have this factor |∆M x |.

We now resume with the proof of the theorem.

Proof. We first give some intuition about the proof: let us analyze the decryption queries made by the adversary A , to give some intuition. Let ( #" y j , τ j , (b j , #" ct j , #" ct † j )) be the jth decryption query and let ( #" y 1 , . . . , #" y i j ) be the key queries made before this decryption query. We now split the analysis in two cases. Case #" y j ∈ Span( #" y 1 , . . . , #" y i j ). (Span( #" y 1 , . . . , #" y i j ) denotes the linear span of the vectors ( #" y 1 , . . . , #" y i j )) In this case, A can derive the key for #" y j and do the decryption anyway, so there is nothing to hide. Case #" y j / ∈ span( #" y 1 , . . . , #" y i j ). In this case, we argue that if b j / ∈ L, then the decryption oracle will output ⊥ with probability 1ε † univ : by definition of the 2-universality of PHF † , we have that conditioned on the value of # " hp † and on the value of the challenge ciphertext (b, #" ct, #" ct †

) if it was already generated:

Pr[hash † (hk † #" y j , b , τ ) = #" y j , #" ct † ] ≤ ε † univ .
Chapter 5

5.5 Inner-Product Functional Encryption Secure Against Chosen-Ciphertext Attacks 81

Unfortunately, the fact that the adversary can adaptively choose the vectors #" y i and #" y j in particular makes the above intuition hard to directly translate into a formal valid proof. To deal with adaptivity, we guess x * = #" x 1 -#" x 0 before using 2-universality. That is why we loose a factor ∆M x in the security reduction.

Let us now do a formal proof by games. We use the same notation as in the proof of Theorem5.3.2. The first four games are basically the same.

Game 0 corresponds to the actual IND-TBIPFE-CCA scheme. The challenge ciphertext is (b, #" ct, #" ct †

). In Game 1 , we change the way of computing the ciphertext. More precisely, we now compute ct i as follows using hk i instead of hp i and w:

ct i ← hash(hk i , b) + x i • g ⊥ ct † i ← hash † (hk † i , b, τ
) , which is perfectly indistinguishable thanks to the correctness of the PHF. Hence, Adv[∆ 1 ] = 0.

In Game 2 , we sample b from L instead of from L. We can construct an attacker B that runs in approximately the same time as A such that Adv[∆ 2 ] ≤ ε B , where B is the advantage of B against (L, L)-indistinguishability.

In Game 3 , we pick a uniform random value x * ∈ ∆M x at the beginning and abort if #" x 1 -#" x 0 = x * and make the adversary win with probability 1 2 in that case. As in the proof of Theorem 5.3.2, we have

Adv[Game 2 ] = |∆M x | • Adv[Game 3 ] .
In Game 4 , we also abort if the adversary queries a vector #" y ∈ M y to the key oracle such that #" y , x * = 0. This game is perfectly indistinguishable from the previous one, as the adversary cannot ask for a key for #" y ∈ M y such that #" y , #"

x 0 = #" y , #" x 1 . Hence, Adv[∆ 4 ] = 0.
In the proof of Theorem 5.3.2, we then proved that Adv[Game 4 ] = 0 using strong diversity and translation indistinguishability. But here, we cannot apply strong diversity directly, as the hashing keys # " hk are still used to answer the queries to the decryption oracle and too much information might leak from there. To conclude the proof, we need more games.

In Game 5 , we sample the hashing keys hk † i as follows:

# " hk † ← # " hk † + x * • hk † with hk † i $ ← hashkg † (Λ) for i = 1, . . . , ; hk † $ ← hashkg † (Λ) .
In the previous game, # " hk † could be seen as being generated as # " hk † ← # " hk † Thanks to universal translation indistinguishability of PHF † , using an hybrid argument, we have:

Adv[∆ 5 ] ≤ • ε †
uti . We remark that in Game 5 , by projection key homomorphism:

# " hp † i = projkg † (hk † i ) = projkg † ( # " hk † i ) + x * i • projkg † (hk †
) . Furthermore, for any vector #" y ∈ M y such that #" y , x * = 0, the corresponding secret key msk #" y = (pp, hk #" y , hk † #" y ) is such that:

hk † #" y = #" y , # " hk † = #" y , # " hk † + #" y , x * • hk † = #" y , # " hk † .
These keys therefore do not reveal any information about hk † . We recall that the only places we compute a key msk #" y are in response to a query to a key oracle or to the decryption oracle.

In the first case, if there is no abort, we always have #" y , x * = 0. Furthermore, we remark that the vector #" ct † of the challenge ciphertext is such that:

ct † i = hash † (hk † i , b, τ ) = hash † (hk † i , b, τ ) + x * i • hash † (hk † , b, τ )
, by key homomorphism. This means that the only information that the attacker sees about hk † comes from:

1. its projection key hp † = projkg † (hk † ), 2. the keys msk #" y used by the decryption oracle on a query associated to a vector #" y ∈ M y such that #" y , x * = 0, 3. the hash value hash † (hk † , b, τ ) used to compute the challenge ciphertext.

In Game 6 , we change the decryption oracle as follows: on input query ( #" y j , τ j , (b j , #" ct j , #" ct † j )):

• if #" y j , x * = 0, it behaves as usual using # " hk #" y j = #" y j , # " hk and

# " hk † #" y j = #" y j , # " hk † to decrypt the ciphertext (b j , #" ct j , #" ct † j )
with the tag τ j ; we recall that this does not reveal any information about hk † ;

• otherwise:

if b j ∈ L, it finds a witness w j , 1 and checks that

#" y , #" ct † j = projhash † ( #" y j , # " hp † , b j , w j , τ )
instead of checking that:

#" y , #" ct † j = hash † (hk † #" y j , b j , τ ) .
This is perfectly indistinguishable by correctness of PHF † and shows that this does not reveal any information about hk † beyond hp † ; if b j ∈ X \ L, then it rejects the ciphertext. This is statistically indistinguishable thanks to the 2-universality.

This game is statistically indistinguishable from the previous one using an hybrid argument changing the way the decryption oracle behaves query by query. We have:

Adv[∆ 6 ] ≤ 2 • q dec • ε † 2u .
In Game 7 , we change again the decryption oracle as follows, on input query ( #" y j , τ j , (b j , #" ct j , #" ct † j )):

• if #" y j , x * = 0, it behaves as usual;

• otherwise:

1 We recall that the reduction is statistical here.

Chapter 5

5.5 Inner-Product Functional Encryption Secure Against Chosen-Ciphertext Attacks 83

if b j ∈ L, it finds a witness w j , it checks #" y , #" ct † j as before, but it now computes ct #" x as follows:

ct #" x ← #" y j , #" ct j -projhash( #" y j , # " hp , b j , w j ) instead of ct #" x ← #" y j ,
#" ct jhash(hk, b j ) , which is perfectly indistinguishable by correctness of PHF.

if b j ∈ X \ L, then it rejects the ciphertext as in the previous game.

We now remark that if we forget about the part #" ct † of all the ciphertexts, we are exactly as in Game 4 of the proof of Theorem 5.3.2. The only information the adversary learns about # " hk is #" y , # " hk , for vectors #" y such that #" y , x * = 0 (if x * was guessed correctly). We conclude as in Theorem 5.3.

2 that Adv[Game 7 ] ≤ • ε ti .
The bound of the theorem follows.

Chapter 6

Chapter 6

Instantiations based on the Decisional Diffie-Hellman Assumption

In this chapter, we instantiate the generic constructions presented from public key encryption and from projective hash function with concrete constructions based on the decisional Diffie-Hellman assumption. We give 3 concrete instantiations of inner-product functional encryption that respectively reach s-IND-IPFE-CPA security, IND-IPFE-CPA security and IND-IPFE-CCA security, and compare their trade-offs between efficiency and security.

The main downside of this construction is that the decryption is expensive: it requires the computation of a discrete logarithm in a group where it is in general hard. So the message space has to be restricted. However, the schemes are conceptually simple and are modular. The first construction is the original one that we proposed in [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF], while the two others are taken from [START_REF] Benhamouda | CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions[END_REF].

The Decisional Diffie Hellman Assumption and Subset Membership Problem

In this section, we recall the decisional Diffie-Hellman (DDH) assumption and its generalization to matrix decisional Diffie-Hellman assumption. Then we present the subset membership problem whose indistinguishability is based on the DDH assumption which will be used to construct key homomorphic projective hash functions and thus IND-IPFE-CCA secure schemes.

The Decisional Diffie Hellman Assumption

The decisional Diffie-Hellman (DDH) assumption has been widely used in public key cryptography since the original two party key exchange that introduced it [DH76] and the very simple public key encryption scheme by ElGamal [ElG85] that we will use to construct an inner-product functional encryption scheme. It is an assumption that can only hold in groups where discrete logarithm are hard, and there are plenty of groups where it is believed to hold. For example, it is used in elliptic curves-based cryptography that is deployed for the security of the Internet.

The Decisional Diffie-Hellman Assumption. Let GroupGen be a probabilistic polynomial-time algorithm that takes as input a security parameter 1 κ , and outputs a triplet (G, q, g) where G is a group of order q that is generated by g ∈ G, and q is a κ-bit prime number.

Then, the Decisional Diffie-Hellman (DDH) assumption states that the tuples (g, g a , g b , g ab ) and (g, g a , g b , g c ) are computationally indistinguishable, where (G, q, g) ← GroupGen(1 λ ), and a, b, c ∈ Z q are chosen independently and uniformly at random. We also define the following subset membership problem that we will use for our projective hash functions based on DDH.

DDH-Based Subset Membership Problem.

Let G be an additive cyclic group of prime order q, let X = G 2 , let L be the subgroup of X generated by g = (g 1 , g 2 ) ∈ G 2 , where g i are random generators of G, and let L = X \ L. A witness w ∈ W = Z q for b ∈ L is such that b = wg. In other words, we have W = Z q and = {(w • g, w) : w ∈ Z q }. We set Λ = (G, g).

This defines a subset membership problem, whose (L, L)-indistinguishability property is equivalent to the DDH assumption.

The Matrix Decisional Diffie-Hellman Assumption

For some interesting cryptographic cyclic groups, such as groups with a symmetric pairing, the DDH assumption does not hold. That is why weaker assumptions, such as the decisional linear assumption (DLIN, [START_REF] Boneh | Short Group Signatures[END_REF]), have been considered. More recently, Escala et al. introduced the Matrix Diffie-Hellman (MDDH ) assumption family [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF] that generalizes DDH and its weaker variants like DLIN. Let us recall the MDDH assumption families in the context of subset membership problems.

MDDH-Based Subset Membership Problem.

Let G be a cyclic group of prime order q. Let D be a distribution of matrices in G t×d with d < t being two positive integers. Let g $ ← D. Let X = G t . Let L be the subgroup of X generated by the columns of g and let L = X \ L. A witness w ∈ W = Z d q for b ∈ L is such Chapter 6

6.2 ElGamal Public Key Encryption Scheme 87 that b = g • w. In other words, we have W = Z d q and = {(g • w, w) : w ∈ Z d q }. We set Λ = (G, g).

This defines a subset membership problem, whose (L, L)-indistinguishability property corresponds to the D-MDDH assumption.

When d = 1, t = 2, and D is the uniform distribution over vectors of two generators of G, then we get back the DDH-based subset membership problem.

ElGamal Public Key Encryption Scheme

We now present the public key encryption scheme whose security is based on the DDH assumption, and then we show that it satisfies the properties defined in Section 4.2.1.

Additively Homomorphic ElGamal

The standard ElGamal [START_REF] Elgamal | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF] public key cryptosystem doesn't directly satisfy the properties that we need. However, as it is multiplicatively homomorphic, it is easy to transform it in a way that satisfy our requirements: instead of directly encoding the message as a group element, we chose a generator g and encode a message m as m • g. This transformed the multiplicative homomorphism into an additive homomorphism, which is exactly what we wanted for our construction. The downside is that now, the decryption requires the computation of a discrete logarithm in base g. As the basis of the discrete logarithm is always the same, it is possible to speed up the decryption process by having precomputed discrete logarithm tables, but this still only allows decryption in a fixed polynomial-sized set.

We now recall the scheme with additive notation: Construction 6.2.1 (Additive ElGamal Public Key Encryption). The additive ElGamal public key encryption scheme E = (Setup, Encrypt, Decrypt) is defined as follows.

• Setup(1 κ ) → (pp, sk, pk). On input security parameter κ samples (G, q, g) $ ← GroupGen(1 κ ) and s $ ← Z q , and outputs public parameters pp = (G, g), secret key sk = s, and public key pk ← s • g;

• Encrypt(pp, pk, m) → ct. On input public parameter pp, public key pk, and plaintext m, samples r $ ← Z q , computes ct 0 ← r • g and ct 1 ← r • pk + m • g outputs ciphertext ct = (ct 0 , ct 1 );

• Decrypt(pp, sk, ct) → m or ⊥. On input public parameters pp, secret key sk, and ciphertext ct, computes and returns m = log g (ct 1sk • ct 0 ) outputs a message m or an error symbol ⊥.

Correctness. If the message belongs in a fixed polynomial range that allows the efficient computation of the discrete logarithm log g (m • g), the correctness comes directly from the fact that s • r • g = r • s • g. We recall that there exist generic algorithms to compute the discrete logarithm of an element t • g ⊥ in O( |T |) group operations, when t is in an interval T ; and in O(T ) group operations, when t is in an arbitrary subset of T ⊆ Z q . Lemma 6.3.3. Using above notation, let hashkg † = hashkg † , Σ † = Z q , ε † 2u = 1/q, M x be a positive integer, and ε † uti = 0. Then, the PHF described above is a (hashkg

† , Σ † , ε † 2u , M x , ε † uti )- IPFE-CCA-friendly.
Proof. Key Homomorphism is straightforward.

Projection Key Homomorphism is straightforward. Universal Translation Indistinguishability follows from Lemma 5.4.4.

2-Universality.

Assume that b = w 1 g 1 w 2 g 2 and b =

w 1 g 1 w 2 g 2 for w 1 = w 2 , p 1 := Pr hk † [H † = hash † (hk † , b, τ ) ∧ H † = hash † (hk † , b , τ ) ∧ hp † = projkg † (hk † )] = Pr hk † H † = hk † • b τ b ∧ H † = hk † • b τ b ∧ hp † = hk † • g 0 0 g = Pr hk †    H † H † hp † 1 hp † 2 = hk † •    w 1 g 1 w 1 g 1 g 1 0 w 2 g 2 w 2 g 2 g 2 0 τ w 1 g 1 τ w 1 g 1 0 g 1 τ w 2 g 2 τ w 2 g 2 0 g 2       = Pr hk † log g 1 H † log g 1 H † log g 1 hp † 1 log g 1 hp † 2 = hk † • M 1 , Chapter 6
6.3 Projective Hash Functions Based on the Decisional Diffie-Hellman Assumptions 91

where

M 1 =    w 1 w 1 1 0 w 2 log g 1 g 2 w 2 log g 1 g 2 log g 1 g 2 0 τ w 1 τ w 1 0 1 τ w 2 log g 1 g 2 τ w 2 log g 1 g 2 0 log g 1 g 2    .
On the other hand,

p 2 := Pr hk † [H † = hash † (hk † , b, τ ) ∧ hp † = projkg † (hk † )] = Pr hk † H † = hk † • b τ b ∧ hp † = hk † • g 0 0 g = Pr hk † H † hp † 1 hp † 2 = hk † • w 1 g 1 g 1 0 w 2 g 2 g 2 0 τ w 1 g 1 0 g 1 τ w 2 g 2 0 g 2 = Pr hk † log g 1 H † log g 1 hp † 1 log g 1 hp † 2 = log g 1 hk † • M 2
where

M 2 =   w 1 1 0 w 2 log g 1 g 2 log g 1 g 2 0 τ w 1 0 1 τ w 2 log g 1 g 2 0 log g 1 g 2   .
The column span of M 2 is included in the column span of M 1 , because M 1 contains M 2 as a submatrix. Moreover, the second column of M 1 is not in the column span of M 2 , so rank(M 1 ) = rank(M 2 ) + 1. Hence, p 1 ≤ p 2 /q. The theorem follows from Lemma 5.4.6.

We use a slight extension of this PHF because we need an exponentially small security parameter ε † 2u , due our security reduction. The following PHF can be seen as repeating ν times the PHF of Lemma 6.3.3:

• The tag set is T = Z q ; • hashkg † (Λ) outputs hk † $ ← Z 4×ν q =: K; • projkg † (hk † ) outputs hp † ← g 0 0 g • hk † ∈ G 2×ν =: K hp ; • hash † (hk † , b, τ ) outputs H † ← hk † • b τ •b ∈ G ν =: Π; • projhash † (hp † , b, w, τ ) outputs pH † ← ( w τ •w ) • hp † ∈ G ν = Π.
This can be use to construct IND-IPFE-CCA inner-product functional encryption schemes as showed by the following lemma. Lemma 6.3.4. Using above notation, let hashkg † = hashkg † , Σ † = Z q , ε † 2u = 1/q ν , M x be a positive integer, and ε † uti = 0. Then, the PHF described above is a (hashkg

† , Σ † , ε † 2u , M x , ε ti )- IPFE-CCA-friendly.
Proof. Key Homomorphism is straightforward.

Projection Key Homomorphism is straightforward.

Universal Translation Indistinguishability follows from Lemma 5.4.4.

Inner-Product Functional Encryption Schemes Based on the Decisional Diffie-Hellman Assumption

In this section, we present 3 inner-product functional encryption schemes based on the decisional Diffie-Hellman assumption. The first one is the most simple, but it only reaches s-IND-IPFE-CPA security. The second one is almost as efficient, adding 1 coordinate to the vectors only, and reaches adaptive IND-IPFE-CPA security. The last one reaches IND-IPFE-CCA security, but is more expensive: the public keys, secret keys, and ciphertexts are bigger than in the two previous schemes. We illustrate the differences between the schemes in Table 6.1 and present the tradeoffs between security and efficiency. We see that the adaptive security is almost for free, thus the second scheme should be prefered to the first one, which is still a good textbook example of inner-product functional encryption. On the other hand, security against active adversary is very expensive, and it should be considered with care if it is required or not.

Scheme Secure Against Selective Chosen-Plaintext Attacks

This scheme can be obtained by plugging the ElGamal public key encryption scheme in Construction 4.3.1. It is depicted on Figure 6.1 We recall that due to the constraint on the decryption, we have to set M x and M y such that the result of the inner-product is not too big in order to ensure correctness. Remember that we also need M x to be small enough for the proof of security. By using Theorem 4.3.3, we immediately get the following security theorem for our construction.

Chapter 6 The sizes are represented as a number of group elements for the master public keys and ciphertexts, while it is represented as the number of scalars in Z q for master and user secret keys. We recall that in order to achieve IND-IPFE-CCA security from the IND-TBIPFE-CCA secure scheme, we just need to add a one-time signature to the ciphertext, and does not make the size of the keys grow.

• Let G be a cyclic group of prime order q, g ⊥ a generator of G.

• Setup(1 κ , 1 ) → (mpk, msk): Set pp = (κ, , G, q, g ⊥ ). For i = 1, . . . , , set

s i $ ← Z q , h i ← s i • g ⊥ ∈ G .
Return msk = #" s ∈ Z q and mpk = #" h ∈ G ;

• KeyDer(msk, #" y ∈ M y ) → sk #" y : Return sk #" y ← #" y , #" s ∈ Z q ;

• Encrypt(mpk, #" x ∈ M x ) → ct #" x : Pick r $ ← Z q and set ct 0 ← r • g ⊥ ∈ G.

For i = 1, . . . , , set

ct i ← x i • g ⊥ + r • hp i ∈ G . Return ct #" x = (ct 0 , #" ct ∈ G ); • Decrypt(sk #" y , ct #" x ): Set ct #" x , #" y ← #" y , #" ct -hk #" y • b ∈ G.
Return log g ⊥ ct #" x , #" y . More precisely, if there exists an attacker A that has advantage ε A in breaking the s-IND-IPFE-CPA security of FE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the DDH assumption, such that ε A ≤ ε B .

Scheme Secure Against Adaptive Chosen-Plaintext Attacks

The following scheme can be obtained in two different ways: plugging the ElGamal public key encryption scheme into Construction 4.4.1, or plugging our key homomorphic projective hash function based on DDH into Construction 5.3.1. It is depicted on Figure 6.2. To satisfy Condition 1, we need to choose the efficiently recognizable subsets M y and M x of R so that the discrete logarithm of #" y , #" x • g ⊥ ∈ G is efficient to compute, for any #" y ∈ M y and #" x ∈ M x . This scheme can easily be extended to rely on any MDDH assumption by using instead projective hash functions defined in Section 6.3.1.2, however we stick to the instantiation based on DDH for simplicity.

• Let G be a cyclic group of prime order q, g ⊥ a generator of G.

• Setup(1 κ , 1 ) → (mpk, msk): Choose g $ ← G 2 . Set pp = (κ, , g). For i = 1, . . . , , set

hk i $ ← Z 2 q , hp i ← hk i • g ∈ G .
Return msk = # " hk ∈ (Z 2 q ) and mpk = # " hp ∈ G .

• KeyDer(msk, #" y ∈ Z q ) → sk #" y : Set hk #" y ← #" y , # " hk ∈ Z 2 q . Return sk #" y = hk #" y ∈ Z 2 q .

• Encrypt(mpk, #" x ∈ Z q ) → ct #" x : Pick r $ ← Z q and set b ← r • g ∈ G 2 . For i = 1, . . . , , set

ct i ← x i • g ⊥ + r • hp i ∈ G . Return ct #" x = (b, #" ct ∈ G ). • Decrypt(sk #" y , ct #" x ): Set ct #" x , #" y ← #" y , #" ct -hk #" y • b ∈ G.
Return log g ⊥ ct #" x , #" y .

Scheme Secure Against Chosen-Ciphertext Attacks

Let us now instantiate the framework for IND-TBIPFE-CCA secure tag-based inner-product functional encryption schemes with the DDH-based IPFE-CPA-friendly PHF defined in Section 6.3.1.1, and the DDH-based IPFE-CCA-friendly tag-based PHF defined in Section 6.3.2. We set R = Z q and M x = q (or any large enough integer). As for the IND-IPFE-CPA secure scheme in the previous section, we need to choose the efficiently recognizable subsets M y and M x of R so that the discrete logarithm of #" y , #" x • g ⊥ ∈ G is efficient to compute, for any #" y ∈ M y and #" x ∈ M x in order to satisfy Condition 2. The resulting construction is depicted on Figure 6.3 and can be easily extended to use any MDDH-based PHF defined in Section 6.3.2.

Applying Theorem 5.5.2, we immediately get the following security theorem. More precisely, if there exists an attacker A that has advantage ε A in breaking the IND-TBIPFE-CCA security of T BFE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the DDH assumption, such that

ε A ≤ 2 • ε B + 2 • q dec • q -ν .
In particular, setting ν = + 1, we have the following bound:

ε A ≤ 2 • ε B + 2 • q dec
q . We consider this setting of parameter for the comparison of the schemes.

Chapter 6 Instantiations based on the Decisional Diffie-Hellman Assumption • Let G be a cyclic group of prime order q, g ⊥ a generator of G.

• Setup(1 κ , 1 ) → (mpk, msk): Choose g $ ← G 2 . Set pp = (κ, , g). For i = 1, . . . , , set

hk i $ ← Z 2 q , hp i ← hk i • g ∈ G . hk † i $ ← Z 4×ν q , hp † i ← g 0 0 g • hk † i ∈ G 2×ν . Return msk = ( # " hk ∈ (Z 2 q ) , # " hk † ∈ (Z 4×ν q
) ) and mpk = (

# " hp ∈ G , # " hp † ∈ (G 2×ν ) ).
• KeyDer(msk, #" y ∈ Z q ) → sk #" y : Set

hk #" y ← #" y , # " hk ∈ Z 2 q , hk † #" y ← #" y , # " hk † ∈ Z 4×ν q . Return sk #" y = (hk #" y ∈ Z 2 q , hk † #" y ∈ Z 4×ν q ). • Encrypt(τ, mpk, #" x ∈ Z q ) → ct #" x : Pick r $ ← Z q and set b ← r • g ∈ G 2 . For i = 1, . . . , , set ct i ← x i • g ⊥ + r • hp i ∈ G , ct † i ← hp † i • ( r τ •r ) ∈ G ν . Return ct #" x = (b, #" ct ∈ G , #" ct † ∈ (G ν ) ).
• Decrypt(τ, sk #" y , ct #" x ): Check that #" y , Chapter 7

#" ct † = hk † #" y • b τ •b ; return ⊥ if it fails. Set ct #" x , #" y ← #" y , #" ct -hk #" y • b ∈ G. Return log g ⊥ ct #" x , #" y .

Instantiations based on the Decisional Composite Residuosity Assumption

In this chapter, we instantiate the generic constructions of inner-product functional encryption from key-homomorphic projective hash functions with concrete constructions based on the decisional composite residuosity assumption. We present two non-modular IPFE schemes reaching respectively IND-IPFE-CPA security (adaptive) and IND-TBIPFE-CCA security and compare their pros and cons in term of efficiency and security. These schemes solve the problem from which the schemes of Chapter 6 suffer: the decryption is very efficient. However, the downside is that the scheme has bigger keys and ciphertexts, because it cannot rely on elliptic curve cryptography, and requires huge integers to guarantee security. The fact that some computations are done over the integers also makes it hard to analyze the efficiency of the scheme. We also note that the schemes presented in this chapter are non-modular, which is also another downside.

The constructions, and proofs that the projective hash functions verify the correct properties are taken from our contribution [START_REF] Benhamouda | CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions[END_REF].

The Decisional Composite Residuosity Assumption and Subset Membership Problem

In this section, we recall the decisional composite residuosity (DCR) assumption and present a subset membership problem whose indistinguishability can be reduced to the DCR assumption, which will be used to construct key homomorphic projective hash functions and inner-product functional encryption schemes.

The Decisional Composite Residuosity Assumption

The DCR assumption was introduced to build public key encryption schemes [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. It is part of one of the two most important famillies of assumption for public key cryptography: assumptions based on the hardness of factorization, that started with the RSA cryposystem [START_REF] Rivest | A Method for Obtaining Digital Signature and Public-Key Cryptosystems[END_REF]. Indeed, if it is easy to factor big numbers, then the DCR assumption does not hold. However, we do not know any better attack on this assumption than factoring the modulus and recover the two primes that compose it. As with all other assumptions based on factoring, we will work in the ring Z N , where N is an RSA number, i.e., a product of two big prime numbers. We need to be careful here because Z N is not a field as was Z q in Chapter 6. However, it is very hard to find a number that do not have an inverse, in fact, it is as hard as finding the two prime factors of N .

The Decisional Composite Residuosity Assumption. Let N = pq be a product of two λ-bit random safe primes p = 2p + 1 and q = 2q + 1, where p and q are also primes and where λ is a function of the security parameter κ. The decisional composite residuosity assumption states that z and y N are computationally indistinguishable, where z and y are chosen uniformly at random from Z N 2 and the exponentiation is done modulu N 2 . We won't directly use this assumption but an assumption which is equivalent for our subset membership problem.

Subset Membership Problem Based on the Decisional Composite Residuosity Assumption

In order to improve the efficiency of our scheme, we will work in the ring Z N s+1 for some integer s instead of the ring Z N 2 . This change was introduced by Damgård and Jurik [START_REF] Damgård | A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[END_REF] to improve the asymptotic efficiency of the Pailler encryption scheme. Everything behaves the same way, but instead of having a message space of size N , we have message space N s , while still having an overhead of log(N ) bits for security reasons.

The second change we make in order to have a better inner-product functional encryption scheme at the end is using the group of signed quadratic residues [FS97; HK09; HKS13]. Basically, we change the group law in order to ensure that we are only dealing with quadratic numbers, and that it is efficient to check if a number is a square. This isn't the case when taking numbers in Z N , in fact it is even a cryptographic assumption: the quadratic residuosity (QR) assumption that is used for example to build public key encryption schemes [START_REF] Goldwasser | Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information[END_REF][START_REF] Goldwasser | Probabilistic Encryption[END_REF]. Using only squares ensures that the smallest subgroup of our field has a big order, because we removed both subgroup of order 2. Hence, when an element is uniform in a subgroup Chapter 7

7.1 The Decisional Composite Residuosity Assumption and Subset Membership Problem99 chosen by the adversary, it is still statistically impossible to guess its value beforehand. Signed Quadratic Residues. Let N = pq be a product of two λ-bit random safe primes p = 2p + 1 and q = 2q + 1, where p and q are also primes and where λ is a function of the security parameter κ and let N = p q . The order of the group Z * N of invertible elements in Z N is φ(N ) = 4N (here, φ is Euler's totient function). We denote by J N the subgroup of Z * N order 2N of elements from Z * N with Jacobi symbol 1. We also denote by QR N = {x : ∃y ∈ Z N , x = y 2 [N ]} the subgroup of J N of order N of quadratic residues modulo N . As N is a Blum integer (since p and q are both safe primes), -1 ∈ J N \ QR N , because it is not a square modulo p nor modulo q. We now write the elements of Z N as {-N -1 2 , . . . , N -1 2 }, and we define the group of signed quadratic residues modulo N

QR + N = {|x| : x ∈ QR N }, where the group operation • is defined through |x| • |y| = |xy|. As for any x ∈ QR N , -x ∈ J N \ QR N , |QR + N | = |QR N | = 1 2 |J N |, so QR + N = J + N , where J + N = {|x| : x ∈ J N } = J N / ± 1.
In particular, since the jacobi symbol of an element is efficiently computable, it is easy to verify if an element is in QR + N or not. We are now ready to define our subset membership problem.

DCR-Based Subset Membership Problem.

Let N = pq be a product of two λ-bit random safe primes p = 2p + 1 and q = 2q + 1, where p and q are also primes and where λ is a function of the security parameter κ, and let N = p q . Let s ≥ 1 be an integer parameter. Let us write

Z * N s+1 ∼ = G N s ⊕ G N ⊕ G 2 ⊕ T
, where ∼ = denotes group isomorphism, ⊕ is the direct sum or Cartesian product, G i are cyclic groups of order i, and T is the order-2 cyclic group generated by -1 mod N s+1 . As previously, let us represent the elements of Z N s+1 as {-(N s+1 -1)/2, . . . , (N s+1 -1)/2}. We define G = X = {|x| : ∃y ∈ Z * N s+1 s.t. x = y 2 } = J N s+1 ∩ {1, . . . , (N s+1 -1)/2} ∼ = G N s ⊕ G N . We will use additive notation for G in order to have notation closer to the ones used for the generic constructions: g 1 + g 2 = |g 1 g 2 |. Let g be a random generator of L ∼ = G N , that is a subgroup of X ; g can be thought of as a random 2N s -th residue. A witness w ∈ W = Z for b ∈ L is such that b = w • g. Finally, let g ⊥ be an arbitrary generator of the cyclic group G N s (for example g ⊥ = 1 + N ∈ Z N s+1 , where + here is the additive law of Z N s+1 ) and let L = L + g ⊥ . We set Λ = (N, s, g, g ⊥ ).

One cannot sample uniform witnesses as W = Z is infinite. We cannot set W = Z N , as computing N from Λ = (N, s, g) requires to factor N . Instead, we sample witnesses uniformly from S N := {0, . . . , N/4 -1}. Clearly, the statistical distance ∆(U (Z N ), U (S N )) = 1p q /(pq/4) = (2p + 2q + 1)/(pq) < 2(p + q)/(pq) < 4/ spf(N ). From this distribution over W, we can derive distributions over , L, and L = L + g ⊥ . The two latter distributions are statistically close to uniform.

This setting defines a subset membership problem, whose (L, L)-indistinguishability property can be proven under the decisional composite residuosity assumption. More precisely, we consider the DCR assumption for moduli that are product of safe primes; the DCR assumption then basically states that in the case s = 1, no probabilistic polynomial time adversary can distinguish between uniform elements of L and X . We note that the original assumption actually does not restrict the the elements to be of Jacobi symbol 1 nor square, but doing this restriction yields an equivalent assumption, since we can multiply element of Jacobi symbol -1 by an arbitrary N s -residue of Jacobi symbol -1, and as we are using the group of signed quadratic residues, we can go from a non square element to a square by multiplying it by -1. This is a classical variant of DCR, which is equivalent to the original DCR assumption [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF], assuming that safe primes are sufficiently dense (see, e.g., [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]). We have the following lemma, following [DJ01]: Lemma 7.1.1. If the DCR assumption holds, the above subset membership problem is (L, L)indistinguishable. More precisely, if there exists an adversary A that has advantage ε A in breaking (L, L)-indistinguishability, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking DCR, such that ε A ≤ 2s•ε B +8/ spf(N ).

Proof. We use an hybrid proof as in [START_REF] Damgård | A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[END_REF] using s hybrids. The term 8/ spf(N ) comes from the statistical distance between our distribution over X and L and the uniform distribution.

Projective Hash Functions Based on the Decisional Composite Residuosity Assumptions

We are now ready to present the projective hash function that we will use to construct inner-product functional encryption scheme. We start with the IPFE-CPA-friendly PHF, and then present the IPFE-CCA-friendly one.

IPFE-CPA-Friendly Projective Hash Function

We now define our IPFE-CPA-friendly projective hash function based on the DCR subset membership problem. It is a generalization of the PHF of Cramer and Shoup based on DCR in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] Let Λ = (N, s, g, g ⊥ ) be defined as in Section 7.1.2. We have:

G = X = J N s+1 ∩ {1, . . . , (N s+1 -1)/2} ∼ = G N s ⊕ G N , L = G N , and L = L + g ⊥ . The element
g is a generator of L, while g ⊥ is a generator of G N s . We recall that we use additive notation for the group G: g 1 + g 2 = |g 1 g 2 |, where elements of Z N s+1 are represented as {-(N s+1 -1)/2, . . . , (N s+1 -1)/2}. We define the DCR-based PHF as follows:

• hashkg(Λ) outputs hk $ ← {0, . . . , M N s+1 /4 } =: K * ⊆ Z =: K, where M is a positive integer and is a parameter of the scheme;

• projkg(hk) outputs hp ← hk • g ∈ G; • hash(hk, b) outputs H ← hk • b ∈ G =: Π; • projhash(hp, b, w) outputs pH ← hp • w ∈ G = Π.
When M = 2, this PHF corresponds to the one of Cramer and Shoup in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF].

We insist on the fact that the set of hashing keys is K = Z so that it is a group. However, hashkg only samples a hashing key from a finite subset K * of K.

Chapter 7

hk ⊥ (b) = N • (N -1 mod N s ) (< N N s < N s+1 /4) .
Then, the PHF described above is (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly.

Proof. Key homomorphism and strong diversity are proven similarly as in the DDH case, while translation indistinguishability follows from Lemma 2.1.2.

Key Homomorphism is straightforward.

Strong Diversity. Assume b ∈ L = L + g ⊥ , write b = wg + g ⊥ for w ∈ Z N . Since the space of projection keys is also a group and projkg is a group homomorphism, we can use Lemma 5.2.4. Hence, we just need to prove that projkg(hk ⊥ (b)) = 0 and hash(hk

⊥ (b), b) = g ⊥ .
The first equality follows from the facts that

projkg(hk ⊥ (b)) = hk ⊥ (b) • g = N • (N -1 mod N s ) • g
and that g has order N . For the second equality, we remark that

hash(hk ⊥ (b), b) = hk ⊥ (b) • b = N • (N -1 mod N s ) • w • g + N • (N -1 mod N s ) • g ⊥ . Since g has order N , as before N • (N -1 mod N s ) • w • g = 0. Furthermore, since g ⊥ has order N s , N • (N -1 mod N s ) • g ⊥ = (N • N -1 mod N s ) • g ⊥ = g ⊥ . Translation Indistinguishability. For any x ∈ {-M x , . . . , M x }, we have ∆(hashkg(Λ), hashkg(Λ) + x • hk ⊥ (b)) = |x • hk ⊥ (b)| |K * | ≤ M x • N N s M N s+1 /4 < M x N/4 M N/4 = M x M = ε ti .
This concludes the proof.

Interestingly, because of our choice of L, hk ⊥ (b) does not depend on b. Note also that for M < M x /ε ti , this PHF is still key-homomorphic and strongly diverse, but might lack the translation indistinguishability property that is necessary for our application.

IPFE-CCA-Friendly Projective Hash Function

We now define our IPFE-CCA-friendly projective hash function based on the DCR subset membership problem. As for the DDH-based IPFE-CCA-friendly projective hash function of Section 6.3.2, we use a PHF that is basically ν copies in parallel of a 2-universal PHF based on DCR. Once again, let Λ = (N, s, g, g ⊥ ) be defined as in Section 7.1.2. We have:

G = X = J N s+1 ∩ {1, . . . , (N s+1 -1)/2} ∼ = G N s ⊕ G N , L = G N , and L = L + g ⊥ .
The element g is a generator of L, while g ⊥ is a generator of G N s . We recall that we use additive notation for the group G:

g 1 + g 2 = |g 1 g 2 |,
where elements of Z N s+1 are represented as {-(N s+1 -1)/2, . . . , (N s+1 -1)/2}. We define a PHF as follows:

• Let N = pq be a product of two λ-bit random safe primes. We suppose that Condition 1 is satisfied. Let u $ ← Z * N s+1 , g ← u 2N s , and g ⊥ ← 1 + N .

• Setup(1 κ , 1 ) → (mpk, msk): Set pp = (κ, , N, g). For i = 1, . . . , , j = 1, 2, and k = 1, . . . , ν, set

hk i $ ← {0, . . . , M N s+1 /4 } ∈ Z , hp i ← g hk i ∈ G , hk † k,i,j $ ← {0, . . . , νM † N s+1 /2 } ∈ Z , hp † k,i,j ← g hk † k,i,j ∈ G . Return msk = (hk ∈ Z , # " hk † ∈ (Z 2×ν ) ) and mpk = (hp ∈ G , # " hp † ∈ (G 2×ν ) ).
• KeyDer(msk, #" y ∈ M y ) → sk #" y : Set

hk #" y ← #" y , # " hk ∈ Z , hk † #" y ← #" y , # " hk † ∈ Z 2×ν ,
where the computation is done over Z. Return msk #" y = (hk #" y ∈ Z, hk † #" y ∈ Z 2×ν ).

• Encrypt(τ, mpk, #" x ∈ M x ) → ct #" x : Sample r $ ← {0, . . . , N/4 } and set b ← g r . Return (msk, mpk). For i = 1, . . . , and k = 1, . . . , ν, set

ct i ← (1 + N ) x i • hp r i ∈ G , ct † k,i = g r•hp † i,k,1 +r•τ •hp † i,k,2 ∈ G . Return ct #" x = (b, #" ct ∈ G , #" ct † ∈ (G ν ) ). • Decrypt(τ, sk #" y , ct #" x ): Check that i=1 y i • ct † i,k = b hk † #" y ,1,k +τ •hk † #" y ,2,k for k = 1, . . . , ν; return ⊥ if any check fails. Set ct #" x , #" y ← i=1 ct y i i /b hk #" y .
Return ct #" x , #" y -1 N mod N s (using the representation in {-N s /2 , . . . , N s /2 }).

≥ log spf(N ) (2 • q dec • |∆M x |) =
O(poly(κ)), we have the following security bound:

ε A ≤ 4s • ε B + 16/ spf(N ) + 4 • 2 -κ .
We note that in general, for security reasons, spf(N ) has to be a really big integer. In this case, one think of ν as a really small constant, i.e., 1, 2, or 3 to be really safe, depending on the message space wanted, and on the number of queries the adversary could potentially make.

Similarly to what happens in our DCR-based IND-IPFE-CPA secure instantiation in Section 7.3.1, although there is an exponential loss in the security reduction of Theorem 5.5.2, we emphasize that there is no exponential loss using these parameters: the security loss is compensated by these well-chosen parameters.

The Learning With Errors Assumption

In this section, we recall the learning with errors (LWE) assumption and discuss its pros and cons.

The Learning With Errors Assumption

A quantum computer would improve efficiency of many known and used algorithms. This includes the algorithms that factors big numbers and find discrete logarithm. These problems becoming efficiently solvable would be a huge issue for public key cryptography, as most of the public key crypto is based on the hardness of either discrete logarithm or factorization. Recently, a lot of work is being put in trying to find alternative encryption schemes that would be easily implemented on classical computer, but would remain secure even if someone tries to break it with a quantum computer. The most trendy assumption in this case is the learning with errors assumption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Informally, it states that giving noisy inner-products with random vectors completely hide a secret vector s and looks uniformly random. This easily yields a secret key encryption scheme that is directly converted into a public key encryption scheme using its additive homomorphic properties. Its hardness is related to lattice problems, hence the nickname of lattice-based cryptography. Those problems have been studied for years, which is comforting for a cryptographic assumption. However, a lot of recent works tend to improve the attacks against lattice-based cryptography, in particular when the parameters are overstretched. Let us first define this assumption, before discussing its parameters.

Learning With Errors. Let n, q be integer parameters. For any noise distribution χ on Z q , and vector s ∈ Z n q , the oracle LWE q,n,χ (s) samples a fresh random n-dimensional vector a ← Z n q , as well as noise e ← χ, and returns (a, a, s + e). The LWE assumption states that LWE q,n,χ (s) is computationally indistinguishable from the uniform distribution on Z q .

We would like to point out that in this assumption, the distribution (either LWE distribution or uniform distribution) is given as an oracle, and can be called any polynomial number of times. This is why some works prefer the notation with matrices and vectors. Some formulations also work in the torus T = R/Z of reals modulo 1. This in fact is equivalent to considering different noise distributions. In this work, we will focus on the noise distribution χ σ , a discrete Gaussian over Z centered on 0 with standard deviation σ.

It makes no doubt that the assumption has now been adopted as a standard, and has been use to create encryption schemes [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], key exchanges [DXL12; Pei14; ADPS15; ADPS16], identity-based encryption [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF], bi-deniable encryption [START_REF] Adam | Bi-Deniable Public-Key Encryption[END_REF], and even the first instances of fully homomorphic encryption [BV11a; GSW13] (The very first construction of FHE [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] is not based on LWE, but on a similar assumption), which allows to compute on encrypted data without learning anything about it.

Hardness Evidences

Since its introduction in machine learning, this problem has seen a lot of interest as a cryptographic assumption. There are two main reasons to this success: the LWE assumption allowed the construction of primitives that have been the holy grail of cryptography for decades: fully homomorphic encryption; the second reason is because it is believed to be hard to solve for quantum computers. Let us first talk about the general hardness of LWE, and then talk about the importance of the parameters and their impact on the hardness of the assumption.

Reductions from Lattice Problems. Regev showed in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] that there is a quantum reduction from the approximate shortest vector problem (GAP-SVP), a lattice problem believed to be hard, even for quantum computers, to LWE that is preserving the dimension n if the standard deviation σ is greater than 2 √ n. Following that reductions, several works tried to dequantize the reduction, like the one of Peikert [START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract[END_REF] and more recently a fully classical reduction has been proven in [START_REF] Brakerski | Classical hardness of learning with errors[END_REF]. Unfortunately, this reduction is not dimension preserving, making this result incomparable to Regev's one.

Modulus-to-Noise Ratio. When measuring the hardness of LWE, the two main parameters to consider are the dimension n of the vectors, and the modulus-to-noise ratio q/σ. The higher the dimension is, the harder it is to distinguish between the LWE q,n,χ (s) distribution, and the uniform distribution. Usually, the dimension n = O(κ) is of the same order of magnitude as the security parameter κ. On the other hand, increasing the modulus-to-noise ratio q/σ decreases the difficulty of the problem. This is why in general it is better to aim at having a polynomial ratio q/σ = O(poly(κ)). Moreover, while there is no known attacks on using a superpolynomial modulus-to-noise ratio, there is less evidences of its hardness.

Public Key Encryption Schemes Secure under the Learning With Error Assumption

In this section, we present a variant of the original public key encryption scheme presented in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and show that it can be used to instantiate Construction 4.3.1 and Construction 4.4.1. We also discuss the choice of parameters needed for the needed properties to be verified.

Regev Public Key Encryption Scheme

Choosing the Parameters. As in [PW08; KTX08], we use encryptions of messages in Z p instead of bits in the case of the original encryption scheme. We let the message space be M = {0, . . . , M x } ⊆ Z p for some integer M x , n be an integer related to the security parameter, p be the modulus of the message space (for the IPFE schemes, we will require that p > M x M y , which is big enough for the inner-product t not wrap around the modulus), q > p be the modulus for the ciphertext and keys. Our public keys and ciphertexts consist of matrices and vectors over Z q . For every v ∈ Z p (i.e., one entry of a message vector), define the "center" for v as t(v) = v • q p ∈ Z q . Let χ σ denote an integer gaussian distribution over Z q with standard deviation σ: χ σ (x) = ρσ(x) ρσ(Z) . Let m = m(n), and σ = σ(n) and σ = σ (n) be positive real Gaussian parameters. The following relations between parameters are required for correctness and security of the public key encryption scheme:

1. m > (1 + )(n + 1) log q; 2. σq > 2 √ n; 3. q 2p > σ √ 2mκ.
The first one is needed to extract the computational entropy contained in the randomness of the encryption with the leftover hash lemma and is used in the security proof. The second one is required for the hardness of the underlying LWE assumption. And the last one is required for correctness, to ensure that the noise doesn't alter the message. Other conditions are required for the additional properties. We will state those conditions when proving that the schemes satisfy the property, and we will recall all needed conditions when showing the concrete IPFE constructions. All operations are performed over Z q .

Construction 8.2.1 (Regev PKE Scheme). We recall the Regev public-key encryption scheme E = (Setup, Encrypt, Decrypt):

• Setup(1 κ ) → (pp, sk, pk). On input security parameter κ samples A

$ ← Z m×n q , s $ ← Z n q
, and e $ ← χ m σ , computes pk ← As + e ∈ Z m q , and outputs public parameters pp = (A, χ σ ), secret key sk = s, and public key pk;

• Encrypt(pp, pk, m) → ct. On input public parameter pp, public key pk, and plaintext m, samples r

$ ← {0, 1} m , computes ct 0 ← A r ∈ Z n q , ct 1 ← pk, r + t(x) ∈ Z q ,
where t(x) = x • q/p ∈ Z q , and outputs ciphertext ct = (ct 0 , ct 1 );

• Decrypt(pp, sk, ct) → m or ⊥. On input public parameters pp, secret key sk, and ciphertext ct computes d = ct 1ct 0 , s , and returns the plaintext x ∈ M , where x is such that dt(x) ∈ Z q is closest to 0 mod q.

We note that the scheme might be slightly optimized by sampling r from {-1, 0, 1} m instead of {0, 1} m , increasing the computational entropy of a ciphertext without increasing the noise at decryption time, but we prefer to keep the latter set for simplicity and to stay closer to the original scheme.

Correctness. In the decryption algorithm, d = t(x) + e, vecr , which means that the algorithm is correct if e, r is smaller than q 2p . e, r is a sum of m discrete Gaussians with standard deviation σ so it is subgaussian with standard deviation at most σ √ m, and hence has magnitude less than σ √ 2mκ with overwhelming probability. Our setting of parameters thus ensures that the decryption is correct.

Additional Properties of Regev Public Key Encryption Scheme

We now go through the additional properties defined in Section 4.2, and show that the Regev encryption scheme defined in Construction 8.2.1 satisfies these properties.

Structure. As required, we can split up the Setup algoritm into two parts:

• SKGen(1 κ ) on input the security parameter and samples s from Z n q and outputs sk = s; Chapter 8 8.2 Public Key Encryption Schemes Secure under the Learning With Error Assumption111

• PKGen(sk, τ ) on input secret key s, parameters τ , and samples e $ ← χ m σ and computes pk ← As + e ∈ Z m q . Then the algorithm outputs pk. Notice that, if τ describes an error distribution then e is sampled from this latter distribution.

As can we do with the Encrypt algorithm:

• C(r) on input a random vector r ∈ {0, 1} m outputs ct 0 ← A r;

• E(pk, x; r) on input public key pk, message x and random vector r, returns ct 1 ← pk, r + t(x).

Semantic Security. Proof of the semantic security of this encryption scheme can be found in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. It relies on the LWE assumption and on the leftover hash lemma, which is a statistical argument. It proceeds in two steps with a hybrid argument: first, we replace the public key by a uniformly random vector. This is indistinguishable from the security game thanks to the LWE assumption. Then we replace the ciphertext by a uniform vector. This is statistically indistinguishable thanks to the leftover hash lemma.

Then we conclude by observing that the view is now independent of the challenge bit.

Linear Key Homomorphism. The first property comes from the fact that secret keys are elements uniformly sampled from the group Z n q , so the secret key space is stable under addition. Moreover, α i s i is a correct secret key for α i (As i + e i ) as long as α i e i remains small, which is true for small values of α i . This is taken into account in our setting of parameters. The scheme will remain correct as long as σ verifies the correctness condition, where σ = σ #" α is a bound on the standard deviation of the new error term.

Linear Ciphertext Homomorphism under Shared Randomness. It is easy to verify that:

pk 1 , r + t(x 1 ) + pk 2 , r + t(x 2 ) = pk 1 + pk 2 , r + t(x 1 + x 2 ),
by the definition of the function t.

-Public-Key Reproducibility. To show that scheme of Construction 8.2.1 has -public-key-reproducibility, for any fixed constant , it is sufficient to show that there are error distributions with standard deviations σ, σ ,

(σ i ) i∈[ ] such that Exp -pk-rep-0 E,κ (A ) is indistinguishable from Exp -pk-rep-1 E,κ (
A ). The idea is that when taking a discrete Gaussian error e and multiplying it by a vector #" α, we obtain correlated Gaussians, so in order to obtain a spherical Gaussian distribution in the end, we add correctly correlated errors in order to unskew the distribution. However, we can only increase the noise by adding something, so we require that the final error distribution used in the scheme has standard deviation σ ≥

(1 + B √ )σ ,
) i∈[ ] ) $ ← M(1 λ ) pk $ ← Z m q , u $ ← Z q pk i = Ask i + e i , for e i ← χ m σ i r $ ← {0, 1} m ct 0 $ ← Z m q , ct = u + t(a) ct i = α i ct + E ((sk i , e i ), x i , ct 0 ; r) Return (pk, (α i , pk i , sk i ) i∈[ ] , ct 0 , (ct i ) i∈[ ] ) proc Finalize(b') Return (b = b)
Let us define the following random variables:

• X is the random variable that takes uniform values of the form (A ∈ Z m×n q , b ∈ Z n q ). • W is the random variable that takes uniform values of the form r ∈ {0, 1} m .

• I is the random variable that takes values of the form ( e 1 , r , . . . , e , r ), where

e i ← χ m , r ∈ {0, 1} m .
Then, by Lemma 2.4.7, we have that H∞

(W |I) ≥ H ∞ (W ) -( -1) log q = m - ( -1) log q. Now, notice that H X (W ) = H (A,b) (r) = (A r, b, r
) is a universal hash function and by applying the generalized leftover hash lemma (Lemma 2.4.8), we have that:

∆((H X (W ), X, I), (U, X, I)) ≤ 1 2 2 -H∞(W |I) q n+1 .
Then, if m ≥ (n + + 1) log q + 2 log 1 + Ω(1), the statistical distance between the two views is at most .

Hybrid H 5 : This is like H 4 except that r is replaced by another random value r .

proc Initialize(κ, M)

(a, (α i , x i , sk i ) i∈[ ] ) $ ← M(1 λ ) pk $ ← Z m q , u $ ← Z q pk i = Ask i + e i , for e i ← χ m σ i r $ ← {0, 1} m ct 0 $ ← Z m
q , ct = u + t(a) ct i = α i ct+ E ((sk i , e i ), x i , ct 0 ; r ) Return (pk, (α i , pk i , sk i ) i∈[ ] , ct 0 , (ct i ) The change from H 6 to H 5 is the same as the change from H 3 to H 4 , except that no information about r is leaked. So Lemma 2.4.7 gives us that the statistical distance between the two views is at most . Once again, the hardness of LWE guarantees that pk looks pseudo-random to the adversary.

We would like to note that reusing the same randomness for different public keys for packing messages was already shown to be secure in [START_REF] Peikert | A Framework for Efficient and Composable Oblivious Transfer[END_REF], but the requirements we made in the generic constructions are stronger.

We are now ready to use this encryption scheme to construct inner-product functional encryption schemes.

Inner-Product Functional Encryption Schemes Based on the Learning With Errors Assumption

In this section, we present the two schemes secure under the LWE assumption obtained by plugging Regev public key encryption scheme described in the previous section in Construction 4.3.1 and Construction 4.4.1. The first one reaches selective security against chosen-plaintext attacks, while the second one reaches adaptive security. The price to pay for adaptivity in this case is a bit heavy, because we need to rely on a stronger assumption where the ratio between the modulus and the standard deviation of the error is superpolynomial. We would like to point out that for the case of adaptive security, [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] reaches better parameter than us and can use a polynomial modulus-to-noise ratio at the price of the genericity of the framework. The main difference between their construction and ours is that they base their IPFE scheme on the Dual Regev public key encryption scheme, which is the same as the one we presented, but interverting the roles of the secret key and the encryption randomness. Then, they use a more subtle statistical argument to conclude their proof, instead of our argument that switches secret keys to change the challenge message.

As the constructions presented in Section 7.3, our two IPFE schemes secure under the LWE assumption have efficient decryption, unlike the schemes of Section 6.4, but suffer the same downside: they are non-modular. We provide a comparison of those two schemes in Table 8.1, where we present the trade-offs they offer between security and efficiency. We note that no construction from projective hash functions is given in this chapter. The main reason is because we don't currently know how to build PHFs with the required properties for reaching IND-IPFE-CCA security. There have been some proposition of projective hash functions from LWE [KV09; BCDP13] that we might be able to use to construct adaptive IND-IPFE-CPA secure scheme, but we felt that the construction from public key encryption was conceptually simpler. The complexity of building PHFs based on lattices already shows up when trying to define a language for your words: the set of ciphertexts that are output by encrypting 0 is different to the set of ciphertexts that decrypts to 0. That is because the decryption must be correct for all ciphertexts returned by encrypt, and adding a really small noise to this ciphertext shouldn't change the decryption value.

Scheme Selectively Secure Against Chosen-Plaintext Attacks

The first scheme is the less secure one. However, it has a pretty good efficiency compared to other schemes that are based on lattices, like fully homomorphic encryption or attribute-based encryption. All operations used are pretty fast, the main downside for the efficiency is that the vectors and matrices can be huge depending on the choice of parameters. If the message space needs to be big, we recommend using schemes based on the DCR assumption, because the message space is set by the security parameter and is very big. One noticeable advantage of this scheme compared to those based on other assumptions is that it is resistant against quantum attacks. We assume that the conditions required are verified:

1. m ≥ (n + + 1) log q + 2 log 1 + Ω(1) ; The sizes are given as number of elements in Z q . We note that the second element of the secret key for the IND-IPFE-CPA secure scheme is conceptually an integer, but we count it as 1 element in Z q since it is smaller than q with our setting of parameters.

5. q 2p > σM y √ 2 mκ .

Our s-IND-IPFE-CPA secure inner-product functional encryption scheme based on LWE is depicted on Figure 8.1.

Correctness. The proof of correctness follows the same path as the one for the basic public key encryption scheme. This time, the final error has standard deviation at most σM y √ m . The correctness then follows from the setting of parameters. Remark 8.3.1 (Optimization of the message space.). It is possible to gain some efficiency and reduce the parameters size by reducing the bound M y on each coordinate of the key • Let n, m, p, q be integer parameters and σ a positive real parameter such that they verify the conditions required. Let A $ ← Z m×n q be a uniformly random matrix.

• Setup(1 κ , 1 ) → (mpk, msk): Set pp = (κ, , n, m, p, q, A). For i = 1, . . . , , set

(s i , e i ) $ ← Z n q × χ m σ , b i ← As i + e i ∈ Z m q .
Return msk = (s i ) i∈[ ] and mpk = (b i ) i∈[ ] ;

• KeyDer(msk, y ∈ M y ) → sk #" y : Return

sk y ← i∈[ ] y i s i ∈ Z n q ;
• Encrypt(mpk, x ∈ M x ) → ct x : Pick r $ ← {0, 1} m and set ct 0 ← A r ∈ Z n q .

For i = 1, . . . , , set

ct i ← b i r + t(x i ) ∈ Z q ,
where t(v) = v • q/p ∈ Z q . Return ct x = (ct 0 , (ct i ) i∈[ ] );

• Decrypt(sk y , ct x ): Set ct x,y ←

i∈[ ] y i ct ict 0 sk y ∈ Z q .

Return the plaintext m, where m is such that dt(m) ∈ Z q is closest to 0 mod q. In order to achieve this, we decompose each coordinate of y in binary and for each coordinate of x we encrypt it multiplied by each of the powers of two. Then the inner-product will reconstruct y and the scheme will be correct. This makes grow by log M y and decreases M y to 1, which greatly improves on the correctness condition, allowing us to use better parameters.

A bit more formally, the new scheme consists in writing y i = j∈{0,...,γ} 2 j y i,j for each coordinate y i of y, where γ = log M y , and use the IPFE schemes replacing vectors: y → (y i,j ) i∈ ,j∈{0,...,γ} , x → (2 j x i ) i∈ ,j∈{0,...,γ} .

It is easy to see that i∈ ,j∈{0,...,γ} y i,j 2 j x i = i∈ ,j∈{0,...,γ} y i x i = x, y .

Security.

Chapter 8

Scheme Adaptively Secure Against Chosen-Plaintext Attacks

Our second scheme reaches adaptive security, which usually is a hard problem when dealing with lattice-based cryptography, because of the noisy nature of the schemes. It is more costly than the previous scheme that was only selectively secure, but if adaptive security is a necessity, it is still more efficient than using the previous scheme and increasing the security paramater to do complexity leveraging. We assume that the conditions required are verified:

1. m ≥ (n + + 2) log q + 2 log 1 + Ω(1) ; Correctness. The proof of correctness follows the same path as the one for the basic public key encryption scheme. This time, the final error has standard deviation at most σM y √ m + σ T M y , which is less than σM 2 y √ m because of the relation between σ and σ . The correctness then follows from the setting of parameters. Remark 8.3.1 still applies in this case, giving the same improvements with the same construction.

Security.

By using Theorem 4.4.2, we immediately get the following security theorem for our construction. More precisely, if there exists an attacker A that has advantage ε A in breaking the IND-IPFE-CPA security of FE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the LWE assumption, such that ε A ≤ ε B .

• Let n, m, p, q be integer parameters and σ a positive real parameter such that they verify the conditions required. Let A $ ← Z m×n q be a uniformly random matrix.

• Setup(1 κ , 1 ) → (mpk, msk): Set pp = (κ, , n, m, p, q, A), and sample (s 0 , e 0 ) $ ← Z n q × χ m γ 0 , b 0 ← As 0 + e 0 ∈ Z m q . For i = 1, . . . , , set (t i , s i , e i ) $ ← {0, . . . , T } × Z n q × χ m σ , b i ← A(t i • s 0 + s i ) + e i ∈ Z m q . Return msk = (s i , t i ) i∈[ ] and mpk = (b 0 , b i ) i∈[ ] ;

• KeyDer(msk, y ∈ M y ) → sk #" y : Set

s y ← i∈[ ] y i s i ∈ Z n q , t y ← i∈[ ] y i t i ∈ Z .
Return sk y = (s y , t y )

• Encrypt(mpk, x ∈ M x ) → ct x : Pick r $ ← {0, 1} m and set ct 0 ← A r ∈ Z n q , ct 1 ← b 0 r ∈ Z q .

For i = 1, . . . , , set ct 2,i ← b i r + t(x i ) ∈ Z q , where t(v) = v • q/p ∈ Z q . Return ct x = (ct 0 , ct 1 , (ct 2,i ) i∈[ ] );

• Decrypt(sk y , ct x ): Set ct x,y ←

i∈[ ] y i ct 2,it y ct 1ct 0 sk y ∈ Z q .

Return the plaintext m, where m is such that dt(m) ∈ Z q is closest to 0 mod q. Chapter 9

Conclusion and Open Questions

Conclusion

In this thesis, we introduced the notion of inner-product functional encryption (IPFE) which is the simplest non-trivial example of functional encryption that allows partial decryption of the plaintext. IPFE finds many theoretical and practical applications, and can be built efficiently from standard assumption.

We analyzed the different notions of security for IPFE, and showed how to generically build a partial function hiding secret key IPFE scheme from a standard public key modular IPFE scheme. This result can find some nice direct applications, and can also be used to build a secret key IPFE that is function hiding against bounded collusions of adversaries.

We presented 4 generic constructions based on 2 different albeit similar frameworks: constructions from public key encryption and from projective hash functions. The first framework is a bit more general as it encompasses some lattice-based IPFE schemes, while the second is more powerful as it allows the construction of schemes secure against chosen-ciphertext attacks, at the cost of efficiency.

We proposed 3 instantiations based on the decisional Diffie-Hellman assumption. All of them suffer the same drawback of having inefficient decryption restricting its input to polynomial size. However, the schemes are very efficient and simple, and compute modular inner-products. One of the schemes is secure against chosen-ciphertext attacks.

We also proposed 2 instantiations based on the decisional composite residuosity in order to avoid the problem of inefficient decryption. The sizes of the ciphertexts are larger than the constructions based on DDH, but the message space is flexible, and these schemes have very good asymptotical efficiency for very large message spaces. One of these schemes is also secure against chosen-ciphertext attacks, with a lower incremental cost than the scheme based on DDH.

Lastly, we proposed 2 instantiations based on the learning with errors assumptions. Those also avoid the problem of inefficient decryption, but the security against adaptive adversary is costly compared to the schemes based on the other assumptions. However, this scheme -121 -Chapter 9 Conclusion and Open Questions is really interesting because it is resistant against attacks from quantum computers, and it might be used in conjunction with other lattice-based tools in order to create more powerful primitives.

Open Questions

Here, I give a few open problems and directions that might be interesting for future works. The first question is also the most obvious. Question 9.1. Can we build a modular inner-product functional encryption with efficient decryption and stateless algorithms?

This would combine the best of all possible worlds. But interestingly enough, all our constructions have some drawbacks that cannot make them fit the nice definition of IPFE.

Question 9.2. Can we build an inner-product functional encryption secure against chosenciphertext attacks under the learning with errors assumption?

As noted previously, attempts at building projective hash functions from lattices don't give primitives powerful enough to build CCA secure schemes. However, there are some instances of lattice-based CCA schemes using different approaches. This approach is different than the one that tries to build functional encryption for all circuits: instead of picking a problem and trying to solve it at all cost, we take one tool and see what we can get from it. Our work is partly based on this question. Partial function hiding is another example of trying to squeeze every drop we can out of the simplest standard assumptions.

Question 9.5. How expressive can we make functional encryption using standard assumptions?

We know that using pairings, we can increase the range of possibilities to bilinear functions, or function hiding, or multi-inputs. On the other hand, recent works show that it is plausible that multilinear map with a degree slightly bigger than 2 would imply functional encryption for all circuits, and indistinguishability obfuscation. So it would seem like we've reached the maximum we can without reaching functional encryption for all circuits. There is still room for improvement, for example one could try and build functional encryption for some randomized functionality.

124

Notation

Notation

General Mathematical Notations

N

The set of natural numbers

Z

The set of integers

R

The set of reals log

The base-2 logarithm ln

The natural logarithm [n] The numbers from 1 to n #" x , x A (column) vector

A A matrix

Abstract

Functional encryption is an emerging framework in which a master authority can distribute keys that allow some computation over encrypted data in a controlled manner. The trend on this topic is to try to build schemes that are as expressive possible, i.e., functional encryption that supports any circuit evaluation. These results are at the cost of efficiency and security. They rely on recent, not very well studied assumptions, and no construction is close to being practical. The goal of this thesis is to attack this challenge from a different angle: we try to build the most expressive functional encryption scheme we can get from standard assumption, while keeping the constructions simple and efficient.

To this end, we introduce the notion of functional encryption for inner-product evaluations, where plaintexts are vectors x, and the trusted authority delivers keys for vectors y that allow the evaluation of the inner-product x, y . This functionality already offers some direct applications, and it can also be used for theoretical constructions, as inner-product is a widely used operation. Finally, we present two generic frameworks to construct inner-product functional encryption schemes, as well as some concrete instantiations whose security relies on standard assumptions. We also compare their pros and cons.

Lemma 2 .

 2 1.1. Let S 1 and S 2 be two finite sets.If S 1 ⊆ S 2 , we have ∆(U (S 1 ), U (S 2 )) = 1 -|S 1 |/|S 2 |. In particular, if |S 2 | = (1 + 1/t) • |S 1 | for some positive integer t, then ∆(U (S 1 ), U (S 2 )) = 1/(t + 1). Proof. ∆(U (S 1 ), U (S 2 )) = 1 2 (|S 2 \ S 1 |/|S 2 | + |S 1 | • (1/|S 1 | -1/|S 2 |)) = 1 -|S 1 |/|S 2 |.Lemma 2.1.2. Let S ⊆ Z be an interval and t be an integer. Then ∆(U (S), U (S + t)) = |t|/|S|.

Figure 3 . 2 :

 32 Figure 3.2: Illustration of the IND-IPFE-CPA security game. Adversary wins if (b = b) ∧ ∀y, x * 0 , y = x * 1 , y .

Figure 3 . 4 :

 34 Figure 3.4: Game Exp s-ind-ipfe-cpa-b F E,κ

Figure 3 . 5 :

 35 Figure 3.5: Game Exp na-sim-ipfe-b F E,κ (A , S ) define NA-SIM security of FE. The procedure Key-Der can only be invoked before invoking Encrypt.

Chapter 3 3. 3 Theorem 3 . 2 . 9 .

 33329 Indistinguishability under Chosen-Ciphertext Attack 27 Let FE be any inner-product functional encryption scheme. If FE is NA-SIM secure and supports key delegation, then it is IND-IPFE-CPA secure.

Figure 3 . 6 :

 36 Figure 3.6: Illustration of the IND-IPFE-CCA security game. Adversary wins if (b = b) ∧ ∀y, x * 0 , y = x * 1 , y . these definitions are equivalent to us. Noticing this, we chose to prove security of our schemes in the one time key model, where a new secret key is generated for each decryption query. We will present a generic construction of IND-IPFE-CCA secure schemes in Chapter 5. In order to lighten the notations in this future construction, we define in this section the notion of tag-based inner product functional encryption, and we show how to convert a IND-TBIPFE-CCA secure scheme into a tagless IND-IPFE-CCA secure scheme. In order to emphasize the difference between IND-IPFE-CCA security and IND-IPFE-CPA security, we present on Figure 3.6 the Figure 3.2 updated with the new decryption oracle. Definition 3.3.1 (Indistinguishability against Chosen-Ciphertext Attacks). For an innerproduct functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define security against chosen-ciphertext attacks (IND-IPFE-CCA security) via the security game depicted on Figure 3.7: we define the advantage of an adversary A to be

  and σ $ ← OT S.Sign(sk, ct x ) and outputs ciphertext ct x = (ct x , vk, σ);• Decrypt(pp , sk y , ct x ) → m or ⊥.On input public parameters pp, user secret key sk y , and ciphertext ct x , verifies that OT S.Verify(vk, ct x ) and returns ⊥ if it fails. Otherwise, computes τ ← H k (vk) and m ← FE.Decrypt(pp, τ, sk y , ct x ) and outputs message m.

Correctness.

  For all (mpk, msk) $ ← Setup(1 κ , 1 ), all y ∈ M y and x ∈ M x , for sk y $ ← KeyDer(msk, y) and ct $ ← Encrypt(mpk, x), we have that Decrypt(mpk, ct, sk y ) = E.Decrypt(sk y , (ct 0 , i∈[ ]

Figure 4 .Definition 4 . 3 . 2 (Figure 4 . 3 :

 443243 Figure 4.3: Illustration for randomness reuse. There are two paths to compute the second part of the ciphertext ct 1 . The left path is used in the real scheme: the encryption randomness is used together with the public key. The right path is only used in the proof: the encryption randomness is not needed, it is sufficient to have the first part of the ciphertext ct 0 = C(r) and the secret key.

Theorem 4 . 3 . 3 .

 433 Let E be a public-key encryption scheme with the structural properties defined in Section 4.2.1, and let FE be the functional encryption scheme for the inner-product functionality obtained by applying Construction 4.3.1 to E. If E is s-IND-CPA, linear-key homomorphic, linear-ciphertext homomorphic under shared randomness, and remains secure under randomness-reuse then FE is s-IND-IPFE-CPA.

  Eventually, this shows that ε is bounded by the best advantage one can get against s-IND-IPFE-CPA of E. Hence, taking the maximal values, the best advantage one can get against s-IND-IPFE-CPA of FE is bounded by the best advantage one can get against s-IND-IPFE-CPA of E.

Theorem 4 . 3 . 5 .

 435 Let E be a public-key encryption scheme with the structural properties defined in Section 4.2.1, and let FE be the functional encryption scheme for the innerproduct functionality obtained by applying Construction 4.3.1 to E. If E is s-IND-CPA, linear-key homomorphic, linear-ciphertext homomorphic under shared randomness, -publickey-reproducible, and -ciphertext-reproducible then FE is s-IND-IPFE-CPA.

Theorem 4 . 4 . 2 .←

 442 Let E be a public-key encryption scheme with the structural properties defined in Section 4.2.1, and let FE be the functional encryption scheme for the inner-product functionality obtained by applying Construction 4.4.1 to E. If E is s-IND-CPA, linearkey homomorphic, linear-ciphertext homomorphic under shared randomness, -public-keyreproducible, and -ciphertext-reproducible with coefficients α i ∈ T , then FE is IND-IPFE-CPA. Proof. We prove security via a sequence of hybrid experiments, and then we show they are indistinguishable. The techniques used to switch public keys and ciphertext values with reproducibility properties closely follows the proof of Theorem 4.3.5. Hybrid H 1 : This is the IND-IPFE-CPA game: KeyDer(msk, y) Return sk y proc Encrypt(x 0 , x 1 ) Ct * $ ← Encrypt(mpk, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)

Figure 5 Figure 5 . 2 :

 552 Figure 5.1: A zero knowledge proof using projective hash functions. w is a witness that b is in the language. In red is Alice's view, and in blue is Bob's view. Green means that Alice and Bob check that they have the same value.

Figure 5 . 4 :

 54 Figure 5.4: Construction of Inner-Product Functional Encryption from Key HomomorphicProjective Hash Function. This illustration is a copy of Figure3.1, replacing the variables by their values in our construction. The correctness follows from the key homomorphism and the correctness of the projective hash function.

5 5. 3

 53 that a probabilistic polynomial time adversary can have in distinguishing between the games Game i and Game i-1 , together with the advantage Adv[Game 4 ] that a probabilistic polynomial time adversary can have in the final game. Game 0 corresponds to the actual IND-IPFE-CPA game. The challenge ciphertext is (b, Inner-Product Functional Encryption Secure Against Chosen-Plaintext Attacks 73 1.

Figure 5 . 5 :

 55 Figure 5.5: Strategy for the proof of Theorem 5.3.2. The first experiment is the IND-IPFE-CPAsecurity game, then we present two other hybrids. In the first one, we change the way to compute the challenge ciphertext. In the second one, we change the word in the language. This last game is statistically unwinnable.

Figure 5 Figure 5 . 6 :

 556 Figure 5.6: Tag-Based Projective Hash Functions. On the first illustration, we see the correctness property: if the same tag is used, then the same hash is derived.On the second illustration, we see the property that will be useful to prove the security against chosen-ciphertext attacks: if the tag is different, it is hard to guess the correct hash value.

Figure 5 . 7 :

 57 Figure 5.7: Encrypt algorithm for our inner-product encryption scheme secure against chosenciphertext attacks. We use a one-time signature and a tag-based projective hash function to prevent malleability and detect ill-formed ciphertext and prevent them from being decrypted.

Contents 6 . 1 6 . 3

 6163 Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Projective Hash Functions Based on the Decisional Diffie-Hellman Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3.1 IPFE-CPA-Friendly Projective Hash Functions . . . . . . . . . . . . 88 6.3.2 IPFE-CCA-Friendly Projective Hash Functions . . . . . . . . . . . . 90 6.4 Inner-Product Functional Encryption Schemes Based on the Decisional Diffie-Hellman Assumption . . . . . . . . . . . . . . . . . . . . 92 6.4.1 Scheme Secure Against Selective Chosen-Plaintext Attacks . . . . . . 92 6.4.2 Scheme Secure Against Adaptive Chosen-Plaintext Attacks . . . . . . 94 6.4.3 Scheme Secure Against Chosen-Ciphertext Attacks . . . . . . . . . . 95

Figure 6 .Theorem 6 . 4 . 1 .

 6641 Figure 6.1: DDH-based inner-product functional encryption secure against selective chosenplaintext attacks

Figure 6 . 2 : 6 6. 4 Theorem 6 . 4 . 2 .

 6264642 Figure 6.2: DDH-based inner-product functional encryption secure against chosen-plaintext attacks

Theorem 6 . 4 . 3 .

 643 Under the DDH assumption in G, the scheme T BFE depicted on Figure 6.2 is IND-TBIPFE-CCA secure.

Figure 6 . 3 :

 63 Figure 6.3: DDH-based tag-based inner-product functional encryption secure against chosenciphertext attacks

Contents 7 . 1

 71 The Decisional Composite Residuosity Assumption and Subset Membership Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.1.1 The Decisional Composite Residuosity Assumption . . . . . . . . . . 98 7.1.2 Subset Membership Problem Based on the Decisional Composite Residuosity Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.2 Projective Hash Functions Based on the Decisional Composite Residuosity Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.2.1 IPFE-CPA-Friendly Projective Hash Function . . . . . . . . . . . . . 100 7.2.2 IPFE-CCA-Friendly Projective Hash Function . . . . . . . . . . . . 101 7.3 Inner-Product Functional Encryption Schemes Based on the Decisional Composite Residuosity Assumption . . . . . . . . . . . . . . . 103 7.3.1 Scheme Secure Against Chosen-Plaintext Attacks . . . . . . . . . . . 103 7.3.2 Scheme Secure Against Chosen-Ciphertext Attacks . . . . . . . . . . 105 -97 -

Figure 7 . 2 :

 72 Figure 7.2: DCR-based tag-based inner-product functional encryption secure against chosenciphertext attacks

Chapter 8 8. 2

 82 Public Key Encryption Schemes Secure under the Learning With Error Assumption109

  i∈[ ] ) proc Finalize(b') Return (b = b)These are exactly the same distribution as r is used nowhere else.

Chapter 8 8. 2

 82 Public Key Encryption Schemes Secure under the Learning With Error Assumption115 Hybrid H 6 : This is like H 5 except that ct 0 is generated as A r and u is replaced bypk, r . proc Initialize(κ, M) (a, (α i , x i , sk i ) i∈[ ] ) $ ← M(1 λ ) pk $ ← Z m q pk i = Ask i + e i , for e i ← χ m σ i r $ ← {0, 1} m , r $ ← {0, 1} m ct 0 = A r, ct = E(pk, a; r) ct i = α i ct + E ((sk i , e i ), x i , ct 0 ; r ) Return (pk, (α i , pk i , sk i ) i∈[ ] , ct 0 , (ct i ) i∈[ ] )proc Finalize(b') Return (b = b)

Hybrid H 7 :

 7 This is the Exp -ct-rep-1E,M,κ (A ). proc Initialize(κ, M) (a, (α i , x i , sk i ) i∈[ ] ) $ ← M(1 λ ) sk $ ← Z n q , e ← χ m σ , pk = Ask + e pk i = Ask i + e i , for e i ← χ m σ i r $ ← {0, 1} m , r $ ← {0, 1} m ct 0 = A r, ct = E(pk, a; r) ct i = α i ct + E ((sk i , e i ), x i , ct 0 ; r ) Return (pk, (α i , pk i , sk i ) i∈[ ] , ct 0 , (ct i ) i∈[ ] )proc Finalize(b') Return (b = b)

Figure 8 .

 8 Figure 8.1: LWE-based inner-product functional encryption secure against selective chosenplaintext attacks

2 .

 2 T = M x • κ ω(1) ; 3. σ ≥ (1 + T √ )σ ; 4. γ 0 > ln(2 (1+1/ ))IND-IPFE-CPA secure inner-product functional encryption scheme based on LWE is depicted on Figure 8.2.

Theorem 8 . 3 . 3 .

 833 Under the LWE assumption with parameters n, q, σ , the scheme FE depicted on Figure8.2 is IND-IPFE-CPA secure.

Figure 8 . 2 :

 82 Figure 8.2: LWE-based inner-product functional encryption secure against adaptive chosenplaintext attacks

Question 9. 3 .

 3 Can we build a secret key function hiding inner-product functional encryption without pairings?Or, more generally: Question 9.4. How far can we go, only using the decisional Diffie-Hellman assumption?

10 2.2 Basic Cryptographic Primitives

  Florian Bourse, and Helger Lipmaa. "CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions". In: PKC 2017, Part II. Ed. by Serge Fehr. Vol. 10175. LNCS. Springer, Heidelberg, Mar. 2017, pp. 36-66 (cit. on pp. 4, 5, 17, 63, 85, 97). . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 One-Time Signature and Collision Resistant Hash Functions . . . . . 10 2.2.2 Public Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Projective Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.1 Subset Membership Problems . . . . . . . . . . . . . . . . . . . . . 13 2.3.2 Projective Hash Functions . . . . . . . . . . . . . . . . . . . . . . . 13 2.

	[BBL17]	Fabrice Benhamouda,

[ABCP16] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Better Security for Functional Encryption for Inner Product Evaluations. Cryptology ePrint Archive, Report 2016/011. http://eprint.iacr.org/2016/011. 2016 (cit. on pp. 4, 5, 17, 41, 107). [ABDP15a] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple Functional Encryption Schemes for Inner Products. Cryptology ePrint Archive, Report 2015/017. http://eprint.iacr.org/2015/017. 2015 (cit. on pp. 4, 107). [ABDP15b] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. "Simple Functional Encryption Schemes for Inner Products". In: PKC 2015. Ed. by Jonathan Katz. Vol. 9020. LNCS. Springer, Heidelberg, Mar. 2015, pp. 733-751. doi: 10.1007/978-3-662-46447-2_33 (cit. on pp. 2, 3, 5, 17, 41, 85, 107). Contents 2.1 Notation and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Mathematical Notions . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 Provable Security . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Additional Preliminaries for Concrete Instantiations

  . . . . . . . . 14 2.4.1 Basic Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.2 Gaussians and Lattices . . . . . . . . . . . . . . . . . . . . . . . . 14

	Chapter 2 Preliminaries
	-7 -

  OT S must be complete, in the sense that if m is in the message space, then for all (sk, vk) Sign(sk, m), it holds that Verify(vk, m, σ) passes the check. Definition 2.2.2 (One-Time Unforgeability). A one-time signature scheme OT S = (Setup, Setup and sends vk to A .2.A chooses adaptively messages queries m i and sends them to the challenger. The challenger sends back σ i = Sign(sk, m i ) to A for each i.

	Sign, Verify) is strongly unforgeable, if no probabilistic polynomial time adversary A has a
	non-negligible advantage in the following game:
	1. The challenger sets (sk, vk)
	Collision Resistant Hash Functions. We call family of hash functions a family of functions (H

2.2 Basic Cryptographic Primitives 11

• Verify(vk, m, σ) → ∅ or ⊥. On input verification key vk, message m and signature σ returns nothing if the signature is valid, and ⊥ otherwise.

$ ← Setup(1 κ ), σ $ ← $ ← 3. A outputs a forgery (m , σ ) / ∈ {(m i , σ i )}

and wins if Verify(vk, m , σ ). k ) k∈K that maps arbitraty bitstrings to fixed-length bitstrings: H k : ×{0, 1} * → {0, 1} κ . Definition 2.2.3 (Collision Resistance). A family of hash functions (H k ) k∈K is collision resistant, if no probabilistic polynomial time adversary A can output a pair (m, m ) such that H k (m) = H k (m ) with non-negligible probability for a randomly chosen key k.

3.1 Definition and Security Model

. . . . . . . . . . . . . . . . . . . . . 18 3.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Indistinguishability-Based Security . . . . . . . . . . . . . . . . . .

19 3.2 Alternative Security Models

. . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 Selectivity vs. Adaptivity . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Simulation-Based Security . . . . . . . . . . . . . . . . . . . . . . . 25 3.

3 Indistinguishability under Chosen-Ciphertext Attack

  . . . . . . . . 27 3.3.1 Tag-Based Inner-Product Functional Encryption . . . . . . . . . . . 28 3.3.2 Removing the Tag . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Function Hiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.1 Function Hiding in the Public Key Setting . . . . . . . . . . . . . . 32 3.4.2 Secret Key Inner-Product Functional Encryption . . . . . . . . . . . 33 3.4.3 Partial Function Hiding . . . . . . . . . . . . . . . . . . . . . . . .

34

-17 -Chapter 3 Inner-Product Functional Encryption

Construction 3.2.4 (

  Inner-Product Functional Encryption Secure against Adaptive Chosen-Plaintext Attacks). Let us assume the existence of a modular IPFE scheme FE = (FE.Setup, FE.KeyDer, FE.Encrypt, FE.Decrypt). We define our improved IPFE scheme FE as follows:• Decrypt(pp , sk y , ct x ) → m or ⊥.On input public parameters pp , user secret key sk y , and ciphertext ct x , computes m ← FE.Decrypt(pp, sk y , ct x ) and outputs message m. Correctness. The correctness of FE directly follows from the correctness of FE, because t, y • 0 = 0. Notice that we require R to be finite in order to sample uniform vectors t. Security. If FE is s-IND-IPFE-CPA secure, then FE is IND-IPFE-CPA secure. More precisely, we have the following theorem.

	• Setup(1 κ , 1 ) → (pp , msk , mpk ). On input security parameter κ and functionality parameter , samples (pp, msk, mpk) $ ← FE.Setup(1 κ , 1 +1 ), and a random vector t $ ← R , and outputs public parameters pp = pp, master secret key msk = (msk, t), and master public key mpk = mpk;
	• KeyDer(pp , msk , y) → sk y . On input public parameter pp , master secret key msk , and key y ∈ R , samples sk y $ ← F EKeyDer(pp, msk, (y, -t, y )) and outputs user secret key sk y = sk y ;
	• Encrypt(pp , mpk , x) → ct x . On input public parameter pp , master public key mpk , and plaintext x ∈ R , samples ct x $ ← FE.Encrypt(pp, mpk, (x, 0)) and outputs ciphertext ct x = ct x ;
	Theorem 3.2.5. Let FE and FE be defined as in Construction 3.2.4. If FE is s-IND-IPFE-CPA secure, then FE is IND-IPFE-CPA secure. More precisely, for any ad-versary A , there exists and adversary B which runs in roughly the same time as A and such
	that:

  3.4 FunctionHiding 31 cannot be signed, and if the tag isn't reused, the security is guaranteed by the security of the tag-based IPFE. In order to transform our tag-based inner-product functional encryption into a tagless inner-product functional encryption and preserve the security properties, we are going to need: a strongly unforgeable one-time signature (see Definitions 2.2.1 and 2.2.2), as well as a collision resistant hash function (see Definition 2.2.3). We now proceed with our inner-product functional encryption construction.

Construction 3.3.5 (Inner-Product Functional Encryption secure against Chosen-Ciphertext Attacks). Let us assume the existence of a tag-based inner-product functional encryption scheme T BFE = (T BFE.Setup, T BFE.KeyDer, T BFE.Encrypt, T BFE.Decrypt), a strongly unforgeable one-time signature OT S and a family of collision resistant hash functions (H k ) k∈K .

  If FE is IND-IPFE-CPA secure, then FE is partially function hiding. More precisely, we have the following theorem. Let FE and FE be defined as in Construction 3.4.10. If FE is IND-IPFE-CPA secure, then FE is partially function hiding. More precisely, for any adversary A , there exists and adversary B which runs in roughly the same time as A and such that:

	Chapter 3 Inner-Product Functional Encryption
	Theorem 3.4.11.

Construction 3.4.10 (Inner-Product Functional Encryption Partially Function Hiding). Let us assume the existence of a modular IPFE scheme FE = (FE.Setup, FE.KeyDer, FE.Encrypt, FE.Decrypt). We define our secret key IPFE scheme FE as follows:

• Setup(1 κ , 1 ) → (pp , msk ). On input security parameter κ and functionality parameter , samples (pp, msk, mpk)

$ ← F E.Setup(1 κ , 1 )

, and a random invertible matrix B $ ← R × , and outputs public parameters pp = pp and master secret key msk = (mpk, msk, B); • KeyDer(pp , msk , y) → sk y . On input public parameter pp , master secret key msk , and key y ∈ R , samples sk y $ ← FE.KeyDer(pp, msk, B -t y) and outputs user secret key sk y = sk y ; • Encrypt(pp , msk , x) → ct x . On input public parameter pp , master secret key msk , and plaintext x ∈ R , samples ct x $ ← FE.Encrypt(pp, mpk, Bx) and outputs ciphertext ct x = ct x ; • Decrypt(pp , sk y , ct x ) → m or ⊥. On input public parameters pp , user secret key sk y , and ciphertext ct x , computes m ← FE.Decrypt(pp, sk y , ct x ) and outputs message m.

Correctness. The correctness of FE directly follows from the correctness of FE, because Bx, B -t y = x t B t B -t y = x, y .

Security.

  • Decrypt(pp, sk y , ct x ) → m or ⊥. On input public parameters pp, user secret key sk y , and ciphertext ct x , outputs FE.Decrypt(pp 1 , sk y , ct x ). Let FE and FE be defined as inConstruction 3.4.12. If FE is partially function hiding, then FE is function hiding against bounded collusions. More precisely, for any adversary A that makes at most q y queries to KeyDer, there exists an adversary B which runs in roughly the same time as A and such that:

	3.4 Function Hiding	39
		Chapter 3
	(y|r)), and outputs user secret key sk y ;	$ ← FE.KeyDer(pp, msk,
	• Encrypt(pp, msk, x) → ct x . On input public parameter pp, master secret key msk, and plaintext x ∈ R , samples ct x $ ← FE.Encrypt(pp, msk, (x|0)) and outputs ciphertext ct x ;

msk). On input security parameter κ and functionality parameter , samples (pp, msk) $ ← FE.Setup(1 κ , 1 +qy+1 ), and outputs public parameters pp and master secret key msk; • KeyDer(pp, msk, y) → sk y . On input public parameter pp, master secret key msk, and key y ∈ R , samples a random vector r $ ← R qy+1 , and sk y Correctness. The correctness of FE follows the one of FE by construction: for any κ ∈ Z, ∈ Z, y ∈ R , x ∈ R , let (pp, msk) $ ← Setup(1 κ , 1 ), sk y $ ← KeyDer(pp, msk, y), ct x $ ← Encrypt(pp, msk, x). We have: Decrypt(pp, sk y , ct x ) = FE.Decrypt(pp, sk y , ct x ) = (x|0), (y|r) = x, y . Security. We have the following security theorem: Theorem 3.4.13.

42 4.2 Additional Properties of Public Key Encryption

4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.1 Structural Properties . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.2 Homomorphic Properties . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.3 Security Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.

3 Generic Selectively Secure Inner-Product Functional Encryption

  . 46 4.3.1 Construction and Correctness . . . . . . . . . . . . . . . . . . . . . 46 4.3.2 A Simpler Case: Randomness Reuse . . . . . . . . . . . . . . . . . . 47 4.3.3 Security in the General Case . . . . . . . . . . . . . . . . . . . . . . 51 4.

4 Generic Adaptively Secure Inner-Product Functional Encryption

  . 56 4.4.1 Construction and Correctness . . . . . . . . . . . . . . . . . . . . . 56 4.4.2 Adaptive Security . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

-41 -

  4.3 Generic Selectively Secure Inner-Product Functional Encryption 47• Setup(1 κ , 1 ) → (msk, mpk). On input security parameter κ and functionality parameter , generates independent key pairs ∀i ∈ [ ], (sk i , pk i )sharing the same public parameters pp, and returns master secret key msk = (sk 1 , . . . , sk ) and master public key mpk = (pk 1 , . . . , pk );• Encrypt(mpk, x) → ct x . On input master public key mpk, and plaintext x ∈ M x , samples shared randomness r in the randomness space of E, and computes ct 0 ← E.C(r), ct

	• KeyDer(msk, y) → sk y . On input master secret key msk, and key y ∈ M y , outputs user secret key i∈[ ] sk y ← y i sk i ;

$ ← E.Setup(1 κ ) i ← E.E(pk i , x i ; r),

and outputs ciphertext ct x = (ct 0 , (ct i ) i∈[ ] ); • Decrypt(sk y , ct x ) → m or ⊥.

On input user secret key sk y , and ciphertext ct x , returns the output of E.Decrypt(sk y , (ct 0 , i∈[ ]

  Let us consider a PKE scheme E = (Setup, Encrypt, Decrypt) with the properties defined previously, we define our inner-product functional encryption scheme FE = (Setup, KeyDer, Encrypt, Decrypt) as follow. We set T = {0, . . . , T } in this case, where T will be set according to the security properties needed. (T /M x superpolynomial is needed for security against polynomially bounded adversaries, T /M x exponential provides security against sub-exponetially bounded adversaries, where M x is the biggest possible coordinate of any vector in M x )

	4.4 Generic Adaptively Secure Inner-Product Functional Encryption	57
	Construction 4.4.1 (Adaptively Secure Inner-Product Functional Encryption from Public Key Encryption). • Setup(1 κ , 1 ) → (msk, mpk). On input security parameter κ and functionality parameter , generates independent secret keys
	∀i ∈ [ ], s i	$ ← E.SKGen(1 κ ),
	and a key pair
	(sk, pk)	$ ← ESetup(1 κ ),
	sharing the same public parameters pp, and
	t

$

← T , and samples public keys corresponding to the secret keys sk

i = s i + t i sk ∀i ∈ [ ], pk i $ ← E.PKGen(s i + t i sk),

and returns master secret key msk = (s 1 , . . . , s , t) and master public key mpk = (pk 1 , . . . , pk , pk);

• KeyDer(msk, y) → sk y . On input master secret key msk, and key y ∈ M y , outputs user secret key sk y ← (

i∈[ ] y i s i , i∈[ ] y i t i );

• Encrypt(mpk, x) → ct x . On input master public key mpk, and plaintext x ∈ M x , samples shared randomness r in the randomness space of E, and computes

ct 0 ← E.C(r), ct 1 ← E.E(pk, 0; r), ∀i ∈ [ ], ct 2,i ← E.E(pk i , x i ; r),

and outputs ciphertext ct x = (ct 0 , ct 1 , (ct 2,i ) i∈[ ] ); • Decrypt(sk y , ct x ) → m or ⊥. On input user secret key sk y , and ciphertext ct x , returns the output of E.Decrypt(sk y,0 , (ct 0 , i∈[ ]

  pk s i where τ is the same as used in the Setup algorithm, and τ i is such that pk s i •pk t i is close to E.PKGen(sk i ). The algorithm returns mpk = (pk, (pk i ) i∈[ ] ) and msk = (s i , t i ) i∈[ ] .Under the -public-key-reproducibility of E, H 1 and H 2 are indistinguishable.Hybrid H 3 : This is like H 2 except that the challenge ciphertext is generated by invoking the algorithm H 3 .Encrypt defined as follows: H 3 .Encrypt(msk, pk, x): The algorithm computes the ciphertext for x in the following way:

	4.4 Generic Adaptively Secure Inner-Product Functional Encryption	59
	proc Initialize(κ)	proc Encrypt(x 0 , x 1 )
	(mpk, msk) V ← ∅ Return mpk proc KeyDer(y) V ← V ∪ {y} sk y $ ← KeyDer(msk, y) Return sk y	Ct * $ ← Encrypt(mpk, x b ) Return Ct * proc Finalize(b') if ∃y ∈ V such that x 0 , y = x 1 , y then return false Return (b = b)
			Chapter 4

$ ← H 2 .Setup(1 κ , 1 )

  Let P be a subset membership problem. Let PHF = (hashkg, projkg, hash, projhash) be a (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly projective hash function and let FE be the inner-product functional encryption scheme defined in Construction 5.3.1. We assume that Condition 1 is satisfied. Then FE is adaptively IND-IPFE-CPA secure. More precisely, if there exists an attacker A = A F E that has advantage ε A in breaking the IND-IPFE-CPA security of FE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the (L, L)-indistinguishability, such that

	Theorem 5.3.2.

Table 6 .

 6 1: Comparison of the three different DDH-based inner-product functional encryption schemes.

	6.4 Inner-Product Functional Encryption Schemes Based on the Decisional Diffie-Hellman Assumption 93
	Security s-IND-IPFE-CPA IND-IPFE-CPA IND-TBIPFE-CCA
	mpk msk sk #" y ct #" x	1 + 1	2 2 + 2	2 2 + 3 4 2 + 6 4 + 6 2 + 2 + 2

  7.2 Projective Hash Functions Based on the Decisional Composite Residuosity Assumptions 101 Using above notation, let M ⊥ = N s , M x be a positive integer, and ε ti = M x /M . Let hk ⊥ be defined as follows:

	Lemma 7.2.1.

  where B is a bound on the size of each α i and σ is the standard deviation of the error in the LWE assumption.

	Chapter 8 Instantiations based on the Learning With Errors Assumption
	random values.
	proc Initialize(κ, M) (a, (α
	Theorem 8.2.2. Construction 8.2.1 has -public-key-reproducibility in a statistical
	sense.
	Proof. Let τ be the description of an error distribution with standard deviation σ, and τ an error distribution with standard deviation σ . A simple calculation show that the covariance of e • #" α is σ 2 #" α #" α . Hence the choice of τ i to unskew the Gaussian distribution. Let {τ i } i∈[ ] describe sampling errors with covariance matrix √ Σ, where

i , x i , sk i

Table 8 .

 8 1: Comparison of the two different LWE-based inner-product functional encryption schemes.

	2. σ ≥ (1 + M x 3. σ q > 2 √ n ;	√ )σ ;
	4. p > M x M y ;

  8.3 Inner-Product Functional Encryption Schemes Based on the Learning With Errors Assumption 119 By using Theorem 4.3.3, we immediately get the following security theorem for our construction. Under the LWE assumption with parameters n, q, σ , the scheme FE depicted on Figure 8.1 is s-IND-IPFE-CPA secure. More precisely, if there exists an attacker A that has advantage ε A in breaking the s-IND-IPFE-CPA security of FE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the LWE assumption, such that ε A ≤ ε B .

	Theorem 8.3.2.

  Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d'effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c'est-à-dire du chiffrement fonctionnel qui permet l'évaluation de n'importe quel circuit. Ces contributions délaissent souvent l'efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n'est proche d'être pratique. Le but de cette thèse est d'attaquer ce défi sous un autre angle: nous essayons de construire des schémas de chiffrement fonctionnel les plus expressifs que nous le pouvons en se basant sur des hypothèses standards, tout en conservant la simplicité et l'efficacité des constructions. C'est pourquoi nous introduisons la notion de chiffrement fonctionnel pour l'évaluation de produits scalaires, où les messages sont des vecteurs x, et l'autorité peut transmettre des clés correspondants à des vecteurs y qui permettent l'évaluation du produit scalaire x, y . Cette fonctionnalité possède immédiatement des applications directes, et peut aussi être utilisé dans d'autres constructions plus théoriques, le produit scalaire étant une opération couramment utilisée. Enfin, nous présentons deux structures génériques pour construire des schémas de chiffrement fonctionnels pour le produit scalaire, ainsi que des instanciations concrètes dont la sécurité repose sur des hypothèses standards. Nous comparons aussi les avantages et inconvénients de chacune d'entre elles.

	Résumé
	Figures
	•, • | #" x | |S| ∆ ∝ o, O, ω, Ω A , B, • • • General Cryptographic Notations The inner-product operation The size of a vector The cardinality of a set The statistical distance Is proportional to Asymptotic notations Algorithms, adversaries κ The security parameter pk A public key sk A secret key ct A ciphertext mpk A master public key msk A master secret key sk y A user secret key Notations Specific to Chapter 5 P A subset membership problem L An NP language b A word w A witness hk A hashing key hp A projection key H A hash Notations Specific to Chapter 6 q a prime number G A cyclic group g Mots Clés A generator Notations Specific to Chapter 7 p, q Safe primes N spf(N ) a N J N QR N N QR * N Λ η (Λ) ρ χ σ χ σ A discrete Gaussian distribution A Gaussian parameter A noise distribution The Gaussian function The smoothing parameter of Λ A lattice Notations Specific to Chapter 8 The group of signed quadratic residues Squares of Z * Elements of Jacobi symbol 1 Jacobi symbol of a Smallest prime factor of N Product of safe primes cryptographie, chiffrement fonctionnel, produit scalaire, sécurité prouvée, constructions génériques, projective hash functions.

We recall that the length of the vectors is assumed to be polynomial in κ.

Remerciements

<('-'<) ~ˆ('-')ˆ~(>'-')> "I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve."

Remerciements vii

Correctness. As in the case of standard inner-product functional encryption, we allow the Decrypt algorithm to output ⊥ if x, y is outside of a polynomial sized set P fixed at setup. We also denote the plaintext space M x and the key space M y , and they may be smaller than the full ring R. Hence the following correctness property: A tag-based inner-product functional encryption scheme is correct if for any tag τ , for any x ∈ M x , y ∈ M y , (pp, msk, mpk) $ ← Setup(1 κ , 1 ), sk y $ ← KeyDer(pp, msk, y), ct x $ ← Encrypt(pp, τ, mpk, x). Then if x, y ∈ P, it holds that Decrypt(pp, τ, sk y , ct x ) = x, y .

We also define IND-TBIPFE-CCA security for TBIPFE schemes, which is similar, but the decryption oracle only allows queries that don't have the same tag as the challenge ciphertext. Definition 3.3.4 (Indistinguishability against Chosen-Ciphertext Attacks). For a tag-based inner-product functional encryption scheme T BFE = (Setup, KeyDer, Encrypt, Decrypt) defined over R, we define security against chosen-ciphertext attacks (IND-TBIPFE-CCA security) via the security game depicted on Figure 3.8: we define the advantage of an adversary A to be Adv ind-tbipfe-cca

T BF E,κ

T BF E,κ

Then we say that FE is secure against chosen-ciphertext attacks (IND-TBIPFE-CCA secure) if Adv ind-tbipfe-cca

Removing the Tag

In order to get a IND-IPFE-CCA secure inner-product functional encryption scheme from a tagbased one, we use a standard technique following the work of [START_REF] Kiltz | Chosen-Ciphertext Security from Tag-Based Encryption[END_REF] to transform tag-based PKE schemes to IND-CCA secure PKE schemes. The tag is the hash of a fresh verification key for a one-time signature scheme, used to sign the ciphertext. This signature prevents attacks using the malleability of the scheme. This way, if the tag is reused, the ciphertext Chapter 4

4.2 Additional Properties of Public Key Encryption 45

Security Properties

In order to prove security of our inner-product functional encryption scheme, we need the following two additional security properties on our public key encryption scheme. The first one is closely related to the linear key homomorphism. Indeed, it states that it is hard to distinguish between a public key that has been freshly generated by PKGen, and a key that has been generated using the homomorphism described in Definition 4.2.1. Of course, for noisy schemes such as lattice-based ones, the distribution will not exactly be the same, so we allow the parameters τ used in the two different world to be different. Definition 4.2.4 ( -Public-Key-Reproducibility.). For a public-key encryption scheme E we define -public-key-reproducibility via the security game depicted on Figure 4.1: we define the advantage of an adversary A to be

Then, we say that E has -public-key-reproducibility if there exists τ, τ ,

(A ) defines -public-key-reproducibility of E. D samples tuples of the form (sk, (α i , sk i ) i∈[ ] ) where sk and the sk i 's are sampled from SKGen, and the α i 's are in M.

The second additional security property on E is related to the linear ciphertext homomorphism under shared randomness. Basically, we want it to be hard for the adversary to dinstinguish between a ciphertext generated by homomorphism, and a fresh ciphertext. But in order to use the LCH property of Definition 4.2.2, we need to be able to generate second parts of ciphertexts using only the first part C(r) of a ciphertext and secret keys sk. Definition 4.2.5 ( -Ciphertext-Reproducibility.). For a public-key encryption scheme E we define -ciphertext-reproducibility via the security game depicted on Figure 4.2: we define the advantage of an adversary A to be

Chapter 4 Generic Construction from Public Key Encryption Then, we say that E has -ciphertext-reproducibility if there exists τ , τ i 's and algorithm E such that Adv -ct-rep

, where sk i 's are sampled from SKGen, α i 's are in M and a and the x i 's are in M x . E is an algorithm that takes as input a secret key in G, a message in R, a first part ciphertext C(r) for some r in the randomness space, and the parameters needed to generate public keys, and output a second part ciphertext.

We are now ready to show our construction of inner-product functional encryption.

Generic Selectively Secure Inner-Product Functional Encryption

We will first define our IPFE scheme and show its correctness, then we start with a proof of security in a simpler case, where the underlying public key encryption scheme has a property that we call randomness reuse. And then we move on to the full proof of security.

Construction and Correctness

Our construction is very simple. The basic idea is to use independent key pairs to encrypt individually the elements of the vector x, and use the homomorphic properties described in Section 4.2.2 in order to compute and decrypt the inner-product with a given vector y.

Chapter

Under the s-IND-CPA security of E, H 4 and H 5 are indistinguishable.

Hybrid H 6 : This is like H 5 except that the challenge ciphertext is generated by invoking the algorithm H 6 .Encrypt defined as follows: H 6 .Encrypt(msk, pk, x): The algorithm computes the ciphertext for x in the following way:

, where r is some randomness in the random space of E. proc Initialize(κ)

Under the -public-key-reproducibility of E, H 7 and H 8 are indistinguishable.

Hybrid H 9 : This is like H 8 except that the simulator guesses the value of x 1 -x 0 and aborts if the guess is wrong.

If the adversary has advantage in H 9 , then it has advantage |{x 1 -x 0 :

Chapter 5

5.5 Inner-Product Functional Encryption Secure Against Chosen-Ciphertext Attacks 77

Important Particular Case: Key Uniformity. For many key-homomorphic tag-based PHFs (i.e., the one based on the DDH assumption and its variants), the output of hashkg † is actually uniform over the group K † . In this case, as for translation indistinguishability (Lemma 5.2.6), the PHF is automatically (hashkg † , •, 0)-universally-translation-indistinguishable, for hashkg † = hashkg † . More formally, we have the following lemma.

Lemma 5.4.4. Let PHF † = (hashkg † , projkg † , hash † , projhash † ) be a key-homomorphic tagbased PHF such that the distribution of hashkg † (Λ) is uniform over K † . Let M x be a positive integer. Then PHF is (hashkg † , M x , 0)-universally-translation-indistinguishable.

Proof. Both hashkg † (Λ) and hashkg † (Λ)+x•hashkg † (Λ) are uniform group elements in K † .

IPFE-CCA Friendliness

We now regroup the 3 properties we have just defined under the IPFE-CCA friendliness property. It is used as a shorthand for the sake of readability and regroups projection key homomorphism, universal translation indistinguishability, and 2-universality on a slight modification of the PHF.

Definition 5.4.5 (IPFE-CCA Friendliness). A tag-based projective hash function PHF

-IPFE-CCA-friendly for a (not necessarily polynomial time) algorithm hashkg † taking as input Λ and outputting a hashing key hk † in some set K * † ⊆ K, and for a positive integer M x , for a subset Σ † of Z, and for a positive integer

, where the algorithm t • hashkg † runs hashkg † and multiplies the output by t.

Important Particular Case: Key Uniformity.For many key-homomorphic PHFs, the output of hashkg † is actually uniform over the group K † . In this case, we have the following lemma which proves IPFE-CCA friendliness from 2-universality. Lemma 5.4.6.

Proof. Since hashkg † (Λ) is uniformly distributed, t • hashkg † (Λ) is as well, so both schemes are equal.

2-universal tag-based PHFs can be constructed from diverse groups, as in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. All the constructions in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] are key-homomorphic and projection-key-homomorphic. And for well-chosen parameters, they actually are IPFE-CCA-friendly.

Inner-Product Functional Encryption Secure Against Chosen-Ciphertext Attacks

In this section, we show a construction of a IND-TBIPFE-CCA secure tag-based inner-product functional encryption scheme. The concrete IND-IPFE-CCA secure inner-product functional

Chapter 6 Instantiations based on the Decisional Diffie-Hellman Assumption

Additional Properties of the Additive ElGamal Public Key Encryption Scheme

We now go through the additional properties defined in Section 4.2, and show that the additive ElGamal encryption scheme defined in Construction 6.2.1 satisfies this properties.

Structure. Let q be a prime and G a group of order q where the DDH assumption is supposed to be hard, and g a generator of G. Then, ElGamal's secret key space is the group (Z q , +, 0), public key space is the group (G, +, 0), and the message space is Z q . An ElGamal ciphertext is of the form ct

Linear Key Homomorphism. It is easy to see that for any two secret keys sk 1 , sk 2 ∈ Z q and any y 1 , y 2 ∈ Z q , the component-wise linear combination formed by y 1 sk 1 + y 2 sk 2 can be computed efficiently only using public parameters, the secret keys sk 1 and sk 2 and the coefficients y 1 and y 2 . And this combination y 1 sk 1 + y 2 sk 2 also functions as a secret key to a public key that can be computed as

where pk 1 (resp. pk 2 ) is a public key corresponding to sk 1 (resp. sk 2 ).

Linear Ciphertext Homomorphism under Shared Randomness. It holds that

Security. The ElGamal encryption scheme remains secure under randomness reuse. In fact, it holds that

Thus, the simplified proof of security applies, hence the construction of two inner-product functional encryption schemes, one being s-IND-IPFE-CPA secure, and the other one reaching adaptive IND-IPFE-CPA security. We will present those schemes in Section 6.4.

Projective Hash Functions Based on the Decisional Diffie-Hellman Assumptions

We are now ready to present the projective hash function that we will use to construct inner-product functional encryption scheme. We start with the IPFE-CPA-friendly PHF, and then present the IPFE-CCA-friendly one.

IPFE-CPA-Friendly Projective Hash Functions

In this section, we describe IPFE-CPA-friendly PHFs for the subset membership problems described in Section 6.1.

Chapter 6

6.3 Projective Hash Functions Based on the Decisional Diffie-Hellman Assumptions 89

Based on Decisional Diffie-Hellman.

Let G be an additive cyclic group of prime order q, let X = G 2 , let L be the subgroup of X generated by g = (g 1 , g 2 ) ∈ G 2 , where g i are random generators of G. A witness

We recall the PHF of Cramer and Shoup [CS01, Section 8.1.1] defined as follows:

• hashkg(Λ) outputs hk

Lemma 6.3.1. Using above notation, let g ⊥ an arbitrary generator of G, M ⊥ = q, M x be a positive integer, and ε ti = 0. For any b ∈ X \ L, let hk ⊥ (b) be defined as follows:

Then, the PHF described above is

Proof. We first remark that hk ⊥ (b) is well defined, as log

Strong Diversity. Since the space of projection keys is also a group and projkg is a group homomorphism, we can use Lemma 5.2.4. Hence, we just need to prove that projkg(hk ⊥ (b)) = 0 and hash(hk ⊥ (b), b) = g ⊥ . This follows from the following two facts:

Translation Indistinguishability follows from Lemma 5.2.6.

Based on Matrix Decisional Diffie-Hellman.

Let Λ = (G, g) be defined as in the MDDH subset membership of Section 6.1. We recall that g ∈ G t×d , X = G t , L is the subgroup generated by the columns of g, and L = X \ L. A witness

We recall the PHF defined by Escala et al. in [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF]:

We can prove the following lemma similarly to Lemma 6. b is not in the span of the columns of g. Then, the PHF described above is (hk ⊥ , g ⊥ , M ⊥ , M x , ε ti )-IPFE-CPA-friendly.

We skip the proof because is follows the previous one in a very straigthforward manner. The two PHFs we have just described can thus easily be used to construct IND-IPFE-CPA secure inner-product functional encryption schemes. We present the one based on DDH in Section 6.4.

IPFE-CCA-Friendly Projective Hash Functions

In this section, we describe IPFE-CCA-friendly PHFs for the subset membership problems described in Section 6.1.

DDH Based IPFE-CCA-Friendly PHF.

Let G be a cyclic group of prime order q, let X = G 2 , let L be the subgroup of X generated by g = (g 1 , g 2 ) ∈ G 2 , where g i are random generators of G * . A witness w ∈ W = Z q for b ∈ L is such that b = w • g. We set Λ = (G, g).

We first recall the following 2-universal hash from [ABP15]:

• The tag set is T = Z q ;

• hashkg † (Λ) outputs hk † $ ← Z 4 q =: K;

We have the following property.

Chapter 6 Instantiations based on the Decisional Diffie-Hellman Assumption 2-Universality. As each 4-tuple of coordinates of hk † are generated independently,

where (hashkg † , projkg † , hash † , projhash † ) is the 1/q-2-universal PHF from Lemma 6.3.3. The theorem follows from Lemma 5.4.6.

The resulting IND-TBIPFE-CCA secure scheme will be explicited in Section 6.4.

MDDH Based IPFE-CCA-Friendly PHF.

The previous construction can be extended in a straightforward way to any MDDH-based subset membership problem in a straightforward way, similar to what is done for our IPFE-CPA-friendly construction in the previous subsection.

• The tag set is T = {0, . . . , N/2 } ⊆ Z N

• hashkg † (Λ) outputs hk † $ ← {0, . . . , νM † N s+1 /2 } 2×ν =: K * ⊆ Z 2×ν =: K, where M † is a positive integer and is a parameter of the scheme;

We have the following property. M x be a positive integer, and ε † uti = M x /M † . Define in addition the following algorithm:

Lemma 7.2.2. Using above notation, Σ

Proof. Key Homomorphism is straightforward.

Projection Key Homomorphism is straightforward. Universal Translation Indistinguishability. We recall the following classical lemma. Lemma 7.2.3. Let (A 1 , . . . , A k ) and (B 1 , . . . , B k ) be two tuples of k independent distributions. Let A (resp. B) be the product distribution of (A 1 , . . . , A k ) (resp. (B 1 , . . . , B k )), i.e., the distributions of tuples (x 1 , . . . , x k ) where x i is distributed according to A i (resp. B i ), for i = 1, . . . , k. Then:

Using this fact, for any x ∈ {-M x , . . . , M x } and any hk † $ ← hashkg † (Λ), we have

2-Universality. As for the case of DDH, we first study the 2-universality of the simple scheme which will be repeated ν times. Then we will conclude using the same argument, that is the parallel repetitions are independent. For the simple scheme, notice that conditioning on projkg † (hk † ) fixes the values of hk † 1 and hk † 2 modulo N , the order of g. So hk † 1 and hk † 2 are uniform in a coset of the subgroup of order N s . Conditioning on hash † (hk † , b, τ ) fixes a relation between hk † 1 and hk † 2 modulo N s depending on τ . However, as τ = τ , this relation does not fix the value of hash † (hk † , b , τ ), and the most likely value still has probability at most spf(N ).

We are now ready to present our inner-product functional encryption schemes.

Inner-Product Functional Encryption Schemes Based on the Decisional Composite Residuosity Assumption

In this section, we present the two schemes secure under the DCR assumption obtained by plugging the PHFs described in the previous section in Construction 5.3.1 and Construction 5.5.1. The first one reaches IND-IPFE-CPA security, the second one is an IND-TBIPFE-CCA secure tag-based IPFE scheme. The most interesting part about these construction is that they fix the biggest problem of the schemes based on the DDH assumption: the decryption is efficient.

On the other hand, the schemes are non-modular, which is not as general as we would like. We recall however that [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] presented a way to convert non-modular IPFE schemes into modular IPFE schemes, the only cost being that the key generation algorithm have to be stateful and remember up to different queries, which is still a reasonably low cost. We provide a comparison of those two schemes in Table 7.1, where we present the trade-offs between security and efficiency.

Security

Table 7.1: Comparison of the two different DCR-based inner-product functional encryption schemes. The sizes are represented as a number of bits, since some elements are in Z. We recall that in order to achieve IND-IPFE-CCA security from the IND-TBIPFE-CCA secure scheme, we just need to add a one-time signature to the ciphertext, and does not make the size of the keys grow.

Scheme Secure Against Chosen-Plaintext Attacks

Before presenting the scheme, let us first discuss the choice of parameters. We set R = Z. Contrary the DDH-based instantiation, the discrete logarithm problem in the subgroup generated by g ⊥ is easy: given t • g ⊥ , we can always efficiently recover t. However, to satisfy Condition 1, we need to choose M y and M x so that for any #" y ∈ M y and #" x ∈ M x , #" y , #" x is the same modulo M ⊥ = N s and over the integers. There are many ways to choose the parameters to satisfy this condition. We propose one possible way here.

Example 7.3.1 (Example of parameters for our DCR-based instantiation). Let M y and M x

be positive integers such that 2M y M x + 1 ≤ M ⊥ = N s . We set:

where . denotes the Euclidean norm, so that | #" y , #" x | ≤ M y M x (when the inner-product is over the integers). For the last inequality, we use the rough inequality

Then, we fix M y and M x so that 2M y M x + 1 ≤ M ⊥ . And we choose M so that M x /M is negligible.

We are now ready to present our DCR-based IND-IPFE-CPA secure IPFE scheme, depicted on Figure 7.1. To make the scheme look mroe familiar, we use the multiplicative notation for

• Let N = pq be a product of two λ-bit random safe primes. We suppose that Condition 1 is satisfied. Let u

, and g ⊥ ← 1 + N .

• Setup(1 κ , 1 ) → (mpk, msk): Set pp = (κ, , N, g). For i = 1, . . . , , set

Return msk = hk ∈ Z and mpk = hp ∈ G .

• KeyDer(msk, #" y ∈ M y ) → sk #" y : Set

where the computation is done over Z. Return msk #" y = hk #" y ∈ Z.

• Encrypt(mpk, #" x ∈ M x ) → ct #" x : Sample r $ ← {0, . . . , N/4 } and set b ← g r . Return (msk, mpk). For i = 1, . . . , , set Note that the sizes of our secret keys is slightly larger than those of [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF], due to our security reduction. In order to have better parameters, they do a more precise analysis of the computational entropy contained in the secret key and show that it is enough to hide the challenge vector. On the other hand, their scheme requires to sample discrete Gaussian Chapter 7

Using parameters from Example 7.3.1, we have the following security bound: ε A ≤ 4s • ε B + 16/ spf(N ) + 2 -κ . Although there is an exponential loss in the security reduction of Theorem 5.3.2, we emphasize that there is no exponential loss using these parameters: the security loss is compensated by these well-chosen parameters. Most importantly, all the algorithms of the resulting scheme run in polynomial time (in the security parameter κ) 1 and the reduction to DCR is polynomial time. There is no complexity leveraging and we do not require subexponential assumption nor exponential-size keys or ciphertexts.

We also note that we could directly have another inner-product functional encryption scheme that is IND-IPFE-CPA secure by instantiating Construction 4.4.1 with the public key encryption scheme from [START_REF] Camenisch | Practical Verifiable Encryption and Decryption of Discrete Logarithms[END_REF] or [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF], but the resulting construction would have worse parameters than our construction from projective hash functions. These schemes are similar to the ElGamal public key encryption scheme, but in a composite group, which means that the message can be embeded in a subgroup where the discrete logarithm is easy to solve, as in our case with the construction from PHF.

Scheme Secure Against Chosen-Ciphertext Attacks

Let us now instantiate the framework for IND-TBIPFE-CCA secure tag-based inner-product functional encryption schemes with the DCR-based IPFE-CPA-friendly PHF defined in Section 7.2.1, and the DCR-based IPFE-CCA-friendly tag-based PHF defined in Section 7.2.2. We use the same parameters as for the IND-IPFE-CPA secure scheme in the previous section. We recall that we use here the multiplicative notation for G: g 1 g 2 = |g 1 g 2 | where elements are represented in {-N s -1 2 , . . . , N s -1 2 }. The resulting scheme is depicted on Figure 7.2. Applying Theorem 5.5.2 and Lemma 7.1.1, we immediately get the following security theorem. More precisely, if there exists an attacker A that has advantage ε A in breaking the IND-TBIPFE-CCA security of T BFE, then there exists an attacker B that runs in approximately the same time and that has advantage ε B in breaking the DCR assumption, such that

Chapter 8

Chapter 8

Instantiations based on the Learning With Errors Assumption

In this chapter, we instantiate the two generic constructions of inner-product functional encryption from public key encryption with a lattice-based public key encryption scheme. As usual with lattice-based cryptography, or noise-based cryptography, the analysis of the scheme is more complicated than in the two previous case of schemes based on the hardness of the discrete logarithm or on the hardness of the factorization. We give 2 concrete instantiations that reach respectively s-IND-IPFE-CPA and IND-IPFE-CPA security, and compare their trade-offs between efficiency and security, and even between security and security: the scheme that reaches the stronger notion of security uses a stronger assumption (that is less likely to hold). These schemes have the advantage of being resistant against quantum attacks, and have efficient decryption, however, they are non-modular. They were first presented in our papers [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF] (details are only found in the full version [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF]) and [START_REF] Abdalla | Better Security for Functional Encryption for Inner Product Evaluations[END_REF]. Finally, let β = I #" α and Σ = Σ 0 0 σ 2 , where I is the identity matrix.

Contents

Then, If b = 0, the errors appearing in pk i come from the distribution χ σI . If b = 1, the errors appearing in pk i come from the distribution βχ √ Σ .

We show that these two distribution are statistically close if

as long as γ 0 > ln(2 (1+1/ )) π by Lemma 2.4.6 and Corollary 2.4.3 -Ciphertext Reproducibility. We show that the scheme of Construction 8.2.1 has -ciphertext-reproducibility for any fixed constant as long as m ≥ (n + + 1) log q + 2 log 1 + Ω(1), by taking error distributions with standard deviations σ , (σ i ) i∈[ ] as chosen for the -public-key-reproducibility, and by the following alternative encryption algorithm E ((s i , e i ), x i , ct 0 ; r ) = s i , ct 0 + e i , r + t(x i ) . as required. This is enough to show that Exp -ct-rep-0 Notice that E ((sk i , e i ), x i , ct 0 ; r) = E(pk i , x i ; r) since ct 0 = A r.

Hybrid