Paper 2025/691

Let us walk on the 3-isogeny graph: efficient, fast, and simple

Abstract

Constructing and implementing isogeny-based cryptographic primitives is an active research. In particular, performing length-$n$ isogenies walks over quadratic field extensions of $\mathbb{F}_p$ plays an exciting role in some constructions, including Hash functions, Verifiable Delay Functions, Key-Encapsulation Mechanisms, and generic proof systems for isogeny knowledge. Remarkably, many isogeny-based constructions, for efficiency, perform $2$-isogenies through square root calculations. This work analyzes the idea of using $3$-isogenies instead of $2$-isogenies, which replaces the requirement of calculating square roots with cube roots. Performing length-$m$ $3$-isogenies allows shorter isogeny walks than when employing length-$n$ $2$-isogenies since a cube root calculation costs essentially the same as computing a square root, and we require $3^m \approx 2^n$ to provide the same security level. We propose an efficient mapping from arbitrary supersingular Montgomery curves defined over $\mathbb{F}_{p^2}$ to the $3$-isogeny curve model from Castryck, Decru, and Vercauteren (Asiacrypt 2020); a deterministic algorithm to compute all order-$3$ points on arbitrary supersingular Montgomery curves, and an efficient algorithm to compute length-$m$ $3$-isogeny chains. We improve the length-$m$ $3$-isogeny walks required by the KEM from Nakagawa and Onuki (CRYPTO 2024) by using our results and introducing more suitable parameter sets that are friendly with C-code implementations. In particular, our experiments illustrate an improvement of 26.41\%--35.60\% in savings when calculating length-$m$ $3$-isogeny chains and using our proposed parameters instead of those proposed by Nakagawa and Onuki (CRYPTO 2024). Finally, we enhance the key generation of $\mathsf{CTIDH}$-2048 by including radical $3$-isogeny chains over the basefield $\mathbb{F}_p$, reducing the overhead of finding a $3$-torsion basis as required in some instantiations of the $\mathsf{CSIDH}$ protocol. Our experiments illustrate the advantage of radical $3$ isogenies in the key generation of $\mathsf{CTIDH}$-2048, with an improvement close to 4x faster than the original $\mathsf{dCTIDH}$.