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 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. Finally, the algebraic structure of ring-LWE might lead to new cryptographic applications previously not known to be based on LWE. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2535925 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
ring-LWE distribution,Ideal Lattices,efficient security reduction,cryptographic application,extra algebraic structure,main open question,lattice-based hash function,algebraic variant,practical lattice-based public-key cryptosystem,worst-case lattice problem,worst-case problem | Journal | 60 |
Issue | ISSN | ISBN |
6 | 0004-5411 | 3-642-13189-1 |
Citations | PageRank | References |
250 | 9.79 | 46 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vadim Lyubashevsky | 1 | 1174 | 59.91 |
Chris Peikert | 2 | 3840 | 154.98 |
Oded Regev | 3 | 2322 | 133.33 |