Multi-Input Inner-Product Functional Encryption without Pairings 

Get Complete Project Material File(s) Now! »

Contribution 1: Tightly CCA-Secure Encryption without Pairing

In [GHKW16], which is presented in Chapter 3 of this thesis, we answer this question nega-tively. Namely, we present the first CCA-secure public-key encryption scheme based on DDH where the security loss is independent of the number of challenge ciphertexts and the number of decryption queries, whereas all prior constructions [LJYP14, LPJY15, HKS15, AHY15a, GCD+16, Hof17] rely on the use of pairings. Moreover, our construction improves upon the concrete efficiency of prior schemes, reducing the ciphertext overhead by about half (to only 3 group elements under DDH), in addition to eliminating the use of pairings. Figure 1.1 gives a comparison between existing CCA-secure public-key encryption schemes.
One limitation of our construction is its large public key: unlike the schemes with looser security reduction from [CS98, KD04, HK07], which admit a public key that only contains a constant number of group elements, our public key contains λ group elements, where λ denotes the security parameter. Using techniques from [Hof17], we present in [GHK17] the first CCA-secure public-key encryption with a tight security reduction to the DDH assumption (without pairings), whose public key only contains a constant number of group elements. The efficiency is comparable with [GHKW16], since the ciphertexts only contain three group elements. We choose to only present in this thesis the work from the precursor [GHKW16].

Functional Encryption

We now proceed to address another limitation of traditional public-key encryption: it only provides an all-or-nothing access to the encrypted data. Namely, with the secret key, one can decrypt the ciphertext and recover the message entirely; without the secret key, nothing is revealed about the encrypted message (beyond its size). To broaden the scope of applications of public-key encryption, [O’N10, BSW11] introduced the concept of functional encryption, which permits selective computations on the encrypted data, that is, it allows some authorized users to compute partial information on the encrypted data.
• Using functional encryption, one can perform machine learning on encrypted data. Namely, after a classifier is learned on plain data, one can generate a functional decryption key associated with this classifier, which allows decryption to run the classification on en-crypted data, and reveals only the result of the classification. In [DGP18], a concrete implementation of functional encryption performs classification of hand-written digits from the MNIST dataset, with 97 54% accuracy, where the encryption and decryption only take a few seconds.
Difference with respect to fully homomorphic encryption. In a fully homomorphic encryption scheme, it is possible to publicly evaluate any function on the encrypted data. This differs from functional encryption in two major ways: first, the result of evaluating a function f on an encryption of message m does not reveal the evaluation f (m) in the clear, but only an encryption of it. Consider the email filtering scenario: using fully homomorphic encryption, the email server would not be able to decide whether an incoming encrypted email is spam, without the intervention of the client, who is the only one who can decrypt the result of the evaluation on encrypted data. Second, using fully homomorphic encryption, anyone can compute arbitrary functions on the encrypted data: there is no guarantee that the computation was performed correctly. In a functional encryption scheme, the owner of the functional decryption key associated with function f can extract f (m), from an encryption of m, and nothing else. In particular, this gives verifiability for free, unlike fully homomorphic encryption, which requires additional costly zero-knowledge proofs to verify that the proper function has been evaluated on the encrypted data.
Security of functional encryption. Security notions for functional encryption were first given in [O’N10, BSW11]. These works present a simulation-based security definition, where an efficient simulator is required to generate the view of the adversary in the security game, only knowing the information that leaks from the encrypted values and corrupted functional decryption keys. They prove that such a security notion is impossible to achieve in general, and give another indistinguishability-based variant of the security definition, essentially a security definition similar to [GM84], generalized to the context of functional encryption. In this security game, an adversary receives the public key of the encryption scheme, and then, it can obtain functional decryption keys for functions f of its choice. It also sends two messages, m0 and m1, to the challenger, in the security game, which samples a random bit b ←R {0, 1}, and sends back an encryption of the message mb. Assuming the functional encryption keys that are obtained by the adversary are associated with functions f that do not distinguish these two messages, that is, for which f (m0) = f (m1), the adversary should not be able to guess which bit b was used with a probability significantly more than 1/2, which can be obtained by random guessing. Intuitively, if the functions f do not help distinguish these two messages, then no information should be revealed about which message mb was encrypted. An artificial but useful weakening of the security model is the so-called selective security, where the game is identical to the description above, except the adversary is required to decide on which messages m0 and m1 to choose beforehand, that is, before seeing the public key or obtaining any functional decryption keys. This notion is useful as a stepping stone towards full-fledged security. Moreover, a guessing argument can convert any selectively-secure scheme into a fully-secure scheme, albeit with a quantitative gap in the quality of the security.

