Paper 2022/1259

Horizontal racewalking using radical isogenies

Wouter Castryck, KU Leuven, Universiteit Gent
Thomas Decru, KU Leuven
Marc Houben, KU Leuven, Leiden University
Frederik Vercauteren, KU Leuven
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\%$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2022
Keywords
post-quantum 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
2022-09-26: approved
2022-09-22: received
See all versions
Short URL
https://ia.cr/2022/1259
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.