Abstract. Functional encryption (FE) is a powerful cryptographic primitive that generalizes many asymmetric encryption systems proposed in recent years. Syntax and security definitions for general FE were recently proposed by Boneh, Sahai, and Waters (BSW) (TCC 2011) and independently by O’Neill (ePrint 2010/556). In this paper we revisit these definitions, identify several shortcomings in them, and propose a new definitional approach that overcomes these limitations. Our definitions display good compositionality properties and allow us to obtain new feasibility and impossibility results for adaptive token-extraction attack scenarios that shed further light on the potential reach of general FE for practical applications. The main contributions of the paper are the following: – We show that the BSW definition of semantic security fails to reject intuitively insecure FE schemes where a ciphertext leaks more about an encrypted message than that which can be recovered from an image under the supported functionality. Our definition (as O’Neill’s) does not suffer from this problem. – We introduce an orthogonal notion of setup security that rejects all FE schemes where the master secret key may give unwanted power to the TA, allowing the recovery of extra information from images under the supported functionality. We prove FE schemes supporting all-or-nothing functionalities are intrinsically setup-secure and further show that many well-known functionalities are all-or-nothing.
Abstract. Functional encryption (FE) is a powerful cryptographic primitive that generalizes many asymmetric encryption systems proposed in recent years. Syntax and security definitions for general FE were recently proposed by Boneh, Sahai, and Waters (BSW) (TCC 2011) and independently by O’Neill (ePrint 2010/556). In this paper we revisit these definitions, identify several shortcomings in them, and propose a new definitional approach that overcomes these limitations. Our definitions display good compositionality properties and allow us to obtain new feasibility and impossibility results for adaptive token-extraction attack scenarios that shed further light on the potential reach of general FE for practical applications. The main contributions of the paper are the following: – We show that the BSW definition of semantic security fails to reject intuitively insecure FE schemes where a ciphertext leaks more about an encrypted message than that which can be recovered from an image under the supported functionality. Our definition (as O’Neill’s) does not suffer from this problem. – We introduce an orthogonal notion of setup security that rejects all FE schemes where the master secret key may give unwanted power to the TA, allowing the recovery of extra information from images under the supported functionality. We prove FE schemes supporting all-or-nothing functionalities are intrinsically setup-secure and further show that many well-known functionalities are all-or-nothing.
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
In recent years, there has been great interest in Functional Encryption (FE), a generaliza-tion of traditional encryption where a token enables a user to learn a specific function of the encrypted data and nothing else. In this paper we put forward a new generalization of FE that we call M ergeable FE (mFE). In a mFE system, given a ciphertext c1 encrypting m1 and a ciphertext c2 encrypting m2, it is possible to produce in an oblivious way (i.e., given only the public-key and without knowledge of the messages, master secret-key or any other aux-iliary information) a ciphertext encrypting the string m1||m2 under the security constraint that this new ciphertext does not leak more information about the original messages than what may be leaked from the new ciphertext using the tokens. For instance, suppose that the adversary is given the token for the function f(·) defined so that for strings x ∈ {0, 1}n, f(x) 4 = g(x) for some function g: {0, 1}n → {0, 1} and for strings y = (x1||x2) ∈ {0, 1}2n, f(x1||x2) 4 = g(x1) ∨ g(x2). Furthermore, suppose that the adversary gets a ciphertext c
Functional encryption (FE) is a powerful primitive enabling fine-grained access to encrypted data. In an FE scheme, secret keys (“tokens”) correspond to functions; a user in possession of a ciphertext ct = Enc(x) and a token TKf for the function f can compute f(x) but learn nothing else about x. An active area of research over the past few years has focused on the development of ever more expressive FE schemes. In this work we introduce the notion of multi-input functional encryption. Here, informally, a user in possession of a token TKf for an n-ary function f and multiple ciphertexts ct1 = Enc(x1), . . . , ctn = Enc(xn) can compute f(x1, . . . , xn) but nothing else about the {xi}. Besides introducing the notion, we explore the feasibility of multi-input FE in the public-key and symmetric-key settings, with respect to both indistinguishability-based and simulation-based definitions of security. ∗ACS. Email: sgordon@appcomsci.com. †Department of Computer Science, University of Maryland. Email: jkatz@cs.umd.edu. This research was sponsored by NSF award #1223623 and by the US Army Research Laboratory and the UK Ministry of Defence under Agreement Number W911NF-06-3-0001. ‡Department of Computer Science, University of Maryland. Email: fenghao@cs.umd.edu. §Department of Computer Science, University of Maryland. Email: elaine@cs.umd.edu. This work is partially supported by NSF award CNS-1314857 and a Google Research Award. ¶Department of Computer Science, Virginia Commonwealth University. Email: hszhou@vcu.edu. This work is partially supported by an NSF CI postdoctoral fellowship, and was mostly done while at the University of Maryland.
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 a functional encryption (FE) scheme, the owner of the secret key can generate restricted decryption keys that allow users to learn specific functions of the encrypted messages and nothing else. In many known constructions of FE schemes, such a notion of security is guaranteed only for messages that are fixed ahead of time (i.e., before the adversary even interacts with the system). This is called selective security, which is too restrictive for many realistic applications. Achieving adaptive security (also called full security), where security is guaranteed even for messages that are adaptively chosen at any point in time, seems significantly more challenging. The handful of known fully-secure schemes are based on specifically tailored techniques that rely on strong assumptions (such as obfuscation assumptions or multilinear maps assumptions). In this paper we show that any sufficiently expressive selectively-secure FE scheme can be transformed into a fully secure one without introducing any additional assumptions. We present a direct black-box transformation, making novel use of hybrid encryption, a classical technique that was originally introduced for improving the efficiency of encryption schemes, combined with a new technique we call the Trojan Method. This method allows to embed a secret execution thread in the functional keys of the underlying
Functional encryption is a powerful cryptographic primitive that enables fine-grained access to encrypted data and underlies numerous applications. Although the ideal security notion for FE, simulation security, has been shown to be impossible in the plain classical setting, those impossibility results rely on inherently classical arguments. This raises a fundamental question: can simulation-secure FE be realized in the quantum regime or in alternative models?
We resolve both directions of this question. On the negative side, we show that the classical impossibility results largely extend to the quantum setting. When the adversary can submit an unbounded number of challenge messages, we establish an unconditional impossibility, matching the classical barrier. In the case where the adversary may obtain many functional keys, classical arguments only yield impossibility under the assumption of pseudorandom functions; we strengthen this by proving impossibility under the potentially weaker assumption of pseudorandom quantum states. We additionally give an independent impossibility based solely on public-key encryption with classical public-keys. Since public-key encryption is not known to imply pseudorandom states, this yields complementary evidence of the barrier and, in particular, establishes unconditional impossibility of public-key functional encryption with classical public-keys. A key technical ingredient in our proofs is a novel incompressibility property for pseudorandom states, which may be of independent interest.
On the positive side, we show how to circumvent these fundamental barriers in memory-restricted models, where the adversary's quantum or classical memory is bounded. In this setting, we obtain new feasibility results for simulation-secure FE that allow many challenge ciphertexts or many functional key queries.