On Ideal Lattices and Learning with Errors over Rings

Vadim Lyubashevsky 1 Chris Peikert 2 Oded Regev 3
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
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 cryptosys- tem 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
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2013, 60 (6), 〈10.1145/2535925〉
Liste complète des métadonnées

Contributeur : Vadim Lyubashevsky <>
Soumis le : samedi 21 décembre 2013 - 13:45:41
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10




Vadim Lyubashevsky, Chris Peikert, Oded Regev. On Ideal Lattices and Learning with Errors over Rings. Journal of the ACM (JACM), Association for Computing Machinery, 2013, 60 (6), 〈10.1145/2535925〉. 〈hal-00921792〉



Consultations de la notice