论文标题
在理想的最短矢量问题上，随机理性素数
On the ideal shortest vector problem over random rational primes
论文作者
论文摘要
数字字段中的任何理想都可以分为主要理想的产品。在本文中，我们研究了$ \ z [x]/（x^{2^n} + 1）$的主要理想最短矢量问题（SVP），这是理想基于晶格的密码系统设计的流行选择。我们表明，大多数理性的素数都在主要的理想下，承认SVP多项式时间算法。尽管理想晶格的最短矢量问题是Ring-Lwe密码系统的安全性，但此工作并没有破坏Ring-Lwe，因为降低安全性是从最坏的情况下为理想的SVP到平均情况case ring-lwe，并且是单向的。
Any ideal in a number field can be factored into a product of prime ideals. In this paper we study the prime ideal shortest vector problem (SVP) in the ring $ \Z[x]/(x^{2^n} + 1) $, a popular choice in the design of ideal lattice based cryptosystems. 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 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.
