Paper 2019/1387
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^{g1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g1}})$ 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 pathfinding algorithm (such as DelfsGalbraith) 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 OorschotWiener algorithm.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Isogeniespostquantum cryptographyabelian varietiesellipticcurve cryptography
 Contact author(s)
 smith @ lix polytechnique fr
 History
 20200127: revised
 20191204: received
 See all versions
 Short URL
 https://ia.cr/2019/1387
 License

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} }