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 $$-isogenies through square root calculations. This work analyzes the idea of using $$-isogenies instead of $$-isogenies, which replaces the requirement of calculating square roots with cube roots. Performing length-$$ $$-isogenies allows shorter isogeny walks than when employing length-$$ $$-isogenies since a cube root calculation costs essentially the same as computing a square root, and we require $$ to provide the same security level. We propose an efficient mapping from arbitrary supersingular Montgomery curves defined over $$ to the $$-isogeny curve model from Castryck, Decru, and Vercauteren (Asiacrypt 2020); a deterministic algorithm to compute all order-$$ points on arbitrary supersingular Montgomery curves, and an efficient algorithm to compute length-$$ $$-isogeny chains. We improve the length-$$ $$-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-$$ $$-isogeny chains and using our proposed parameters instead of those proposed by Nakagawa and Onuki (CRYPTO 2024). Finally, we enhance the key generation of $$-2048 by including radical $$-isogeny chains over the basefield $$, reducing the overhead of finding a $$-torsion basis as required in some instantiations of the $$ protocol. Our experiments illustrate the advantage of radical $$ isogenies in the key generation of $$-2048, with an improvement close to 4x faster than the original $$.