Paper 2021/1133

Multiradical isogenies

Wouter Castryck and Thomas Decru

Abstract

We argue that for all integers $N\ge 2$ and $g\ge 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k,\dots ,N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k\ge 2$. The formulae are complete: each iteration involves the extraction of $g(g+1)/2$ different $N$th roots, whence the epithet multiradical, and by varying which roots are chosen one computes all $N^{g(g+1)/2}$ extensions to an $(N^k,\dots ,N^k)$-isogeny of the incoming $(N^{k-1},\dots ,N^{k-1})$-isogeny. Our group-theoretic argumentation is heuristic, but it is supported by concrete formulae for several prominent families. As our main application, we illustrate the use of multiradical isogenies by implementing a hash function from $(3,3)$-isogenies between Jacobians of superspecial genus-$2$ curves, showing that it outperforms its $(2,2)$-counterpart by an asymptotic factor $$ in terms of speed.