CryptoDB
Let us walk on the 3-isogeny graph: efficient, fast, and simple
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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. |
BibTeX
@article{tches-2025-35988,
title={Let us walk on the 3-isogeny graph: efficient, fast, and simple},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={644-666},
url={https://tches.iacr.org/index.php/TCHES/article/view/12424},
doi={10.46586/tches.v2025.i4.644-666},
author={Jesús-Javier Chi-Domínguez and Eduardo Ochoa-Jiménez and Ricardo-Neftalí Pontaza-Rodas},
year=2025
}