### 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2022
Keywords
Contact author(s)
alexjl @ mit edu
mook e @ northeastern edu
quach w @ northeastern edu
wichs @ ccs neu edu
History
2022-09-20: revised
See all versions
Short URL
https://ia.cr/2022/869

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.