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 : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral




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