DE BOER, Koen; DUCAS, Leo; PELLET-MARY, Alice; WESOLOWSKI, Benjamin

doi:10.1007/978-3-030-56880-1_9

La plateforme OSKAR Bordeaux évolue pour rejoindre l'archive ouverte HAL. Retrouvez tous vos dépôts sur le nouveau portail HAL UB : https://u-bordeaux.hal.science/. Pour toute aide ou information, contactez-nous info@oskar-bordeaux.fr

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

DE BOER, Koen
Centrum Wiskunde & Informatica [CWI]

DUCAS, Leo
Centrum Wiskunde & Informatica [CWI]

PELLET-MARY, Alice
Catholic University of Leuven = Katholieke Universiteit Leuven [KU Leuven]

Langue

Communication dans un congrès

Ce document a été publié dans

CRYPTO 2020, 2020-08-17, Santa Barbara.

Résumé en anglais

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 $\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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

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

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche