On Ideal Lattices and Learning with Errors over RingsOn Ideal Lattices and Learning with Errors over Rings

Access Restriction
Subscribed

 Author Lyubashevsky, Vadim ♦ Peikert, Chris ♦ Regev, Oded Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 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 The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called $\textit{ring-LWE},$ and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE. 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 2013-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 6 Page Count 35 Starting Page 1 Ending Page 35

Open content in new tab

Source: ACM Digital Library