logo IMB
Retour

Séminaire de Théorie des Nombres

Random Self-reducibility of Ideal-SVP via Arakelov Random Walks

Alice Pellet-Mary

( IMB )

Salle de Conférences

le 28 mai 2021 à 14:00

The objective of this talk is to provide a worst case to average case reduction for the shortest vector problem in ideal lattices (ideal-SVP). More formally, the ideal-SVP problem asks, given as input an ideal of a number field (seen as a lattice), to find a soemhow short vector of the ideal. With our worst-case to average-case reduction, we show that, given as input any ideal, it is possible to re-randomize it in a way that any short vector of the rerandomized ideal can be transformed back into a short vector of the input ideal. In other words, this shows that in order to solve ideal-SVP for all lattices, it is sufficient to be able to solve it with non-negligible probability for a random ideal. The rerandomizetion procedure uses a random walk in the Arakelov class group, which was shown to provide a ``uniform'' ideal (for some appropriate definition of ``uniform''). This is a joint work with Koen de Boer, Léo Ducas and Benjamin Wesolowski