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

Koen de Boer; Léo Ducas; Alice Pellet-Mary; Benjamin Wesolowski

Paper 2020/297

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

Koen de Boer, Léo Ducas, Alice Pellet-Mary, and Benjamin Wesolowski

Abstract

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 -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 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.

Note: more details about Gentry's reduction

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in CRYPTO 2020
Keywords: Ideal Lattices Random Walk Worst-Case Hardness Arakelov L-functions
Contact author(s): K de Boer @ cwi nl
ducas @ cwi nl
alice pelletmary @ kuleuven be
benjamin wesolowski @ math u-bordeaux fr
History: 2020-09-08: last of 2 revisions; 2020-03-09: received; See all versions
Short URL: https://ia.cr/2020/297
License: CC BY

BibTeX

@misc{cryptoeprint:2020/297,
      author = {Koen de Boer and Léo Ducas and Alice Pellet-Mary and Benjamin Wesolowski},
      title = {Random Self-reducibility of Ideal-{SVP} via Arakelov Random Walks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/297},
      year = {2020},
      url = {https://eprint.iacr.org/2020/297}
}