State of the Art in Functional Encryption

Identity-based encryption. Historically, the first functional encryption scheme beyond traditional public-key encryption dates back to identity-based encryption, where a constant-size public key is used to encrypt messages to different users, represented by their identity. Functional decryption keys are also associated with an identity, and decryption succeeds to recover the encrypted message if the identities associated with the ciphertext and the functional decryption key match. For instance, identities can be email addresses, and with a single public key, it is possible to encrypt a message to any user whose email address is known. The concept was thought of in [Sha84], and the first constructions whose security relied on standard assumptions were given in [BF01, Coc01].
Attribute-based encryption. Later, a more general concept was introduced: attribute-based encryption, where ciphertexts are associated with an access policy, and functional de-cryption keys are associated with a set of attributes. Decryption recovers the encrypted mes-sage if the attributes associated with the functional decryption key satisfy the access policy embedded in the ciphertext. Note that the role can be switched, that is, ciphertexts can be as-sociated with attributes, and functional decryption keys embed access policies, as in [BSW07]. These are referred to as key-policy and ciphertext-policy attributed-based encryption, respec-tively. Such attribute-based encryption schemes have been first realized from standard as-sumptions in [SW05, GPSW06] for policies that can be represented as Boolean formulas, or in [GVW13, GVW15a, BGG+14] for policies that can be represented as any arbitrary circuit of polynomial size. Note that a ciphertext only hides the underlying message it encrypts, but reveals the associated access policy (or attributes, depending on whether we consider ciphertext-policy or key-policy attribute-based encryption).
Predicate encryption. Predicate encryption schemes are even more powerful than attribute-based encryption schemes, since the access policy associated with a ciphertext remains hidden (or the attributes, depending on whether we consider the ciphertext-policy or the key-policy variant). The first constructions from standard assumptions were given in [BW07] for com-parison and subset queries, in [KSW08, KSW13] for constant-depth Boolean formulas, and in [GVW15b] for all circuits. Such predicate encryption schemes are sometimes referred to as private-index predicate encryption, whereas attribute-based encryption (which do not hide the policy or attributes underlying each ciphertext) are referred to as public-index predicate en-cryption. It is important to note that the construction from [GVW15b] only hides the attributes underlying each ciphertext (they build a key-policy predicate encryption, where attributes are associated with ciphertexts) when the adversary can only obtain functional decryption keys for access policies which are not satisfied by the attribute of the challenge ciphertext. This is referred to as weakly-hiding the attributes. Prior works [BW07, KSW08, KSW13] fully hide the attributes associated with each ciphertext, the only information that leaks being the value of the predicate evaluation, namely, whether or not the decryption succeeds. In fact, fully-hiding predicate encryption for all circuits essentially implies functional encryption for all circuits, for which we have no construction based on standard assumptions. We defer the interested reader to [GVW15b, 1.3 Discussion] for further details on the connections between predicate encryption and functional encryption for all circuits.
Functional encryption beyond predicates. So far, we have only discussed special kinds of functional encryption where decryption successfully recovers the entire message if the at-tributes associated with the ciphertext (resp. the functional decryption key) satisfy the access policy embedded in the key (resp. the ciphertext). While this is a fruitful generalization of traditional public-key encryption, since it permits embedding complex access policy into the encrypted data, this is still an all-or-nothing encryption: either the message is entirely recov-ered by the decryption, or no information whatsoever is revealed about the message. Not much is known about functional encryption with fine-grained access to the encrypted data, that is, where decryption recovers partial information about the encrypted data. In [ABDP15], the authors build the first construction of functional encryption from standard assumptions be-yond predicates. In [ABDP15], messages to be encrypted are vectors of integers, in Zd, for some dimension d ∈ N that is fixed during the setup of the scheme. Functional decryption keys are associated with vectors y ∈ Zd. Decryption of an encryption of x ∈ Zd with a functional decryption key associated with y ∈ Zd recovers x, y ∈ Z, which denotes the inner product between x and y. Otherwise stated, this encryption scheme lets owners of functional decryp-tion keys compute weighted sum on the encrypted data. Moreover, it is possible to encode any constant-depth formula as a polynomial of constant degree, which can be evaluated via functional encryption for inner products. That is, this scheme handles computation of NC0 circuits on encrypted data. Later, [ALS16] gave fully-secure functional encryption schemes (the original schemes from [ABDP15] being only selectively-secure). In this thesis, we present extensions of these functional encryption for inner products, and new functional encryption schemes with succinct ciphertexts that supports the evaluation of degree-2 polynomials on encrypted data. More details on the contributions of this thesis are given below.
Related works: functional encryption for bounded collusion. The case where security is guaranteed only when a constant number of functional decryption keys are corrupted has been considered in prior works. [SS10] built the first functional encryption for all circuits, where security handles the corruption of one functional decryption key, using garbled circuits and public-key encryption. In this functional encryption, the ciphertext size depends on the size of the circuit associated with the functional decryption keys (which thus needs to be bounded during the setup of the scheme). [GKP+13] improves upon [SS10] since the ciphertext size depends only on the size of the output of the function for which functional decryption keys are generated. They use attributed-based encryption for all circuits, and fully homomorphic encryption, both of which admits construction from standard assumptions. Note that the security of both of these constructions breaks down as soon as two functional decryption keys are corrupted. [GVW12, Agr17] show how to generically turn any functional encryption secure only when one functional decryption key is corrupted, into a functional encryption scheme where security handles an a priori bounded polynomial number of collusions. We now consider the case of general functional encryption with unbounded collusions.
Theoretical motivation: the power of general purpose functional encryption. As mentioned before, the existing functional encryption schemes from standard assumptions only permit the evaluation of degree-1 (inner products) or degree-2 polynomials on the encrypted data. However, there are feasibility results for functional encryption schemes where functions associated to functional decryption keys can be any arbitrary circuits (such schemes are called general purpose functional encryption schemes). The first candidate construction for general purpose functional encryption appeared in [GGH+13b, GGH+16]. It relies on Indistinguisha-bility Obfuscation, a powerful object, originally defined in [BGI+01, BGI+12], that has been remarkably successful at providing an all-purpose tool for solving cryptographic problems, as shown in [SW14]. [GGH+13b, GGH+16] gave a construction for Indistinguishability Obfusca-tion that relies on cryptographic multilinear maps, for which there is currently no construction from standard assumptions. Other works [BLR+15, GGHZ16] gave direct candidate construc-tions of functional encryption from multilinear maps.
Follow-ups [Lin16, LV16, Lin17, AS17, LT17] focused on reducing the degree of the required multilinear map, all the way down to 3 in [LT17] (the degree of the multilinear map required in prior works depends on the complexity of the circuits for which functional decryption keys are generated). Namely, in [LT17], general purpose functional encryption is built from succinct functional encryption which handles evaluation of degree-3 polynomials on encrypted data (which can be built from degree 3 multilinear maps), together with some assumptions on the existence of special kind of pseudo-random generators1. Here, succinctness refers to the fact that the ciphertext size only depends on the underlying message, and not the functions for which functional decryption keys are generated. Unfortunately, there is no construction of even degree-3 multilinear from standard assumptions. To sum up, all existing general purpose func-tional encryption schemes either rely on multilinear maps, or Indistinguishability Obfuscation, both of which rely on non-standard assumptions. In fact, general purpose functional encryption has been shown to imply Indistinguishability Obfuscation in [AJ15, BV15, BNPW16].

