Orienteering on Supersingular Isogeny Volcanoes Using One Endomorphism

Renate Scheidler (University of Calgary, Canada)

Elliptic curve isogeny path finding has many applications in number theory and cryptography. For supersingular curves, this problem is known to be easy when one small endomorphism or the entire endomorphism ring are known. Unfortunately, computing the endomorphism ring, or even just finding one small endomorphism, is hard. How difficult is path finding in the presence of one (not necessarily small) endomorphism? We use the volcano structure of the oriented supersingular isogeny graph to answer this question. We give a classical algorithm for path finding that is subexponential in the degree of the endomorphism and linear in a certain class number, and a quantum algorithm for finding a smooth isogeny (and hence also a path) that is subexponential in the discriminant of the endomorphism. A crucial tool for navigating supersingular oriented isogeny volcanoes is a certain class group action on oriented elliptic curves which generalizes the well-known class group action in the setting of ordinary elliptic curves.