International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Post-Quantum Insecurity from LWE

Authors:
Alex Lombardi , MIT
Ethan Mook , Northeastern University
Willy Quach , Northeastern University
Daniel Wichs , Northeastern University and NTT Research
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: We show that for many fundamental cryptographic primitives, proving classical security under the learning-with-errors (LWE) assumption, does \emph{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 \emph{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 \emph{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.
BibTeX
@inproceedings{tcc-2022-32563,
  title={Post-Quantum Insecurity from LWE},
  publisher={Springer-Verlag},
  author={Alex Lombardi and Ethan Mook and Willy Quach and Daniel Wichs},
  year=2022
}