Contribution 2: Functional Encryption with New Features, and Richer Functionalities

Motivated by the quest for succinct functional encryption for richer classes of functions, we follow the bottom-up approach initiated by [ABDP15], which consists of building functional encryption as expressive as possible from standard assumptions. The benefit of this approach is two-fold: first, it aims at bridging the gap between the powerful Indistinguishability Obfusction, and the current constructions from standard assumptions; second, it gives practically relevant schemes based from concrete assumptions, which are interesting in their own right. We present extensions of the original functional encryption for inner products from [ABDP15, ALS16] with additional features: in contribution 2.1, we extend functional encryption for inner products to the multi-input setting, and to the multi-client setting in contribution 2.2, both of which generalize the standard single-input setting. Then, we expand functional encryption for richer classes of functions in contribution 2.3. These contributions are presented in more details below.

Contribution 2.1: multi-input encryption for inner products.

We present here an extension of the original functional encryption from [ABDP15, ALS16] to the more general multi-input setting.
Definition of multi-input functional encryption. As explained above, in a functional encryption (FE) scheme [SW05, BSW11], an authority can generate restricted decryption keys that allow users to learn specific functions of the encrypted messages and nothing else. That is, each FE decryption key dkf is associated with a function f and decrypting a ciphertext Enc(x) with dkf results in f (x). Multi-input functional encryption (MIFE) introduced by [GGG+14] is a generalization of functional encryption to the setting of multi-input functions. A MIFE, the scheme has several encryption slots and each decryption key dkf for a multi-input function f decrypts jointly ciphertexts Enc(x1), , Enc(xn) for all slots to obtain f (x1, , x n) without revealing anything more about the encrypted messages. The MIFE functionality provides the capability to encrypt independently messages for different slots. This facilitates scenarios where information, which will be processed jointly during decryption, becomes available at different points of time or is provided by different parties. MIFE has many applications related to computation and data mining over encrypted data coming from multiple sources, which include examples such as executing search queries over encrypted data, processing encrypted streaming data, non-interactive differentially private data releases, multi-client delegation of computation, order-revealing encryption [GGG+14, BLR+15].
Application of multi-input functional encryption for inner products. For instance, consider a database that contains profiles of the employees in company, where each profile describes the qualifications that the person has and the position that she can hold. Each such profile can be represented as an integer vector that contains the scores that person has received for her qualifications in her last evaluation. The employee profiles are sensitive information and only direct managers can access the profile information of the people in their teams. Therefore, the information of profiles needs to be protected from everyone else in the company. At the same time when the company starts a new project, the manager assigned to lead the project needs to select people for the new team. According to the needs of the project, the team should have people serving different roles; the qualifications of each team member have different importance for every project. The selection criterion for the team members can be described as an integer vector that assigns weights to the different qualifications for the members in all team positions. In order to evaluate and compare potential teams, the manager needs to obtain the team score for each of them, which is the weighted sum of the individual qualifications.

