Welcome to the resource topic for 2021/245
Title:
On the Ideal Shortest Vector Problem over Random Rational Primes
Authors: Yanbin Pan, Jun Xu, Nick Wadleigh, 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.
ePrint: https://eprint.iacr.org/2021/245
Talk: https://www.youtube.com/watch?v=FdXxnYr-hsQ
Slides: https://iacr.org/submit/files/slides/2021/eurocrypt/eurocrypt2021/240/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .