Paper 2014/505
On the quaternion $\ell$-isogeny path problem
David Kohel, Kristin Lauter, Christophe Petit, and 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.
Note: To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.
- Keywords
- number theory
- Contact author(s)
- christophe petit @ uclouvain be
- History
- 2014-06-26: received
- Short URL
- https://ia.cr/2014/505
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/505,
author = {David Kohel and Kristin Lauter and Christophe Petit and Jean-Pierre Tignol},
title = {On the quaternion $\ell$-isogeny path problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/505},
year = {2014},
url = {https://eprint.iacr.org/2014/505}
}
