Welcome to the resource topic for 2025/691
Title:
Let us walk on the 3-isogeny graph: efficient, fast, and simple
Authors: Jesús-Javier Chi-Domínguez, Eduardo Ochoa-Jimenez, Ricardo-Neftalí Pontaza-Rodas
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}.
ePrint: https://eprint.iacr.org/2025/691
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 .