Afficher la notice abrégée

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

hal.structure.identifierCentrum Wiskunde & Informatica [CWI]
dc.contributor.authorDE BOER, Koen
hal.structure.identifierCentrum Wiskunde & Informatica [CWI]
dc.contributor.authorDUCAS, Leo
hal.structure.identifierCatholic University of Leuven = Katholieke Universiteit Leuven [KU Leuven]
dc.contributor.authorPELLET-MARY, Alice
hal.structure.identifierLithe and fast algorithmic number theory [LFANT]
dc.contributor.authorWESOLOWSKI, Benjamin
dc.date.accessioned2024-04-04T02:49:37Z
dc.date.available2024-04-04T02:49:37Z
dc.date.conference2020-08-17
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191837
dc.description.abstractEnFixing 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.
dc.language.isoen
dc.title.enRandom Self-reducibility of Ideal-SVP via Arakelov Random Walks
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-030-56880-1_9
dc.subject.halMathématiques [math]/Théorie des nombres [math.NT]
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleCRYPTO 2020
bordeaux.countryUS
bordeaux.conference.citySanta Barbara
bordeaux.peerReviewedoui
hal.identifierhal-02513308
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02513308v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=DE%20BOER,%20Koen&DUCAS,%20Leo&PELLET-MARY,%20Alice&WESOLOWSKI,%20Benjamin&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée