Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2309.06702

Simulation-Secure Functional Encryption in the Bounded Storage Model

Mohammed Barhoush, Louis Salvail

Published Sep 13, 2023• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2309.06702

Related papers

On the Feasibility of Simulation-Secure Quantum Functional Encryption

Mohammed Barhoush, Arthur Mehta, Anne Müller +1 more

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.

cs.CRCross-listedarXiv:2601.17497•Jan 27, 2026•0 citations

An Adaptively Secure Functional Encryption for Randomized Functions

Muhua Liu, Ping Zhang

Abstract Functional encryption (FE) can provide a fine-grained access control on the encrypted message. Therefore, it has been applied widely in security business. The previous works about functional encryptions most focused on the deterministic functions. The randomized algorithm has wide application, such as securely encryption algorithms against chosen ciphertext attack, privacy-aware auditing. Based on this, FE for randomized functions was proposed. The existing constructions are provided in a weaker selective security model, where the adversary is forced to output the challenge message before the start of experiment. This security is not enough in some scenes. In this work, we present a novel construction for FE, which supports the randomized functionalities. We use the technology of key encapsulated mechanism to achieve adaptive security under the simulated environment, where the adversary is allowed to adaptively choose the challenge message at any point in time. Our construction is built based on indistinguishability obfuscation, non-interactive witness indistinguishable proofs and perfectly binding commitment scheme.

The Computer Journal•Nov 20, 2019•1 citation

Certified Everlasting Functional Encryption

Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki +1 more

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.

arXiv:2207.13878•Jul 28, 2022•4 citations

Selective Opening Secure Functional Encryption

Yuanyuan Ji, Haixia Xu, Peili Li

Functional encryption (FE) has more fine-grained control to encrypted data than traditional encryption schemes. The well-accepted security of FE is indistinguishability-based security (IND-FE) and simulation-based security (SIMFE), but the security is not sufficient.For example, if an adversary has the ability to access a vector of ciphertexts and can ask to open some information of the messages, such as coins used in the encryption or secret key in multikey setting, whether the privacy of the unopened messages is guaranteed.This is called selective opening attack (SOA).In this paper, we propose a stronger security of FE which is secure against SOA (we call SO-FE) and propose a concrete construction of SO-FE scheme in the standard model.Our scheme is a non-adaptive IND-FE which satisfies selective opening secure in the simulation sense.In addition, the scheme can encrypt messages of any bit length other than bitwise and it is secure against SOA-C and SOAK simultaneously while the two attacks were appeared in different model before.According to the different functionality f, our scheme can specialize as IBE, ABE and even PE schemes secure against SOA.

•Dec 28, 2015•0 citations

Practical CCA-Secure Functional Encryptions for Deterministic Functions

Huige Wang, Kefei Chen, Tianyu Pan +1 more

Functional encryption (FE) can implement fine-grained control to encrypted plaintext via permitting users to compute only some specified functions on the encrypted plaintext using private keys with respect to those functions. Recently, many FEs were put forward; nonetheless, most of them cannot resist chosen-ciphertext attacks (CCAs), especially for those in the secret-key settings. This changed with the work, i.e., a generic transformation of public-key functional encryption (PK-FE) from chosen-plaintext (CPA) to chosen-ciphertext (CCA), where the underlying schemes are required to have some special properties such as restricted delegation or verifiability features. However, examples for such underlying schemes with these features have not been found so far. Later, a CCA-secure functional encryption from projective hash functions was proposed, but their scheme only applies to inner product functions. To construct such a scheme, some nontrivial techniques will be needed. Our key contribution in this work is to propose CCA-secure functional encryptions in the PKE and SK environment, respectively. In the existing generic transformation from (adaptively) simulation-based CPA- (SIM-CPA-) secure ones for deterministic functions to (adaptively) simulation-based CCA- (SIM-CCA-) secure ones for randomized functions, whether the schemes were directly applied to CCA settings for deterministic functions is not implied. We give an affirmative answer and derive a SIM-CCA-secure scheme for deterministic functions by making some modifications on it. Again, based on this derived scheme, we also propose an (adaptively) indistinguishable CCA- (IND-CCA-) secure SK-FE for deterministic functions. The final results show that our scheme can be instantiated under both nonstandard assumptions (e.g., hard problems on multilinear maps and indistinguishability obfuscation (IO)) and under standard assumptions (e.g., DDH, RSA, LWE, and LPN).

Security and Communication Networks•Sep 8, 2020•1 citation

Secure Computation on Encrypted Data in Multi-User Systems

Robert Schädlich

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.

•Dec 2, 2025•0 citations
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.
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.
Abstract Functional encryption (FE) can provide a fine-grained access control on the encrypted message. Therefore, it has been applied widely in security business. The previous works about functional encryptions most focused on the deterministic functions. The randomized algorithm has wide application, such as securely encryption algorithms against chosen ciphertext attack, privacy-aware auditing. Based on this, FE for randomized functions was proposed. The existing constructions are provided in a weaker selective security model, where the adversary is forced to output the challenge message before the start of experiment. This security is not enough in some scenes. In this work, we present a novel construction for FE, which supports the randomized functionalities. We use the technology of key encapsulated mechanism to achieve adaptive security under the simulated environment, where the adversary is allowed to adaptively choose the challenge message at any point in time. Our construction is built based on indistinguishability obfuscation, non-interactive witness indistinguishable proofs and perfectly binding commitment scheme.
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.
Functional encryption (FE) has more fine-grained control to encrypted data than traditional encryption schemes. The well-accepted security of FE is indistinguishability-based security (IND-FE) and simulation-based security (SIMFE), but the security is not sufficient.For example, if an adversary has the ability to access a vector of ciphertexts and can ask to open some information of the messages, such as coins used in the encryption or secret key in multikey setting, whether the privacy of the unopened messages is guaranteed.This is called selective opening attack (SOA).In this paper, we propose a stronger security of FE which is secure against SOA (we call SO-FE) and propose a concrete construction of SO-FE scheme in the standard model.Our scheme is a non-adaptive IND-FE which satisfies selective opening secure in the simulation sense.In addition, the scheme can encrypt messages of any bit length other than bitwise and it is secure against SOA-C and SOAK simultaneously while the two attacks were appeared in different model before.According to the different functionality f, our scheme can specialize as IBE, ABE and even PE schemes secure against SOA.
Functional encryption (FE) can implement fine-grained control to encrypted plaintext via permitting users to compute only some specified functions on the encrypted plaintext using private keys with respect to those functions. Recently, many FEs were put forward; nonetheless, most of them cannot resist chosen-ciphertext attacks (CCAs), especially for those in the secret-key settings. This changed with the work, i.e., a generic transformation of public-key functional encryption (PK-FE) from chosen-plaintext (CPA) to chosen-ciphertext (CCA), where the underlying schemes are required to have some special properties such as restricted delegation or verifiability features. However, examples for such underlying schemes with these features have not been found so far. Later, a CCA-secure functional encryption from projective hash functions was proposed, but their scheme only applies to inner product functions. To construct such a scheme, some nontrivial techniques will be needed. Our key contribution in this work is to propose CCA-secure functional encryptions in the PKE and SK environment, respectively. In the existing generic transformation from (adaptively) simulation-based CPA- (SIM-CPA-) secure ones for deterministic functions to (adaptively) simulation-based CCA- (SIM-CCA-) secure ones for randomized functions, whether the schemes were directly applied to CCA settings for deterministic functions is not implied. We give an affirmative answer and derive a SIM-CCA-secure scheme for deterministic functions by making some modifications on it. Again, based on this derived scheme, we also propose an (adaptively) indistinguishable CCA- (IND-CCA-) secure SK-FE for deterministic functions. The final results show that our scheme can be instantiated under both nonstandard assumptions (e.g., hard problems on multilinear maps and indistinguishability obfuscation (IO)) and under standard assumptions (e.g., DDH, RSA, LWE, and LPN).
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.