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
Computational security in cryptography has a risk that computational assumptions underlying the security are broken in the future. One solution is to construct information-theoretically-secure protocols, but many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. A nice compromise (intrinsic to quantum) is certified everlasting security, which roughly means the following. A receiver with possession of quantum encrypted data can issue a certificate that shows that the receiver has deleted the encrypted data. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded. Although several cryptographic primitives, such as commitments and zero-knowledge, have been made certified everlasting secure, there are many other important primitives that are not known to be certified everlasting secure. In this paper, we introduce certified everlasting FE. In this primitive, the receiver with the ciphertext of a message m and the functional decryption key of a function f can obtain f(m) and nothing else. The security holds even if the adversary becomes computationally unbounded after issuing a valid certificate. We, first, construct certified everlasting FE for P/poly circuits where only a single key query is allowed for the adversary. We, then, extend it to q-bounded one for NC1 circuits where q-bounded means that q key queries are allowed for the adversary with an a priori bounded polynomial q. For the construction of certified everlasting FE, we introduce and construct certified everlasting versions of secret-key encryption, public-key encryption, receiver non-committing encryption, and a garbling scheme, which are of independent interest.
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.
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