On lattices, learning with errors, random linear codes, and cryptography
Abstract
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ( n 2 ) and encrypting a message increases its size by a factor of Õ( n ) (in previous cryptosystems these values are Õ( n 4 ) and Õ( n 2 ), respectively). In fact, under the assumption that all parties share a random bit string of length Õ( n 2 ), the size of the public key can be reduced to Õ( n ).
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Key security relies on the hardness of the Learning with Errors (LWE) problem, which remains computationally infeasible even on a quantum computer.
“Key security relies on the hardness of the Learning with Errors (LWE) problem, and it will remain computationally infeasible even on a quantum computer”
From A hybrid encryption algorithm based on AES and Kyber for secure image protection in the post-quantum era (2026) · cites this paper as [60]
The Learning-With-Errors (LWE) problem, introduced by Regev, is the hardness assumption behind lattice-based cryptography.
“The Learning-With-Errors (LWE) problem, introduced by Regev [60], is the hardness assumption behind lattice-based cryptography.”
From A hybrid encryption algorithm based on AES and Kyber for secure image protection in the post-quantum era (2026) · cites this paper as [60]
Cites
<i>Quantum Computation and Quantum Information</i>
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895 · see citing works
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397 · see citing works
Bernstein, D. J., & Lange, T. (2017) · Nature · doi:10.1038/nature23461 · Cited by 1,242 · see citing works
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898 · see citing works
Efficient and Privacy-Enhanced Federated Learning for Industrial Artificial Intelligence
Hao, M., Li, H., Luo, X., Xu, G., Yang, H., & Liu, S. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2945367 · Cited by 569 · see citing works
A Systematic Review of Homomorphic Encryption and Its Contributions in Healthcare Industry
Munjal, K., & Bhatia, R. (2023) · Complex & Intelligent Systems · doi:10.1007/s40747-022-00756-z · Cited by 269 · see citing works
Cyber-physical defense in the quantum Era
Barbeau, M., & Garcia-Alfaro, J. (2022) · Scientific Reports · doi:10.1038/s41598-022-05690-1 · Cited by 22 · see citing works
Exploring Bitslicing Architectures for Enabling FHE-Assisted Machine Learning
Sinha, S., Saha, S., Alam, M., Agarwal, V., Chatterjee, A., Mishra, A., Khazanchi, D., & Mukhopadhyay, D. (2022) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2022.3204909 · Cited by 4 · see citing works
Post-Quantum Key Encapsulation Mechanisms: A Comparative Review of ML-KEM, BIKE, and HQC
Reazaei, P., Rashid, A. S. K., Mand, A. A., & Saberikamarposhti, M. (2026) · 2026 22nd IEEE International Colloquium on Signal Processing &amp; Its Applications (CSPA) · doi:10.1109/cspa68262.2026.11517877 · Cited by 1 · see citing works
Singh, P., Hasija, T., Ramkumar, K. R., & Kanika (2026) · Discover Computing · doi:10.1007/s10791-026-10577-0
“The Learning-With-Errors (LWE) problem, introduced by Regev [60], is the hardness assumption behind lat-tice-based cryptography.”
- Authors
- Regev, O.
- Affiliations
- Tel Aviv University (IL)
- Corresponding author
- Regev, Oded
- ORCID
- Regev, Oded
- Venue
- Journal of the ACM
- Published
- 2009-09
- Volume
- 56
- Issue
- 6
- Pages
- 1-40
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2007466965
- Cited by
- 2,315
- References
- 2
- Citations by year
- 2026: 258 · 2025: 303 · 2024: 251 · 2023: 232 · 2022: 219 · 2021: 181 · 2020: 162 · 2019: 136 · 2018: 102 · 2017: 90 · 2016: 70 · 2015: 79 · 2014: 71 · 2013: 54 · 2012: 41
- FWCI
- 37.89
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of the ACM (publishedVersion)
- Funders
- Sixth Framework Programme (15848)
- Army Research Office (DAAD19-03-1-0082)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Keywords
- lattice-based cryptography, learning with errors, random linear codes, worst-case hardness, quantum reduction, public-key cryptosystems, post-quantum cryptography, lattice problems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
