Paper 2025/155

Cycles and Cuts in Supersingular L-Isogeny Graphs

Sarah Arpin, Virginia Tech
Ross Bowden, University of Bristol
James Clements, University of Bristol
Wissam Ghantous, University of Central Florida
Jason T. LeGrow, Virginia Tech
Krystal Maughan, University of Vermont
Abstract

Supersingular elliptic curve isogeny graphs underlie isogeny-based cryptography. For isogenies of a single prime degree , their structure has been investigated graph-theoretically. We generalise the notion of -isogeny graphs to -isogeny graphs (studied in the prime field case by Delfs and Galbraith), where is a set of small primes dictating the allowed isogeny degrees in the graph. We analyse the graph-theoretic structure of -isogeny graphs. Our approaches may be put into two categories: cycles and graph cuts. On the topic of cycles, we provide: a count for the number of non-backtracking cycles in the -isogeny graph using traces of Brandt matrices; an efficiently computable estimate based on this approach; and a third ideal-theoretic count for a certain subclass of -isogeny cycles. We provide code to compute each of these three counts. On the topic of graph cuts, we compare several algorithms to compute graph cuts which minimise a measure called the edge expansion, outlining a cryptographic motivation for doing so. Our results show that a greedy neighbour algorithm out-performs standard spectral algorithms for computing optimal graph cuts. We provide code and study explicit examples. Furthermore, we describe several directions of active and future research.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
isogeny-based cryptographysupersingular elliptic curvesgraph cutsisogeny cycles
Contact author(s)
sarpin @ vt edu
ross bowden @ bristol ac uk
james clements @ bristol ac uk
wissam ghantous @ ucf edu
jlegrow @ vt edu
Krystal Maughan @ uvm edu
History
2025-02-01: approved
2025-01-31: received
See all versions
Short URL
https://ia.cr/2025/155
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/155,
      author = {Sarah Arpin and Ross Bowden and James Clements and Wissam Ghantous and Jason T. LeGrow and Krystal Maughan},
      title = {Cycles and Cuts in Supersingular L-Isogeny Graphs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/155},
      year = {2025},
      url = {https://eprint.iacr.org/2025/155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.