On the quaternion -isogeny path problem
Let $\cO$ be a maximal order in a definite quaternion algebra over of prime discriminant , and a small prime. We describe a probabilistic algorithm, which for a given left -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 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.