Abstract
Supersingular Isogeny Graphs were introduced as a source of hard problems in cryptography by Charles, Goren, and Lauter [Citation6] for the construction of cryptographic hash functions and have been used for key exchange SIKE. The security of such systems depends on the difficulty of finding a path between two random vertices. In this article, we study several aspects of the structure of these graphs. First, we study the subgraph given by j-invariants in , using the related isogeny graph consisting of only -rational curves and isogenies. We prove theorems on how the connected components thereof attach, stack, and fold when mapped into the full graph. The -rational vertices are fixed by the Frobenius involution on the graph, and we call the induced graph the spine. Finding paths to the spine is relevant in cryptanalysis. Second, we present numerous computational experiments and heuristics relating to the position of the spine within the whole graph. These include studying the distance of random vertices to the spine, estimates of the diameter of the graph, how often paths are preserved under the Frobenius involution, and what proportion of vertices are conjugate. We compare some of the heuristics with known results on other Ramanujan graphs.
1 Introduction
Supersingular Isogeny Graphs have been the subject of recent study due to their significance in recently proposed post-quantum cryptographic protocols. In 2006, Charles, Goren, and Lauter proposed a hash function based on the hardness of finding paths (routing) in Supersingular Isogeny Graphs [Citation6]. A few years later, De Feo, Jao, and Plût proposed a key exchange based on Supersingular Isogeny Graphs [Citation12]. The security of most currently deployed cryptographic systems relies on either the hardness of factoring large integers of a certain form or the hardness of computing discrete logarithms in certain cyclic groups. Both problems can be efficiently solved using Shor’s algorithm [Citation23] on a large-scale quantum computer once it exists. In 2015, NIST announced a contest to standardize cryptographic algorithms that are not known to be broken by quantum computers. Now in its third round, SIKE (https://sike.org/, based on Supersingular Isogeny Graphs) has been shortlisted as an alternate candidate.
To date, there are no known classical or quantum attacks that break the cryptographic protocols that use Supersingular Isogeny Graphs. But the graphs themselves have been relatively unstudied until recently. More study is needed before we can confidently recommend protocols which rely on the difficulty of the hard problem of finding paths in Supersingular Isogeny Graphs. There have been several approaches tried so far to attack cryptographic protocols based on Supersingular Isogeny Graphs. One of them uses the quaternion analogue of the graph and presents an efficient algorithm for navigating between maximal orders [Citation18]. This approach leads to the results presented in [Citation13] showing that the hardness of the path finding problem is essentially equivalent to the hardness of computing endomorphism rings of supersingular elliptic curves.
For distinct primes p and , let denote the graph whose vertices are isomorphism classes of supersingular elliptic curves over and whose edges correspond to isogenies of degree defined over . The vertices can be labeled with the j-invariant of the curve, which is an -isomorphism invariant. For the graph is known to be a -regular Ramanujan graph, and is one of two known families of Ramanujan graphs.
In this article, we study two related graphs to help understand the structure of . First, the full subgraph of consisting of only vertices : We denote this subgraph by and call it the spine, which is new terminology. Second, we look at the graph whose vertices are elliptic curves up to -isomorphism and edges are -isogenies of degree , already studied by Delfs and Galbraith [Citation11].
We were motivated to continue the study of the graph for several reasons. First, subexponential quantum algorithms are known for navigating between -vertices [Citation3], so paths to these vertices are of particular interest. Second, the graph maps into the full to become the spine in a surprising way, which we study in detail. Third, the Frobenius map acts on the full graph by sending each j-invariant in to its conjugate jp, and the vertices in the spine are the fixed points of this involution. If we have a path from a random j-invariant to a j-invariant in , then applying the involution to the vertices in the path we obtain a mirror path from to jp.
In Section 3 of this article, we compare with the spine . The main results of Section 3 show how the components of (which look like volcanoes) fit together to form the spine when passing to the full graph . We define the notions of stacking, folding, and attaching to describe how becomes the spine, when isogenies defined over are added and j-invariants which are twists are identified. We achieve this by comparing the possible neighbors of the vertices in that have the same j-invariant. We prove that the only vertices that do not have the same neighbors are those with (Lemma 3.17 and Proposition 3.22).
For , for odd class numbers, we show that the number of edges in that do not come from isogenies defined over is bounded by and for any p, this bound can be sharpened for any , based on congruence conditions on p. Further, we show that the components containing are “symmetric” and the opposite vertices of form a pair of -isogenous quadratic twists, whereas all other components admit a “twist twin”: a component that is isomorphic to it as labeled graphs if we label the vertices by the j-invariants of the curves (Theorem 3.18).
For , we provide a similar analysis. Again, the component containing 1728 is “symmetric” and all other components admit a “twist twin,” except for the case of one edge . Moreover, in this case, at most 2 new edges are added that do not correspond to loops and we identify at which vertices these can occur.
We conclude that for any fixed and p, the resulting shape of the spine depends on the congruence class of p, the structure of the class group , where , and the behavior of the prime above in the class group of K, and we show how to determine it explicitly. In Section 3.5, we generate experimental data to study how the components of the spine are distributed throughout the graph and we estimate how many components there are in the spine.
In Section 4.1, we study the distance between Galois conjugate pairs of vertices, that is, pairs of -invariants of the form , . Our data suggest these vertices are closer to each other than a random pair of vertices in . In Section 4.2 we test how often the shortest path between two conjugate vertices goes through the spine , or equivalently, contains a j-invariant in . We find conjugate vertices are more likely than a random pair of vertices to be connected by a shortest path through the spine. Finally, we examine the distance between arbitrary vertices and the spine in Section 4.3. Section 5 provides heuristics on how often conjugate -invariants are -isogenous for , a question motivated by the study of mirror paths provided in Section 4.
Another family of Ramanujan graphs are certain Cayley graphs constructed by Lubotzky, Philips, and Sarnak (LPS graphs [Citation20]). The relationship between LPS graphs and Supersingular Isogeny Graphs is studied in [Citation5]. Sardari [Citation22] provides an analysis of the diameters of LPS graphs, and in Section 6 of this article, we provide heuristics and a discussion of the diameters of supersingular 2-isogeny graphs.
Our experiments and data suggest a noticeable difference in the Supersingular Isogeny Graphs depending on the congruence class of the prime . It has been known since the introduction of Supersingular Isogeny Graphs into cryptography [Citation6] that the congruence class of the prime p has an important role to play in the properties of the graph. In particular, it was shown there how the existence of short cycles in the graph depends explicitly on the congruence conditions on p. In this article, we extend this observation and find significant differences in the graphs depending on the congruence class of p. In summary, the data seem to suggest the following:
:
smaller 2-isogeny graph diameters (Section 6.1),
larger number of spinal components (Section 3.6), and
larger proportion of 2-isogenous conjugate pairs (Section 5.2.1),
:
larger 2-isogeny graph diameters,
smaller number of spinal components, and
smaller proportion of 2-isogenous conjugate pairs.
To accompany the experimental results of this article, we have made the Sage code for all the computations available, along with a short discussion of the different algorithms included. The code is posted at https://github.com/krstnmnlsn/Adventures-in-Supersingularland-Data.
1.1 Related work
Adj, Ahmadi, and Menezes [Citation1] were the first to study the fine structure of the graph . In particular, they studied , which is the graph whose vertices are elliptic curves with fixed trace of Frobenius t and whose edges are -isogenies. They showed that the graph is isomorphic as a graph to . Our approach in the current article also studies a subclass of curves and the paths passing through these curves. After our preprint appeared [Citation2], a related approach was introduced by Boneh and Love [Citation4] to study a subgraph which contains supersingular curves with small non-integer endomorphisms. Such small endomorphisms can be used to efficiently compute isogenies between the special curves.
Shortly after our work was first posted [Citation2], Castryck, Panny, and Vercauteren posted a article on rational isogenies [Citation10]. Their work gives an algorithm for computing an ideal to connect two supersingular elliptic curves over which have the same -endomorphism ring. Their focus on -curves is parallel to our results regarding the structure of the isogeny graph and the spine .
More recently, Eisentraeger et al. [Citation14] gave a cycle finding algorithm to compute endomorphism rings of supersingular elliptic curves. A key part of their algorithm involves finding j-invariants that are -isogenous to their conjugates. Since this is done by performing random walks, they determine a lower bound for the size of the set of such j-invariants. This gives a partial answer to our Question 3 in Section 5.
2 Definitions
Let k be a finite field of characteristic and let E be an elliptic curve over k. We may assume that is given by an equation for some (and such that does not have a multiple root). A point on E is simply given by its coordinates (xP, yP) for . Elliptic curves have a group law given by algebraic formulas that can be efficiently computed. Moreover, the number of points in these groups can be counted fast, which makes them both particularly rich objects to work with and very handy objects for cryptographic constructions.
We focus on supersingular elliptic curves: Curves E/k with endomorphism ring a maximal order in a quaternion algebra. Equivalent definitions can be found in [24, Theorem V.3.1]. Endomorphism rings of elliptic curves with j-invariant in are characterized in [11, Prop. 2.4]: for p > 3, a supersingular elliptic curve can be defined over if and only if .
Supersingular elliptic curves can all be identified with a j-invariant in . We will use the notation Ej to fix an elliptic curve with j-invariant j. The j-invariants classify the -isomorphism classes of supersingular elliptic curves. When we instead consider supersingular elliptic curves with up to -isomorphism, two -isomorphism classes share the same j-invariant [11, Prop. 2.3]. One can distinguish between the two classes by the Weierstrass models of the elliptic curves.
2.1 Isogeny graphs
To introduce the graphs, we borrow the following notions from Sutherland [25, Section 2.2]. We denote by the -modular polynomial. We let Ej denote an elliptic curve of j-invariant j, up to isomorphism. This is a polynomial of degree in both X and Y, symmetric in X and Y, and such that there exists a cyclic -isogeny if and only if .
In principle, the modular polynomials can be computed and they are accessible via tables for small values of . However, their coefficients are rather large, as we see already for :(1) (1)
A separable isogeny is determined by its kernel [Citation24]. In addition, we will need the notion of equivalence of isogenies:
Definition 2.1
(Equivalent isogenies). Let k be a field. We say two separable isogenies between k-isomorphism classes of elliptic curves are equivalent if , for some automorphism ψ of the codomain.
Notice that equivalent isogenies share the same kernel, and inequivalent isogenies from E correspond to distinct roots of .
Definition 2.2
(Supersingular -isogeny graph over : ). The graph has vertex set -isomorphism classes of supersingular elliptic curves over , labeled by their j-invariants in . There is a directed edge from vertex j to for every root of the modular polynomial , considered with multiplicity.
We label the vertices of with j-invariants but sometimes it is more convenient to talk about elliptic curves. By definition, every edge corresponds to an -isogeny for any choice of Ej and .
Remark 2.3.
Every vertex in this graph has outgoing degree , however, vertices with j-invariant or 1728 have fewer incoming edges (due to automorphisms). Identifying isogenies with their dual isogenies makes this graph undirected and -regular except at those vertices or their neighbors. The graphs displayed in this article are pictured as undirected, so we expect irregularities in these figures at j = 0, 1728.
The isogeny graphs are Ramanujan graphs for (see [Citation7]). Kohel [19, Ch. 7] proved that every pair of supersingular elliptic curves are connected by a chain of -isogenies, which implies that the graph is connected. If p > 3, the number of vertices of is , depending on the congruence class of [24, Section V.4].
If j is a supersingular j-invariant, then so is its -conjugate jp. Moreover, because modular polynomials have integer coefficients, if j and satisfy then also (in )
This means that for any edge , there is a mirror edge .
This leads to the idea of a mirror involution on :
Definition 2.4.
The mirror involution on is the map defined by sending the vertex represented by to the vertex represented by jp.
A vertex is fixed under the mirror involution if and only if . We are interested in the subgraph of induced by these vertices:
Definition 2.5
(Spine). The spine is the induced subgraph of consisting of all vertices whose j-invariants lie in and all edges between them in .
Note that many of the edges do correspond to isogenies defined over but there can be edges coming from isogenies only defined over . In Section 3, we determine all possible such edges.
The number of vertices in the spine depends on the class number of the imaginary quadratic field and is of size . The size, shape and number of connected components of the spine will be studied in Section 3.
To study the spine, we introduce some notation that will help keep track of whether the j-invariants we are studying are defined over or not: Whenever we want to stress that a j-invariant of an elliptic curve lies in , we use bold letters (such as j). If we want to stress that a particular j-invariant lies in , we will use the more curly bold .
We were motivated to study the spine because the vertices may play a role in attacks on Supersingular Isogeny Graph-based cryptosystems. In [Citation11], Delfs and Galbraith construct an isogeny between two supersingular elliptic curves by first finding an isogeny from each curve to a curves whose j-invariant lies in , and then constructing an isogeny between the curves in . They argue that while taking random walks in , one can find elements in with probability given (roughly) by the size of the subgraph divided by the size of the full isogeny graph. However, we will see in Section 3 that there is still a lot of structure in that cannot be discounted.
In Sections 4 and 5, we then investigate other questions relating to whether the spine is close to a random subgraph or whether the bountiful structure of the spine is visible inside the Supersingular Isogeny Graph .
To explain the terminology ‘spine’: Starting from , we can construct by adding j-invariants in conjugate pairs: starting with j in , if there is an isogeny from to , there is a conjugate isogeny from to the conjugate . Hence we imagine the ‘spine’ as being the backbone of the Supersingular Isogeny Graph .
Definition 2.6.
We say that a path P with vertices (considered as an undirected path) is a mirror path if it is invariant under the mirror involution.
There exists at least one mirror path between any two conjugate j-invariants: it suffices to find a path from one j-invariant, say , to an j-invariant and then conjugate this path.
In general, mirror paths have either the formpassing through an -vertex, or passing through a pair of conjugate j-invariants.
2.2 Special j-invariants
In this section, we discuss j-invariants with special properties which require attention in the discussions to follow, focusing on j-invariants with extra automorphisms and then on j-invariants that are contained in very short cycles in : self-loops and cycles of length 2 (double edges).
2.2 Automorphisms
First, and correspond to curves with extra automorphisms, which make the graph undirected (see Remark 2.3). The j-invariant is supersingular if and only if and is supersingular if and only if (see [24, Chapter V]).
2.2 Loops
Loops in the graph are easily read off from the factorization of : a vertex represented by a j-invariant j admits a loop if and only if . For , factoring over the polynomial from (1) we get:(2) (2)
Therefore, loops in are only possible at the vertices (two loops), (one loop, explained in Example 3.8) and (one loop). These j-invariants need not be supersingular for a particular prime p, so they do not always appear in .
2.2 Double edges
The following lemma describes double edges in the -isogeny graph. This lemma applies mutatis mutandis for ordinary curves, replacing by the -isogeny graph of ordinary elliptic curves.
Lemma 2.7
(Double edge lemma). If two j-invariants j1, j2 in the -isogeny graph have a double-edge between them, then j1 and j2 are both roots of the polynomial (3) (3)
The degree of is bounded by .
Proof.
Suppose that j1 and j2 are two vertices in the -isogeny graph connected with a double edge. Considered as a polynomial in Y, the polynomial for some . The derivative with respect to Y then also vanishes at . The polynomials and share the root X = j1, and so by definition j1 is a root of the resultant . This argument is also true for j2, so j2 is also a root of .
The total degree of is and the total degree of is . Since the resultant of two polynomials P(X, Y) and Q(X, Y) of total degrees d and e generically has degree , we obtain the bound □
Example 2.8
(Double edges for ). For , we can factor the resultant over as follows:(4) (4)
Therefore, any double edge in can only appear between j-invariants from this list: or a root of .
By factoring for these values, we can for instance see that is the only j-invariant that admits a triple edge in .
Remark 2.9
(Short cycles and tightness of the bound). Note that the bound on the degree in Lemma 2.7 is not tight. For example for , the bound is 12 whereas the polynomial has degree 9. A sharper estimate could be obtained as a sum of class numbers using an approach from [Citation6] as follows. A double edge in gives a cycle of length 2 in the same graph. Short cycles were already studied in [Citation6], where it was shown that for a fixed , the existence of short cycles depends on congruence conditions on p. A short cycle of length n corresponds to an element of norm in the endomorphism rings of the curves whose j-invariants form this cycle. For instance, a double edge in gives a non-trivial quadratic element of norm 4 in . Elliptic curves defined over a number field with CM by an imaginary quadratic field K reduce to supersingular elliptic curves modulo p if p is inert in K. The only imaginary quadratic fields that contain an element of norm 4 are and and the factors of are the Hilbert class polynomials for these fields. So it is not surprising that the resultants factor as a product of Hilbert class polynomials for imaginary quadratic fields, and thus the degree of can be bounded by the sum of the class numbers of these imaginary quadratic fields. For any given , there are at most such imaginary quadratic fields possible, all with discriminant bounded by . So to get a sharper bound on the degree, we only need to sum the class numbers of these quadratic fields.
3 Structure of the -subgraph: the spine
In this section, we investigate the shape of the spine , which was introduced in Definition 2.5 as the subgraph of consisting of the vertices defined over . The motivation for studying the structure of this subgraph is the existence of attacks on SIDH that work by finding j-invariants. This idea was presented in [Citation11], and a quantum attack based on it was given by Biasse, Jao and Sankar [Citation3]. See also [Citation15] for an overview of the security considerations for SIDH.
In Section 3.1, we start with the graph , the structure of which is understood well. We base our investigations on the study of done by Delfs and Galbraith in [Citation11].
Moreover, a version of the -graph (allowing edges corresponding to -isogenies for multiple primes) has also been proposed for post-quantum cryptography in [Citation8]. We recall the results of [Citation11] in some detail and give a few explicit examples of their results about endomorphisms of certain elliptic curves.
In Section 3.2, we discuss how the spine can be obtained from in two steps: first vertices corresponding to the same j-invariant are identified and then a few new edges are added. The possible ways the connected components can identify are given by Definition 1 and we call them stacking, folding, attaching along a j-invariant and attaching by a new edge.
In Section 3.3 we study stacking, folding and attaching for and give an example of the theory we develop for in Section 3.3.1. In this section we also give a complete description of stacking, folding and attaching in Theorem 3.21. We return to the case in Section 3.4, giving a similar complete description in Theorem 3.29 and some data on how often attachment of distinct components happens. Section 3.5 contains some experimental data on the distances between the connected components of .
In this section, we assume that all elliptic curves are supersingular.
3.1 Structure of the -Graph
To study the spine , we will use the following isogeny graph defined over , first studied by Delfs and Galbraith [Citation11].
Definition 3.1
(Supersingular -isogeny graph over ). The graph has vertex set the -isomorphism classes of supersingular elliptic curves defined over . The edges correspond to -equivalence classes (in the sense of Definition 2.1) of -isogenies defined over .
For p > 3, each supersingular j-invariant corresponds to exactly two -isomorphism classes of curves. These curves can be distinguished by other invariants (such as the c4 and c6 values from [24, III.1]). We will use notation such as va and wa to denote the vertices corresponding to the two twists with j-invariant a. For visualization, we will label the vertices of the graph only by j-invariants.
Remark 3.2.
We highlight the differences between and :
has half as many vertices as , since the vertices in the spine are considered up to -isomorphism and up to -isomorphism in the graph .
can have edges between j-invariants previously not connected in . However, we will show in Lemma 3.14 that this is a fairly rare occurrence.
We will use the equivalent definition of supersingularity for elliptic curves over pointed out by [Citation11]: an elliptic curve is supersingular if and only if . If , the order is strictly contained in the maximal order . It is convenient to distinguish these two cases:
Definition 3.3
(Surface and Floor). Let E be a supersingular elliptic curve over . We say E is on the surface (resp. E is on the floor) if (resp. ).
Note that for , surface and floor coincide.
Definition 3.4
(Horizontal and Vertical Isogenies.). Let be an -isogeny between supersingular elliptic curves E and over . If then is called horizontal. Otherwise, is called vertical.
The following is Theorem 2.7 of [Citation11].
Theorem 3.5
(Structure of ). Let p > 3 and be primes.
For , there are no vertical isogenies. If , then there are two horizontal -isogenies from each vertex and beyond this no other -isogenies. Hence every connected component of is a cycle.
Case . There is one level in : all elliptic curves E have . For : from each vertex there is one outgoing 2-isogeny.
There are vertices on the surface (which coincides with the floor).
Case . There are two levels in : surface and floor. For :
If , there is exactly one vertical isogeny from any vertex on the surface to a vertex on the floor, every vertex on the surface admits two horizontal isogenies and there are no horizontal isogenies between the curves on the floor.
There are vertices on the floor and vertices on the surface.
If , from every vertex on the surface, there are exactly three vertical isogenies to the floor, and there are no horizontal isogenies between any vertices.
There are vertices on the floor and vertices on the surface.
This implies that every connected component of is an isogeny volcano, first studied by Kohel [Citation19]. For a reference on the name and basic properties we refer to [Citation25].
Let and be a prime above in , and the class number of K. Let n be the order of in . The surface of any volcano in is a cycle of precisely n vertices. There are h/n connected components (volcanoes) in , the index of in .
The following lemma is due to [Citation11].
Lemma 3.6.
Let p > 5. Let E be a supersingular elliptic curve defined over . Then
Note that for , the ring is not an order of , so no supersingular elliptic curves in have their full 2-torsion defined over .
We recall the following definition from [Citation24]: a twist of an elliptic curve E over a field K is a curve which is isomorphic to E over . Two twists are considered equivalent if they are isomorphic over K. The group of twists of a given elliptic curve is given by the standard formula in [24, Proposition X.5.4]. For the field , every supersingular j-invariant will have precisely two isomorphism classes of twists: Curves with j-invariant not equal to 1728 have two isomorphism classes of quadratic twists, and j = 1728 has two isomorphism classes of quartic twists.
The following corollary of Lemma 3.6 will be essential in our discussion in Section 3.4.
Corollary 3.7
(Endomorphism rings of quadratic twists). Let p > 3 be a prime, let E be an elliptic curve defined over and let Et denote its quadratic twist. Then
Proof.
Suppose . Then the quadratic twist is , where d is a quadratic non-residue and the isomorphism over is given as So if and only if . □
Example 3.8
(The j-invariant 1728 is both on the surface and on the floor). Suppose . The isogeny given asis a vertical 2-isogeny with kernel (0, 0) of non--isomorphic elliptic curves with j-invariant 1728.
Note that the curves in Example 3.8 are quartic, not quadratic twists, so this example does not contradict Corollary 3.7. The example is, up to equivalence, the only vertical isogeny between two supersingular elliptic curves with the same j-invariant.
Corollary 3.9.
If , then the two distinct vertices corresponding to the j-invariant are either both on the floor or on the surface of .
Another proof of this statement can be found in the appendix of [Citation17] and is obtained by a careful examination of Hilbert polynomials of discriminant – p and , considered modulo p.
3.2 Passing from the graph to the spine
To understand the graph , we will describe it as a certain quotient of the graph under an equivalence relation which identifies some vertices and some edges. This will allow us to identify which edges in do not come from isogenies already defined over and describe the shape of the spine using the easily visualized graph .
We can obtain the spine from the graph in the following two steps:
Identify the vertices with the same j-invariant: these two vertices of glue to a single vertex on . Identify equivalent edges.
Add the edges from between vertices in corresponding to isogenies which are defined over .
Recall the notation that for a j-invariant a, the two vertices in corresponding to this j-invariant will be labeled va, wa. We extend this notation as follows: the vertex va, resp. wa will lie on the connected component V, resp. W, of . Note that V and W are not necessarily distinct. The vertex correspoding to a in will be simply denoted by a.
Remember that is not a subgraph of since both the vertices and edges of may be merged in . However, distinct edges from the same vertex in correspond to distinct edges in .
Lemma 3.10
(-edges from one vertex). Let E be an elliptic curve with defined over (with ). Suppose that there are two -isogenies from E defined over . Then they are equivalent over if and only if they are equivalent over .
Proof.
If the isogenies are equivalent over via a pair of -isomorphisms, then they are equivalent over as well.
The reverse direction is easiest to see from the kernel definition of equivalence. If the kernels of and are equal over they are certainly equal over .
One can see the isogeny definition implies the kernel definition as follows. Let and be two isogenies that are equivalent over . We want to show that they are equivalent over . By hypothesis, there exist (-)isomorphisms and such . We know that the kernel of the map is . Therefore, the kernel of the map is also . This means that By the hypothesis on j(E), we have , and since , it follows that . □
Lemma 3.10
for gives the following corollary.
Corollary 3.11.
If an elliptic curve E with j-invariant j in has 3 neighbors with j-invariants and (not necessarily distinct), then the 3 neighbors of j in have j-invariants and .
Example 3.12.
() If the vertex va has neighbors in (with b, c, d not necessarily distinct), then the three neighbors of vertex a in are b, c, d.
Since there are at most 2 neighbors of any vertex in for , the above corollary does not generalize. However, it is true that if the neighbors of va, wa have j-invariants , then there are (not necessarily distinct) edges and in . In Lemma 3.17, we will show that typically and explain how to find j-invariants a for which this property fails.
Let V and W be two components of . Passing from to the spine , the following can happen (and we will show that the list of events is complete):
Definition 3.13
(Stacking, folding and attaching).
We say that the components V and W stack if, when we relabel the vertices va by the j-invariant a, they are the same graph.
We say that the component V folds if V contains vertices corresponding to both quadratic twists of every j-invariant on V. The term is meant to invoke what happens to this component when the quadratic twists are identified in .
Two connected components V and W of become attached by a new edge in if there is a new edge corresponding to an isogeny between vertices and that is not defined over .
(for ) We say that components V and W attach along the j-invariant a if they both contain a vertex with j-invariant a and the j-invariants of neighbors of va in V and the neighbors of wa in W do not give the same (multi)sets.
Examples of the first three of the four above are given by . An example of attachment along a j-invariant can be seen in . It can happen that an attachment is actually attaching the component V to itself. See . We will show that attachment along the j-invariant for cannot happen in Corollary 3.24, however, the j-invariant 1728 is the only possible j-invariant for which the two vertices in do not have the same neighbor set (Proposition 3.22), but in this case these vertices are already connected by an edge.
We now begin analyzing the ‘new’ edges in : the edges that do not come from isogenies defined over . For an elliptic curve E, all -isogenies are given by order subgroups of the -torsion subgroup . An -isogeny is defined over if and only if its kernel is fixed by the Frobenius endomorphism. Note that this does not mean that all the points in the kernel need to be fixed by Frobenius.
Let us look at again: the edges in the spine between vertices corresponding to j-invariants 150 and 189 in do not correspond to isogenies defined over . Also, the vertex 4 (and note ) on the floor of has no edge to a curve with j-invariant 19, but there is an edge coming from the two isogenies from vertex 4 on the surface. Lemma 3.10 gives us that there is a double edge . This not a coincidence, as we explain in Lemma 3.14.
Lemma 3.14
(One new isogeny implies two new isogenies). Let correspond to -elliptic curves Ea and Eb with j-invariants a, b respectively with . Assume that there is no edge , but there is an edge . Then there are two isogenies defined between which are inequivalent over and hence a double edge .
Proof.
We know that there is an -isogeny to some elliptic curve E with j-invariant b. Since j(E) = b, then E is isomorphic to Eb over . Composing with this isomorphism, we obtain an -isogeny . However, ψ cannot be defined over , since we assumed there was no edge .
The kernel of ψ is not defined over (otherwise ψ would be defined over ), so the p-power Frobenius map does not preserve . There is an isogeny from Ea with kernel . This isogeny has degree since has order and it is not equivalent to ψ. Using the construction of isogenies from Vélu’s formulae [Citation27], we obtain the rational maps for defining . In particular, the j-invariant of the target of is necessarily . Hence, there are two inequivalent isogenies between Ea and Eb and hence two edges . □
The corollary below explains why for both attachment by a new edge (cf. and ) and attachment along a j-invariant (cf. ), we always see double edges.
Corollary 3.15.
Attachment of components by a new edge from va to wb forces a double edge in . Attachment along the j-invariant j implies a double edge from j in .
Proof.
In the first case, we are adding an edge between va and wb that is not defined over and we can directly apply Lemma 3.14. In the second case, assume there is a neighbor vb of such that wb is not a neighbor of . Apply the Lemma 3.14 to the isogeny from to vb. □
Because we take the isogeny graphs undirected, we need to make choices at or . In this case, double edges might get identified because of the choices for the undirectedness of the graph.
3.3 The spine for
For this section, we consider the spine for . In this case, there are no vertical isogenies, hence the graph is a union of disjoint cycles: the cycles of vertices corresponding to curves either only with endomorphism ring , or only with endomorphism ring . The main tool for understanding the spine will be the Neighbor Lemma 3.17, in which we show that the vertices va and wa have neighbors with the same j-invariants, provided . If the neighbors have different j-invariants, then we would get attachment along a vertex and this situation we solve in Proposition 3.16. Using the information about the shape of the graph and the neighbor lemma, we can completely describe the spine in Theorem 3.18.
We will avoid the case when the graph is just a disjoint union of vertices (i.e., when there are no isogenies defined over ) by assuming is split in . If one assumes that , then and there are -rational points of order . We will also assume that the class number is odd, which is equivalent to .
Proposition 3.16
(Attachment along a vertex can only happen at a vertex with automorphisms). Let p and be primes satisfying . Let j be a j-invariant such that attachment along a vertex happens. Then , the two neighbors in of v1728 have the same j-invariant and the neighbors of w1728 have the same j-invariant.
The proof below uses the properties of the -endomorphism ring as a maximal order in a quaternion algebra. For references see Kohel’s thesis [Citation19], the work of Kaneko [Citation17] and Ibukiyama [Citation16].
Proof.
We first show that j corresponds to an elliptic curve with automorphism group larger than , so or 0. Then, we show that cannot happen.
Let E be a supersingular elliptic curve and let be its endomorphism ring. Recall that is a maximal order in a quaternion algebra. Every element is quadratic, meaning α generates a quadratic number field .
From Kaneko’s Theorem 2’ [Citation17], we know that If are maximal quadratic orders lying in different imaginary quadratic fields that embed to then
Suppose now that we have attachment at a vertex j. Let va, vb be the neighbors of and let wc, wd be the neighbors of , with . Then, by Corollary 3.15, there is a double edge from and, by symmetry, there is a double edge from either c or d, assume without loss of generality that it is from c. Any double edge gives a non-trivial element of norm in . Let α denote the cycle arising from the double edge at a, and γ the cycle arising from the double edge at c.
Suppose that α and γ generate different quadratic number fields. Then, we observe thatand we obtain a similar statement for γ. Using Kaneko’s theorem we deduce that which is impossible for . We conclude that α and γ generate the same quadratic field, say K. Let be the ring of integers in K. By uniqueness of ideal factorization:
Since cannot be inert. If is ramified, we see:for some unit . It is not possible that , so .
If splits, suppose without loss of generality that . Then eitherfor some unit . Again implies that has non-trivial units and .
Curves with automorphism group larger than correspond to . Suppose . If there is an isogeny from an elliptic curve E0 to an elliptic curve Ea with j-invariant a, there have to be at least three distinct isogenies from E0 to Ea: precompose the first one with . However, suppose that there were three edges from 0 to a. By symmetry, there would be three edges from 0 to c in . By combining these edges, we would have 6 cycles from 0 of length 2. But even in , up to sign (±), there are not enough different elements of norm .
Hence attachment along a vertex can only happen for . □
Lemma 3.17
(The neighbor lemma). Suppose . Let and suppose that va, wa are the two vertices in corresponding to elliptic curves with j-invariant a. If the neighbors of va have j-invariants b, c, then then neighbors of wa have j-invariants b, c.
Proof.
Let wd, we be the neighbors of wa in . If , then there is attachment along the j-invariant a, which is only possible for . Hence the neighbors of va and wa have the same j-invariants. □
Recall that the attachment of components by a new edge implies a double edge by Corollary 3.15. The main result of this section is the following one.
Theorem 3.18
(Stacking, folding and attaching for ). Let p be a prime and let be such that the order of the prime above in the class group of is odd. While passing from to , the following happens:
the components containing 1728 fold and get attached along the j-invariant 1728 (this only happens if ),
all other components stack,
the number of new edges is bounded by and there are at most n vertices at which a new edge is added, where n is the number of distinct roots of .
Note that the conditions on p and are always satisfied when and , which is the most cryptographically relevant application.
Proof.
We will pass from to in two steps: first, we identify the j-invariants and equivalent edges in , and after discussing what happens with the components of , we add the new edges in .
We showed in Lemma 3.17 that for , the vertices va and wa have the same neighbors.
Suppose there is a component V that does not stack. This either means that there is a vertex va whose neighbors are different than those of wa. But in this case a is an attaching j-invariant and so a = 1728 and we will treat this case later.
Or, there is a j-invariant a such that both the vertices va, wa are in the component V. We know that V is a cycle with odd number of vertices. The vertices va, wa divide the cycle in two halves. Choose either half H. Look at the neighbors of va and wa. If they have the same j-invariant b, replace a with b and continue moving along the halves of the cycle, until either of the following happens:
the vertices va and wa are neighbors in and hence will induce a loop in . Note that in this case, the number of vertices in H is necessarily even.
The only neighbor of va and wa is a vertex vj with j-invariant j. This is necessarily an attaching j-invariant because the neighbors of wj cannot have j-invariants a. Hence . This also means that H has an odd number of vertices.
The neighbor vb of va has j-invariant b and the neighbor wc of wa has j-invariant c, for . Then either the other neighbor of wa is wb or a is an attaching j-invariant (and a = 1728). Suppose a is not an attaching j-invariant. Continuing along the whole cycle V in the direction of the edge , and symmetrically in the direction of , we will reach a point when the neighbor of some vc is not a neighbor of the wc. This happens when the cycle has an odd number of vertices because two identical paths would give us a cycle of even length. Here we also obtain an attaching j-invariant.
The cases above actually cover every possibility: if we are in case (3.3), the half H has an even number of vertices, and then necessarily has an odd number of vertices and since the neighbors of va, wa have to have the same j-invariant, we are in case (3.3).
Let us remark that the last case (3.3) shows that the isogenies between twists go ‘in the other direction’: if one walks on the cycle V in the direction of the edge , one will encounter an edge , not an edge .
We now discuss what happens with the components that contain 1728. We know that there are two components V and W containing curves with j-invariant 1728. Let be on the surface (with curves having ) and let be on the floor (with curves having ). We have shown in 3.16 that both v1728 and w1728 have two neighbors neighbors with the same j-invariant. We will show that both the components fold.
Starting at the vertex , we know that its neighbors va, wa have the same j-invariant by Lemma 3.16. Start walking away from v1728. By the Neighbor Lemma 3.17, the neighbors of the vertices va, wa that are different from v1728 have the same j-invariants. Continuing this reasoning, since the cycle contains an odd number of vertices, one finally arrives at a pair of vertices vb, wb with same j-invariant b, which are connected by an -isogeny. The same proofs holds for the component W containing w1728.
Finally, adding new edges that are only defined over , some components can get attached. However, we have proved in Corollary 3.15 that an attachment by a new edge from j to double means a double edge . Hence j and are both roots of by Lemma 2.7, which has degree bounded by . □
Remark 3.19
(The ‘other side’ of 1728). We showed that the only component for which attachment by a vertex can happen are the two components containing 1728, moreover these components fold. This means that the neighbors of v1728 have the same j-invariant, their neighbors as well and if we continue walking along both sides, we will ultimately meet ‘opposite of’ v1728 at a pair of conjugate j-invariants. See . Conversely, any such pair of conjugate j-invariants needs to be ‘opposite’ of a vertex with j-invariant 1728.
Since posting the first version of our article which did not fully explain these ideas, Castryck, Panny and Vercauteren posted a preprint [Citation10] that arrives at the same conclusion using more highbrow tools. Their approach identifies the ‘opposite’ j-invariant as a certain CM j-invariant.
As noted Corollary 3.15, attachments imply double edges. To find vertices with attachment, we can use Lemma 2.7. Conversely, if we want a prime p with no attachments, we can find a congruence condition on p such that none of the roots if are supersingular j-invariants.
3.3.1 Example: the spine for
In this section, we decsribe the spine for by means of stacking, folding and attaching behavior for . The case is interesting, because of the use of in SIDH and SIKE (and analogously, the case will be discussed in Section 3.4). Since the starting vertex for these protocols is typically taken in , understanding the spine is important for understanding where the j-invariants are located in the graph .
We start with factoring over the polynomial introduced in (3):
The irreducible factors are Hilbert class polynomials of discriminants and –35, respectively. Removing the repeated factors, we see that there are at most 10 vertices at which a double edge can occur.
Double-edges also arise in loops (double self-3-isogenies), which accounts for some of the factors of . We find the self loops by factoring the modular 3-isogeny polynomial:
At and , there are two self-3-isogenies and no attachment at these vertices.
Example 3.20
(Vertices with loops). In this example, we determine the neighbors of and –32768. This is done by factoring :
: Factor . The isogeny v0, w0 is defined over : the factor x has multiplicity 1, so it is not a double-edge and cannot appear only over . Moreover, the neighbors of v0 are w0 and and the neighbors of w0 are and v0. Hence there cannot be attaching edges.
: There is one self-3-isogeny which arises from a 3-isogeny ψ between (non-isomorphic) quadratic twists with j = 54000 and that can be written explicitly. Factoring we can check that the j-invariant 54000 does not admit a double edge.
: we have and so there is a double loop . Neither of the loops occur over : both cannot occur over because there are no double edges in . If only one of them came from an isogeny over , then we could use Lemma 3.14 to get a third loop, which is not possible (for large p).
: again, . Repeating the argument we gave above for , the self loops cannot come from isogenies over .
To conclude: For and 54000, the self-3-isogeny comes from an isogeny between the twists in , and for , the double self-3-isogenies are not defined over .
The following theorem is a specialization of Proposition 3.18. We are mainly interested in the cryptographic applications, so we restrict to the case . Then, the class numbers and are both odd. With our assumption , we have .
Theorem 3.21
(Stacking, folding and attaching for ). Let p be prime, . When passing from to the spine ,
all components that do not contain 0 or 54000 stack,
there are two distinct connected components V and W that contain a j-invariant 1728, one of them contains both vertices with j-invariant 0 and the other one both vertices with j-invariant 54000. V and W fold and get attached at the j-invariant 1728.
At most 8 vertices admit new edges, attaching at most 4 pairs of components by a new edge.
Proof.
This follows from Theorem 3.18. In Example 3.20, we showed that the only possible opposite vertices have j-invariants 0 and 54000. For , there are two components containing 1728: by Example 3.8, one of the vertices corresponding to 1728 is on the floor and the other one is on the surface, so they are on different components of . One of these vertices is on the same component of as the vertices with j-invariant 0 and the other one will contain both vertices with j-invariant 54000. The rest comes from looking at the factors of . □
3.4 The spine for
In this section, we describe the spine for . The added difficulty are vertical isogenies (see Definition 3.4). We describe how the components of come together in in a way analogous to (see Theorem 3.29). We determine whether attachment can happen for and (see Corollary 3.30) and we give experimental data on .
Delfs and Galbraith [Citation11] described the possible shapes for , which we will extensively use in this section:
Table
Recall that we form the graph from in two steps: first merge vertices corresponding to the same j-invariant and their edges, then add new edges. We will show that:
Two vertices with the same j-invariant also have the same j-invariants as neighbors (Proposition 3.22). This will imply that only stacking and folding is possible in Theorem 3.29.
At most one component folds, and for this is the component containing (Proposition 3.26).
Attaching of components by a new edge happens between at most one pair of vertices, and those vertices are roots of the Hilbert class polynomial of (Proposition 3.25).
We begin with some results on the neighbors of vertices with the same j-invariant. From Corollary 3.7, we know that (except for 1728) twists have isomorphic endomorphism rings and hence lie on the same level in the volcano. More is true:
Proposition 3.22.
Let j be a supersingular j-invariant and let and be two distinct vertices in corresponding to elliptic curves with j-invariant j. If , then two vertices with the same j-invariants have the same neighbors, that is:
If and the neighbor of is , then the neighbor of is .
If and if
the vertices and are both on the floor, then and are each connected to a vertex with j-invariant ,
the vertices and are both on the surface, then has 3 neighbors with distinct j-invariants a, b, c and has three neighbors with the same distinct j-invariants a, b, c.
Proof.
For , any connected component of is an edge. If and lie on the same component, then the result follows. Otherwise, the result can be obtained by contradiction and an application of Lemma 3.14.
If , Corollary 3.9 gives are either both on the surface and on the floor of their respective components.
If they are both on the surfaces of their respective components, then they each have three neighbors: one on the floor and two on the surface. The j-invariants of the neighbors of match the j-invariants of the neighbors of . Any coincidences of these j-invariants would contradict the fact that there can be no cycles of length 2: for , the class number is odd.
If they are both on the floors of their respective components, then they each have one neighbor on the surface. The j-invariants of these neighbors must be the same, otherwise we arrive at a contradiction via Lemma 3.14 as in 1.
Corollary 3.23
(Isogenies for twists). Let be an -isogeny of degree 2 and assume . Then, there is an 2-isogeny over between the quadratic twists .
Corollary 3.24
(Attachment along a j-invariant for ). Attachment along a j-invariant cannot happen for .
We already know that attaching two components by a new edge would imply a double edge (Corollary 3.15).
Proposition 3.25
(Possible attachment by a double edge). Attachment by an edge can only happen between vertices whose j-invariants correspond to the roots of
in , provided these are supersingular j-invariants not equal to or 0.
Proof.
By Lemma 2.7 and Corollary 3.15, any such attaching j-invariants need to be roots of . By examining the neighbors of the j-invariants 0, 1728 and –3375, we can easily see that they do not admit new edges coming from isogenies not defined over . □
Proposition 3.26
(The component of folds). Let be prime. The connected component containing the vertices corresponding to is symmetric over a reflection passing through the vertices v1728 lying on the surface of V and w1728 lying on the floor of V. In particular, the component V folds when we pass from to .
To understand this symmetry, picture the surface of the component V as a perfect circle with equidistant vertices and all the edges to the floor are perpendicular to the surface. Then V is symmetric with respect to the line extending the edge . See the leftmost component in . This symmetry has already mentioned in Remark 5 of [Citation8], albeit without proof or reference.
Proof.
Case . V is a claw (see ) and the proof of Proposition 3.25 shows that there is one 2-isogeny down from the surface vertex corresponding to to each vertex with j-invariant 287496 and the other vertex corresponding to j-invariant 1728. The claw V is clearly symmetric and folds as described.
Case . In this case, is odd. We may assume that (otherwise we are in the claw situation discussed above).
Then and are both on the surface. By Proposition 3.22, their neighbors have the same j-invariants, say: . Say the neighbors of v are va, vb and the neighbors of w are wa, wb. Assume that va is on the floor. Since , Lemma 3.9 tells us wa is also on the floor. Thus, both vb and wb are on the surface and the symmetry is preserved.
Continuing in this manner, because is odd, we will arrive at a pair of vertices that share an edge, accounting for all of the vertices in the component. The symmetry holds. □
Remark 3.27.
In Proposition 3.26 for , the opposite vertices from j = 1728 necessarily induce a loop in . Since are on the surface of , we conclude that (see Section 2.2). So there always is an -rational 2-power isogeny between any two supersingular elliptic curves with j-invariants 1728 and 8000.
Corollary 3.28
(Folding). Suppose is a component which folds when passing from to .
If , then V is a single edge between vertices with j = 8000.
If , then V contains both the vertices corresponding to .
Proof.
If , then V is an edge: . Folding happens if and only if a = b, resulting in a self-2-isogeny in . For , the only vertices with self-2-isogenies are , when these j-invariants are supersingular (see Section 2.2).
For j = 8000, there is a 2-isogeny from the curve with j-invariant 8000 given by the equation to its twist . The latter is a twist of E by 2, and 8000 is only supersingular for , so 2 is a nonsquare modulo p.
For , there are two self-loops in , and at least one of them is not defined over . Applying Lemma 3.14 to this loop, we conclude that neither of these loops are defined over and folding does not happen for the edge containing –3375.
If , then let V be a component that folds. The surface has vertices and this class number is odd. We assume that V folds, so every vertex in it gets identified with the vertex corresponding to its twist. By Corollary 3.9, for , the two vertices are either both on the surface or both on the floor. Since there are odd number of vertices on the surface, there cannot only be pairs of twists on the surface, so V must contain the two vertices corresponding to , one on the floor and the other on the surface. □
We are now ready to prove the main theorem describing the spine :
Theorem 3.29
(Stacking, folding and attaching). Only stacking, folding or at most 1 attachment by a new edge are possible. No attachments at a j-invariant are possible.
Proof.
First, let . The components of are edges. Corollary 3.28 shows that the edge containing the two vertices with j-invariant 8000 folds (if 8000 is a supersingular j-invariant for p, i.e., ). For the other edges, Proposition 3.22 says that for any edge the twists wa, wb also give an edge . Moreover, Proposition 3.25 gives that there is at most 1 attachment among these edges.
For , take any component V of and any vertex va on the surface of V, . Choose a neighbor vb of va. Continue along the surface in the direction of the edge and consider the sequence j-invariants of neighbors until we reach a vertex with j-invariant a. Similarly, on the component W containing the edge wa, wb, consider the sequence of j-invariants of the neighbors until we reach a vertex with j-invariant a (every surface is a cycle, so this will happen in finitely many steps). We have the following possible outcomes:
For some i, we find that . This means that the curve i away from va on V has a different neighbor than its twist, which is i away from wa. But this can only happen for bi = 1728 and hence the component folds by Proposition 3.26.
The sequences are equal, but stops at the twist wa and stopped at the curve va. Then va, wa are on the same component V and the cycle on the surface has length . As is odd, this is not possible.
The sequences and are the same: the components V and W are isomorphic as graphs upon replacing the labels of vertices by their j-invariants. The components V and W stack.
Finally, in Proposition 3.25, we showed that at most one attachment is possible. □
To conclude this section, we study the possible attachments given by the roots of the polynomial . Because the polynomial f(X) is the Hilbert class polynomial of , roots of f(X) in give a supersingular j-invariant if and only if . By factoring the discriminant of f(X) as we see that there is a root in if and only if . Combining these, we obtain that the roots of f(X) are j-invariants of a supersingular elliptic curves defined over if and only if or .
We have an additional result about when attachment occurs, as a corollary to Proposition 3.25:
Corollary 3.30
(Attachment happens for ). Suppose that and suppose that j and are two distinct -roots of (it suffices to assume p > 101). Then, the new edge is an attaching edge.
This means that attachment happens whenever it can happen (i.e., when the roots of f(X) are in ) for . This is not true for (See Section 3.5).
Proof.
First, let . The components are horizontal edges. Suppose that the j-invariant j admits a double edge that it is not an attaching edge, i.e., there is an edge in . By Lemma 3.14, there is then a triple edge . This is only possible if . For j or to be equal to 0, we would need X to be a factor of f(X). Since , for p > 11 attachment happens whenever it can.
Next, let . The components of are claws. If the double edge is not between two different components, then and are on the same claw (for some choice of the twists). Assuming, , they both lie on the floor.
Let va be the unique surface vertex of V (see ). This gives us two distinct loops in of length 3 corresponding to endomorphisms of norm 8 in .
To check for the existence of such an endomorphism, we need to check whether the roots of f(X) can simultaneously be the roots of the modular polynomial . Taking the resultant we get
For primes p > 101, this will be nonzero, and there is no such a loop in ; hence, attachment happens. In the factorization of the resultant, there are two primes satisfying and . For p = 11, we only have one connected component of , for p = 59, attachment happens. □
In the case , not all attachments that can happen necessarily do. We checked this for all primes between 50, 000 and 100, 000 such that the primes above 2 do not generate the class group (in this case, there is clearly only one connected component of ). There are 217 such primes, and for 41 of them the attachment happens. However, there are 12 primes p for which the attachment can happen ( or 59 ) but there is no attachment. For instance, for p = 53639, the two roots of f(X) are and . There are two elliptic curves with these j-invariants on the same component of which are 48 edges apart.
3.5 Distances between the components of the
In Sections 3.3 and 3.4, we described how the spine is formed by passing from to . In principle, one can then describe the shape and connectedness of based on the knowledge of and congruence conditions on p. A natural and important question is how the spine sits inside the graph . We study this question for .
For primes , the subgraph is given by single edges (with a possibility of an isolated vertex and one component of size 4), as we showed in Section 3.2. We expect the distances between components of the graph to behave like the distances between random vertices of the graph. To investigate if the -components are somehow distinguished, we compare the distances between -components with the distances between random vertices of the graph: In , we compare these distances for 254 primes with from 10253 to 65437. The primes were chosen to be spaced with a gap of at least 200. To approximate the distance between random points, we sample the distances between 100 pairs of random points on the graph. The vertical axis of this figure represents the difference [(average distance of -components) – (average distance between 100 random pairs of points)]. For this range of primes, the average distances between -components ranged between 8.20 and 10.95. The average distances between pairs of randomly chosen vertices ranged between 7.82 and 10.85. Notice that these differences are mostly positive: The average distances between components is slightly larger than distance between two random points in (around 3.6% larger).
We now consider the case where . In this case, the graph is a union of 2-level volcanoes, each with vertices on the surface and vertices on the floor. The size of the surface of any volcano is the order of the prime above 2 in the class group . If a prime above 2 generates the class group, is connected and so is . The converse is not true, as it is possible for to become connected via attaching. In this case, we again compare the distances between -components and the distances between random vertices. In the range , there are 217 primes for which a prime above 2 does not generate the class group. For these 217 primes, we observed that for 12 primes, the spine is nonetheless connected. For 57 of those primes, there were exactly two connected components. The distances between these connected components was less than or equal to 6.
The graphs have between 5400 and 8300 vertices and diameters of length between 14 and 16. For 2-isogeny graphs of this size, the average distance between two random vertices is around 9 ( diameter). This number grows slowly (for primes , the average distance between two random vertices is diameter) and we expect it to converge to the diameter. We also computed the average of the mean distances between connected components of for these primes. The mean is 4.3395, with standard deviation 1.1092. The maximum is 7.000 and the minimum 2.333, which indicates that the components tend to be close to each other.
3.6 The number of components in the spine for
In this section, we briefly comment on the number of connected components of and relatedly, on the number of connected components in . By Theorem 3.29, we know at most one component of folds, and at most two components are attached by a new edge. It is therefore easy to determine the approximate number of components depending on the size of the spine and the shape of the connected components in .
The number of vertices in can be determined from [Citation9]where h(d) is the class number of the imaginary quadratic field . Using standard estimates for class numbers, one typically approximates .
4 Conjugate vertices, distances, and the spine
The existence of mirror paths (see Definition 2.6) in motivates us to question their length in relation to the diameter of the graph. Delfs and Galbraith [Citation11] show that if one navigates to the spine , one can solve the path finding problem in subexponential time using the quantum algorithm in [Citation3]. This leads naturally to the question of how the spine sits in the full -isogeny graph. We consider these questions from three perspectives in this chapter. In Section 4.1 we study the distance between Galois conjugate pairs of vertices, that is, pairs of -invariants of the form , . Our data suggest these vertices are closer to each other than a random pair of vertices in . In Section 4.2, we test how often the shortest path between two conjugate vertices goes through the spine (contains a j-invariant in ). We find conjugate vertices are more likely than a random pair of vertices to be connected by a shortest path through the spine. Finally, we continue to examine the question of navigating to the spine by considering the distance between arbitrary vertices and the spine in Section 4.3.
4.1 Distance between conjugate pairs
Isogeny-based cryptosystems such as cryptographic hash functions and key exchange algorithms rely on the difficulty of computing paths (routing) in the supersingular graph . Our experiments with show that two random conjugate vertices are closer than two random vertices. These shorter distances may indicate that it is computationally easier to find paths between conjugate vertices, when compared with random graph vertices. We analyze the differences between these distances in this section, using the following experimental practices: Given prime p, we constructed the graph . Then we computed the distances between all pairs of -vertices . These values were organized into two lists:
We call the pairs from Cp conjugate pairs and pairs from Ap arbitrary pairs.
The distributions Cp and Ap for p = 19489 are shown in . For a larger prime, it is too costly to iterate over all vertices. Instead, we took a random sample of 1000 conjugate and arbitrary pairs. The data collected for the prime p = 1000003 is shown in .
In these examples, we see different distributions for the conjugate pair distances compared with the arbitrary pair distances. For both primes, conjugate pairs are more likely to be closer than arbitrary pairs. This indicates that conjugate pairs of vertices have a somehow special position in the graph. This is likely related to the fact that the neighbors of curves with conjugate j-invariants are also conjugate, as discussed in Section 2.
In , we see a clear bias toward paths of odd length (that is, paths with an odd number of edges). This is due to the fact that conjugate j-invariants often admit a shortest path that is a mirror path (Definition 2.6). These paths do not usually go through the spine , so they have an even number of vertices and an odd number of edges. This topic is studied further in Section 4.2.
Further studies on a broader sample of primes would be required to fully explore the differences between the distributions of distances between conjugate and arbitrary vertices.
4.2 How often do shortest paths go through the spine
Motivated by the work of Delfs and Galbraith [Citation11], we consider the question of how easy it is to navigate to the spine . In their work, Delfs–Galbraith use L-isogenies to navigate to the spine , where L is a set of small primes. We study the situation when . Any path from to a vertex j in the spine can then be mirrored to obtain a path of equal length from j to , and hence a path between and passing through the spine. This construction motivates the following definition:
Definition 4.1.
A pair of vertices are opposite if there exists the shortest path between them that passes through the spine.
4.2.1 Experimental methods
We used built-in functions of Sage [Citation26] to perform our computations. We tested how often a shortest path between two conjugate vertices went through the spine . Shortest paths are not necessarily unique, so it is not enough to compute a shortest path and check whether it passes through the spine. Instead, to verify whether a pair is opposite, we run over all vertices in and check whether there is a j such that
For smaller primes (< 5000), we computed the proportions for all pairs of vertices in . For larger primes, we randomly selected 1000 pairs of points in and checked whether each of the pairs were opposite.
In the following two subsections, we present these data sorted in two ways: comparing conjugate pairs and arbitrary pairs, and comparing differences in distances between arbitrary vertices for different congruence classes of .
4.2.2 Conjugate pairs vs. arbitrary pairs
For each prime p ranging between 50000 and 100000, we sampled data from 1000 random conjugate pairs of vertices and 1000 pairs of arbitrary vertices. We computed the proportions of conjugate pairs which are opposite and the proportions of arbitrary pairs which are opposite. This data is displayed in .
Our data suggest conjugate vertices are more likely to be opposite than arbitrary vertices and that this bias increases with p. For the primes displayed in , conjugate pairs are more than four times as likely to be opposite, compared with arbitrary pairs. For (not displayed), conjugate pairs are approximately twice as likely to be opposite than random pairs.
The graph can be symmetrically constructed from by adding edges and mirror edges at once, leading one to suspect to be central to the graph. However, we have found the shortest paths between arbitrary pairs of vertices are less likely to pass through the spine, contradicting that perspective.
4.2.3 Varying the residue class of p
In this section, we consider only arbitrary pairs of vertices, and we study the overall connectivity of the graph by looking at the proportions of opposite arbitrary vertices, for primes p in different congruence classes modulo 8. See .
In these data, we have computed for each prime p a random sample of 1000 arbitrary pairs of vertices and checked how many are opposite. Then, we take this number and divide by , to account for differences in the numbers of vertices for these primes. We have sorted the data by primes and displayed it in the graphs in . Our results suggest that the size and connectedness of the spine could be the key factor affecting the proportion of opposite pairs:
Size of : Shortest paths are more likely to pass through if it is larger. We account for this by dividing the proportions of opposite arbitrary pairs of vertices by in . The normalized proportions still differ modulo 8, indicating another factor is at play, possibly the connectedness of .
Connectedness of : When is less connected, pairs are more likely to have shortest paths through it. From the table in Section 3.6, the spine is the least connected when , and can be most connected when . This could explain the difference in proportions when normalized by the size of .
For example, consider ( is connected, ) and ( is maximally disconnected, ). We would expect times more opposite pairs in the p1 case. However, for 1000 arbitrary pairs, only 266 pairs were opposite for p1 compared to 112 pairs for p2.
To further study whether differences occurring in the normalized proportions of vertices which are opposite for were due to the connectedness of , we took a random subgraph of the same size as and obtained the proportion of pairs of arbitrary vertices with a shortest path passing through the random subgraph. We took the average of these results over 10 random subgraphs for each prime between 1000 and 5000. The data, in , show less distinction compared to the data in . This suggests that the connectedness of is a dominant factor affecting the normalized proportion of opposite pairs of vertices.
4.3 Distance to spine
In this section, we investigate how connected the spine is to the rest of the graph, motivated by the path-finding algorithm of Delfs and Galbraith [Citation11].
4.3.1 Distance to the spine versus a random subgraph
For two fixed primes, we study how the spine fits into the graph, and compare this with a randomly selected subgraph. Specifically, we compare a random vertex’s distance to the spine, with a random vertex’s distance to a random subgraph of the same size as the spine. We observe that if the spine is connected, then the distance to the spine seems greater than the distance to a random subgraph. This agrees with the intuition that a small connected subgraph () will be further from most vertices than a random subgraph, which will have many connected components uniformly distributed throughout the graph.
We studied these distances for the primes, p = 19991 and . For p = 19991, the subgraph is connected, and for p = 19993, is maximally disconnected (see [Citation11]). For each value of p, we constructed the graph , the spine , and chose several random subgraphs . We define the distance between a vertex j and a subgraph Si to be
We computed lists in order to measure how dispersed Si is in . Histograms of the distributions of the di are given in .
The significant difference between the two primes shown in can also be explained by the number of vertices in . Since is a 3-regular graph, for a random vertex j, there are at most vertices of distance d away from j (and this limit is achieved if there are no collisions on the paths leaving j). If has N vertices and H is a random subgraph with M vertices, then the expected distance to H from a random vertex should be . For p = 19991, , so we expect the average distance to to be 3.06. For p = 19993, , so we expect the average distance to to be 5.80.
When maximally disconnected, the distances to the spine were similar to that of a random subgraph. However, when the spine is connected, the distances are slightly longer. This shows that modeling the spine as a random subgraph may lead to an underestimate of the distances.
4.3.2 Comparison across primes p
In order to compare the distances to across different primes and account for the expected average distance based on the size of we consider normalized distances as follows:
Recall that is the expected distance to the spine from a random vertex. We observed that the average distances were lower than the expected distance based on the connectedness of . There are also clear differences in the distributions of dp when considering residue classes of p modulo 8. This is shown in . In particular, the data match our findings on the proportion of opposite pairs, see .
However, the different behavior of dp for the different congruence classes can be explained by the size of the spine. If the size of the spine is large, we will need fewer steps to reach the spine from a random vertex v. Hence, when counting the paths of length d from v, we will encounter less backtracking and the estimate is more precise. Looking at , we see that for , the size of the spine is the largest, and for , the size of the spine is the smallest.
We also tested this within a fixed congruence class: for primes p with and , the mean distance to the spine is 4.040 with standard deviation 0.413 if and mean 3.007 with standard deviation 0.335 if .
5 When are conjugate j-invariants -isogenous?
5.1 Motivation
In Section 4.2, we studied paths between conjugate j-invariants in that go through the spine . If and happen to be 2-isogenous, then the shortest path between them has length one and does not go through . This leads us to the natural question:
Question 1. How often are conjugate j-invariants -isogenous, for ?
5.2 Experimental data: 2-isogenies
We collected data on supersingular j-invariants over for all primes (a total of 9605 primes). For each p, we determined all of the j-invariants and counted those that are also 2-isogenous to their conjugates.
With a few exceptions, all of the proportions computed are positive and strictly less than 1. The small primes (roughly p < 5000) have a wide range of proportions, between 0 and 1. This is expected due to the small number of points on their graphs. For example: there are some primes p such that all of the pairs of conjugates are 2-isogenous. On the other hand, if then the proportion will be trivially zero. This happens only for 15 small primes, namely those dividing the order of the Monster group [Citation21]. Notably, the only examples of p for which the proportion is zero, but not trivially zero, are p = 101, 131.
To avoid small prime phenomena, we focused on analyzing the data we collected for , a total of 8378 primes. The graph of proportions for these data can be found in . We found that the mean proportion in the data is 0.032780 with a standard deviation of 0.019134.
We then sorted the data by congruence conditions to look for patterns. The biggest difference appeared when we re-sorted the data according to the congruence class of the primes modulo 12. The primes in this range are fairly evenly distributed into the congruence classes modulo 12, as one can see in .
5.2.1 Primes modulo 12
In , we summarize the differences between the congruence classes modulo 12. Note the similar, higher means for and the similar, lower means for . These distributions are skewed according to the congruence class, as we can also see from the graph in . There appears to be a correlation between primes and between primes . A two-sample t-test confirms these correlations at the 99.8% level.
5.3 Experimental data: 3-isogenies
We collected data on the supersingular j-invariants over for all the primes (a total of 9,605 primes) and computed the proportion of conjugate pairs that are also 3-isogenous. We present these data in the same format as the 2-isogeny data presented in Section 5.2.
Once again, we observe some small prime phenomena (proportions of 1 and 0 for p small). However, in the 3-isogeny case we do not have nontrivial examples of primes p for which the proportion of 3-isogenous conjugates is 0. On the contrary, if there exist conjugate j-invariants in , then there is at least one pair of 3-isogenous conjugates. (Recall that the two counterexamples to this statement in the 2-isogeny case were p = 101131.)
To avoid small prime phenomena, we again focused on analyzing the data we collected for , a total of 8378 primes. The graph of proportions for these data can be found in .
In this collection of data, for primes , we found there to be a mean proportion of 3-isogenous conjugate pairs of 0.047306, with standard deviation of 0.026568.
As in the 2-isogeny case, we again sorted the data by congruence conditions to look for patterns. The biggest difference appeared when we re-sorted the data according to the congruence class of the primes modulo 12.
5.3.1 Primes modulo 12
In , we summarize the differences between the different congruence classes modulo 12. Note the similar and higher means for and the similar and lower means for , as we can also observe in . There appears to be a correlation between primes and between primes . A two-sample t-test confirms these correlations at the 99.8% level.
5.4 Further Questions
Our experimental data suggest that, at least for and with the exception of a few small primes, the proportion of conjugate pairs that are -isogenous is a small positive number. In particular, all of the primes with supersingular j-invariants in observed have at least one such pair. This motivates the following two questions:
Question 2. For p > 131, is there always at least one pair of -isogenous conjugate j-invariants on ?
Question 3. For large p, is there a nontrivial lower and/or upper bound for the proportion of -isogenous conjugate j-invariants on ?
A partial answer to Question 3 can be found in Lemma 6 of [Citation6], which states that, in the case when , the set of j-invariants that are adjacent to their conjugates in is of size , which yields an upper bound. [Citation14] provided an answer regarding the lower bound in Question 3, and thus also for Question 2. [Citation14] is concerned with computing endomorphism rings of supersingular elliptic curves over by finding cycles in . The construction of these cycles involves finding j-invariants that are adjacent to their -conjugates. As part of the analysis of the algorithm, they proved that the cardinality of the set of such j-invariants is larger than , for some constant C depending on (assuming GRH). Both of these proofs assume that .
However, these bounds do not seem to explain the significant difference in the average of the proportion of -isogenous conjugate pairs when we vary the congruence class of p modulo 12. This prompts us to formulate the question:
Question 4. How does the proportion of -isogenous conjugate j-invariants on relate to the conjugacy class of ?
Remark 5.1.
We can also consider -isogenous conjugate pairs of j-invariants in the context of the modular curve . In [Citation21], Ogg defined , the Atkin-Lehner quotient of by the Fricke involution. If two conjugate j-invariants are -isogenous, then is a point of . The image of under the quotient map is an -rational point of . Conversely, any -rational point of whose preimage in contains a non- point corresponds to an -isogenous conjugate pair . Intersecting with the supersingular locus, we have an alternative description of the set of -isogenous conjugate pairs in the Supersingular Isogeny Graph.
6 Diameter
Numerical experiments in [Citation22] estimated the diameters of k-regular LPS Ramanujan graphs and random Cayley graphs to be asymptotically and respectively, where n is the number of vertices. We present data on the diameters of the supersingular 2-isogeny graphs, which are 3-regular on vertices, with , or 2, depending on the congruence class of p .
For , the j-invariant 1728 appears in a special place of the graph - it is only 2-isogenous to one other curve. This isolated position in the graph may lead to longer diameters of for .
We can see a lower boundon the diameter as follows. Starting from a random vertex and taking a walk of length n, the walk reaches at most vertices as endpoints (exactly that number if there are no collisions). Since there are vertices in the graph, with , the diameter cannot be less that the smallest n0 such that
We collected graph data for the diameters of the supersingular 2-isogeny graphs for 4600 primes p. We used the built-in Sage” diameter” function [Citation26] on the graphs. The implementation can be found in the walk.sage worksheet available on our github repository. We collected diameters of in batches for ranges of primes. The smallest prime we have data for is and the largest is p = 9501511. This data is displayed in .
The shifted graph (in a solid line) seems to increase too steeply for larger prime values. This could suggest that the 2-isogeny graph diameters may be more like random Cayley graphs, i.e. with distribution closer to . However, our numerical data are inconclusive: diameters for larger primes would be needed to make a conclusion, but our algorithm would not be able to find those in a reasonable amount of time.
For this reason, we adjusted our algorithm to find lower bounds on the diameter: We chose as the starting vertex and in every step, we added the neighbors of all the known vertices, and truncated the computation instead of computing the entire graph. This gives a lower bound on the diameter. This algorithm allowed us to find lower bounds for the diameters of for larger primes p, shown in . We see in that the dashed curve no longer fits the data. We chose primes . See Section 6.1 for discussion on the difference ; we also chose so that the spine (see Definition 2.5) has the same structure and approximate size (see Section 3.6).
We tried fitting the curves and with the best constants α, β and as a first approximation we tried minimizing the sum of squares of distances to these curves, yielding and .
6.1 How does diameter vary for different congruence classes of primes modulo 12?
We investigated the behavior of the diameter as p varies modulo 12. We found a slight, but noticeable, bias: Primes tend to have a 2-isogeny graph of larger diameter compared with primes . This is visible in . In , the diameters tend to be slightly larger than the graph of , whereas those in tend to be more evenly distributed above and below . supports the visible bias.
7 Conclusions
We determined how the connected components of merge together to give the spine . For any specific and any p, one can determine the resulting shape explicitly if one knows the structure of the class group .
For , we summarize the biases we observed in our heuristic data, for the different congruence classes of . The data suggest the following, although more careful analysis is needed to confirm:
:
smaller 2-isogeny graph diameters,
larger number of spinal components, and
larger proportion of 2-isogenous conjugate pairs,
:
larger 2-isogeny graph diameters,
smaller number of spinal components, and
smaller proportion of 2-isogenous conjugate pairs.
Netherlands Organisation for Scientific Research;
Acknowledgments
This article is the result of a collaboration started at Alice Silverberg’s 60th birthday conference on open questions in cryptography and number theory https://sites.google.com/site/silverberg2018/. We would like to thank Heidi Goodson for her significant contributions to this project. We are grateful to Microsoft Research for hosting the authors for a follow-up visit. We would like to thank Steven Galbraith, Shahed Sharif, and Katherine E. Stange for helpful conversations. We thank the reviewers for their thoughtful and helpful comments, leading to a many improvements in this article. Authors are listed in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf.
Declaration of Interest
No potential conflict of interest was reported by the author(s).
Additional information
Funding
References
- Gora Adj, O. A., Menezes, A. On isogeny graphs of supersingular elliptic curves over finite fields. Finite Fields Their Appl., 55, 268–283.
- Arpin, S., Camacho-Navarro, C., Lauter, K., Lim, J., Nelson, K., Scholl, T., Sotáková, J. (2019). Adventures in supersingularland.
- Biasse, J.-F., Jao, D., and Sankar, A. (2014), A quantum algorithm for computing isogenies between supersingular elliptic curves. In Progress in cryptology—INDOCRYPT 2014, volume 8885 of Lecture Notes in Comput. Sci., Springer, Cham, pp. 428–442.
- Costache, A., Feigon, B., Lauter, K., Massierer, M., Pusks, A. Ramanujan graphs in cryptography. In: Jennifer, S. B., Folsom, A., Laln, M., Manes, M. Eds., Research Directions in Number Theory, Association for Women in Mathematics Series, Springer International Publishing, pp. 1–40.
- Charles, D., Goren, E., Lauter, K. (2006), Cryptographic hash functions from expander graphs. Cryptology ePrint Archive, Report 2006/021. Available at: https://eprint.iacr.org/2006/021.
- Charles, D., Goren, Ey., and Lauter, K. (2009), Families of Ramanujan graphs and quaternion algebras, In: Groups and symmetries, CRM Proc. Lecture Notes, Amer. Math. Soc., Vol. 47, pp. 53–80.
- Castryck, W., Lange, T., Martindale, C., Panny, L., and Renes, J. CSIDH: An efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S., Advances in Cryptology ASIACRYPT 2018, Lecture Notes in Computer Science, Springer International Publishing, pp. 395–427.
- Cox, D. (1989), Primes of the form x2 + ny2. New York: John Wiley and Sons, Inc.
- Castryck, W., Panny, L., and Vercauteren, F. (2020), Rational isogenies from irrational endomorphisms. In: Canteaut, A., Ishai, Y., Eds., Advances in Cryptology EUROCRYPT 2020, Lecture Notes in Computer Science, Springer International Publishing, pp. 523–548.
- Delfs, C., and Galbraith, S. D. (2016), Computing isogenies between supersingular elliptic curves over 𝔽p. Des. Codes Cryptog., 78: 425–440. Available at: https://arxiv.org/pdf/1310.7789.pdf.
- Hallgren, E.S., Lauter, K., Morrison, T., and Petit, C. (2018), Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In: Nielsen, J. B., Rijmen, V., Eds., Advances in Cryptology EUROCRYPT 2018, Lecture Notes in Computer Science, Springer International Publishing, pp. 329–368.
- Eisentrger, K., Hallgren, S., Leonardi, C., Morrison, T., Park, J. Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs. In Proceedings of the Fourteenth Algorithmic Number Theory Symposium, Vol. 4, Mathematical Sciences Publishers, pp. 215–232.
- Galbraith, S. D., Petit, C., Shani, B., and Ti, Y. B. (2016), On the security of supersingular isogeny cryptosystems. In: Cheon, J. H., Hee, J., Takagi, T., Eds., Advances in Cryptology ASIACRYPT 2016, Lecture Notes in Computer Science, Springer.
- Ibukiyama, T. (1982), On maximal orders of division quaternion algebras over the rational number field with certain optimal embeddings. Nagoya Math. J., 88: 181–195.
- Jao, D., De Feo, L. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B-Y., Ed., Post-Quantum Cryptography, Lecture Notes in Computer Science, Springer, pp. 19–34.
- Kaneko, M. (1989), Supersingular j-invariants as singular moduli mod p. Osaka J. Math., 26, 12.
- Kohel, D., Lauter, K., Petit, C., and Tignol, J-P. (2014), On the quaternion ℓ-isogeny path problem. LMS J. Comput. Math., 17: 418–432.
- Kohel, D. (1996), Endomorphism rings of elliptic curves over finite fields. PhD thesis, Berkely: University of California.
- Love, J., Boneh, D. Supersingular curves with small noninteger endomorphisms. In: Proceedings of the Fourteenth Algorithmic Number Theory Symposium, Vol. 4, Mathematical Sciences Publishers, pp. 7–22.
- Lubotzky, A., Phillips, R. S., Sarnak, P. C. (1988), Ramanujan graphs. Combinatorica, 8: 261–277. doi:10.1007/BF02126799
- Ogg, A. P. (1975), Automorphismes de courbes modulaires. Séminaire Delange-Pisot-Poitou. Théorie des nombres, 16:1–8.
- Sardari, N. T. Diameter of Ramanujan graphs and random cayley graphs. 39: 427–446.
- Shor, P. W. (1999), Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev., 41: 303–332.
- Silverman, J. H. (2009), The Arithmetic of Elliptic Curves, 2nd ed. New York: Springer-Verlag.
- Sutherlandm, A. V. (2013), Isogeny volcanoes. In: ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium, volume 1 of Open Book Ser. Berkeley, CA: Math. Sci. Publ., pp. 507–530.
- The Sage Developers. (2019), SageMath, the Sage Mathematics Software System (Version 8.7). Available at: https://www.sagemath.org.
- Vlu, J. (1971), Isognies entre courbes elliptiques. Comptes Rendus de l’Acadmie des Sciences de Paris, 273: 238–241.