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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/505}},
      url = {https://eprint.iacr.org/2014/505}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.