In 2013, Boneh and Zhandry introduced the notion of indistinguishability (IND) in chosen plaintext (CPA) and chosen ciphertext (CCA) attacks by a quantum adversary which is given superposition access to an oracle for encryption and decryption queries but is restricted to classical queries in the challenge phase. In this paper we define IND-CPA and IND-CCA notions for symmetric encryption schemes where the adversary has full quantum superposition access to the oracle, and give constructions that achieve these security notions. Our results are formulated in the concrete security framework.
In 2013, Boneh and Zhandry introduced the notion of indistinguishability (IND) in chosen plaintext (CPA) and chosen ciphertext (CCA) attacks by a quantum adversary which is given superposition access to an oracle for encryption and decryption queries but is restricted to classical queries in the challenge phase. In this paper we define IND-CPA and IND-CCA notions for symmetric encryption schemes where the adversary has full quantum superposition access to the oracle, and give constructions that achieve these security notions. Our results are formulated in the concrete security framework.
Quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key requires a linear number of decryption queries. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.
Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong “quantum access” security models have shown that numerous symmetric-key cryptosystems are also vulnerable. In this paper, we consider classical encryption in a model that grants the adversary quantum oracle access to encryption and decryption, but where we restrict the latter to non-adaptive (i.e., pre-challenge) queries only. We formalize this model using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA 1 in analogy to the classical CCA 1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA 1 -secure when instantiated with quantum-secure primitives. Our security proofs use a strong bound on quantum random-access codes with shared randomness. Revisiting plain IND − CPA -secure Learning with Errors ( LWE ) encryption, we show that leaking only a single quantum decryption query (and no other leakage or queries of any kind) allows the adversary to recover the full secret key with constant success probability. Information-theoretically, full recovery of the key in the classical setting requires at least a linear number of decryption queries. Our results thus challenge the notion that LWE is unconditionally “just as secure” quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein–Vazirani algorithm. Finally, we emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.
Uncloneable decryptors are encryption schemes (with classical plaintexts and ciphertexts) with the added functionality of deriving uncloneable quantum states, called decryptors, which could be used to decrypt ciphers without knowledge of the secret key (Georgiou and Zhandry, IACR'20). We study uncloneable decryptors in the computational setting and provide increasingly strong security notions which extend the various indistinguishable security notions of symmetric encryption. We show that CPA secure uncloneable bit decryptors could be instantiated from a copy protection scheme (Aaronson, CCC'09) for any balanced binary function. We introduce a new notion of flip detection security for copy protection schemes inspired by the notions of left or right security for encryption schemes, and show that it could be used to instantiate CPA secure uncloneable decryptors for messages of unrestricted length. We then show how to strengthen the CPA security of uncloneable decryptors to CCA2 security using strong EUF-CMA secure digital signatures. We show that our constructions could be instantiated relative to either the quantum oracle used in [Aar09] or the classical oracle used in (Aaronson et al., CRYPTO'21) to instantiate copy protection schemes. Our constructions are the first to achieve CPA or CCA2 security in the symmetric setting.
In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes, originally initiated by Boneh and Zhandry (CRYPTO 2013, for a classical challenge indistinguishability phase) and imprioved by Gagliardoni et al. (CRYPTO 2016, for the symmetric key case). For public key encryption schemes, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by using so-called type-2 operators for encrypting the challenge message. This brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness during decryption. On the other hand, many real-world schemes suffer from a small probability of decryption failures. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that for these schemes the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural. We also observe that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, (4) study the general classification of quantum-resistant public key encryption schemes, and (5) compare our results to a concurrent and independent work by Chevalier et al. (2020).
We investigate the quantum security of nonce-based encryption under the indistinguishability against quantum chosen-plaintext attacks (IND-qCPA). While classical results establish that IV-based modes such as CBC, CFB, OFB, and CTR achieve IND-qCPA security, we demonstrate that simply replacing the random IV with a nonce undermines both classical and quantum security. To address this, we propose a general transformation from R-IND-qCPA security to N-IND-qCPA security and introduce enhanced variants, namely, CBC2, CFB2, OFB2, and CTR2, that are provably secure in the nonce-based quantum setting. We further show that nonce-based stream cipher encryption inherently satisfies N-IND-qCPA security. These results provide a systematic framework for upgrading IV-based constructions to secure nonce-based counterparts, thereby strengthening practical symmetric encryption against quantum adversaries.
Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that Sahai’s construction for SS-NIZK (in the CRS model) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.