[Resource Topic] 2024/971: A Note on (2, 2)-isogenies via Theta Coordinates

Welcome to the resource topic for 2024/971

A Note on (2, 2)-isogenies via Theta Coordinates

Authors: Jianming Lin, Saiyu Wang, Chang-An Zhao


In this paper, we revisit the algorithm for computing chains of (2, 2)-isogenies between products of elliptic curves via theta coordinates proposed by Dartois et al. For each fundamental block of this algorithm, we provide a explicit inversion-free version. Besides, we exploit a novel technique of x-only ladder to speed up the computation of gluing isogeny. Finally, we present a mixed optimal strategy, which combines the inversion-elimination tool with the original methods together to execute a chain of (2, 2)-isogenies.

We make a cost analysis and present a concrete comparison between ours and the previously known methods for inversion elimination. Furthermore, we implement the mixed optimal strategy for benchmark. The results show that when computing $(2, 2)$-isogeny chains with lengths of 126,  208 and 632, compared to  Dartois, Maino,  Pope and Robert's original  implementation, utilizing our techniques can reduce $30.8\%$, $20.3\%$ and $9.9\%$  multiplications over the base field $\mathbb{F}_p$, respectively.  Even for the updated version which employs their inversion-free methods, our techniques still possess a slight advantage.

ePrint: https://eprint.iacr.org/2024/971

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 .