Paper 2026/2429
Rapid mixing in superspecial isogeny graphs
, École Normale Supérieure de Lyon, French National Centre for Scientific Research, École Normale Supérieure de Lyon, École Normale Supérieure de Lyon, French National Centre for Scientific ResearchAbstract
We prove expansion properties of superspecial isogeny graphs in dimension $g \geq 2$, including arbitrary level structure. In particular, we provide explicit bounds for the spectral gap, and a fine characterization of obstructions created by level structures (disconnectedness and periodicity). Without the level structure (the only case which was previously studied), our bounds dramatically improve the state of the art. These isogenies in dimension greater than one have become increasingly important in isogeny-based cryptography, and previous works have already conjectured consequences of their expansion properties. We present several applications of our result: we transform conjectural predecessors into rigorous algorithms, and we give the first algorithm for computing endomorphism rings of superspecial principally polarized abelian varieties in arbitrary dimension, with complexity $\tilde O(p^{g-1})$.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- isogeny-based cryptographyprincipally polarised abelian varietiesexpander graphs
- Contact author(s)
-
maria corte_real_santos @ ens-lyon fr
harun kir @ ens-lyon fr
olivier taibi @ ens-lyon fr
benjamin wesolowski @ ens-lyon fr - History
- 2026-10-12: approved
- 2026-10-09: received
- See all versions
- Short URL
- https://ia.cr/2026/2429
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2429,
author = {Maria Corte-Real Santos and Harun Kır and Olivier Taïbi and Benjamin Wesolowski},
title = {Rapid mixing in superspecial isogeny graphs},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2429},
year = {2026},
url = {https://eprint.iacr.org/2026/2429}
}
