On the quaternion -isogeny path problem
Top Cited Papers
Open Access
- 1 August 2014
- journal article
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 17 (A) , 418-432
Abstract
Let $\mathcal{O}$ 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 $\mathcal{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 solves 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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Full Cryptanalysis of LPS and Morgenstern Hash Functions2008
- Cryptographic Hash Functions from Expander GraphsJournal of Cryptology, 2007
- Explicit bounds for primality testing and related problemsMathematics of Computation, 1990
- An algorithm for computing modular forms on Γ0(N)Journal of Algebra, 1980
- Arithmétique des Algèbres de Quaternions1980
- The Least Quadratic Non ResidueAnnals of Mathematics, 1952
- Die Typen der Multiplikatorenringe elliptischer FunktionenkörperAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1941