On Ideal Lattices and Learning with Errors over Rings
On Ideal Lattices and Learning with Errors over Rings
复制标题
DOI：
10.1145/2535925
复制
发表时间：
2013-11-01
影响因子：
2.5
通讯作者：
Regev, Oded
中科院分区：
文献类型：
--
作者：
Lyubashevsky, Vadim;Peikert, Chris;Regev, Oded
“带误差学习”（LWE）问题是将受到少量噪声干扰的随机线性方程组与真正均匀的线性方程组区分开来。这个问题已经被证明和最坏情况下的格问题一样困难，近年来它已经成为大量密码学应用的基础。不幸的是，这些应用程序是相当低效的，由于在使用LWE固有的二次开销。一个主要的开放问题是LWE及其应用程序是否可以利用额外的代数结构，真正有效的，是基于格的哈希函数（和相关的原语）。我们解决这个问题的肯定，通过引入一个代数变体LWE称为环LWE，并证明它也享有非常强的硬度保证。具体来说，我们证明了环LWE分布是伪随机的，假设理想格上的最坏情况下的问题是很难多项式时间量子算法。应用包括第一个真正实用的基于格的公钥密码系统，具有有效的安全性降低;此外，LWE的许多其他应用可以通过使用环LWE变得更加有效。
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.