On lattices, learning with errors, random linear codes, and cryptography

By Oded Regev. JACM, 2009

1,327 citations recorded by the source corpus.

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 Õ(n2) and encrypting a message increases its size by a factor of Õ(n) (in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d47cc092877ba3c891bb013c68f469e80b770f3b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Predicting many properties of a quantum system from very few measurements (2020, background): “One of the most widely used conjectures for building post-quantum cryptography is the hardness of learning with error (LWE) [63].”
Compressible FHE with Applications to PIR (2019, methodology): “1 Just like GSW, the security of our scheme is based on the learning with errors assumption [Reg09] or its ring variant [LPR13].”
Privacy-preserving matrix factorization (2013, background): “We further assume that the recommender and CSP do not collude; the case of a malicious RecSys is discussed in Section 4.”
Quantum computing: A taxonomy, systematic review and future directions (2020, background): “The hardness of various schemes (like Ring-SIS, R-LWE) would be impacted with successful ideal lattice exploitation.”
A Survey on Homomorphic Encryption Schemes (2017, background): “A basis is called "good" if the basis vectors are almost orthogonal and, otherwise it is called "bad" basis of the lattice [Micciancio and Regev 2009].”
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography (2020, methodology): “Such self-reductions were described in [GPV08, ACPS09, Pei10] (the latter for discrete Gaussian error), based on the observation that they are just special cases of Regev’s core reduction [Reg05] from Bounded Distance Decoding (BDD) to LWE, and that LWE is an average-case BDD variant.”
Post-quantum cryptography (2008, neutral): “There are many potential attack avenues against NTRU and other lattice-based cryptosystems (such as cryptosystems based on “Ring-LWE” [17]).”
Private quantum computation: an introduction to blind quantum computing and related protocols (2016, background): “It should be noted, however, that even in the classical context this has only been achieved by making use of assumptions about the hardness of certain computational problems, such as the approximate shortest vector problem 56 or the learning with errors problem.(57) While for many cryptographic prob”
The power of localization for efficiently learning linear separators with noise (2013, background): “In the context of theoretical computer science more broadly, problems of noisy learning are r elated to seminal results in approximation-hardness [1, 27], cryp tographic assumptions [14, 39], and are connected to other classic que stions in learning theory (e.”
Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping (2017, methodology): “Distinguishing TLWE encryptions of 0 from random samples in TN [X]k × TN [X] is equivalent to the LWE problem initially defined by Regev [28] and its ring [25] and Scale invariant [6, 11, 13] variants.”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “Much of this progress has been greatly aided by the use of simple and flexible average-case problems — namely, the short integer solution (SIS) introduced by Ajtai [2] and the learning with errors (LWE ) problem of Regev [ 33 ] — that are provably as hard as certain lattice problems in the worst cas”