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

IACR Communications in Cryptology

Simulatability versus Indistinguishability SOA: CCA Relations are Sampler-Dependent

Hans Heum

Published Jan 8, 2026• 0 citations
Publisher

Abstract

Contrary to expectation, we show that there is no general reduction from simulation-based selective opening security (SSO) to indistinguishability-based selective opening security (ISO) in the CCA setting. In particular, we show that when restricted to certain message distributions, SSO-CCA is incomparable with ISO-CCA. This contrasts the CPA case, where SSO-CPA is known to be strictly stronger than ISO-CPA relative to any message sampler. Any sampler with high enough min-entropy suffices for this “semi-separation” to appear. On the other hand, we show that restricting to distributions with very low min-entropy gives rise to an implication. Our main result does not rely on the presence of selective openings, but rather follow from subtleties in the game structures. At a glance, this may seem to contradict known equivalences between indistinguishability, semantic security, and selective opening security under trivial openings. We reconcile the apparent contradiction by showing that the CCA landscape splits into a “high-entropy” and a “low-entropy” world, which for notions of SOA must be treated separately.

DOI
10.62056/abbngyl7s

Related papers

Simulation-Based Selective Opening Security for Receivers under Chosen-Ciphertext Attacks.

Zhengan Huang, Junzuo Lai, Wenbin Chen +3 more

Security against selective opening attack (SOA) for receivers requires that in a multi-user setting, even if an adversary has access to all ciphertexts, and adaptively corrupts some fraction of the users to obtain the decryption keys corresponding to some of the ciphertexts, the remaining (potentially related) ciphertexts retain their privacy. In this paper, we study simulation-based selective opening security for receivers of public key encryption (PKE) schemes under chosen-ciphertext attacks (RSIM-SO-CCA). Concretely, we first show that some known PKE schemes meet RSIM-SO-CCA security. Then, we introduce the notion of master-key SOA security for identity-based encryption (IBE), and extend the Canetti–Halevi–Katz transformation to show generic PKE constructions achieving RSIM-SO-CCA security. Finally, we show how to construct an IBE scheme achieving master-key SOA security.

•Jan 1, 2018•0 citations

Public-Key Encryption with Tight Simulation-Based Selective-Opening Security

Lin Lyu, Shengli Liu, Shuai Han

In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012.

The Computer Journal•Aug 16, 2017•2 citations

Selective Opening Security for Receivers.

Carmit Hazay, Arpita Patra, Bogdan Warinschi

In a selective opening (SO) attack an adversary breaks into a subset of honestly created ciphertexts and tries to learn information on the plaintexts of some untouched (but potentially related) ciphertexts. Contrary to intuition, standard security notions do not always imply security against this type of adver-sary, making SO security an important standalone goal. In this paper we study receiver security, where the attacker is allowed to obtain the decryption keys corresponding to some of the ciphertexts. First we study the relation between two existing security definitions, one based on simulation and the other based on indistinguishability, and show that the former is strictly stronger. We continue with feasibility results for both notions which we show can be achieved from (variants of) non-committing encryption schemes. In particular, we show that indistinguishability-based SO security can be achieved from a tweaked variant of non-committing encryption which, in turn, can be instantiated from a variety of basic, well-established, assumptions. We conclude our study by showing that SO security is however strictly weaker than all variants of non-committing encryption that we consider, leaving potentially more efficient constructions as an interesting open problem.

•Jan 1, 2015•0 citations

Standard Security Does Imply Security Against Selective Opening for Markov Distributions.

Felix Heuer, Eike Kiltz, Krzysztof Pietrzak

About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are sampled independently from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.

•Jan 1, 2015•0 citations

Standard Security Does Not Imply Security Against Selective-Opening

Mihir Bellare Y, Rafael Dowsley, Brent R. Waters +1 more

