Worst-case to average-case reduction for lattice problems in a genus ; and some perspectives for codes.

par Dr Maxime Bombar (Université de Bordeaux)

jeudi 8 oct. 2026, 14:00 → 15:00 Europe/Paris

XR203 (XLIM)

Random self-reducibility is a useful property of some cryptographic problems: it shows
that solving randomly distributed instances is as hard as solving any fixed instance,
potentially adversarially chosen. Such results typically rely on a randomization
procedure, and the main difficulty is to relate solutions on the randomized instance back
to the original input.

In this talk I will present a random-walk procedure on the so-called Kneser (p)-neighbor
graph of the (special) genus of a lattice. The crucial property is that two neighbors only
differ *locally* when looking at the completion at a given prime, and therefore stay close
enough to transfer instances of several problems including (H)SVP, BDD and other. At the
same time, the walk equidistributes quickly. The mixing time is analyzed through spectral
bounds for the associated Hecke operators.

I will then discuss some potential adaptations to code-based problems.

This talk is based on a joint work with Koen de Boer, Aurel Page and Wessel van Woerden which I hope will be online by the time of the talk.