Source-linked AI summary
Faster computation of isogenies of large prime degree
Daniel Bernstein, Luca de Feo, Antonin Leroux, Benjamin Smith
TL;DR
Large-degree isogeny computation traditionally requires eO(ℓ) Fq-operations, motivating faster evaluation of the quotient curve and isogeny images. The paper develops structured polynomial-evaluation algorithms for elliptic-curve torsion points and obtains eO(√ℓ) complexity, with applications to isogeny-based cryptography.
Problem
The paper addresses how to compute an ℓ-isogeny’s codomain and evaluate φ(Q) without the conventional eO(ℓ) cost.
Method
It exploits additive structure in index sets and elliptic-curve resultant techniques to evaluate functions of torsion-point coordinates efficiently.
Results
Theorem 4.11 achieves eO(√ℓ) complexity for a large class of sets, including the elliptic-curve x-coordinate case.
Takeaways & Limitations
The asymptotic speedup applies to isogeny evaluation in CSIDH, CSURF, CRS, and B-SIDH as security levels increase.
Takeaways & Limitations
The elliptic-curve approach does not transfer directly to higher-dimensional PPAVs because coordinate addition relations require multiple even coordinates and multivariate resultants.
Abstract
from arXiv · showhide
Let $\mathcal{E}/\mathbb{F}_q$ be an elliptic curve, and $P$ a point in $\mathcal{E}(\mathbb{F}_q)$ of prime order $\ell$. Vélu's formulae let us compute a quotient curve $\mathcal{E}' = \mathcal{E}/\langle{P}\rangle$ and rational maps defining a quotient isogeny $φ: \mathcal{E} \to \mathcal{E}'$ in $\tilde{O}(\ell)$ $\mathbb{F}_q$-operations, where the $\tilde{O}$ is uniform in $q$.This article shows how to compute $\mathcal{E}'$, and $φ(Q)$ for $Q$ in $\mathcal{E}(\mathbb{F}_q)$, using only $\tilde{O}(\sqrt{\ell})$ $\mathbb{F}_q$-operations, where the $\tilde{O}$ is again uniform in $q$.As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.
1. Introduction
The paper reframes large-degree isogeny evaluation as structured polynomial and rational-function evaluation, reducing the target cost from eO(ℓ) to eO(√ℓ) operations under suitable structure. It applies this framework to elliptic-curve x-coordinates and discusses cryptographic applications and practical limits.
- Contribution: For composite kernel order n, the isogeny is decomposed into prime-degree isogenies, reducing the computational discussion to n = ℓ prime.Factoring n is stated not to be the bottleneck relative to computing the prime-degree isogenies considered.
- Baseline: The direct approach computes the rational-function coefficients and evaluates them in eO(ℓ) operations.The goal is evaluation, rather than explicitly computing the coefficients of the defining functions.
- Problem: The core problem is evaluating polynomials and rational functions whose roots are function values from a cyclic group over Fq.The framework includes elliptic-curve kernel polynomials as a central example.
- Contribution: When the index set has additive structure and the function is sufficiently compatible with the group law, evaluation can use eO(√ℓ) operations.Theorem 4.11 establishes this quasi-square-root complexity for a large class of sets when f is the elliptic-curve x-coordinate.
- Scope and limits: The asymptotic analysis is uniform over q, but polylogarithmic factors can dominate for small ℓ and algebraic algorithms can hurt practical performance.Appendix A studies the degree threshold at which the new algorithms outperform conventional ones.
- Scope and limits: The framework is algebraic and can extend beyond Fq, including suitable rings where required divisions are available.The paper notes that odd characteristic may still be required in some cases.
2. Strassen’s deterministic factorization algorithm
This section presents Strassen’s deterministic factorization method through fast evaluation of a polynomial with roots in an arithmetic progression. Product trees, remainder trees, and resultants reduce the modular-factorial computation from linear multiplication count to eO(ℓ) operations.
- Algorithm: Strassen’s algorithm deterministically factors n in eO(n^1/4) time by testing for small prime factors through modular factorials.Binary search identifies the smallest prime factor, and repetition completely factors n.
- Algorithm: The key subproblem is computing ℓ! mod n using eO(ℓ) additions, subtractions, and multiplications in Z/nZ.A straightforward computation uses ℓ−1 modular multiplications.
- Polynomial formulation: The factorial is represented as evaluating hS(X) = (X − 1)···(X − ℓ) at ℓ + 1 or, up to sign, at 0.This places modular factorials within the paper’s general polynomial-evaluation framework.
- Polynomial formulation: A product tree builds hI for a short initial interval, while hJ and a resultant combine blocks to obtain (b^2)! mod n.The remaining factors from b^2 + 1 through ℓ are then multiplied directly.
3. Evaluation of polynomials whose roots are powers
The paper accelerates evaluation of products with roots forming powers by exploiting additive structure in the exponent set and the homomorphism s ↦ ζ^s. Resultants or multipoint evaluation then achieve quasi-square-root complexity for suitable sets.
- Setup: Pollard’s geometric-progression method evaluates products with roots ζ^s, complementing Strassen’s arithmetic-progression method.The direct method costs O(ℓ), while the structured method targets eO(√ℓ).
- Structures in S and f: The exponent map s ↦ ζ^s is a group homomorphism, so ζ^(i+j) factors as ζ^iζ^j when the index set decomposes additively.This multiplicative compatibility is the key structure enabling block evaluation.
- Structures in S and f: If I and J have no common differences, the map I × J → I + J is bijective, allowing hI+J to be computed through a bivariate resultant.The polynomial roots over I + J are thereby organized from the smaller index sets.
- Evaluation algorithm: Algorithm 1 evaluates hS(α) in eO(max(#I, #J, #K)) Fq-operations for S = (I + J) ∪ K.The method combines the resultant-based evaluation for I + J with direct evaluation over K.
- Optimization: The square-root bound is essentially the best possible for this decomposition because #S = #I·#J + #K forces max(#I, #J, #K) to be large.The paper identifies this as the best conceivable case for Proposition 3.5 as a function of #S.
- Optimization: For arithmetic progressions, choosing #I = #J = b and #K = n − b^2 ≤ 2b yields eO(√n) operations.The construction uses I and J with step r and block size b.
- Related perspective: The exponent-set technique generalizes known arithmetic and geometric progression algorithms, with Shanks’ baby-step giant-step method appearing when r = 1.The comparison connects the construction to a familiar index-set decomposition.
4. Elliptic resultants
The paper adapts polynomial evaluation techniques to elliptic-curve torsion points, overcoming the non-homomorphic x-map with addition–subtraction relations and resultants. An index-system decomposition then yields quasi-square-root evaluation costs.
- The main contribution adapts power-root polynomial evaluation to roots given by functions of elliptic-curve torsion points, especially x-coordinates.Unlike the multiplicative setting, the x-map is not a homomorphism.
- The non-homomorphic x-map prevents directly representing x([i+j]P) from x([i]P) and x([j]P), so the method incorporates both sums and differences.The construction uses the algebraic relation among x(P), x(Q), x(P+Q), and x(P−Q).
- Resultant construction: Biquadratic relations between x-coordinates enable a resultant expression for hI±J, reducing evaluation to smaller polynomials.Lemma 4.9 combines hI, DJ, and EJ through a resultant.
- Index systems: An index system requires the maps (i,j)↦i+j and (i,j)↦i−j to be injective with disjoint images, preventing redundancy in the decomposition.The represented set is I±J=(I+J)∪(I−J).
- Complexity: Algorithm 2 evaluates hS(α) in eO(max(#I, #J, #K)) Fq-operations, where K=S\(I±J).For the kernel-polynomial setting, the chosen index system gives ΨG(α) in quasi-square-root cost.
- Scope: The approach is specialized to elliptic curves: higher-dimensional PPAVs generally require multivariate polynomials and resultants because one coordinate is insufficient.The article leaves that extension beyond scope.
5. Computing elliptic isogenies
The paper applies elliptic polynomial evaluation to Montgomery-model isogenies, computing x-coordinate evaluations and codomain curves through kernel-polynomial evaluations. Both tasks use quasi-square-root operation counts in the isogeny degree.
- The isogeny application targets Montgomery curves and divides the task into evaluating isogenies on points and computing codomain curves.The methods also adapt to Weierstrass and other models.
- Isogeny evaluation: The x-coordinate map φx(α) is rewritten using hS for S={1,3,…,ℓ−2}, reducing its computation to two applications of Algorithm 2.Exceptional inputs where denominators vanish are handled separately.
- Codomain curves: The codomain coefficient A′ can be obtained by evaluating the isogeny over an extended base ring at a 2-torsion point, or by explicit formulas.The ring method avoids requiring a square root, while the alternative may use Fq2.
- Complexity: A′ is computable in eO(√ℓ) operations because the required tasks reduce to evaluations of hS plus asymptotically negligible work.This matches the paper’s accelerated isogeny-evaluation framework.
6. Applications in isogeny-based cryptography
The techniques apply to cryptographic protocols that use large-degree isogenies, including CRS, CSIDH, CSURF, and B-SIDH. The authors establish asymptotic speedups while distinguishing them from guaranteed gains at fixed security levels.
- CRS, CSIDH, and CSURF use large-degree isogenies whose largest degree grows quasi-linearly with the pre-quantum security level.B-SIDH uses even larger prime degrees because of its smaller prime fields.
- CSIDH and CSURF: The algorithm seamlessly replaces Vélu’s formulas in CSIDH and CSURF for computing quotient curves after sampling points of suitable order.CSURF can compute the codomain using rational 2-torsion, while CSIDH can use the codomain techniques from Section 5.2.
- Asymptotic impact: The asymptotic evaluation improvement implies asymptotic speedups for CRS, CSIDH, CSURF, and B-SIDH as the security level increases.This statement concerns asymptotic security growth rather than every concrete parameter set.
- Scope: Protocols using KLPT path renormalization may benefit when they require irrational torsion points, but the paper does not investigate those protocols further.The stated examples are a signature scheme and the encryption scheme SÉTA.
Appendix A. Concrete costs and cross-overs
The appendix measures concrete cross-over points rather than relying only on asymptotic notation. It finds that the cross-over lies within CSIDH-512’s prime range and reports measurable speed records for CSIDH-512 and CSIDH-1024.
- Conventional ℓ-isogeny evaluation costs Θ(ℓ), while the new algorithms have quasi-linear-in-√ℓ asymptotic behavior with polylogarithmic factors.The appendix emphasizes that asymptotic notation alone does not determine when the new method becomes faster.
- Cross-over analysis: The appendix quantifies the cross-over point at which the new algorithms outperform conventional algorithms.This addresses the effect of hidden polylogarithmic factors.
- Concrete results: The cross-over point is within the range of primes used in CSIDH-512 across the metrics considered.The result connects asymptotic improvements to concrete parameter sizes.
- Benchmarks: The new ℓ-isogeny algorithm sets small but measurable speed records for CSIDH-512 and CSIDH-1024, with greater effects for protocols using larger ℓ-isogenies.The implementation is publicly available at velusqrt.isogeny.org.
A.1. Choice of function to compute.
The appendix evaluates an ℓ-isogeny on one point while computing the target Montgomery curve coefficient. It contextualizes the method with implementations and a B-SIDH parameter choice involving very large degrees.
- Subroutine: The highlighted subroutine takes an odd prime ℓ, a Montgomery-curve coefficient, and coordinates for kernel and evaluation points, returning the target coefficient and evaluated image.It evaluates a separable ℓ-isogeny with kernel generated by P.
- Software context: The subroutine is the sole use of isogenies in the cited CSIDH software, although total software speedup also depends on other operations and the number of evaluated points.The authors note that pushing more or fewer points through one isogeny changes the practical impact.
- Protocol context: The experiments measure costs for CSIDH-512, CSIDH-1024, CSURF-512, and B-SIDH implementations.These measurements place ℓ-isogeny costs in protocol context.
- B-SIDH setting: The B-SIDH experiment uses a 256-bit prime assembled from specified factors, with one participant evaluating degrees as large as ≈2^23.The other participant handles degrees below 2^14.
A.2. Choices of cost metric.
The appendix compares software time, algebraic-operation counts, and hardware-level costs. These metrics expose different tradeoffs between implementation overhead, portability, and modeling simplicity.
- Metrics: The study measures Magma, Julia/Nemo, C/FLINT, arbitrary machine-language software, and multiplication counts in algebraic algorithms.The algebraic metric counts additions, subtractions, and multiplications without divisions under projective representations.
- Metric tradeoffs: Algebraic multiplication counts are clear and traditional, but ignore addition costs, non-algebraic overhead, divisions, and faster non-algebraic polynomial multiplication.They therefore provide a simplified cost model rather than a complete runtime model.
- Hardware dependence: Physical time measurements include overheads but depend on the CPU; the experiments use one 3.40GHz Intel Core i7-6700 core.Turbo Boost was disabled.
- Software dependence: Library-based timings depend on specific versions and implementations, so library improvements could shift the ℓ cross-over points.The reported data remain examples of tradeoffs between CPU time and programmer time.
- Arithmetic costs: At the reported hardware level, GMP modular multiplication takes about 600–700 cycles, while its exponentiation and optimized field multiplication routines are faster in their respective settings.The cited figures are about 302n cycles for a 2^n-th power and about 200 cycles for optimized multiplication.
- Alternative metrics: Parallel and hardware-oriented metrics can expose costs hidden by operation counts, including resultant-computation depth and area-time overhead.Remainder trees mitigate the stated depth disadvantage for resultants.
A.3. Results for ℓ-isogenies.
The authors implement the new ℓ-isogeny algorithm across four software environments and compare it with conventional methods. The results show practical gains at sufficiently large degrees, with the crossover depending on the implementation.
- Implementations: Four implementations estimate upper bounds for the new algorithm’s costs across the first four metrics, using the CSIDH-512 prime field except where noted.The measured subroutine evaluates an ℓ-isogeny on one point and computes the new curve coefficient.
- Plots: The figures plot ℓ horizontally and cost divided by ℓ+2 vertically, contrasting conventional and new algorithms with repeated experimental medians.Blue pluses represent the conventional algorithm and red crosses the new algorithm.
- Magma: ℓ≥113 is the threshold at which the new Magma algorithm becomes better than the old algorithm.This crossover is reported from the cycle-count graph.
- FLINT: At ℓ=587, the new FLINT implementation uses 2,026,744 cycles, about 45% faster than the old one.The reported cost is approximately 3440.992(ℓ+2) cycles.
- Assembly-backed software: At ℓ=587, the new assembly-backed software uses 745,862 cycles, about 22% faster than the software from.For small ℓ, automatic tuning falls back to the conventional algorithm.
- Algebraic metric: At ℓ=587, the new algorithm uses 2,296 multiplications, about 55% fewer than the conventional algorithm’s 3,550.The multiplication count is automatically retuned for this metric.
- Validation: The SageMath implementation was used only to check output correctness, not to evaluate performance.It is therefore excluded from the performance comparisons.
A.4. Results for protocols.
The authors integrate their ℓ-isogeny implementations into CSIDH and CSURF code and evaluate protocol costs across multiple implementations. The new algorithm improves performance for sufficiently large ℓ, with especially large gains reported for degree-p±1 isogenies.
- Implementations: The implementations were integrated into CSIDH-512, CSURF-512, and B-SIDH code, with assembly field arithmetic also adapted to CSIDH-1024.The CSIDH-1024 adaptation saves about a factor 3 compared to the referenced C code.
- Protocol evaluation: The Magma implementation outperforms the old algorithm for ℓ≥113, while protocol graphs compare conventional and new algorithms on identical key samples.The Magma and FLINT implementations switch back to the old algorithm below their respective thresholds.
- Caveat: The protocol implementations are not constant-time, and the final performance of constant-time CSIDH, CSURF, and B-SIDH remains uncertain.The paper identifies constant-time implementations as an active area of research.
- Protocol-scale results: A degree-p−1 isogeny takes about 0.56 seconds and a degree-p+1 isogeny about 10 seconds with the new algorithm.The conventional algorithms take approximately 2 seconds for degree p−1, while one naive degree-p+1 experiment takes 6.5 minutes.
A.5. Techniques to save time inside the ℓ-isogeny algorithm.
The paper surveys implementation techniques that reduce the cost of evaluating ℓ-isogenies and computing new curve coefficients. These techniques target remainder trees, polynomial arithmetic, field operations, and the organization of intermediate computations.
- Polynomial arithmetic: Computations of Q(α), Q(1/α), Q(1), and Q(−1) can be merged across the corresponding evaluations of hS.Q(1) and Q(−1) are self-reciprocal quadratics, enabling specialized multiplication of half-size polynomials.
- Remainder trees: Scaled remainder trees and precomputed product trees can replace traditional remainder-tree implementations when they are faster.The recommendation applies to product trees used inside the remainder trees as well.
- Polynomial arithmetic: Polynomial divisions can be accelerated by precomputing reciprocals of tree nodes, while polynomial multiplications can exploit low, high, and middle products.The paper notes that several reciprocal-saving techniques are not yet incorporated into the current software.
- Polynomial arithmetic: Polynomial multiplication costs 2n−1 field multiplications in large characteristic when the product is interpolated from values at 0, 1, ..., 2n−2.Projective output representations can replace interpolation divisions by multiplications and additions.
- Parameter tuning: Reducing field-operation cycles and selecting #I and #J according to all operation costs are important higher- and lower-level optimization choices.The asymptotically optimal #I/#J ratio is expected to converge to a constant, but that constant is metric-dependent and not obvious.