Project topics and materials
Get Complete Project Material File(s) Now! »
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.
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.
A MIFE for inner products provides a perfect solution for the above scenario that protects the privacy of the profiles while enabling managers to evaluate possible team configurations. MIFE encryption slots will correspond to different team positions. Each person’s profile will be a vector of her scores, which will be encrypted for the slot corresponding to the position she is qualified to hold. When a new project is established, the leading manager is granted a decryption key that is associated with an integer vector that assigns appropriate weight to each qualification of different team members. The manager can use this key to evaluate different combinations of people for the team while learning nothing more about the people’s profiles than the team score. A similar example is the construction of a complex machine that requires parts from different manufacturers. Each part is rated based on different quality characteristics and prices, which are all manufacturer’s proprietary information until a contract has been signed. The ultimate goal is to assemble a construction of parts that achieve a reasonable trade-off between quality and price. In order to evaluate different construction configurations, the company wants to compute cumulative score for each configuration that is a weighted sum over the quality rates and price of each of the parts.
State of the art for multi-input functional encryption. There are several construc-tions of MIFE schemes, which can be broadly classified as follows: (i) feasibility results for general circuits [GGG+14, BGJS15, AJ15, BKS16], and (ii) constructions for specific func-tionalities, notably comparison, which corresponds to order-revealing encryption [BLR+15]. Unfortunately, all of these constructions rely on indistinguishability obfuscation, single-input FE for circuits, or multilinear maps [GGH+13b, GGH13a], which we do not know how to instantiate under standard and well-understood cryptographic assumptions.2
A new construction of MIFE for inner products. In [AGRW17], we present a multi-input functional encryption scheme (MIFE) for inner products based on standard assumptions in prime-order bilinear groups. Our construction works for any polynomial number of encryp-tion slots and achieves adaptive security against unbounded collusion, while relying on standard polynomial hardness assumptions. Prior to this work, we did not even have a candidate for 3-slot MIFE for inner products in the generic bilinear group model. Our work is also the first MIFE scheme for a non-trivial functionality based on standard cryptographic assumptions, as well as the first to achieve polynomial security loss for a super-constant number of slots under falsifiable assumptions. Prior works required stronger non-standard assumptions such as indistinguishability obfuscation or multilinear maps. Later, in [ACF+18], we put forward a novel methodology to convert single-input functional encryption for inner products into multi-input schemes for the same functionality. Our transformation is surprisingly simple, general and efficient. In particular, it does not require pairings and it can be instantiated with all known single-input schemes. This leads to two main advances. First, we enlarge the set of assumptions this primitive can be based on, notably, obtaining new MIFEs for inner products from plain DDH, LWE, and Decisional Composite Residuosity. Second, we obtain the first MIFE schemes from standard assumptions where decryption works efficiently even for mes-sages of super-polynomial size. In this thesis, we strengthen the security of these constructions to handle corruption of the input slots. That is, to encrypt, each input slot i ∈ [n] requires an encryption key eki. We consider the private-key setting, where encryption keys remain secret.
This is actually more relevant than the public-key setting, where the encryption keys eki are revealed to everyone. Indeed, in such a case, anyone can encrypt arbitrary message for any input slot. That weakens security drastically, since a challenge ciphertext Enc(eki, mb) for mes-sage mbi, where b ←R {0, 1} is chosen by the security game, can be combined with encryption of arbitrary messages for the other input slots during decryption. That means that given even a single functional decryption key for a function f , one can learn f (∗, • • • , ∗, mbi, ∗, x • • • , ∗), where each ∗ can be any arbitrary message. This is simply too much information in most rel-evant use cases. Thus, we consider the setting where encryption keys eki aren’t public, which avoids precisely this kind of leakage of information. In the schemes presented in Chapter 4 and Chapter 5, the security holds even when some eki are corrupted. That means that even given eki for some slots i ∈ [n], the security remains for other slots j = i. This is an important security feature, since that means even colluding users cannot learn any information about the encrypted messages by other users. This is relevant to assume such collusions, since in a multi-input encryption scheme, users do not communicate with each other, and do not trust each other. This is a novelty compared to [AGRW17, ACF+18]. A summary of our results and prior works on functional encryption for inner products is shown in Figure 1.3.
multi-client functional encryption for inner products.
We now present another contribution of this thesis, which is an extension of multi-input func-tional encryption, where the encryption can additionally handle labels, which prevents mixing and matching different ciphertexts with different labels, thereby giving a stronger security notion. The labels are typically set to be time stamps, for the application we have in mind.
Definition of multi-client functional encryption. In multi-client functional encryption, as defined in [GGG+14, GKL+13], the single input x to the encryption procedure is bro-ken down into an input vector (x1, , x n) where the components are independent. An index i for each client and a (typically time-based) label ℓ are used for every encryption: (c1 = Enc(1, x1, ℓ), , c n = Enc(n, xn, ℓ)). Anyone owning a functional decryption key dkf , for an n-ary function f and multiple ciphertexts for the same label ℓ, c1 = Enc(1, x1, ℓ), , c n = Enc(n, xn, ℓ), can compute f (x1, , x n) but nothing else about the individual xi’s. The combination of ciphertexts generated for different labels does not give a valid global ciphertext and the adversary learns nothing from it. This is different from multi-input functional encryption, where every ciphertext for every slot can be combined with any other ciphertext for any other slot, and used with functional decryption keys to decrypt an exponential number of values, as soon as there is more than one ciphertext per slot. This “mix-and-match” feature is crucial for some of the applications of MIFE, such as building Indistinguishability Obfuscation [GGG+14]. However, it also means the information leaked about the underlying plaintext is too much for some applications. In the multi-client setting, however, since only ciphertexts with the same label can be combined for decryption, the information leaked about the encrypted messages is drastically reduced.
Decentralized multi-client functional encryption. While it allows independent genera-tion of the ciphertexts, multi-client functional encryption (like multi-input functional encryp-tion) still assumes the existence of a trusted third party who runs the Setup algorithm and distributes the functional decryption keys. This third party, if malicious or corrupted, can easily undermine any client’s privacy. We are thus interested in building a scheme in which such a third party is entirely taken out of the equation. In [CDG+18a], we introduce the no-tion of decentralized multi-client functional encryption, in which the authority is removed and the clients work together to generate appropriate functional decryption keys. We stress that the authority is not simply distributed to a larger number of parties, but that the resulting protocol is indeed decentralized : each client has complete control over their individual data and the functional keys they authorize the generation of.
A new decentralized multi-client functional encryption for inner products. In [CDG+18a], we give the first decentralized multi-client functional encryption from standard assumptions, for inner products. Security is proven using bilinear pairing groups, and handles corruption of input slots. We first give an efficient centralized scheme whose security does not take into account the information leaked when decrypting incomplete ciphertexts, that is, ciphertexts for some, but not all, slots i ∈ [n]. Moreover, this scheme is only secure when there is only one challenge ciphertext per pair (i, ℓ), where i ∈ [n] is an input slot, and ℓ is a label. The construction we give in Chapter 6 is a generalization of [CDG+18a] to encrypt vectors (instead of scalars in [CDG+18a]). Then, we deal with the limitation in the security model that requires for complete ciphertexts only. Our solution is quite generic, as this is an additional layer that is applied to the ciphertexts so that, unless the ciphertext is complete (with all the encrypted components), no information leaks about the individual ciphertexts, and thus on each component. This technique relies on a linear secret sharing scheme, hence the name Secret Sharing Encapsulation (SSE). It can also be seen as a decentralized version of Al l-Or-Nothing Transforms [Riv97, Boy99, CDH+00]. We propose a concrete instantiation in pairing-friendly groups, under the Decisional Bilinear Diffie-Hellman problem, in the ran-dom oracle model. This transformation works on any MCFE, and not only MCFE for inner products. Secondly, we show how another independent layer of single-input functional encryp-tion for inner products authorizes repetitions: more precisely, we remove the restriction of a unique input per client and per label. Finally, we propose an efficient decentralized algorithm to generate a sum of private inputs, which can convert an MCFE for inner products into a decentralized MCFE for inner products: this technique is inspired from [KDK11], and only applies to the functional decryption key generation algorithm, and so this is compatible with the two above conversions. The resulting scheme is completely decentralized, in the sense that users do not need a trusted third party, even for setting up parameters (they just need to agree on a specific pairing group and a hash function that will be used later). These techniques used to strengthen the security of MCFE, as well as decentralize the key generation and setup, appeared in [CDG+18b].
A use case. Consider a financial firm that wants to compute aggregates of several companies’ private data (profits, number of sales) so that it can better understand the dynamics of a sector. The companies may be willing to help the financial firm understand the sector as whole, or may be offered compensation for their help, but they don’t trust the financial firm or each other with their individual data. After setting up a DMCFE, each company encrypts its private data with a time-stamp label under its private key. Together, they can give the financial firm a decryption aggregation key that only reveals a sum on the companies’ private data weighted by public information (employee count, market value) for a given time-stamp. New keys can retroactively decrypt aggregates on old data.
Private stream aggregation (PSA). This notion, also referred to as Privacy-Preserving Aggregation of Time-Series Data, is an older primitive introduced by Shi et al. [SCR+11]. Even though it is quite similar to our target DMCFE scheme, PSA does not consider the possibility of adaptively generating different keys for different inner-product evaluations, but only enables the aggregator to compute the sum of the clients’ data for each time period. PSA also typically involves a Differential Privacy component, which has yet to be studied in the larger setting of DMCFE. Further research on PSA has focused on achieving new properties or better efficiency [CSS12, Emu17, JL13, LC13, LC12, BJL16] but not on enabling new functionalities.
Functional encryption for quadratic functions.
In [BCFG17], we build the first functional encryption scheme based on standard assump-tions that supports a functionality beyond inner products, or predicates. Our scheme al-lows to compute bilinear maps over the integers: messages are expressed as pairs of vectors (x, y) ∈ Zn × Zm, secret keys are associated with n • m coefficients αi,j , and decryption allows to compute i,j αi,j xiyj . Bilinear maps represent a very general class of quadratic functions that includes, for instance, multivariate quadratic polynomials. These functions have several practical applications. For instance, a quadratic polynomial can express many statistical func-tions (e.g. (weighted) mean, variance, covariance, root-mean-square), the Euclidean distance between two vectors, and the application of a linear or quadratic classifier (e.g., linear or quadratic regression).
In [DGP18], we implement a functional encryption scheme for bilinear maps to perform machine learning on encrypted data. Namely, a quadratic classifier is learned on plain data, then, a functional decryption key is generated for a function that corresponds to the quadratic classifier. Using functional encryption, users can encrypt data, and the owner of the functional decryption key can perform classification of the encrypted data, without ever decrypting the data. In particular, no information apart from the result of the classification4 is revealed about the encrypted data. In [DGP18], the quadratic classifier has an accuracy of 97 54% on MNIST data set of hand-written digits, where encryption and decryption only take a few seconds. In [BCFG17], we present a fully-secure construction whose security is proven in an idealized model, called the Generic Group Model (GGM), where the adversary cannot use the structure of the underlying pairing group. This is justified in practice, since for well-chosen elliptic curves, the only known attacks are generic, they do not use the structure of the underlying group. The security of the construction from [DGP18] also relies on the generic group model. In Chapter 7, we present the construction from [BCFG17] that is proven selectively-secure under standard assumptions, as opposed to relying on the generic group model. Note that [AS17, Lin17] concurrently exhibited functional encryption schemes supporting the evaluation of degree-2 polynomials, but on the arguably simpler private-key setting, where encryption requires a secret key. A comparison of existing functional encryption schemes for quadratic functions is given in Figure 7.1.
Other contributions
In this manuscript, we focus on presenting tightly-secure encryption, and functional encryption schemes. During this thesis, we have been also working on other topics, which led to papers accepted in peer-reviewed conferences. We give a brief description of these contributions here. A list of personal publications appears at the end of this manuscript.
• In [GMW15], we construct a lattice-based predicate encryption scheme for multi-dimensional range and multi-dimensional subset queries. Our scheme is selectively-secure and weakly attribute-hiding, and its security is based on the standard Learning With Errors (LWE) assumption. Multi-dimensional range and subset queries capture many interesting appli-cations pertaining to searching on encrypted data. To the best of our knowledge, these were the first lattice-based predicate encryption schemes for functionalities beyond IBE and inner products.
• In [CGW15], we present a modular framework for the design of efficient adaptively se-cure attribute-based encryption (ABE) schemes for a large class of predicates under the standard k-Lin assumption in prime-order groups; this is the first uniform treatment of dual system ABE across different predicates and across both composite and prime-order groups. Via this framework, we obtain concrete efficiency improvements for several ABE schemes. Our framework has three novel components over prior works: (i) new techniques for simulating composite-order groups in prime-order ones (ii) a refinement of prior en-codings framework for dual system ABE in composite-order groups (iii) an extension to weakly attribute-hiding predicate encryption (which includes anonymous identity-based encryption as a special case).
• In [GKW15], we initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parame-ters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.
• In [FGKO17], we build new Access Control Encryption (ACE), which is a novel paradigm for encryption which allows to control not only what users in the system are allowed to read but also what they are allowed to write. The original work of Damgård et al. [DHO16] introducing this notion left several open questions, in particular whether it is possible to construct ACE schemes with polylogarithmic complexity (in the number of possible identities in the system) from standard cryptographic assumptions. In this work we answer the question in the affirmative by giving (efficient) constructions of ACE for an interesting class of predicates which includes equality, comparison, interval membership, and more. We instantiate our constructions based both on standard pairing assumptions (SXDH) or more efficiently in the generic group model.
• In [AGRW17], we present a multi-input functional encryption scheme (MIFE) for inner products based on the k-Lin assumption in prime-order bilinear groups. Our construc-tion works for any polynomial number of encryption slots and achieves adaptive security against unbounded collusion, while relying on standard polynomial hardness assump-tions. Prior to this work, we did not even have a candidate for 3-slot MIFE for inner products in the generic bilinear group model. Our work is also the first MIFE scheme for a non-trivial functionality based on standard cryptographic assumptions, as well as the first to achieve polynomial security loss for a super-constant number of slots under falsifiable assumptions. Prior works required stronger non-standard assumptions such as indistinguishability obfuscation or multilinear maps.
• In [BCFG17], we present two practically efficient functional encryption schemes for a large class of quadratic functionalities. Specifically, our constructions enable the computation of so-called bilinear maps on encrypted vectors. This represents a practically relevant class of functions that includes, for instance, multivariate quadratic polynomials (over the integers). Our realizations work over asymmetric bilinear groups and are surprisingly efficient and easy to implement. For instance, in our most efficient scheme the public key and each ciphertext consists of 2n+1 and 4n+2 group elements respectively, where n is the dimension of the encrypted vectors, while secret keys are only two group elements. Our two schemes build on similar ideas, but develop them in a different way in order to achieve distinct goals. Our first scheme is proved (selectively) secure under standard assumptions, while our second construction is concretely more efficient and is proved (adaptively) secure in the generic group model. As a byproduct of our functional encryption schemes, we show new predicate encryption schemes for degree-two polynomial evaluations, where ciphertexts consist of only O(n) group elements. This significantly improves the O(n2) bound one would get from predicate encryption for inner products.
• In [ABGW17], we propose, implement, and evaluate fully automated methods for proving security of ABE in the Generic Bilinear Group Model ([BBG05, Boy08]), an idealized model which admits simpler and more efficient constructions, and can also be used to find attacks. Our method is applicable to Rational-Fraction Induced ABE, a large class of ABE that contains most of the schemes from the literature, and relies on a Master Theorem, which reduces security in the GGM to a (new) notion of symbolic security, which is amenable to automated verification using constraint- based techniques. We relate our notion of symbolic security for Rational-Fraction Induced ABE to prior notions for Pair Encodings. Finally, we present several applications, including automated proofs for new schemes.
• In [FG18], we focus on structure-preserving signatures on equivalence classes, or equivalence-class signatures for short (EQS), are signature schemes defined over bilinear groups whose messages are vectors of group elements. Signatures are perfectly randomizable and given a signature on a vector, anyone can derive a signature on any multiple of the vector; EQS thus sign projective equivalence classes. Applications of EQS include the first constant-size anonymous attribute-based credentials, efficient round-optimal blind sig-natures without random oracles and efficient access-control encryption. To date, the only existing instantiation of EQS is proven secure in the generic-group model. In this work we show that by relaxing the definition of unforgeability, which makes it efficiently verifiable, we can construct EQS from standard assumptions, namely the Matrix-Diffie-Hellman assumptions. We then show that our unforgeability notion is sufficient for most applications.
• In [GHKP18], We provide a structure-preserving signature (SPS) scheme with an (al-most) tight security reduction to a standard assumption. Compared to the state-of-the-art tightly secure SPS scheme of Abe et al. [AHN+17], our scheme has smaller signatures and public keys (of about 56%, resp. 40% of the size of signatures and public keys in Abe et al.’s scheme), and a lower security loss (of O(log Q) instead of O(λ), where λ is the se-curity parameter, and Q = poly(λ) is the number of adversarial signature queries). While our scheme is still less compact than structure-preserving signature schemes without tight security reduction, it significantly lowers the price to pay for a tight security reduction. In fact, when accounting for a non-tight security reduction with larger key (i.e., group) sizes, the computational efficiency of our scheme becomes at least comparable to that of non-tightly secure SPS schemes. Technically, we combine and refine recent existing works on tightly secure encryption and SPS schemes. Our technical novelties include a modular treatment (that develops an SPS scheme out of a basic message authentication code), and a refined hybrid argument that enables a lower security loss of O(log Q) (instead of O(λ)).
• In [ACF+18], we present new constructions of multi-input functional encryption (MIFE) schemes for the inner-product functionality that improve the state of the art solution of Abdalla et al. [AGRW17] in two main directions. First, we put forward a novel methodology to convert single-input functional encryption for inner products into multi-input schemes for the same functionality. Our transformation is surprisingly simple, general, and efficient. In particular, it does not require pairings and it can be instantiated with all known single-input schemes. This leads to two main advances. First, we enlarge the set of assumptions this primitive can be based on, notably obtaining new MIFEs for inner products from plain DDH, LWE and Composite Residuosity. Second, we obtain the first MIFE schemes from standard assumptions where decryption works efficiently even for messages of super-polynomial size. Our second main contribution is the first function-hiding MIFE scheme for inner products based on standard assumptions. To this end, we show how to extend the original, pairing-based, MIFE by Abdalla et al. [AGRW17] in order to make it function hiding, thus obtaining a function-hiding MIFE from the MDDH assumption.
• In [GKW18], we present a new public-key broadcast encryption scheme where both the ciphertext and secret keys consist of a constant number of group elements. Our result improves upon the work of Boneh, Gentry, and Waters [BGW05] in two ways: (i) we achieve adaptive security instead of selective security, and (ii) our construction relies on the decisional k-Linear Assumption in prime-order groups (as opposed to q-type assump-tions or subgroup decisional assumptions in composite-order groups); our improvements come at the cost of a larger public key. Finally, we show that our scheme achieves adap-tive security in the multi-ciphertext setting with a security loss that is independent of the number of challenge ciphertexts.
• In [CDG+18a], we consider a situation where multiple parties, owning data that have to be frequently updated, agree to share weighted sums of these data with some aggrega-tor, but where they do not wish to reveal their individual data, and do not trust each other. We combine techniques from Private Stream Aggregation (PSA) and Functional Encryption (FE), to introduce a primitive we call Decentralized Multi-Client Functional Encryption (DMCFE), for which we give a practical instantiation for inner products. This primitive allows various senders to non-interactively generate ciphertexts which support inner-product evaluation, with functional decryption keys that can also be generated non-interactively, in a distributed way, among the senders. Interactions are required during the setup phase only. We prove adaptive security of our constructions, while allowing corruptions of the clients, in the random oracle model.
Road-map. The rest of this thesis is organized as follows. In Chapter 2, we give the relevant background on public-key encryption and functional encryption, including security definitions and concrete assumptions that will be used throughout this thesis. In Chapter 3, we give our tightly CCA-secure encryption without pairings. Then, in Chapter 4, we present our multi-input functional encryption for inner products from pairings. In Chapter 5, we present our multi-input functional encryption for inner products without pairings. In Chapter 6, we exhibit our multi-client functional encryption for inner products. Finally, in Chapter 7, we present our functional encryption for quadratic functions, before concluding in Chapter 8.
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
