Paper 2022/1259
Horizontal racewalking using radical isogenies
Abstract
We address three main open problems concerning the use of radical isogenies, as presented by Castryck, Decru and Vercauteren at Asiacrypt 2020, in the computation of long chains of isogenies of fixed, small degree between elliptic curves over finite fields. Firstly, we present an interpolation method for finding radical isogeny formulae in a given degree $N$, which bypasses the need for factoring division polynomials over large function fields. Using this method, we are able to push the range for which we have formulae at our disposal from $N \leq 13$ to $N \leq 37$ (where in the range $18 \leq N \leq 37$ we have restricted our attention to prime powers). Secondly, using a combination of known techniques and adhoc manipulations, we derive optimized versions of these formulae for $N \leq 19$, with some instances performing more than twice as fast as their counterparts from 2020. Thirdly, we solve the problem of understanding the correct choice of radical when walking along the surface between supersingular elliptic curves over $\mathbb{F}_p$ with $p \equiv 7 \bmod 8$; this is nontrivial for even $N$ and was settled for $N = 2$ and $N = 4$ only, in the latter case by Onuki and Moriya at PKC 2022. We give a conjectural statement for all even $N$ and prove it for $N \leq 14$. The speedups obtained from these techniques are substantial: using $16$isogenies, the computation of long chains of $2$isogenies over $512$bit prime fields can be accelerated by a factor $3$, and the previous implementation of CSIDH using radical isogenies can be sped up by about $12\%$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2022
 Keywords
 postquantum cryptography isogenies modular curves CSIDH
 Contact author(s)

wouter castryck @ esat kuleuven be
thomas decru @ esat kuleuven be
marc houben @ kuleuven be
frederik vercauteren @ esat kuleuven be  History
 20220926: approved
 20220922: received
 See all versions
 Short URL
 https://ia.cr/2022/1259
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1259, author = {Wouter Castryck and Thomas Decru and Marc Houben and Frederik Vercauteren}, title = {Horizontal racewalking using radical isogenies}, howpublished = {Cryptology ePrint Archive, Paper 2022/1259}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1259}}, url = {https://eprint.iacr.org/2022/1259} }