Security Proofs and Reductions in Lattice Schemes
Understand worst-case to average-case reductions and what they mean for the security of lattice cryptosystems.
What Security Proofs Guarantee
A security proof for a cryptographic scheme is a formal mathematical argument showing that breaking the scheme implies solving an underlying hard problem. The proof does not guarantee absolute security; it shows that any efficient adversary against the scheme can be converted into an efficient solver for the hard problem. If the hard problem is intractable, the scheme is secure.
Regev's Reduction Revisited
Regev's seminal 2005 proof shows that a polynomial-time algorithm solving decisional LWE can be used to solve worst-case GapSVP (Gap Shortest Vector Problem) on n-dimensional lattices. The reduction is quantum: it uses a quantum sampling procedure to convert an LWE solver into a lattice solver. This means LWE is at least as hard as worst-case lattice problems under quantum computation.
All lessons in this course
- Learning With Errors: The Hard Problem
- NTRU: History, Design, and Security
- Ring-LWE and Module Lattices
- Security Proofs and Reductions in Lattice Schemes