Table of contents :

1 Introduction 
1.1 Tight Security
1.1.1 State of the Art in Tight Security
1.1.2 Contribution 1: Tightly CCA-Secure Encryption without Pairing
1.2 Functional Encryption
1.2.1 State of the Art in Functional Encryption
1.2.2 Contribution 2: Functional Encryption with New Features, and Richer Functionalities
1.2.3 Other contributions
2 Preliminaries 
2.1 Notations and Basics
2.1.1 Collision resistant hashing
2.1.2 Symmetric-Key Encryption
2.1.3 Authenticated Encryption
2.1.4 Public-Key Encryption
2.1.5 Key-Encapsulation Mechanism
2.2 Cryptographic Assumptions
2.2.1 Prime-Order Groups
2.2.2 Pairing Groups
2.2.3 Matrix Diffie-Hellman
2.2.4 Decisional Composite Residuosity
2.2.5 Learning With Errors
2.3 Definitions for Single-Input Functional Encryption
2.3.1 Security notions
2.4 Definitions for Multi-Input Functional Encryption
2.4.1 Security notions
2.4.2 Removing the extra condition generically
2.5 Definitions for Multi-Client Functional Encryption
2.6 Concrete Instances of Functional Encryption for Inner Products
2.6.1 Inner-Product FE from MDDH
2.6.2 Inner-Product FE from LWE
2.6.3 Inner-Product FE from DCR
3 Tightly CCA-Secure Encryption without Pairings 
3.1 Multi-ciphertext PCA-secure KEM
3.1.1 Our construction
3.1.2 Security proof
3.2 Multi-ciphertext CCA-secure Public Key Encryption scheme
3.2.1 Our construction
3.3 Security proof of PKE
4 Multi-Input Inner-Product Functional Encryption from Pairings 
4.1 Selectively-Secure, Private-Key MIFE for Inner Products
4.1.1 Selectively-secure, multi-input scheme from single-input scheme
4.1.2 Putting everything together
4.2 Achieving Adaptive Security
5 Multi-Input Inner-Product Functional Encryption without Pairings 
5.1 From Single to Multi-Input FE for Inner Product
5.1.1 Information-Theoretic MIFE with One-Time Security
5.1.2 Our Transformation for Inner Product over ZL
5.1.3 Our Transformation for Inner Product over Z
5.2 Concrete instances of FE for Inner Product
5.2.1 Inner Product FE from MDDH
5.2.2 Inner Product FE from LWE
5.2.3 Inner Product FE from DCR
6 Multi-Client Inner Product Functional Encryption 
6.1 MCFE with one-AD-IND-weak security
6.2 From one to many ciphertext for MCFE
6.3 Secret Sharing Encapsulation
6.3.1 Definitions
6.3.2 Construction of the Secret Sharing Encapsulation
6.4 Strengthening the Security of MCFE Using SSE
6.4.1 Generic construction of xx-AD-IND security for MCFE
6.5 Decentralizing MCFE
6.5.1 Distributed Sum
6.5.2 Our DSum Protocol
6.5.3 Security Analysis
6.5.4 Application to DMCFE for Inner Products
7 Functional Encryption for Quadratic Functions 
7.1 Private-key FE with one-SEL-IND security
7.2 Public-key FE
8 Conclusion 
8.1 Summary of the Contributions
8.2 Open Problems

GET THE COMPLETE PROJECT