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.
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.
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.
Quantum algorithms have demonstrated promising speed-ups over classical algorithms in the context of computational learning theory - despite the presence of noise. In this work, we give an overview of recent quantum speed-ups, revisit the Bernstein-Vazirani algorithm in a new learning problem extension over an arbitrary cyclic group and discuss applications in cryptography, such as the Learning with Errors problem. We turn to post-quantum cryptography and investigate attacks in which an adversary is given quantum access to a classical encryption scheme. In particular, we consider new notions of security under non-adaptive quantum chosen-ciphertext attacks and propose symmetric-key encryption schemes based on quantum-secure pseudorandom functions that fulfil our definitions. In order to prove security, we introduce novel relabeling techniques and show that, in an oracle model with an arbitrary advice state, no quantum algorithm making superposition queries can reliably distinguish between the class of functions that are randomly relabeled at a small subset of the domain. Finally, we discuss current progress in quantum computing technology, particularly with a focus on implementations of quantum algorithms on the ion-trap architecture, and shed light on the relevance and effectiveness of common noise models adopted in computational learning theory.
We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes poly(λ) queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most poly(λ) and the valid agreement probability is inverse-polynomial.
As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.
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.
Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, Ba˘etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of Ba˘etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.
To prevent eavesdropping and tampering, network security protocols take advantage of asymmetric ciphers to establish session-specific shared keys with which further communication is encrypted using symmetric ciphers. Commonly used asymmetric algorithms include public key encryption, key exchange, and identity-based encryption (IBE). However, network security protocols based on classic identity-based encryption schemes do not have perfect forward secrecy. To solve this problem, we construct the first quantum IBE (QIBE) scheme based on the learning with errors (LWE) problem, which is also the first cryptographic scheme that applies the LWE problem to quantum encryption. We prove that our scheme is fully secure under the random oracle model and highlight the following advantages: (1) Network security protocols with our QIBE scheme provide perfect forward secrecy. The ciphertext is transmitted in the form of a quantum state unknown to the adversary and cannot be copied and stored. Thus, in network security protocols based on QIBE construction, the adversary does not have any previous quantum ciphertext to decrypt for obtaining the previous session key, even if the private identity key is threatened. (2) Classic key generation centre (KGC) systems can still be used in the QIBE scheme to generate and distribute private identity keys, reducing the cost when implementing this scheme. The classic KGC systems can be used because the master public and secret keys of our scheme are both in the form of classic bits. Finally, we present quantum circuits to implement this QIBE scheme and analyse its required quantum resources for given numbers of qubits, Hadamard gates, phase gates, T gates, and CNOT (controlled-NOT) gates. One of our main findings is that the quantum resources required by our scheme increase linearly with the number of plaintext bits to be encrypted.