Paper 2022/869

Post-Quantum Insecurity from LWE

Alex Lombardi, Massachusetts Institute of Technology
Ethan Mook, Northeastern University
Willy Quach, Northeastern University
Daniel Wichs, Northeastern University, NTT Research
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/869}},
      url = {https://eprint.iacr.org/2022/869}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.