Cryptology ePrint Archive: Report 2021/245

On the Ideal Shortest Vector Problem over Random Rational Primes

Yanbin Pan and Jun Xu and Nick Wadleigh and Qi Cheng

Abstract: 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.

Category / Keywords: public-key cryptography / Ring-LWE, Ideal lattice, Average case computational complexity

Original Publication (with minor differences): IACR-EUROCRYPT-2021

Date: received 1 Mar 2021

Contact author: panyanbin at amss ac cn,xujun@iie ac cn,qcheng@ou edu,ndwadleigh@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210302:204441 (All versions of this report)

Short URL: ia.cr/2021/245


[ Cryptology ePrint archive ]