On the Ideal Shortest Vector Problem over Random Rational Primes
On the Ideal Shortest Vector Problem over Random Rational Primes
复制标题
随机有理素数上的理想最短向量问题
DOI：
10.1007/978-3-030-77870-5_20
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Cheng, Qi
中科院分区：
文献类型：
--
作者：
Pan, Yanbin;Xu, Jun;Wadleigh, Nick;Cheng, Qi
数域中的任何非零理想都可以分解为素理想的乘积。在本文中，我们报告了一个令人惊讶的连接之间的复杂性的最短向量问题（SVP）的素理想在数域和他们的分解群。当将结果应用于基于格的密码系统中流行的数域时，例如幂2分圆域，我们表明大多数有理素数位于允许SVP的多项式时间算法的素理想之下。虽然理想格的最短向量问题支撑了Ring-LWE密码系统的安全性，但这项工作并没有破坏Ring-LWE，因为安全性降低是从最坏情况的理想SVP到平均情况的Ring-LWE，并且它是单向的。
Any non-zero ideal in a number field can be factored into a product of prime ideals. In this paper we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields popular in lattice based cryptosystems, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of the Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.