Second Floor Lounge
Post-Quantum Insecurity from LWE
Speaker: Willy Quach.
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 was previously known for interactive protocols, due to the issue of rewinding.
We observe that this issue can also arise for some non-interactive primitives. Concretely, we give (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.
Based on joint work with Alex Lombardi, Ethan Mook, and Daniel Wichs