## CryptoDB

### Paper: Random Self-reducibility of Ideal-SVP via Arakelov Random Walks

Authors: Koen de Boer , CWI Léo Ducas , CWI Alice Pellet-Mary , KU Leuven Benjamin Wesolowski , University of Bordeaux DOI: http://dx.doi.org/10.1007/978-3-030-56880-1_9 (login may be required) Search ePrint Search Google CRYPTO 2020 Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an Abelian group, called the *Arakelov class group*. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to significant cryptanalytic advances: the class group and the unit torus. In the present article, we show that the Arakelov class group has more to offer. We start with the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke L-functions, certain random walks on the Arakelov class group have a rapid mixing property. We then exploit this result to relate the average-case and the worst-case of the Shortest Vector Problem in ideal lattices. Our reduction appears particularly sharp: for Hermite-SVP in ideal lattices of certain cyclotomic number fields, it loses no more than a $\tilde O(\sqrt n)$ factor on the Hermite approximation factor. Furthermore, we suggest that this rapid-mixing theorem should find other applications in cryptography and in algorithmic number theory.
##### BibTeX
@inproceedings{crypto-2020-30425,
title={Random Self-reducibility of Ideal-SVP via Arakelov Random Walks},
publisher={Springer-Verlag},
doi={http://dx.doi.org/10.1007/978-3-030-56880-1_9},
author={Koen de Boer and Léo Ducas and Alice Pellet-Mary and Benjamin Wesolowski},
year=2020
}