### The supersingular isogeny problem in genus 2 and beyond

Craig Costello and Benjamin Smith

##### Abstract

Let $A/\overline{\mathbb{F}}_p$ and $A'/\overline{\mathbb{F}}_p$ be supersingular principally polarized abelian varieties of dimension $g>1$. For any prime $\ell \ne p$, we give an algorithm that finds a path $\phi : A \rightarrow A'$ in the $(\ell, \dots , \ell)$-isogeny graph in $\widetilde{O}(p^{g-1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum computer. The idea is to find paths from $A$ and $A'$ to nodes that correspond to products of lower dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith) can be invoked to connect the paths in dimension $g=1$. In the general case where $A$ and $A'$ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where $A$ and $A'$ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over the quantum claw finding algorithms and an asymptotic improvement over the classical van Oorschot--Wiener algorithm.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Isogeniespost-quantum cryptographyabelian varietieselliptic-curve cryptography
Contact author(s)
smith @ lix polytechnique fr
History
2020-01-27: revised
See all versions
Short URL
https://ia.cr/2019/1387

CC BY

BibTeX

@misc{cryptoeprint:2019/1387,
author = {Craig Costello and Benjamin Smith},
title = {The supersingular isogeny problem in genus 2 and beyond},
howpublished = {Cryptology ePrint Archive, Paper 2019/1387},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1387}},
url = {https://eprint.iacr.org/2019/1387}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.