**On the quaternion $\ell$-isogeny path problem**

*David Kohel, Kristin Lauter, Christophe Petit, Jean-Pierre Tignol*

**Abstract: **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 $\cO$-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.

**Category / Keywords: **number theory

**Original Publication**** (in the same form): **To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.

**Date: **received 4 Jun 2014

**Contact author: **christophe petit at uclouvain be

**Available format(s): **PDF | BibTeX Citation

**Note: **To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.

**Version: **20140626:212328 (All versions of this report)

**Short URL: **ia.cr/2014/505

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]