Paper 2022/869
Post-Quantum Insecurity from LWE
Abstract
We show that for many fundamental cryptographic primitives, proving classical security under the learning-with-errors (LWE) assumption, does not imply post-quantum security. This is despite the fact that LWE is widely believed to be post-quantum secure, and our work does not give any evidence otherwise. Instead, it shows that post-quantum insecurity can arise inside cryptographic constructions, even if the assumptions are post-quantum secure. Concretely, our work provides (contrived) constructions of pseudorandom functions, CPA-secure symmetric-key encryption, message-authentication codes, signatures, and CCA-secure public-key encryption schemes, all of which are proven to be classically secure under LWE via black-box reductions, but demonstrably fail to be post-quantum secure. All of these cryptosystems are stateless and non-interactive, but their security is defined via an interactive game that allows the attacker to make oracle queries to the cryptosystem. The polynomial-time quantum attacker can break these schemes by only making a few classical queries to the cryptosystem, and in some cases, a single query suffices. Previously, we only had examples of post-quantum insecurity under post-quantum assumptions for stateful/interactive protocols. Moreover, there appears to be a folklore belief that for stateless/non-interactive cryptosystems with black-box proofs of security, a quantum attack against the scheme should translate into a quantum attack on the assumption. This work shows otherwise. Our main technique is to carefully embed interactive protocols inside the interactive security games of the above primitives. As a result of independent interest, we also show a 3-round quantum disclosure of secrets (QDS) protocol between a classical sender and a receiver, where a quantum receiver learns a secret message in the third round but, assuming LWE, a classical receiver does not.
Note: Fixed typos in Theorem 5.2 and Corollary 5.3.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2022
- Keywords
- Post-quantum security Quantum advantage
- Contact author(s)
-
alexjl @ mit edu
mook e @ northeastern edu
quach w @ northeastern edu
wichs @ ccs neu edu - History
- 2022-09-20: revised
- 2022-07-03: received
- See all versions
- Short URL
- https://ia.cr/2022/869
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/869,
author = {Alex Lombardi and Ethan Mook and Willy Quach and Daniel Wichs},
title = {Post-Quantum Insecurity from {LWE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/869},
year = {2022},
url = {https://eprint.iacr.org/2022/869}
}