Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Conference on Computational Complexity (CCC)

The Learning with Errors Problem (Invited Survey)

Oded Regev

Published Jun 1, 2010• 262 citations
Publisher

Abstract

In this survey we describe the Learning with Errors (LWE) problem, discuss its properties, its hardness, and its cryptographic applications.
DOI
10.1109/ccc.2010.26

Related papers

LWE-based Identification Schemes

Rosemberg Silva, Antonio C. de A. Campello, Ricardo Dahab

Some hard problems from lattices, like LWE (Learning with Errors), are particularly suitable for application in Cryptography due to the possibility of using worst-case to average-case reductions as evidence of strong security properties. In this work, we show two LWE-based constructions of zero-knowledge identification schemes and discuss their performance and security. We also highlight the design choices that make our solution of both theoretical and practical interest.

arXiv:1109.0631•Sep 3, 2011•1 citation

LWE-based identification schemes

Rosemberg Silva, Antonio C. de A. Campello, Ricardo Dahab

Some hard problems from lattices, like LWE (Learning with Errors), are particularly suitable for application in Cryptography due to the possibility of using worst-case to average-case reductions as evidence of strong security properties. In this work, we show two LWE-based constructions of zero-knowledge identification schemes and discuss their performance and security. We also highlight the design choices that make our solution of both theoretical and practical interest.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•7 citations

Classical hardness of learning with errors

Zvika Brakerski, Adeline Roux-Langlois, Chris Peikert +2 more

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•646 citations

Classical Hardness of Learning with Errors

Zvika Brakerski, Adeline Roux-Langlois, Chris Peikert +2 more

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.

arXiv:1306.0281•Jun 3, 2013•36 citations

On Advances of Lattice-Based Cryptographic Schemes and Their Implementations

Harshana Bandara, Yasitha Herath, Thushara Weerasundara +1 more

Lattice-based cryptography is centered around the hardness of problems on lattices. A lattice is a grid of points that stretches to infinity. With the development of quantum computers, existing cryptographic schemes are at risk because the underlying mathematical problems can, in theory, be easily solved by quantum computers. Since lattice-based mathematical problems are hard to be solved even by quantum computers, lattice-based cryptography is a promising foundation for future cryptographic schemes. In this paper, we focus on lattice-based public-key encryption schemes. This survey presents the current status of the lattice-based public-key encryption schemes and discusses the existing implementations. Our main focus is the learning with errors problem (LWE problem) and its implementations. In this paper, the plain lattice implementations and variants with special algebraic structures such as ring-based variants are discussed. Additionally, we describe a class of lattice-based functions called lattice trapdoors and their applications.

Cryptography•Nov 9, 2022•36 citations

Universal product learning with errors: A new variant of LWE for lattice-based cryptography

Shaojun Yang, Xinyi Huang

Theoretical Computer Science•Mar 1, 2022•11 citations
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.
Lattice-based cryptography is centered around the hardness of problems on lattices. A lattice is a grid of points that stretches to infinity. With the development of quantum computers, existing cryptographic schemes are at risk because the underlying mathematical problems can, in theory, be easily solved by quantum computers. Since lattice-based mathematical problems are hard to be solved even by quantum computers, lattice-based cryptography is a promising foundation for future cryptographic schemes. In this paper, we focus on lattice-based public-key encryption schemes. This survey presents the current status of the lattice-based public-key encryption schemes and discusses the existing implementations. Our main focus is the learning with errors problem (LWE problem) and its implementations. In this paper, the plain lattice implementations and variants with special algebraic structures such as ring-based variants are discussed. Additionally, we describe a class of lattice-based functions called lattice trapdoors and their applications.