Paper 2023/1370
Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
, Institut de Mathématiques de Bordeaux, Centre National de la Recherche Scientifique, Inria Bordeaux - Sud-Ouest Research CentreAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2023
- Keywords
- ideal SVPreductionself reducibility
- Contact author(s)
-
joel felderhoff @ ens-lyon fr
alice pellet-mary @ math u-bordeaux fr
damien stehle @ cryptolab co kr
benjamin wesolowski @ ens-lyon fr - History
- 2023-09-15: approved
- 2023-09-13: received
- See all versions
- Short URL
- https://ia.cr/2023/1370
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1370,
author = {Joël Felderhoff and Alice Pellet-Mary and Damien Stehlé and Benjamin Wesolowski},
title = {Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals},
howpublished = {Cryptology ePrint Archive, Paper 2023/1370},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1370}},
url = {https://eprint.iacr.org/2023/1370}
}
