On the quaternion ℓ-isogeny path problem

2014/06/04 by Kohel, David, Lauter, Kristin, Petit, Christophe +1 · 2 citations
#11-Gxx #11-Rxx #11-Sxx #11-Yxx #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1406.0981

Abstract

Let \cO be a maximal order in a definite quaternion algebra over ℚ of prime discriminant p, and ℓ a small prime. We describe a probabilistic algorithm, which for a given left O-ideal, computes a representative in its left ideal class of ℓ-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.

Cited by

• Refined Humbert Invariants in Supersingular Isogeny Degree Analysis
• Evaluation of Modular Polynomials from Supersingular Elliptic Curves

Related

• The supersingular isogeny path and endomorphism ring problems are\n equivalent
• Computing Isomorphisms between Products of Supersingular Elliptic Curves
• Supersingular elliptic curves, quaternion algebras and applications to cryptography
• Algorithmic enumeration of ideal classes for quaternion orders
• Ideal Class Group Algorithms in the Ring of Integral Quaternions