Source-linked AI summary
On the quaternion $\ell$-isogeny path problem
David Kohel, Kristin Lauter, Christophe Petit, Jean-Pierre Tignol
TL;DR
The paper addresses the quaternion analogue of the supersingular ℓ-isogeny path problem, whose elliptic-curve counterpart underlies the Charles–Goren–Lauter hash function. It gives a probabilistic algorithm that finds equivalent left ideals of ℓ-power or smooth norm, with expected polynomial runtime under prime-distribution heuristics. The result distinguishes the efficiently solvable quaternion setting and suggests implications for attacks and security reductions involving supersingular elliptic curves.
Problem
The paper studies the quaternion ideal analogue of the supersingular ℓ-isogeny path problem, motivated by the difficulty underlying the Charles–Goren–Lauter hash function.
Method
The paper develops a probabilistic algorithm that transforms a given left ideal into an equivalent ideal of ℓ-power norm, with extensions to smooth or powersmooth norms and general maximal orders.
Results
The algorithm is efficient in practice and runs in expected polynomial time under heuristic assumptions on prime distributions, distinguishing the quaternion problem from the resistant elliptic-curve analogue.
Takeaways & Limitations
The results suggest partial attacks on the Charles–Goren–Lauter hash function in extremal cases and security reductions to computing supersingular elliptic-curve endomorphism rings.
Takeaways & Limitations
The expected polynomial runtime depends on heuristic assumptions about prime distributions and representations by quadratic forms.
Abstract
from arXiv · showhide
Let $\cO$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$ of prime discriminant $p$, and $\ell$ a small prime. We describe a probabilistic algorithm, which for a given left $O$-ideal, computes a representative in its left ideal class of $\ell$-power norm. In practice the algorithm is efficient, and subject to heuristics on expected distributions of primes, runs in expected polynomial time. This breaks the underlying problem for a quaternion analog of the Charles-Goren-Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves.
1 Introduction
The paper gives a probabilistic algorithm for finding ℓ-power-norm representatives of quaternion ideal classes, motivated by the equivalent supersingular-isogeny path problem. Under heuristic prime-distribution assumptions, it runs in expected polynomial time and distinguishes the quaternion setting from the still-resistant elliptic-curve problem.
- Contribution: The algorithm computes, for a left O-ideal I, an equivalent ideal J of norm ℓ^k and extends to smooth or powersmooth norms.It is described for a special maximal order and extends to arbitrary maximal orders through a reduction.
- Performance: Under heuristics on expected prime distributions, the algorithm runs in expected polynomial time and is efficient in practice.
- Motivation: The quaternion problem is motivated by an explicit equivalence between left O-ideals and supersingular elliptic curves and their isogenies.The correspondence maps an isogeny to a left ideal whose norm is its degree.
- Problem: The corresponding elliptic-curve path problem asks for an ℓ-power isogeny between given supersingular curves, while the quaternion analogue asks for an ℓ-power-norm ideal in a given class.
- Security context: The algorithm separates the efficient quaternion-ideal problem from the analogous supersingular-elliptic-curve problem underlying the Charles–Goren–Lauter hash function, which has resisted attack.The paper connects this gap to questions about transporting information between the algebraic and geometric categories.
2 The quaternion ℓ-isogeny path problem
The paper formulates the quaternion ℓ-isogeny path problem through the categorical equivalence between left ideals and supersingular elliptic curves, then develops the quaternion-algebra and ideal structures used to study it. Special p-extremal orders and reduced norms provide the algebraic framework for representing the problem and its transformations.
- 2.1 “Hard” isogeny problems: The elliptic-curve formulation includes finding an ℓ^k-degree isogeny between two supersingular curves and finding two distinct such paths for collisions.
- 2.1 “Hard” isogeny problems: The quaternion ℓ-isogeny path problem asks for an equivalent representative of a given left O-ideal having norm ℓ^k.This is the ideal-theoretic analogue of finding an ℓ-power isogeny between supersingular elliptic curves.
- 2.1 “Hard” isogeny problems: Left O-ideals, with morphisms given by inclusions Iα ⊆ J, form a category equivalent to supersingular elliptic curves and isogenies.
- 2.2 Quaternion algebras: The ambient algebra is the definite quaternion algebra Bp,∞ ramified only at p and ∞, which is isomorphic to End(E) ⊗ Q for supersingular E over Fp2.
- 2.3 Extremal orders: A special p-extremal maximal order contains π with π^2 = −p and is chosen with minimal distinguished quadratic-subring discriminant.Such orders are introduced as the main setting for the construction and are later used to reduce the general case.
- 2.3 Extremal orders: For a special order, the suborder R + Rj has index |D| in O and reduced norms decompose as f(x1,y1) + p f(x2,y2), with f a quadratic form of discriminant D.
- 2.4 Reduced norms and ideal morphisms: Reduced norms extend from quaternion elements to ideals, are multiplicative, and make ideal isomorphisms into similitudes of positive-definite quadratic modules.
3 Preliminary algorithmic results
The section develops two probabilistic tools: finding prime-norm representatives within ideal classes and representing sufficiently large integers by special quaternion-order norm forms. Their practical performance is favorable, but runtime and termination rely on heuristic assumptions about primes and represented values.
- The section provides two algorithmic tools: prime-norm representatives for ideal classes and integer representations by p-extremal order norm forms.These tools are used to solve the quaternion ℓ-isogeny path problem.
- 3.1 Computing prime norm representatives in ideal classes: A probabilistic algorithm transforms a left O-ideal into an equivalent ideal of prime norm by sampling elements whose quadratic-form values are prime.It samples combinations of a Minkowski-reduced basis and returns I(ᾱ/N) after finding prime q_I(α).
- 3.1 Computing prime norm representatives in ideal classes: For generic ideals, the algorithm expects q_I(α) in ˜O(m^2√p), while worst-case ideals may require ˜O(p) fourth successive minima.In practice, polynomially growing m sufficed, but provable termination may require m exceeding O(⁴√p), potentially producing outputs larger than O(p).
- 3.1 Computing prime norm representatives in ideal classes: The prime-norm implementation handled ideals from random walks with primes up to 200 bits in seconds, and output norms were experimentally only slightly larger than √p.The tests used Magma on an Intel Xeon X5500 system with 24 GB RAM.
- 3.2 Representing integers by special orders: For a p-extremal order, integer representation samples β until r = M − p f(x₂,y₂) is a suitable split principal prime, then returns α + βj of norm M.The method uses a principal form f and assumes suitable primes occur with the expected density and distribution.
- 3.2 Representing integers by special orders: Under the prime-distribution heuristics, the integer-representation procedure tests an expected 2h(R) log(M) random β values and uses expected-polynomial-time subroutines.The assumptions include prime density in arithmetic progressions, equidistribution among splitting conditions and ideal classes, and random-like primality probabilities.
4 Main algorithm
The paper reduces the quaternion ℓ-isogeny path problem to effective strong approximation and constructs an equivalent left ideal of ℓ-power norm. The probabilistic algorithm extends from special p-extremal orders to arbitrary maximal orders, with heuristic polynomial-time expectations and successful experiments on 200-bit primes.
- 4.1 Overview of the algorithm: The approach reduces the problem to finding an element β in the ideal with reduced norm Nℓ^e, then converts it into an equivalent ideal of norm ℓ^e.Strong approximation supplies β, while β’s conjugate yields the desired ideal representative.
- 4.3 Isomorphism of O/NO-ideals: The core construction uses linear algebra over Z/NZ to find [µ], followed by specialized strong approximation to lift it to an element of ℓ-power norm.The computation exploits the explicit identification O/NO ≅ M2(Z/NZ) and restricts [µ] to (R/NR)∗[j].
- 4.4 Approximating elements of (R/NR)∗[j] by ℓ-power norm representatives: The norm-equation stage repeatedly samples representations until r or rq is prime, splits, and representable by the relevant quadratic form, with expected trials proportional to log(N^4|D|p)h(D).This heuristic governs the practical search for a suitable ℓ-power norm representative.
- 4.5 Algorithm analysis and experimental results: For N in the range Õ(√p), the exponent is expected to satisfy e ∼ log_ℓ(N^4|D|p) ∼ 3 log_ℓ(p).The implementation starts with the smallest admissible exponent and increases it when necessary.
- 4.5 Algorithm analysis and experimental results: Theorem 7 gives a probabilistic algorithm that maps any left O-ideal to an isomorphic left O-ideal of ℓ-power reduced norm.The method is first analyzed for special p-extremal maximal orders.
- 4.6 Generalization to arbitrary orders: The general maximal-order case reduces to the p-extremal case with the same complexity up to polynomial factors, while experiments terminated within 250 seconds for 200-bit primes.The reduction uses two applications of the special-order algorithm and may increase the resulting power of ℓ.
5 Conclusion and future work
The paper presents a probabilistic algorithm for the quaternion ideal analogue of the supersingular ℓ-isogeny path problem, with expected polynomial runtime under prime-distribution heuristics and practical efficiency. Through Deuring’s correspondence, the results suggest partial attacks on the CGL hash function and security reductions involving supersingular elliptic-curve endomorphism rings.
- The algorithm solves a quaternion ideal analogue of the supersingular ℓ-isogeny path problem and is efficient in practice.Its expected polynomial runtime depends on heuristics concerning expected distributions of primes.
- Under Deuring’s correspondence, the techniques are expected to enable partial attacks on the CGL hash function and security reductions to computing supersingular elliptic-curve endomorphism rings.
- The results are also expected to support a constructive version of Deuring’s correspondence from maximal quaternion orders to supersingular elliptic curves.
A Experimental results
The experiments used initially minimal parameter values selected from probabilistic prime-distribution arguments, increasing them when necessary.
- The algorithms began with minimal m and Φ values predicted probabilistically, then increased them when needed.
A.1 Prime norm ideals
Experiments on the prime norm algorithm found output norms slightly above p^1/2 and running time cubic in log(p).
- The output ideal norms were slightly larger than p^1/2, while computation time was cubic in log(p).
A.2 Quaternion elements with particular norms
The experiments measure how the algorithms’ required exponents compare with probabilistic predictions across several primes and small values of ℓ. The reported computations all completed in under one second.
- All computations for the Section 3.2 algorithms took less than one second.
- Figure 1 reports the logarithm of output norm q_I(α) and the cubic root of running time against log p.
- Figure 2 compares the minimal exponent e with a probabilistic prediction for norms Nℓ^e at ℓ=2 and ℓ=3 across p values.
- Figure 3 compares the minimal exponent e with a probabilistic prediction for norms ℓ^e across ℓ∈{2, 3, 5, 7} and various p values.
A.3 Ideals with ℓ-power norms
The section reports experimental measurements of quaternion and ideal sizes and algorithm runtimes for ℓ=2 and ℓ=3 across various p values.
- Figures 4 and 6 measure the sizes of ℓ-power norm quaternions and ideals returned by the algorithms for ℓ=2 and ℓ=3.
- Figures 5 and 7 measure the time taken by the algorithms for various p values with ℓ=2 and ℓ=3.