Paper 2021/1133
Multiradical isogenies
Wouter Castryck and Thomas Decru
Abstract
We argue that for all integers $N \geq 2$ and $g \geq 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k, \ldots, N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k \geq 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, \ldots, N^k)$-isogeny of the incoming $(N^{k-1}, \ldots, N^{k-1})$-isogeny. Our argumentation is heuristic, but we provide 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 $\approx 9$ in terms of speed.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- isogenyabelian varietyJacobianhash function
- Contact author(s)
- wouter castryck @ esat kuleuven be,thomas decru @ esat kuleuven be
- History
- 2021-12-01: last of 2 revisions
- 2021-09-07: received
- See all versions
- Short URL
- https://ia.cr/2021/1133
- License
-
CC BY