On the quaternion ℓ-isogeny path problem

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

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

Let O be a maximal order in a definite quaternion algebra over Q 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 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.
Original languageEnglish
Pages (from-to)418-432
Number of pages15
JournalLondon Mathematical Society. Journal of Computation and Mathematics
Volume17
Issue numberA
DOIs
Publication statusPublished - 1 Aug 2014
EventAlgorithmic Number Theory Symposium 2014 (ANTS XI) - GyeongJu, Korea, Republic of
Duration: 7 Aug 201411 Aug 2014

Bibliographical note

Publisher Copyright:
© The Author(s) 2014.

ASJC Scopus subject areas

  • Pharmacology
  • Psychiatry and Mental health
  • Pharmacology (medical)

Fingerprint

Dive into the research topics of 'On the quaternion ℓ-isogeny path problem'. Together they form a unique fingerprint.

Cite this