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

Constructing and implementing isogeny-based cryptographic primitives is an active research. In particular, performing length-n isogenies walks over quadratic field extensions of Fp 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 3m ≈ 2n to provide the same security level.We propose an efficient mapping from arbitrary supersingular Montgomery curves defined over Fp2 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 between 26.41% and 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 CTIDH-2048 by including radical 3-isogeny chains over the basefield Fp, reducing the overhead of finding a 3-torsion basis as required in some instantiations of the CSIDH protocol. Our experiments illustrate the advantage of radical 3 isogenies in the key generation of CTIDH-2048, with an improvement up to 4 times faster than the original CTIDH.