Place : LIX, Salle Henri Poincaré
Title : The supersingular isogeny problem in genus 2 and beyond (with Craig Costello)
Abstract : Let A and A’ be superspecial principally polarized abelian varieties of dimension g > 1 over F_p. For any fixed prime \ell \not= ̸p, we give an algorithm that finds a path from A to A’ in the (\ell,…,\ell)-isogeny graph in \softO(p^{g-1}) group operations on a classical computer, and O(p^{(g-1)/2}) calls to a Grover oracle on a quantum computer. The idea is to find paths from A and A’ to nodes corresponding to products of lower-dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm 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 quantum claw-finding algorithms and the classical van Oorschot–Wiener algorithm.
