Cryptology ePrint Archive: Report 2022/562

Orientations and cycles in supersingular isogeny graphs

Sarah Arpin and Mingjie Chen and Kristin E. Lauter and Renate Scheidler and Katherine E. Stange and Ha T. N. Tran

Abstract: The paper concerns several theoretical aspects of oriented supersingular l-isogeny volcanoes and their relationship to closed walks in the supersingular l-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular l-isogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular l-isogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular l-isogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.

Category / Keywords: public-key cryptography / supersingular, isogeny, elliptic curve, orientation

Date: received 8 May 2022

Contact author: kstange at math colorado edu

Available format(s): PDF | BibTeX Citation

Version: 20220510:082215 (All versions of this report)

Short URL: ia.cr/2022/562


[ Cryptology ePrint archive ]