One of the main lines of research in functional encryption (FE) has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. { TCC’11, O’Neill { ePrint’10] where it was rst shown that for FE the indistinguishabilitybased (IND) security notion is not sucient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. { CRYPTO’13] have shown strong impossibility results for SIM-Security. One way to overcome these impossibility results was rst
One of the main lines of research in functional encryption (FE) has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. { TCC’11, O’Neill { ePrint’10] where it was rst shown that for FE the indistinguishabilitybased (IND) security notion is not sucient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. { CRYPTO’13] have shown strong impossibility results for SIM-Security. One way to overcome these impossibility results was rst
Abstract. This work attempts to clarify to what extent simulationbased security (SIM-security) is achievable for functional encryption (FE) and its relation to the weaker indistinguishability-based security (INDsecurity). Our main result is a compiler that transforms any FE scheme for the general circuit functionality (which we denote by Circuit-FE) meeting indistinguishability-based security (IND-security) to a Circuit-FE scheme meeting SIM-security, where: – In the random oracle model, the resulting scheme is secure for an unbounded number of encryption and key queries, which is the strongest security level one can ask for. – In the standard model, the resulting scheme is secure for a bounded number of encryption and non-adaptive key queries, but an unbounded number of adaptive key queries. This matches known impossibility results and improves upon Gorbunov et al. [CRYPTO’12] (which is only secure for non-adaptive key queries).
In the recent years, functional encryption (FE) has received a lot of attention due to its versatility and unique challenges it poses. In FE, a receiver with secret-key sky can com-pute from an encryption of x the value F (y, x) for some functionality F. The seminal work of Boneh, Sahai and Waters [TCC’11] showed that for functional encryption the indistin-guishability notion of security (IND-Security) is weaker then simulation-based and, moreover, showed that simulation-based security is impossible to achieve even in weaker settings. This has opened up the door to a plethora of papers, showing feasibility and new impossibility re-sults, having in common the pursuit of a reasonable and achievable simulation-based security definition. With the same aim, in this work, we propose a new simulation-based security definition that we call rewinding simulation-based security (RSIM-Security). Rewinding arguments have been used in all sorts of interactive protocols and have been shown to be highly useful to argue security. We exploit this power allowing the simulator to rewind the adversary under specific constraints. Specifically, the simulator will be able to rewind the adversary
In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.
This work furthers the exploration of meaningful definitions for security of Functional Encryption. We propose new simulation based definitions for function privacy in addition to data privacy and study their achievability. In addition, we improve efficiency/ underlying assumptions/ security achieved by existing inner product Functional Encryption and Property Preserving Encryption schemes, in both the private and public key setting. Our results can be summarized as follows: • We present a new simulation based definition, which we call Relax-AD-SIM, that lies between simulation based (SIM) and indistinguishability based (IND) definitions for data privacy, and implies the function privacy definition of [BRS13a]. Our definition relaxes the requirements on the simulator to bypass impossibility of SIM in the standard model. We show that the inner product FE scheme of [KSW08] enjoys Relax-AD-SIM security for function hiding and the inner product FE scheme of [LOS10] enjoys Relax-AD-SIM security for data hiding. • We study whether known impossibilities for achieving strong SIM based security imply actual real world attacks. For this, we present a new UC-style SIM based definition of security that captures both data and function hiding, both public key and symmetric key settings and represents the “dream” security of FE. While known impossibilities rule out its achievability in the standard model, we show, surprisingly, that it can be achieved in the generic group model for Inner Product FE ([KSW08]). This provides evidence that FE implementations may enjoy extremely strong security against a large class of real world attacks, namely generic attacks. It also implies a program obfuscator for the inner product functionality in the generic group model, which is related to the hyperplane-membership obfuscator of [CRV10]. • We provide several improvements to known constructions of Inner Product FE. In the private key setting, the construction by Shen et al. was based on non-standard assumptions, used composite order groups, and only achieved selective security. We give the first construction of a symmetric key inner product FE which is built using prime order groups, and is fully secure under the standard DLIN assumption. Our scheme is more efficient in the size of key and ciphertext than [SSW09], when the latter is converted to prime-order groups. We also port the public key inner product scheme of [KSW08] to prime order groups. • We give the first standard model construction of a property preserving encryption (PPE) scheme [PR12] for inner-products. Our scheme is secure under the DLIN assumption and satisfies the strongest definition of security – Left-or-Right security. Note that previously known constructions were only known to be secure in the generic group model. ∗UIUC. Email: sagrawl2@illinois.edu. †I.I.T, Delhi. Email: shweta.a@gmail.com. ‡UIUC. Email: bsaikrishna7393@gmail.com. §UCLA Email: abishekk@cs.ucla.edu. ¶UIUC. Email: manojmp@gmail.com. ‖UCLA Email: sahai@cs.ucla.edu.
This paper explains that SS1-secure functional encryption (FE) as defined by Boneh, Sahai and Waters implicitly incorporates security under key-revealing selective opening attacks (SOA-K). This connection helps intuitively explain their impossibility results and also allows us to prove stronger ones. To fill this gap and move us closer to the (laudable) goal of a general and achievable notion of FE security, we seek and provide two “sans SOA-K ” definitions of FE security that we call SS2 and SS3. We prove various possibility results about these definitions. We view our work as a first step towards the challenging goal of a general, meaningful and achievable notion of FE security. 1
Functional encryption is an emerging paradigm for public-key encryption that enables finegrained control of access to encrypted data. In this work, we present new perspectives on security definitions for functional encryption, as well as new lower bounds on what can be achieved. Our main contributions are as follows: • We show a lower bound for functional encryption that satisfies a weak (non-adaptive) simulation-based security notion, via pseudo-random functions. This is the first lower bound that exploits unbounded collusions in an essential way. • We put forth and discuss a simulation-based notion of security for functional encryption, with an unbounded simulator (called USIM). We show that this notion interpolates indistinguishability and simulation-based security notions, and has strong correlations to results and barriers in the zero-knowledge and multi-party computation literature.