Access Restriction

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

   Open content in new tab
Source: ACM Digital Library