Paper 2026/2589

Cyclic isogeny walks on genus-zero modular curves

Abstract

Isogeny-based cryptography implementations have to navigate a large space of options for representing elliptic curves and isogenies and for the corresponding arithmetic. This work collects, completes, and organizes the set of algebraic maps and relations available when working with genus-zero modular curves $X_0(N)$, which parametrize cyclic $N$-isogenies of elliptic curves and can be represented by a single field element. This abstract notion covers many single-parameter curve models, such as Montgomery, Edwards, Jacobi quartic, Hessian curve, Deuring normal form. Such single-parameter models for the same modular curve are related by degree-1 rational maps, which limits the remaining options for improving the expressions. This representation is universal in the sense that it can be obtained from any other algebraic parametrization of such isogenies, or simply from the $j$-invariants through which the isogeny passes, away from singularities. We propose a method to derive rational maps for computing such lifting from the $j$-line to $X_0(N)$. Our main technical contribution is the definition, analysis, and computation of non-backtracking modular polynomials over these curves obtained using an extended method of Elkies. In addition to characterizing cyclic extensions of isogenies, they have many other useful properties, such as having lower degree and being sparser than other typical modular polynomials, smoother walk models (being better at distinguishing different isogenies), carrying additional isogeny of different degree along the walk. We also propose radical representations of the same relation, which sheds new light on a few existing radical isogeny formulas. We illustrate the use of the framework by achieving more compact R1CS encodings for isogeny proofs of knowledge.