Welcome to the resource topic for 2023/1370
Title:
Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
Authors: Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski
Abstract: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 (below d^{O(d)} for cyclotomic fields, here d refers to the field degree). De Boer et al. [CRYPTO’20] obtained another random self-reducibility result for an average-case distribution involving integral ideals of norm 2^{O(d^2)}.
In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry’s reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of \emph{small-norm prime ideals}. Using the reduction from Pellet-Mary and Stehl'e [ASIACRYPT’21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.
ePrint: https://eprint.iacr.org/2023/1370
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 .