CryptoDB
Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| 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, where d refers to the field degree). De Boer et al. [CRYPTO’20] btained 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 small-norm prime ideals. Using the reduction from Pellet-Mary and Stehlé [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. |
BibTeX
@inproceedings{tcc-2023-33387,
title={Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals},
publisher={Springer-Verlag},
author={Joël Felderhoff and Alice Pellet-Mary and Damien Stehlé and Benjamin Wesolowski},
year=2023
}