International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the ideal shortest vector problem over random rational primes

Authors:
Yanbin Pan , Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Jun Xu , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Nick Wadleigh , University of Oklahoma
Qi Cheng , University of Oklahoma
Download:
DOI: 10.1007/978-3-030-77870-5_20 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2021
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.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30816,
  title={On the ideal shortest vector problem over random rational primes},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77870-5_20},
  author={Yanbin Pan and Jun Xu and Nick Wadleigh and Qi Cheng},
  year=2021
}