On the ideal shortest vector problem over random rational primes

2020/04/21 by Yanbin Pan, Pan, Yanbin, Jun Xu +5
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.CR #math.NT

paper · pdf · doi:10.48550/arxiv.2004.10278

arxiv created 2021/03/02 · arxiv updated 2021/03/03

Abstract

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²ⁿ + 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.

Related

• Subfield Algorithms for Ideal- and Module-SVP Based on the Decomposition Group
• A fast algorithm for finding a short generator of a principal ideal of ℚ(ζ_p^s)
• Embedding Integer Lattices as Ideals into Polynomial Rings
• Density of Ideal Lattices
• Public-key cryptosystems from the worst-case shortest vector problem