**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.

**Category / Keywords: **public-key cryptography / Isogenies; post-quantum cryptography; abelian varieties; elliptic-curve cryptography

**Date: **received 2 Dec 2019, last revised 27 Jan 2020

**Contact author: **smith at lix polytechnique fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20200127:161831 (All versions of this report)

**Short URL: **ia.cr/2019/1387

[ Cryptology ePrint archive ]