[Resource Topic] 2025/155: Cycles and Cuts in Supersingular L-Isogeny Graphs

Welcome to the resource topic for 2025/155

Title:
Cycles and Cuts in Supersingular L-Isogeny Graphs

Authors: Sarah Arpin, Ross Bowden, James Clements, Wissam Ghantous, Jason T. LeGrow, Krystal Maughan

Abstract:

Supersingular elliptic curve isogeny graphs underlie isogeny-based cryptography. For isogenies of a single prime degree \ell, their structure has been investigated graph-theoretically.
We generalise the notion of \ell-isogeny graphs to L-isogeny graphs (studied in the prime field case by Delfs and Galbraith), where L is a set of small primes dictating the allowed isogeny degrees in the graph. We analyse the graph-theoretic structure of L-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 L-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 L-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.

ePrint: https://eprint.iacr.org/2025/155

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .