UCalgary Algebra and Number Theory Seminar: Renate Scheidler

Given two elliptic curves, the path finding problem asks to find an isogeny (i.e. a group homomorphism) between them, subject to certain degree restrictions. Path finding has uses in number theory as well as applications to 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.