Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals

ePrint Report: Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals

Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski

The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO'10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm …

alice crypto eprint report foundation hard prime problem report security security foundation understand