February 21st at 1:30pm
For efficiency reasons, a lot of widely used lattice-based cryptosystems use structured lattices (e.g. module lattices over power-of-two cyclotomics of rank >=2). A way to study those structured lattices is to study an easier version of them: rank-1 module lattices, or ideal lattices. The problem of finding a short vector in them is Ideal-SVP. We will be interested in Ideal-SVP, where the input ideal is sampled from a certain distribution. 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. De Boer et al. [CRYPTO’20] obtained another random self-reducibility result for an average-case distribution involving integral ideals of large norm. In this presentation, we will prove that solving Ideal-SVP for small-norm prime uniform prime ideal is as hard as solving Ideal-SVP in the worst-case.
Campus de la Plaine, N/O building, 8th floor, salle rotule
