# Classical Hardness of Learning with Errors

arXiv: https://arxiv.org/abs/1306.0281 · HTML: https://mlsanity.com/paper/1306.0281/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2013.

## Built on by (most cited first, 11 of 11)

- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [SALSA PICANTE: a machine learning attack on LWE with binary secrets](https://mlsanity.com/paper/2303.04178/) (2023)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)
- [Towards Automated Homomorphic Encryption Parameter Selection with Fuzzy Logic and Linear Programming](https://mlsanity.com/paper/2302.08930/) (2023)
- [A Provably Secure Strong PUF based on LWE: Construction and Implementation](https://mlsanity.com/paper/2303.02802/) (2023)
- [The informativeness of the gradient revisited](https://mlsanity.com/paper/2505.22158/) (2025)
- [Exact Coset Sampling for Quantum Lattice Algorithms](https://mlsanity.com/paper/2509.12341/) (2025)
- [NoMod: A Non-modular Attack on Module Learning With Errors](https://mlsanity.com/paper/2510.02162/) (2025)

## Abstract (arXiv)

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.