Functional encryption is an important generalization of several types of encryption such as publickey, identity-based, and attribute-based encryption. Numerous different security definitions for functional encryption have been proposed, most of them being rather complex and involving several algorithms. Many of these definitions differ in details such as which algorithm has oracle access to which oracle, while the consequences of specific choices are often unclear. This spans a large space of possible definitions without a consensus on the adequacy of specific points in this space. What a particular definition means and for which applications it is suitable remains unsettled. To remedy this situation, we propose a novel interpretation of functional encryption, based on the Constructive Cryptography framework, in which a protocol is seen as a construction of an ideal resource with desired properties from a real resource, which is assumed to be available. The resulting ideal resource can then be used as a real resource in other protocols to construct more advanced resources. The real resource we consider here corresponds to a public repository that allows everyone to read its contents. Such repositories are indeed widely available on the internet. Using functional encryption, we construct, as the ideal resource, a repository with fine-grained access control. Based on this constructive viewpoint, we propose a new security definition, called FA-security, for functional encryption by adequately modifying an established definition, and prove the equivalence to our notion of construction. This gives evidence that FA-security is an appropriate definition. We further consider known impossibility results and examine a weaker security definition. We show that this weaker definition, for which secure schemes exist, is sufficient to construct a repository that restricts the number and order of interactions. This makes explicit how such schemes can be used. 1
Functional encryption is an important generalization of several types of encryption such as publickey, identity-based, and attribute-based encryption. Numerous different security definitions for functional encryption have been proposed, most of them being rather complex and involving several algorithms. Many of these definitions differ in details such as which algorithm has oracle access to which oracle, while the consequences of specific choices are often unclear. This spans a large space of possible definitions without a consensus on the adequacy of specific points in this space. What a particular definition means and for which applications it is suitable remains unsettled. To remedy this situation, we propose a novel interpretation of functional encryption, based on the Constructive Cryptography framework, in which a protocol is seen as a construction of an ideal resource with desired properties from a real resource, which is assumed to be available. The resulting ideal resource can then be used as a real resource in other protocols to construct more advanced resources. The real resource we consider here corresponds to a public repository that allows everyone to read its contents. Such repositories are indeed widely available on the internet. Using functional encryption, we construct, as the ideal resource, a repository with fine-grained access control. Based on this constructive viewpoint, we propose a new security definition, called FA-security, for functional encryption by adequately modifying an established definition, and prove the equivalence to our notion of construction. This gives evidence that FA-security is an appropriate definition. We further consider known impossibility results and examine a weaker security definition. We show that this weaker definition, for which secure schemes exist, is sufficient to construct a repository that restricts the number and order of interactions. This makes explicit how such schemes can be used. 1
Functional encryption (FE) is an advanced form of traditional public-key encryption that enables complex computations to be performed directly on encrypted data, revealing only the final result of the computation. This thesis presents new constructions for two variants of FE, targeting specific limitations of the standard FE model. The proposed schemes advance the state of the art along (a subset of) the axes expressiveness, security, computational assumptions, and efficiency.First, standard FE requires encrypting the entire input in one shot. In practice, however, it may be desirable to encrypt portions of the data independently, for example at separate locations or by different parties. To address this, we study the multi-client extension of FE, focusing on attribute-based functionalities that provide fine-grained access control to data. Our constructions support a range of policy classes, including \NC0 and conjunction policies, and achieve varying levels of security assuming matrix DDH on pairings, LWE, or public-coin evasive LWE.Second, standard FE relies on a trusted authority to issue secret keys, which is often difficult to implement and undesirable in decentralized environments. To overcome this, we investigate the recently introduced primitive of registered functional encryption (RFE). In RFE, each user independently generates a public/secret key pair and registers their public key along with a function to an auditable key curator. We provide two types of results: constructions for restricted function classes under the standard matrix DDH assumption, and schemes supporting powerful function classes---including both unbounded depth circuits and Turing machines---under a nonstandard lattice-based assumption. Notably, we study RFE for uniform models of computation for the first time in the literature.
Abstract. A receiver-anonymous channel allows a sender to send a message to a receiver without an adversary learning for whom the message is intended. Wireless broadcast channels naturally provide receiver anonymity, as does multi-casting one message to a receiver population containing the intended receiver. While anonymity and confidentiality appear to be orthogonal properties, making anonymous communication confidential is more involved than one might expect, since the ciphertext might reveal which public key has been used to encrypt. To address this problem, public-key cryptosystems with enhanced security properties have been proposed. We investigate constructions as well as limitations for preserving receiver anonymity when using public-key encryption (PKE). We use the constructive cryptography approach by Maurer and Renner and interpret cryptographic schemes as constructions of a certain ideal resource (e.g. a confidential anonymous channel) from given real resources (e.g. a broadcast channel). We define appropriate anonymous communication resources and show that a very natural resource can be constructed by using a PKE scheme which fulfills three properties that appear in cryptographic literature (IND-CCA, key-privacy, weak robustness). We also show that a desirable stronger variant, preventing the adversary from selective “trial-deliveries ” of messages, is unfortunately unachievable by any PKE scheme, no matter how strong. The constructive approach makes the guarantees achieved by applying a cryptographic scheme explicit in the constructed (ideal) resource; this specifies the exact requirements for the applicability of a cryptographic scheme in a given context. It also allows to decide which of the existing security properties of such a cryptographic scheme are adequate for the considered scenario, and which are too weak or too strong. Here, we show that weak robustness is necessary but that so-called strong robustness is unnecessarily strong in that it does not construct a (natural) stronger resource.
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.
Functional encryption (FE) is a versatile paradigm that enables fine-grained access control over encrypted data. Despite its potential, achieving the gold standard of simulation-based security for FE is impossible in full generality. Known impossibility results demonstrate that simulation security cannot be attained if an adversary in the security experiment is permitted either an unbounded number of functional key queries or an unbounded number of challenge ciphertexts. In this work, we circumvent these fundamental barriers by considering two distinct memory-restricted settings: the Bounded Quantum Storage Model and the Bounded Classical Storage Model. In these settings, the plain model impossibility results no longer apply, allowing us to obtain new positive results. Specifically, we construct two adaptively simulation-secure FE schemes in the Bounded Quantum Storage Model: 1) Many functional key scheme: A construction supporting many functional key queries and a single challenge ciphertext, assuming only the existence of one-way functions. 2) Many ciphertext scheme: An information-theoretic secure construction supporting a single non-adaptive functional key, many challenge ciphertexts, and many adaptive functional key queries. Furthermore, we demonstrate that both schemes can be ported to the Bounded Classical Storage Model, assuming the existence of disappearing grey-box obfuscation.
Abstract We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption. Such a feature further broadens the practical applicability of the functional encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care for the security definition. Our contribution is threefold: We define our new primitive with a security notion in the indistinguishability setting. Within CUFE, functional decryption keysandciphertexts are labeled with tags such that only if the tags of the decryption key and the ciphertext match, then decryption succeeds. Furthermore, we allow ciphertexts to switch their tags to any other tag via update tokens. Such tokens are generated by the holder of the main secret key and can only be used in the desired direction. We present a generic construction of CUFE for any functionality as well as predicates different from equality testing on tags which relies on the existence of indistinguishability obfuscation (iO). We present a practical construction of CUFE for the inner-product functionality from standard assumptions (i.e., LWE) in the random-oracle model. On the technical level, we build on the recent functional encryption schemes with fine-grained access control and linear operations on encrypted data (Abdalla et al., AC’20) and introduce an additional ciphertext updatability feature. Proving security for such a construction turned out to be non-trivial, particularly when revealing keys for the updated challenge ciphertext is allowed. Overall, such construction enriches the set of known inner-product functional encryption schemes with the additional updatability feature of ciphertexts.
Functional encryption provides fine-grained access control for encrypted data, allowing each user to learn only specific functions of the encrypted data. We study the notion of hierarchical functional encryption, which augments functional encryption with delegation capabilities, offering significantly more expressive access control. We present a generic transformation that converts any general-purpose public-key functional encryption scheme into a hierarchical one without relying on any additional assumptions. This significantly refines our understanding of the power of functional encryption, showing that the existence of functional encryption is equivalent to that of its hierarchical generalization. Instantiating our transformation with the existing functional encryption schemes yields a variety of hierarchical schemes offering various trade-offs between their delegation capabilities (i.e., the depth and width of their hierarchical structures) and underlying assumptions. When starting with a scheme secure against an unbounded number of collusions, we can support arbitrary hierarchical structures. In addition, even when starting with schemes that are secure against a bounded number of collusions (which are known to exist under rather minimal assumptions such as the existence of public-key encryption and shallow pseudorandom generators), we can support hierarchical structures of bounded depth and width.