License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2019.1
URN: urn:nbn:de:0030-drops-103939
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10393/
Alagic, Gorjan ;
Jeffery, Stacey ;
Ozols, Maris ;
Poremba, Alexander
On Quantum Chosen-Ciphertext Attacks and Learning with Errors
Abstract
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.
BibTeX - Entry
@InProceedings{alagic_et_al:LIPIcs:2019:10393,
author = {Gorjan Alagic and Stacey Jeffery and Maris Ozols and Alexander Poremba},
title = {{On Quantum Chosen-Ciphertext Attacks and Learning with Errors}},
booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
pages = {1:1--1:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-112-2},
ISSN = {1868-8969},
year = {2019},
volume = {135},
editor = {Wim van Dam and Laura Mancinska},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10393},
URN = {urn:nbn:de:0030-drops-103939},
doi = {10.4230/LIPIcs.TQC.2019.1},
annote = {Keywords: quantum chosen-ciphertext security, quantum attacks, learning with errors}
}
|
Keywords: |
|
quantum chosen-ciphertext security, quantum attacks, learning with errors |
|
Collection: |
|
14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
31.05.2019 |
