Orientations and cycles in supersingular isogeny graphs

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

Paper 2022/562

Orientations and cycles in supersingular isogeny graphs

Sarah Arpin, Universiteit Leiden

Mingjie Chen, University of Birmingham

Kristin E. Lauter, Facebook AI Research

Renate Scheidler, University of Calgary

Katherine Stange, University of Colorado Boulder

Ha T. N. Tran, Concordia University of Edmonton

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: supersingular isogeny elliptic curve orientation
Contact author(s): S A Arpin @ math leidenuniv nl
m chen 1 @ bham ac uk
klauter @ fb com
rscheidl @ ucalgary ca
kstange @ math colorado edu
hatran1104 @ gmail com
History: 2022-12-04: revised; 2022-05-10: received; See all versions
Short URL: https://ia.cr/2022/562
License: CC BY

BibTeX

@misc{cryptoeprint:2022/562,
      author = {Sarah Arpin and Mingjie Chen and Kristin E.  Lauter and Renate Scheidler and Katherine Stange and Ha T.  N.  Tran},
      title = {Orientations and cycles in supersingular isogeny graphs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/562},
      year = {2022},
      url = {https://eprint.iacr.org/2022/562}
}