Improved Algorithms for Ascending Isogeny Volcanoes, and Applications

This chapter delves into the intricate world of ascending isogeny volcanoes, focusing on improved algorithms and their applications in modern cryptography. The text begins by discussing Tate's isogeny theorem and the challenges of recovering isogenies between elliptic curves. It then introduces Galbraith's 1999 algorithm and its improvements, highlighting the use of Kani's lemma to enhance worst-case complexities. The chapter further explores the computation of vertical or ascending isogenies, presenting new methods for determining these isogenies when the endomorphism ring is known. A significant portion of the text is dedicated to the use of self-pairings, which can be evaluated using only one elliptic curve point and provide non-trivial outputs. The authors simplify the framework for these pairings and demonstrate how they can be used to recover vertical isogenies. The chapter also includes a simplified proof of a special case of a result from previous work, making it accessible to non-experts. The text carefully characterizes various cases involving the order of the torsion subgroup and the conductor, as well as the degree of the secret isogeny. It then shows how to encode missing information into a conic equation and treats degenerate and non-degenerate conics individually. The chapter concludes by applying these new tools to compute unknown vertical isogenies and considering the computational isogeny problem on certain curves with large volcanoes. The authors also discuss the elimination of heuristic assumptions from Galbraith's work and detail an algorithm for solving the computational isogeny problem in volcanoes with craters larger than polynomial size. The chapter provides a comprehensive analysis of the computational complexity of these algorithms, making it a valuable resource for researchers and practitioners in the field of cryptography.