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

Access Restriction
Subscribed

 Author Regev, Oded Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Lattice ♦ Average-case hardness ♦ Cryptography ♦ Public key encryption ♦ Quantum computation 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 $\textit{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 $Õ(\textit{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 $Õ(\textit{n}).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-09-08 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 6 Page Count 40 Starting Page 1 Ending Page 40

#### Open content in new tab

Source: ACM Digital Library