Welcome to the resource topic for 2022/1259
Title:
Horizontal racewalking using radical isogenies
Authors: Wouter Castryck, Thomas Decru, Marc Houben, Frederik Vercauteren
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 by-passes 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 ad-hoc 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 non-trivial 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 speed-ups 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\%.
ePrint: https://eprint.iacr.org/2022/1259
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .