mlsanityData to 7 Oct 2026

Classical Hardness of Learning with Errors

arXiv 1306.0281 ↗First posted 3 Jun 2013cs.CC cs.CRcited by 11

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 3; 2024: 1; 2025: 3.

11 papers.

  1. 2022No Free Lunch Theorem for Security and Utility in Federated Learningcited by 39
  2. 2022SALSA: Attacking Lattice Cryptography with Transformerscited by 28
  3. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  4. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  5. 2023SALSA PICANTE: a machine learning attack on LWE with binary secretscited by 11
  6. 2024Sparse Linear Regression and Lattice Problemscited by 1
  7. 2023Towards Automated Homomorphic Encryption Parameter Selection with Fuzzy Logic and Linear Programmingcited by 0
  8. 2023A Provably Secure Strong PUF based on LWE: Construction and Implementationcited by 0
  9. 2025The informativeness of the gradient revisitedcited by 0
  10. 2025Exact Coset Sampling for Quantum Lattice Algorithmscited by 0
  11. 2025NoMod: A Non-modular Attack on Module Learning With Errorscited by 0