BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Worst-case to average-case reduction for lattice problems in a gen
 us \; and some perspectives for codes.
DTSTART:20261008T120000Z
DTEND:20261008T130000Z
DTSTAMP:20261003T074100Z
UID:indico-event-17462@indico.math.cnrs.fr
DESCRIPTION:Speakers: Maxime Bombar (Université de Bordeaux)\n\nRandom se
 lf-reducibility is a useful property of some cryptographic problems: it sh
 owsthat solving randomly distributed instances is as hard as solving any f
 ixed instance\,potentially adversarially chosen. Such results typically re
 ly on a randomizationprocedure\, and the main difficulty is to relate solu
 tions on the randomized instance backto the original input.\nIn this talk 
 I will present a random-walk procedure on the so-called Kneser (p)-neighbo
 rgraph of the (special) genus of a lattice. The crucial property is that t
 wo neighbors onlydiffer *locally* when looking at the completion at a give
 n prime\, and therefore stay closeenough to transfer instances of several 
 problems including (H)SVP\, BDD and other. At thesame time\, the walk equi
 distributes quickly. The mixing time is analyzed through spectralbounds fo
 r the associated Hecke operators.\nI will then discuss some potential adap
 tations to code-based problems.\nThis talk is based on a joint work with K
 oen de Boer\, Aurel Page and Wessel van Woerden which I hope will be onlin
 e by the time of the talk.\n\nhttps://indico.math.cnrs.fr/event/17462/
LOCATION:XR203 (XLIM)
URL:https://indico.math.cnrs.fr/event/17462/
END:VEVENT
END:VCALENDAR