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

Relaxing Chosen-Ciphertext Security.

Ran Canetti, Hugo Krawczyk, Jesper Buus Nielsen

Published Jan 1, 2003• 1 citation
OpenAlex

Abstract

Abstract. Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat too strong: there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure “for most practical purposes.” We propose a relaxed variant of CCA security, called Replayable CCA (RCCA) security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security. We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches, respectively. We show that the three formulations are equivalent in most interesting cases. 1

Related papers

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

On Modeling IND-CCA Security in Cryptographic Protocols.

Dennis Hofheinz, Jörn Müller‐Quade, Rainer Steinwandt

Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet “slightly” weaker than) securely realizing the ideal functionality FPKE in the general modeling of cryptographic protocols of [Can01a]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing FPKE (see [Can01a]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.

•Jan 1, 2003•23 citations

Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions

Ran Canetti, Huijia Lin, Rafael Pass

We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition- assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angelbased" framework of Prabhakaran and Sahai (STOC'04) and implies super-polynomial time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment-attacks (CCA security), means that security holds even if the attacker has access to a extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent non-malleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted set-up. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive requiring adaptive hardness from standard hardness assumptions, using no trusted set-up or public keys.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•90 citations

Chosen-Ciphertext Security via Correlated Products.

Alon Rosen, Gil Segev

Abstract We initiate the study of one-wayness under correlated products. We are interested in identify-ing necessary and sufficient conditions for a function f and a distribution on inputs (x1,..., xk),so that the function ( f (x1),..., f (xk)) is one-way. The main motivation of this study is theconstruction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCA). We show that any collection of injective trapdoor functions that is secure under a verynatural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security.We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functionsthat are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, weargue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of lossy trapdoor functions from trapdoor functions that aresecure under correlated products.

•Jan 1, 2008•0 citations

Chosen-Ciphertext Security via Correlated Products

Alon Rosen, Gil Segev

We initiate the study of one-wayness under correlated products. We are interested in identifying necessary and sufficient conditions for a function f and a distribution on inputs $(x_1,\dots,x_k)$ so that the function $(f(x_1),\dots,f(x_k))$ is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCAs). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork, and Naor [SIAM J. Comput., 30 (2000), pp. 391–437], while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions [Peikert and Waters, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 187–196] yield injective trapdoor functions that are secure under the above-mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.

SIAM Journal on Computing•Jan 1, 2010•37 citations

Chosen‐Ciphertext Security from Identity‐Based Encryption

Dan Boneh, Ran Canetti, Shai Halevi +1 more

We propose simple and efficient CCA‐secure public‐key encryption schemes (i.e., schemes secure against adaptive chosen‐ciphertext attacks) based on any identity‐based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and practical interest. First, our schemes give a new paradigm for achieving CCA‐security; this paradigm avoids “proofs of well‐formedness” that have been shown to underlie previous constructions. Second, instantiating our construction using known IBE constructions we obtain CCA‐secure encryption schemes whose performance is competitive with the most efficient CCA‐secure schemes to date. Our techniques extend naturally to give an efficient method for securing IBE schemes (even hierarchical ones) against adaptive chosen‐ciphertext attacks. Coupled with previous work, this gives the first efficient constructions of CCA‐secure IBE schemes.

SIAM Journal on Computing•Dec 21, 2006•415 citations
Abstract. Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat too strong: there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure “for most practical purposes.” We propose a relaxed variant of CCA security, called Replayable CCA (RCCA) security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security. We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches, respectively. We show that the three formulations are equivalent in most interesting cases. 1
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).
Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet “slightly” weaker than) securely realizing the ideal functionality FPKE in the general modeling of cryptographic protocols of [Can01a]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing FPKE (see [Can01a]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.
We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition- assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angelbased" framework of Prabhakaran and Sahai (STOC'04) and implies super-polynomial time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment-attacks (CCA security), means that security holds even if the attacker has access to a extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent non-malleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted set-up. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive requiring adaptive hardness from standard hardness assumptions, using no trusted set-up or public keys.
Abstract We initiate the study of one-wayness under correlated products. We are interested in identify-ing necessary and sufficient conditions for a function f and a distribution on inputs (x1,..., xk),so that the function ( f (x1),..., f (xk)) is one-way. The main motivation of this study is theconstruction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCA). We show that any collection of injective trapdoor functions that is secure under a verynatural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security.We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functionsthat are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, weargue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of lossy trapdoor functions from trapdoor functions that aresecure under correlated products.
We initiate the study of one-wayness under correlated products. We are interested in identifying necessary and sufficient conditions for a function f and a distribution on inputs (x1,…,xk)(x_1,\dots,x_k)(x1​,…,xk​) so that the function (f(x1),…,f(xk))(f(x_1),\dots,f(x_k))(f(x1​),…,f(xk​)) is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCAs). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork, and Naor [SIAM J. Comput., 30 (2000), pp. 391–437], while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions [Peikert and Waters, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 187–196] yield injective trapdoor functions that are secure under the above-mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.
We propose simple and efficient CCA‐secure public‐key encryption schemes (i.e., schemes secure against adaptive chosen‐ciphertext attacks) based on any identity‐based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and practical interest. First, our schemes give a new paradigm for achieving CCA‐security; this paradigm avoids “proofs of well‐formedness” that have been shown to underlie previous constructions. Second, instantiating our construction using known IBE constructions we obtain CCA‐secure encryption schemes whose performance is competitive with the most efficient CCA‐secure schemes to date. Our techniques extend naturally to give an efficient method for securing IBE schemes (even hierarchical ones) against adaptive chosen‐ciphertext attacks. Coupled with previous work, this gives the first efficient constructions of CCA‐secure IBE schemes.