Classical Hardness of Learning with Errors

Abstract

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

Preliminary version in STOC'13

Cited by in corpus (6)

• Computing-in-Memory for Performance and Energy Efficient Homomorphic Encryption
• Non-interactive classical verification of quantum computation
• On estimating the entropy of shallow circuit outputs
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ${\ell }_p$ norm
• The Systematic Normal Form of Lattices
• Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling