Paper 2022/870 Original: eprint.iacr.org/2022/870 ↗

Computing \(2^a\)-isogenies in Legendre Form

Abstract

We introduce a method for efficiently computing $2^a$-isogenies in Legendre form with applications in post-quantum cryptography. An example of a secure application is the Charles-Goren-Lauter (CGL) hash function, which recently saw significant improvement in complexity by Doliskani et al. The majority of work on isogeny computation uses elliptic curves in Montgomery form; this includes the original work on SIDH by Jao, De Feo and Plût and the state of the art implementation of SIKE. Elliptic curves in twisted Edwards form have also been used due to their efficient elliptic curve arithmetic, and complete Edwards curves have been used for their benefit of providing added security against side channel attacks. As far as we know, elliptic curves in Legendre form have not yet been explored for isogeny-based cryptography. Legendre form has the benefit of a very simple defining equation, and the simplest possible representation of the $2$-torsion subgroup. In this work, we develop a new framework for constructing $2^a$-isogenies using elliptic curves in Legendre form, and in doing so optimize Legendre curve arithmetic and $2$-isogeny computations on Legendre curves by avoiding any square root computations.