A Caltech Library Service

On Quantum Chosen-Ciphertext Attacks and Learning with Errors

Alagic, Gorjan and Jeffery, Stacey and Ozols, Maris and Poremba, Alexander (2020) On Quantum Chosen-Ciphertext Attacks and Learning with Errors. Cryptography, 4 (1). Art. No. 10. ISSN 2410-387X. doi:10.3390/cryptography4010010.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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 QCCA1 in analogy to the classical CCA1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA1 -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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ( Received: 16 December 2019; Accepted: 18 March 2020; Published: 21 March 2020. We thank Ronald de Wolf for helpful discussions, Jop Bri t for Lemma A1 and Peter Humphries for providing us with a simple proof of Lemma A2. GA is supported by National Science Foundation (NSF) grant CCF-1763736. SJ is supported by an NWO WISE Grant and NWO Veni Innovational Research Grant under project number 639.021.752. MO is supported by Leverhulme Trust Early Career Fellowship (ECF-2015-256). AP is partially supported by AFOSR YIP award number FA9550-16-1-0495, the IQIM—an NSF Physics Frontiers Center (NSF Grant PHY- 1733907), and the Kortschak Scholars program. Author Contributions: All authors contributed equally to this work. Conceptualization, G.A., S.J., M.O. and A.P.; formal analysis, G.A., S.J., M.O. and A.P.; writing—original draft preparation, G.A., S.J., M.O. and A.P.; writing—review and editing, G.A., S.J., M.O. and A.P. All authors have read and agreed to the published version of the manuscript. The authors declare no conflict of interest.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)639.021.752
Leverhulme TrustECF-2015-256
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Kortschak Scholars ProgramUNSPECIFIED
Subject Keywords:quantum chosen-ciphertext security; quantum attacks; key-recovery; learning with errors
Issue or Number:1
Record Number:CaltechAUTHORS:20200323-103442039
Persistent URL:
Official Citation:Alagic, G.; Jeffery, S.; Ozols, M.; Poremba, A. On Quantum Chosen-Ciphertext Attacks and Learning with Errors. Cryptography 2020, 4, 10.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102046
Deposited By: Tony Diaz
Deposited On:23 Mar 2020 17:54
Last Modified:16 Nov 2021 18:08

Repository Staff Only: item control page