Paper 2021/245

On the Ideal Shortest Vector Problem over Random Rational Primes

Yanbin Pan, Jun Xu, Nick Wadleigh, and Qi Cheng


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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Ring-LWEIdeal latticeAverage case computational complexity
Contact author(s)
panyanbin @ amss ac cn
xujun @ iie ac cn
qcheng @ ou edu
ndwadleigh @ gmail com
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Yanbin Pan and Jun Xu and Nick Wadleigh and Qi Cheng},
      title = {On the Ideal Shortest Vector Problem over Random Rational Primes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/245},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.