Events Summer 2022

Crypto+Lattices Talks

Wednesday, Jun. 22, 2022 4:00 pm5:00 pm PDT

Add to Calendar


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