We show that no commitment scheme that is hiding andbindingaccordingtothestandarddefinition is semantically-secure under selective opening attack (SOA), resolving a long-standing and fundamental open question about the power of SOAs. We also obtain the first examples of IND-CPA encryption schemesthatarenotsecureunderSOA, bothforsendercorruptionswhereencryptioncoinsare revealed and receiver corruptions where decryption keys are revealed. These results assume only the existence of collision-resistant hash functions.

•Jan 1, 2012•0 citations

Receiver Selective Opening CCA Secure Public Key Encryption from Various Assumptions

Yi Lu, Keisuke Hara, Keisuke Tanaka

Receiver selective opening (RSO) attack for public key encryption (PKE) captures a situation where one sender sends messages to multiple receivers, an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers' ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 15, 2021•0 citations
Contrary to expectation, we show that there is no general reduction from simulation-based selective opening security (SSO) to indistinguishability-based selective opening security (ISO) in the CCA setting. In particular, we show that when restricted to certain message distributions, SSO-CCA is incomparable with ISO-CCA. This contrasts the CPA case, where SSO-CPA is known to be strictly stronger than ISO-CPA relative to any message sampler. Any sampler with high enough min-entropy suffices for this “semi-separation” to appear. On the other hand, we show that restricting to distributions with very low min-entropy gives rise to an implication. Our main result does not rely on the presence of selective openings, but rather follow from subtleties in the game structures. At a glance, this may seem to contradict known equivalences between indistinguishability, semantic security, and selective opening security under trivial openings. We reconcile the apparent contradiction by showing that the CCA landscape splits into a “high-entropy” and a “low-entropy” world, which for notions of SOA must be treated separately.
Security against selective opening attack (SOA) for receivers requires that in a multi-user setting, even if an adversary has access to all ciphertexts, and adaptively corrupts some fraction of the users to obtain the decryption keys corresponding to some of the ciphertexts, the remaining (potentially related) ciphertexts retain their privacy. In this paper, we study simulation-based selective opening security for receivers of public key encryption (PKE) schemes under chosen-ciphertext attacks (RSIM-SO-CCA). Concretely, we first show that some known PKE schemes meet RSIM-SO-CCA security. Then, we introduce the notion of master-key SOA security for identity-based encryption (IBE), and extend the Canetti–Halevi–Katz transformation to show generic PKE constructions achieving RSIM-SO-CCA security. Finally, we show how to construct an IBE scheme achieving master-key SOA security.
In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012.
In a selective opening (SO) attack an adversary breaks into a subset of honestly created ciphertexts and tries to learn information on the plaintexts of some untouched (but potentially related) ciphertexts. Contrary to intuition, standard security notions do not always imply security against this type of adver-sary, making SO security an important standalone goal. In this paper we study receiver security, where the attacker is allowed to obtain the decryption keys corresponding to some of the ciphertexts. First we study the relation between two existing security definitions, one based on simulation and the other based on indistinguishability, and show that the former is strictly stronger. We continue with feasibility results for both notions which we show can be achieved from (variants of) non-committing encryption schemes. In particular, we show that indistinguishability-based SO security can be achieved from a tweaked variant of non-committing encryption which, in turn, can be instantiated from a variety of basic, well-established, assumptions. We conclude our study by showing that SO security is however strictly weaker than all variants of non-committing encryption that we consider, leaving potentially more efficient constructions as an interesting open problem.
About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are sampled independently from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.
We show that no commitment scheme that is hiding andbindingaccordingtothestandarddefinition is semantically-secure under selective opening attack (SOA), resolving a long-standing and fundamental open question about the power of SOAs. We also obtain the first examples of IND-CPA encryption schemesthatarenotsecureunderSOA, bothforsendercorruptionswhereencryptioncoinsare revealed and receiver corruptions where decryption keys are revealed. These results assume only the existence of collision-resistant hash functions.
Receiver selective opening (RSO) attack for public key encryption (PKE) captures a situation where one sender sends messages to multiple receivers, an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers' ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.