key: cord-0135450-3weaep8p
authors: Eisentraeger, Kirsten; Hallgren, Sean; Leonardi, Chris; Morrison, Travis; Park, Jennifer
title: Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
date: 2020-04-24
journal: nan
DOI: nan
sha: c94c218ed230ddea0ce36ad7dcc97ae3ed5ed67d
doc_id: 135450
cord_uid: 3weaep8p

Computing endomorphism rings of supersingular elliptic curves is an important problem in computational number theory, and it is also closely connected to the security of some of the recently proposed isogeny-based cryptosystems. In this paper we give a new algorithm for computing the endomorphism ring of a supersingular elliptic curve $E$ that runs, under certain heuristics, in time $O((log p)^2p^{1/2})$. The algorithm works by first finding two cycles of a certain form in the supersingular $ell$-isogeny graph $G(p,ell)$, generating an order $Lambda subseteq operatorname{End}(E)$. Then all maximal orders containing $Lambda$ are computed, extending work of Voight. The final step is to determine which of these maximal orders is the endomorphism ring. As part of the cycle finding algorithm, we give a lower bound on the set of all $j$-invariants $j$ that are adjacent to $j^p$ in $G(p,ell)$, answering a question in arXiv:1909.07779.

Computing the endomorphism ring of an elliptic curve defined over a finite field is a fundamental problem in computational arithmetic geometry. For ordinary elliptic curves the fastest algorithm is given by Bisson and Sutherland [5] who gave a subexponential time algorithm to solve this problem. In the supersingular case, no subexponential time algorithm is known.

Computing endomorphism rings of supersingular elliptic curves is also closely connected to the security of some of the recently proposed isogeny-based cryptosystems [14, 11] , and one proposal that advanced to Round 2 of the NIST postquantum competition [9] is based on isogenies [19, 2] . Using the supersingular ℓ-isogeny graph for cryptographic purposes was first proposed in [8] .

Computing the endomorphism ring of a supersingular elliptic curve E was first studied by Kohel [21, Theorem 75] , who gave an approach for generating a subring K.E of finite index of the endomorphism ring End(E). The algorithm was based on finding cycles in the ℓ-isogeny graph of supersingular elliptic curves, and the running time of the probabilistic algorithm was O(p 1+ε ). In [14] it is argued that heuristically one expects O(log p) many calls to a cycle finding algorithm until the cycles generate End(E). An algorithm for computing cycles with complexityÕ(p 1/2 ) and polynomial storage is given by Delfs and Galbraith [10] .

One can also compute End(E) using an isogeny φ : E 0 → E, where E 0 is an elliptic curve with known endomorphism ring. McMurdy was the first to compute End(E) via such an approach [25] , but did not determine its complexity. In [15] a polynomial-time reduction from computing End(E) to finding an isogeny φ of powersmooth degree was given assuming some heuristics, while [13] used an isogeny φ of ℓ-power degree.

In this paper we give a new algorithm for computing the endomorphism ring of a supersingular elliptic curve E: first we compute two cycles through E in the supersingular ℓ-isogeny graph that generate an order Λ in End(O). Then we compute all maximal orders O that contain Λ. The final step is to determine which of those superorders of Λ is the endomorphism ring of E. Our algorithm for computing maximal superorders of Λ is efficient when Λ is local and Bass. This extends work of Voight who showed how to compute one maximal order containing Λ in polynomial time if the factorization of the discriminant of Λ is given [28, Theorem 7.14] . As part of the analysis of the cycle finding algorithm, we give a lower bound on the size of the set of all j-invariants j that are adjacent to j p in G(p, ℓ), answering the lower-bound part of Question 3 in [1] .

Both the algorithm for generating the suborder of End(E) and the algorithm for computing the maximal orders containing a given order are new. However, our overall algorithm is still exponential: the two cycles are found in time O((log p) 2 p 1/2 ), and the overall algorithm has the same running time, assuming several heuristics. This saves at least a factor of log p versus the previous approach by [15] that uses cycles in G(p, ℓ) to compute End(E). This is because with that approach one expects to compute O(log p) many cycles, while the expected number of calls to an algorithm for computing cycles in G(p, ℓ) in our new algorithm for computing End(E) is bounded by a constant, assuming that certain heuristics hold. Also, our cycle finding algorithm requires only polynomial storage, while achieving the same run time as a generic collision-finding algorithm, which require exponential storage.

In the last section of the paper we give a new polynomial-time reduction from computing End(E) to pathfinding in the ℓ-isogeny graph which is simpler in several ways than previous ones. For this we need to assume GRH and the heuristics of [15] . We observe that this reduction, together with the algorithms in [22, 10, 15, 11] gives an algorithm for pathfinding in G(p, ℓ) with O((log p) 2 p 1/2 ) time and polynomial storage, assuming the various required heuristics for these algorithms [22, 15] .

The paper is organized as follows. In Section 3 we give an algorithm for computing cycles in the ℓ-isogeny graph G(p, ℓ) so that the corresponding endomorphisms generate an order in the endomorphism ring of the associated elliptic curve. In Section 4 we show that this order can be enlarged locally to match the local data of a maximal order, and in Section 5 we construct all global maximal orders that satisfy these local conditions. In Section 6 we show how to determine which of these maximal orders is isomorphic to End(E). In Section 7 we give a reduction from the endomorphism ring problem to the problem of computing ℓ-power isogenies in G(p, ℓ) that is then used to attack the second preimage resistance of the hash function in [8] .

For the definition of an elliptic curve, its j-invariant, isogenies of elliptic curves, their degrees, and the dual isogeny see [26] . 2 . 1 . Endomorphism rings, supersingular curves, ℓ-power isogenies. Let E be an elliptic curve defined over a finite field F q . An isogeny of E to itself is called an endomorphism of E. The set of endomorphisms of E defined over F q together with the zero map is called the endomorphism ring of E, and is denoted by End(E).

If the endomorphism ring of E is non-commutative, E is called a supersingular elliptic curve. Otherwise we call E ordinary. Every supersingular elliptic curve over a field of characteristic p has a model that is defined over F p 2 because the j-invariant of such a curve is in F p 2 .

Let E, E ′ be two supersingular elliptic curves defined over F p 2 . For each prime ℓ = p, E and E ′ are connected by a chain of isogenies of degree ℓ. By [21, Theorem 79], E and E ′ can be connected by m isogenies of degree ℓ, where m = O(log p). For ℓ a prime different from p, the supersingular ℓ-isogeny graph in characteristic p is the multi-graph G(p, ℓ) whose vertex set is

and the number of directed edges from j to j ′ is equal to the multiplicity of j ′ as a root of Φ ℓ (j, Y ). Here, given a prime ℓ, Φ ℓ (X, Y ) ∈ Z[X, Y ] is the modular polynomial. This polynomial has the property that Φ ℓ (j, j ′ ) = 0 for j, j ′ ∈ F q and q = p r if and only if there exist elliptic curves E(j), E(j ′ ) defined over F q with j-invariants j, j ′ such that there is a separable ℓ-isogeny from E(j) to E(j ′ ).

Algebras, orders and sizes of orders. For a, b ∈ Q × , let H(a, b) denote the quaternion algebra over Q with basis 1, i, j, ij such that i 2 = a, j 2 = b and ij = −ji. That is, H(a, b) = Q+Q i+Q j +Q ij. Any quaternion algebra over Q can be written in this form. There is a canonical involution on H(a, b) which sends an element α = a 1 + a 2 i + a 3 j + a 4 ij to α := a 1 − a 2 i − a 3 j − a 4 ij. Define the reduced trace of an element α as above to be Trd(α) = α + α = 2a 1 , and the reduced norm to be Nrd(α) = αα = a 2 1 − aa 2 2 − ba 2 3 + aba The size of a lattice or an order Λ in a quaternion algebra B is the size of the coefficients of the basis specifying Λ plus the size of B, which is specified by a basis and a multiplication table. We denote by B p,∞ the unique quaternion algebra over Q that is ramified exactly at p and ∞. The endomorphism ring of a supersingular elliptic curve is isomorphic to a maximal order in B p,∞ . 2 . 3 . Bass, Eichler, and Gorenstein orders in quaternion algebras; discriminants and reduced discriminants. Let B be a quaternion algebra over Q. We define the discriminant of B, denoted disc B, to be the product of primes that ramify in B; then disc B is a squarefree positive integer. If O ⊂ B is an order, we define the discriminant of O to be disc

The discriminant of an order is always a square, and the reduced discriminant An order is basic if it contains a commutative, quadratic subalgebra R such that R is integrally closed in QR. When B is a quaternion algebra over Q p and O is a Z p -order in B, we similarly define lattices, ideals, and the various types of orders in B.

Computing an order in the endomorphism ring of a supersingular elliptic curve 3. 1 . Computing cycles in G(p, ℓ). Fix a supersingular elliptic curve E 0 defined over F p 2 with j-invariant j 0 . In this section we describe and analyze an algorithm for computing two cycles through j 0 in G(p, ℓ) that generate an order in End(E 0 ). We will first show how to construct two distinct paths from j 0 to j p 0 . Given two such paths P and P ′ , then first traversing through P and then traversing through P ′ in reverse gives a cycle through j 0 . This uses the fact that if j is adjacent to j ′ , then j p is adjacent to (j ′ ) p . Now let P 1 be a path of length k from j 0 to some other vertex j k in G(p, ℓ). Denote the not necessarily distinct vertices on the path by j 0 , j 1 , . . . , j k and assume that j k is adjacent to j p k ∈ G(p, ℓ).

The concatenation P := P 1 P p 1 is a path from j 0 to j p 0 . Such paths were also considered in [8, Section 7]. We give an algorithm for computing such paths so that the resulting cycles generate an order and and analyze its running time.

If j 0 = j p 0 , then P is already a cycle starting at j 0 , so this gives a cycle through j 0 . Otherwise, one can repeat this process to find another path P ′ := P 2 P p 2 (with possibly a different j k ) that passes through at least one vertex not in P . Concatenating P and P ′ (in reverse order) gives a cycle starting and ending at j 0 ; this corresponds to an endomorphism of E. We will need the notion of a path/cycle with no backtracking and trimming a path/cycle to remove backtracking. ) . We say that a path or cycle with a specified start vertex j 0 , following edges (e 1 , . . . , e k ) and ending at vertex j k has no backtracking if e i+1 is not dual to e i for i = 1, . . . , k − 1.

In our definition, a cycle has a specified start vertex j 0 , and we consider a cycle a special case of a path starting and ending at j 0 . So according to our definition, even if the first edge e 1 and the last edge e k are dual to each other in a cycle, it is not considered backtracking.

Definition 3. 2 . Given a path (e 1 , . . . , e k ) from j 0 to j k (with j 0 = j k ) or a cycle with specified start vertex j 0 = j k , define trimming as the process of iteratively removing pairs of adjacent dual edges until none are left.

One can show that given a path P from j 0 to j k with j 0 = j k , or a cycle C with start vertex j 0 = j k , the trimmed versionsP orC may result in a smaller set of vertices. The vertices j 0 and j k will still be there inP , and the only way that j 0 and j k may disappear fromC is if the whole cycle gets removed. Definition 3. 3 . Given a path P in G p,ℓ from j 0 to j k , we define P R to be the path P traversed in reverse order, from j k to j 0 , using the dual isogenies.

We can now give the algorithm to find cycle pairs: Algorithm 3. 4 . Finding cycle pairs for prime ℓ Input: prime p = ℓ and a supersingular j-invariant j 0 ∈ F p 2 . Output: two cycles in G(p, ℓ) through j 0 .

(1) Perform N = Θ( √ p log p log log p) random walks of length k = Θ(log(p 3/4 (log log p) 1/2 )) starting at j 0 and select a walk that hits a vertex j k ∈ S p , i.e. such that j k is ℓ-isogenous to j p k ; let P 1 denote the path from j 0 to j k .

(2) Let P p 1 be the path given by j k , j p k , j p k−1 , . . . , j p 0 . (3) Let P denote the path from j 0 to j p 0 given as the concatenation of P 1 and P p 1 . (4) If j 0 ∈ F p then P 1 P p 1 is a cycle through j 0 . Remove any self-dual self-loops and backtracking from P 1 P p 1 . (5) If j 0 ∈ F p 2 − F p repeat steps (1)-(3) again to find another path P ′ = P 2 P p 2 from j 0 to j p 0 , then P (P ′ ) R is a cycle. Remove any self-dual self-loops and backtracking from the cycle. (6) Repeat Steps (1)-(5) a second time to get a second cycle.

Remark 3. 5 . Instead of searching for a vertex j in Step (1) such that j is adjacent to j p , one could also search for a vertex j ∈ F p , i.e. j = j p or a vertex j whose distance from j p in the graph is bounded by some fixed integer B. Our algorithm that searches for a vertex such that j is adjacent to j p was easier to analyze because there were fewer cases to consider in which the trimmed cycles would not generate an order.

To analyze the running time of Algorithm 3.4, we will use the mixing properties in the Ramanujan graph G(p, ℓ). This is captured in the following proposition, which is an extension of [20, Lemma 2.1] in the case that G(p, ℓ) is not regular or undirected (that is, when p ≡ 1 (mod 12)).

Proposition 3. 6 . Let p > 3 be prime, and let ℓ = p also be a prime. Let S be any subset of the vertices of G(p, ℓ) not containing 0 or 1728. Then a random walk of

will land in S with probability at least 6|S| p . One can prove this since the eigenvalues for the adjacency matrix of G(p, ℓ) satisfy the Ramanujan bound. This allows us to prove the following theorem.

Theorem 3. 7 . Under GRH, Algorithm 3.4 computes two cycles in G(p, ℓ) through j 0 that generate an order in the endomorphism ring of

as long as the two cycles do not pass through the vertices 0 or 1728, with probability

The algorithm requires poly log p space.

Remark 3. 8 . In Section 6 we use this proposition to compute endomorphism rings, and from this point there is no problem with excluding paths through 0 or 1728. This is because the endomorphism rings of the curves with j-invariants 0 and 1728 are known, and a path of length log P , starting at j 0 going through 0 or 1728 lets us compute End(E 0 ) via the reduction in Section 7.

Proof. Assuming GRH, by Theorem 3.9 below, |S p | = Ω( √ p/ log log p) (treating ℓ as a constant). Proposition 3.6 implies that the endpoint j k of a random path found in

Step (1) is in S p with probability Ω(1/( √ p log log p)). The probability that none of the N + 1 paths lands in S p is at most ( 

where C is from Theorem 3.9 and c is the constant used in the choice of N .

If j 0 ∈ F p , then P 1 P p 1 is a cycle through j 0 since j 0 = j p 0 . If j 0 ∈ F p 2 − F p then Step (5) computes a second path from j 0 to j p 0 , which is concatenated to the first path, but in reverse, forming a cycle C 0 . In Step 6, a second cycle C 1 is found.

Now we must show that with high probability the two cycles C 0 , C 1 returned by the algorithm are linearly independent. We will use Corollary 4.12 of [3] . This corollary states that two cyclesC 0 andC 1 with no self-loops generate an order inside End(E 0 ) if (1) they do not go through 0 or 1728, (2) have no backtracking, and (3) have the property that one cycle contains a vertex that the other does not contain. LetC 0 ,C 1 be the trimmed versions of the cycles C 0 , C 1 returned by Algorithm 3. 4 . It is easy to see that if the trimmed cyclesC 0 ,C 1 are linearly independent, then so are the original cycles C 0 , C 1 . Hence it is enough to show that the trimmed cycles C 0 ,C 1 satisfy the conditions of Corollary 4.12 of [3] .

To prove this, we first claim that with high probability, the end vertex j k ∈ S p in the path P 1 from j 0 to j k will not get removed if the path P 1 P p 1 is trimmed. Then we show it's also still there in the trimmed cycle. Observe that if the path P 1 were to be trimmed to obtain a pathP 1 with no backtracking, thenP 1 is still a nontrivial path that starts at j 0 and ends at j k as long as j 0 and j k are different which occurs with probability 1 − O(1/p). After concatenatingP 1 with its corresponding path P p 1 , the pathP 1P p 1 has backtracking only if the last edge ofP 1 is dual to the first edge inP p 1 , i.e. if j k−1 = j p k . If that is the case, remove the last edge fromP 1 and the first edge fromP p 1 , and call the remaining pathP 1 . The new pathP 1 still has the property that it ends in a vertex j = j p k that is ℓ-isogenous to its conjugate (j p k ) p = j k . After concatenatingP 1 with its correspondingP p 1 , this still gives a path from j 0 to j p 0 . Again, the concatenation of these two paths has no backtracking unless the last edge inP 1 is the first edge inP p 1 , i.e. if the last edge inP 1 is an edge from j k to j p k . But this cannot happen, because otherwise the trimmed pathP 1 would have backtracking because it would go from j k to j p k and back to j k , contradicting the definition of a trimmed cycle. (With negligible probability, the vertex j k has multiple edges, so we exclude this case here.) Hence the trimmed version of P 1 P p 1 isP 1P p 1 , and this path still contains the vertex j k , sinceP p 1 contains the vertex j k . Now we can finish the argument by considering two cases:

The above argument about trimming shows that if the vertex j k appearing in the second cycle C 1 is different from all the vertices appearing in C 0 and their conjugates, which happens with probability 1 − O(log p/p), then that vertex j k will appear in the trimmed cycleC 1 , but not inC 0 . (This is because in this case the trimmed path P 1 P p 1 is already a cycle.) Hence by [3, Corollary 4.12] , C 0 andC 1 are linearly independent.

Case 2: If j 0 ∈ F p 2 − F p , then with probability 1 − O(log(p)/p), the endpoint j k of P 2 is a vertex such that it or its conjugate do not appear as a vertex in P 1 . The concatenation of the two paths P = P 1 P p 1 and P ′ = P 2 P p 2 in reverse is a cycle C 0 through j 0 . When we trim it, it is still a cycle through j 0 in which the endpoint j k from P 2 appears because that j k or its conjugate did not appear in P 1 . Similarly, Algorithm 3.4 finds a second cycle C 1 with probability 1 − log(p)/p that contains a random vertex that was not on the first cycle C 0 . This means that by Corollary 4.12 of [3] ,C 0 andC 1 and hence C 0 and C 1 are linearly independent.

The running time is O( √ p (log p) 2 ) because we are considering O( √ p) paths of length O(log p), and going from one vertex to the next takes time polynomial in ℓ log p, and we are assuming that ℓ is fixed here. The storage is polynomial in log p because we only have to store the paths P 1 , P 2 that lands in S p and can delete all other ones.

Determining the size of S p . Will now determine a lower bound for the size of the set S p := {j ∈ F p 2 : j is supersingular and j is adjacent to j p in G(p, ℓ)}. In [8, Section 7] , an upper bound is given for S p , but in order to estimate the chance that a path lands in S p we need a lower bound for this set. Let ℓ, p be primes such that ℓ < p/4. Let O K be the ring of integers of K := Q( √ −ℓp). We use the terminology and notation in in [12, 4] . Let Emb OK (F p 2 ) be the collection of pairs (E, f ) such that E is an elliptic curve over F p 2 and f : O K ֒→ End(E) is a normalized embedding, taken up to isomorphism. We say

Theorem 3. 9 . Assume that ℓ < p/4. Let S p = {j ∈ F p 2 : j is supersingular and Φ ℓ (j, j p ) = 0}.

Under GRH there is a constant C > 0 (depending on ℓ) such that |S p | > C Proof. First, if E is a supersingular elliptic curve defined over F p 2 with j-invariant j and E (p) is a curve with j-invariant j p and ℓ < p/4 is also a prime, then E is ℓ-isogenous to E (p) if and only if Z[ √ −ℓp] embeds into End(E) (see [8] , Lemma 6).

For any element (E, f ) ∈ Emb OK (F p 2 ), E is supersingular, since p ramifies in Q( √ −ℓp). Moreover j(E) ∈ S p by the above fact. Thus the map ρ :

To get a lower bound for S p we will show that for j ∈ S p , the size of ρ −1 (j) is bounded by (ℓ + 1) · 6 and that | Emb OK (F p 2 )| ≫ √ ℓp log log(ℓp) . These two facts imply that

To get a lower bound for | Emb OK (F p 2 )| we can use Proposition 2.7 of [16] to show that this order equals | Emb OK (F p 2 )| = | Cl(O K )|. Class group estimates from [24] give

log log(ℓp) . It remains to bound the size of ρ −1 (j). We claim that an equivalence class of pairs (E, f ) determines an edge in G(p, ℓ). Let [(E, f )] ∈ Emb OK (F p 2 ) and choose a representative curve E. First assume that j(E) = 0, 1728. Then (E, f ) ≃ (E, g) implies that f = g, since Aut(E) = ±1. Thus we may identify [(E, f )] with the edge in G(p, ℓ) corresponding to the kernel of f ( √ −ℓp). When j(E) = 0 or 1728, we may assume that E is defined over F p . Then let [(E, f )] ∈ Emb OK (F p 2 ) and suppose (E, f ) is equivalent to (E, g). We can factor f ( √ −ℓp) = π • φ and g( √ −ℓp) = π • φ ′ , where φ, φ ′ are degree ℓ endomorphisms of E and π is the Frobenius endomorphism of E. Additionally, πφ = uπφ ′ u −1 . We claim that u and φ commute. If not, then they generate an order Λ such that the following formula holds (see [23] ):

One can show that this contradicts our assumption that p/4 > ℓ. Thus u and φ commute, and we see that f ( √ −ℓp) and g( √ −ℓp) have the same kernel and thus determine the same edge in G(p, ℓ).

We now count how many elements of Emb OK (F p 2 ) determine the same edge in G(p, ℓ). Suppose that [(E, f )], [(E, g)] ∈ Emb OK (F p 2 ) and that ker(f ( √ −ℓp)) = ker(g( √ −ℓp)). Writing f ( √ −ℓp) = φ • Frob and g( √ −ℓp) = φ ′ • Frob we see that φ and φ ′ must have the same kernel as well. Thus φ ′ = uφ for some u ∈ Aut(E). Because p > 4ℓ > 3, Aut(E) ≤ 6 and we conclude that there are at most 6 classes [(E, f )] determining the same edge emanating from E in G(p, ℓ). Thus |ρ −1 (j)| ≤ (ℓ + 1) · 6.

Assuming GRH, this result settles the lower-bound portion of Question 3 in [1] . See Lemma 6 of [8] regarding the upper-bound.

Let q be a prime. In this section, we give an algorithm for the following problem: Problem 1. Given a Z q -order Λ q ⊆ M 2 (Q q ), find all maximal orders containing Λ q .

The following algorithm solves Problem 1. To compute the maximal superorders of a Z q -order, one uses the theory of the Bruhat-Tits tree ( §23.5, [27] ). Given an Eichler order Λ q = O∩O ′ , the maximal orders containing Λ q are the maximal orders in the path in T between O and O ′ in this setting (23.5.15 of [27] If Λ q is a Bass order, the runtime is polynomial in log q · log(discrd(Λ q )).

For the definition of the size of a lattice see Section 2. 2. Step 1 can be accomplished in time polynomial in log q · size(Λ q ) with Algorithm 7.10 of [28] . We can accomplish Step 3(c)i with linear algebra over Z q . Now we show that the algorithm correctly computes every maximal order containing Λ q by showing that A forms a connected subtree of T . Suppose O, O ′ are maximal orders containing Λ q . Then O ∩ O ′ is an Eichler order containing Λ q . The maximal orders in M 2 (Q q ) containing O ∩ O ′ form a path in T , and each such order also contains Λ q . Thus A forms a connected set, as claimed.

Finally, to see that the algorithm is efficient when Λ q is Bass, we use the results of [6] . First assume Λ q is Eichler. Then there are e + 1 maximal orders containing Λ q , where e = log q (discrd(Λ q )) by Corollary 2.5 of [6] . If Λ q is Bass but not Eichler, then there are either 1 or 2 maximal orders containing Λ q by Proposition 3.1, Corollary 3.2, and Corollary 4.3 in [6] .

Note that if B is a division quaternion algebra over Q q , then the algorithm of [28] already solves Problem 1 in that case: there is only one maximal order in B. In later sections, we will be interested in enumerating the q-maximal orders containing a Z-order Λ in a quaternion algebra B over Q. The algorithm below uses Algorithm 4.1 to accomplish this. Algorithm 4. 3 . Enumerate the q-maximal Z-orders O containing Λ Input: a Z-order Λ and prime q Output: All Z-orders O ⊃ Λ such that O is q-maximal and O ⊗ Z q ′ = Λ ⊗ Z q ′ for all primes q = q ′ .

(1) Let e = v q (discrd(Λ)) (2) Compute an approximate embedding f : Λ ֒→ M 2 (Z q ) up to precision e If Λ⊗Z q is Bass, the run time is polynomial in log(discrd(Λ ⊗ Z q )).

Step 2, we compute approximations of the coefficients in Z q -linear combinations of the basis elements of Λ which can be identified with a basis of an order in M 2 (Q q ) isomorphic to Λ. This can be efficiently executed using Algorithm 4.3 of [28] . We will compute these coefficients up to precision e = v q (discrd(Λ)). For each maximal Z q -order O ⊃ f (Λ), we then compute a corresponding Z-order O ′ ⊃ Λ, whose generators are Z[q −1 ]-linear combinations of generators of Λ, where the denominator of these coefficients is at most q −e . It is straightforward to check that the lattice Λ + O ′ is actually a Z-order and has the desired completions.

In this section we enumerate all maximal orders O of a quaternion algebra B over Q that contain a given Z-order Λ. To do this, we use the results from the previous section; there we showed that for any prime q dividing disc(Λ) we can enumerate all Z-orders O such that O ⊗ Z q is a maximal order containing Λ ⊗ Z q and such that O ⊗ Z q ′ = Λ ⊗ Z q ′ for all q ′ = q. 

Step 3(b)i is done by computing a generating set for O + O iji , using lattice reduction, and expressing the resulting Z-basis as a Q-linear combination of a basis of Λ. We now show that the algorithm is correct. First, let O i be an arbitrary order in X i , for i = 1 to m, and define

is a maximal Z qi -order, for each i. If q = q i for any i = 1, . . . , m, then (q, discrd(Λ)) = 1, which implies that O ′ ⊗ Z q = Λ ⊗ Z q is maximal. We note that O ′ is a maximal order, because all of its localizations are maximal orders (Theorem 10.4.2 of [27] ). Finally, we observe that every maximal order O ⊇ Λ is enumerated, because in our construction we loop through every possible tuple of maximal orders in the completions (see Theorem 9.5.1 of [27] ). 6 . Recovering End(E) from a suborder 6. 1 . Computing End(E) by considering all possible local conditions. In this section, we describe how to recover End(E) from a Bass suborder Λ, using the algorithms from Sections 4 and 5. For this we use an isomorphism f : Λ⊗Q → B p,∞ , which can be computed using the algorithms in [18] , which require factoring integers and polynomials in finite fields. We can test whether f (O) ≃ End(E) using Algorithm 12 of [11] . Checking each order takes time polynomial in log p (assuming the heuristics in [15, 11] ).

Our computational data shows that we get the same running time when the discriminant of Λ is not square-free. This leads us to the following Conjecture 6. 3 . Fix an integer k ≥ 0 and assume that Λ ⊆ End(E) is a Bass order of size polynomial in log p and with discrd(Λ) = O(p k ). Then for any ǫ > 0, Algorithm 6.1 terminates in timeÕ(p ǫ ). 6 .2. Computing End(E). Now we can describe our algorithm to compute the endomorphism ring of E. By computing End(E) we mean computing a basis for an order O in B p,∞ that is isomorphic to End(E), and that we can evaluate the basis at all points of E via an isomorphism B p,∞ → End(E) ⊗ Q. (2) Using the Gram-Schmidt process, compute a, b ∈ Z so that Λ⊗Q ≃ H(a, b) .

(3) Use Algorithm 6.1 to determine End(E).

Based on our numerical experiments, in which more than 60% of our orders were Bass, we introduce a new heuristic assumption. This is needed to argue that the expected number of calls we must make to our cycle finding algorithm in order to compute a Bass order is bounded by a constant. When we generated random orders inside a maximal order we received a similar proportion of how many of those were Bass.

Heuristic: Our cycle finding algorithm produces cycles of length at most L = ⌈3 log p⌉, and the corresponding endomorphisms' discriminants have the distribution which is approximately the distribution of random discriminants in the range [−4p 3 , 0]. Proof. The algorithm computes the endomorphism ring by putting together algorithms from previous sections. In

Step 1b, the Gram matrix for Λ is computed using a generalization of Schoof's algorithm (see Theorem A.6 of [3] ), which can be done in time polynomial in log p and log of the norm of α, β.

Next, we discuss the number of calls we must make to an algorithm for factoring integers. For each pair of cycles computed, the discriminant of the order they generate must be factored. Let Λ ⊆ End(E) denote the Bass order generated by the cycles. Computing the isomorphism f : Λ ⊗ Q ≃ B p,∞ requires one call to an algorithm for factoring integers (and poly log p calls to algorithms for factoring polynomials over F p , see [18] ). Hence the expected number of calls to an algorithm for factoring integers is bounded by a constant.

To check that Λ is Bass, it is enough to check that Λ is Bass at each q dividing disc(Λ) ([7, Theorem 1.2]). To check that Λ is Bass at q it is enough to check that Λ ⊗ Z q and (Λ ⊗ Z q ) ♮ are Gorenstein (see Corollary 1.3 of [7] ). An order is Gorenstein if and only if its ternary quadratic form is primitive (see Corollary 24.2.10 of [27] ), and this can be checked efficiently. Thus, given a factorization of disc(Λ), we can efficiently decide if Λ is Bass.

As an order is Bass if and only if it is basic, and being basic is a local property (see Theorem 1.2 in [7] ), it follows that Λ is Bass whenever the conductors of Z[α] and Z[β] are coprime and the fundamental discriminants of Z[α] and Z[β] are not equal. This will occur whenever the discriminants of α and β are coprime which will happen with probability approximately 6/π 2 ≈ . 6 . See the data in Figure 6 .2.

Since each cycle we compute has length O(log p), the corresponding endomorphism has norm O(p). Using the bound that we obtained for discrd(Λ) in the proof of Theorem 3.9 shows that our orders Λ ⊆ End(E) satisfy discrd(Λ) = O(p k ) for some k. If Λ is Bass, then Step 3 requires polynomial storage, since we must store O(log discrd(Λ)) many q-maximal orders containing Λ, each of which has size which is polynomial in the size of Λ. By Conjecture 6.3 

We implemented a cycle finding algorithm in Sage along with an algorithm for computing traces of cycles in G(p, ℓ). For each p in Figure 6 .2, and for 100 iterations, we computed a pair of cycles in G(p, 2). We then tested whether they generate a Bass order by testing whether the two quadratic orders had coprime conductors and computed the discriminant of the order that they generate. We also computed an upper bound on the number of maximal orders containing Λ when Λ was Bass: suppose discrd(Λ) = p i q ei i , then there are at most N (Λ) := i (e i + 1) many maximal orders containing Λ. We report how often the two cycles generated an order, how many of those orders were Bass, and the average value of N (Λ). We remark that the cycle-finding algorithm we implemented differs from the version described earlier -it searches for j ∈ F p to build the cycles, and it does not take care to avoid finding a second cycle which may commute with the first. We also only computed cycles at j ∈ F p 2 \ F p because this is the case of interest: there are no obvious embeddings of imaginary quadratic orders when Frobenius is not an endomorphism.

Given an order O ⊃ Λ such that O is q-maximal but otherwise has localizations equal to Λ, and given α ∈ O, we can test whether α ∈ End(E) in time polynomial in discrd(O ⊗ Z q ) and the size of Λ. We expect this to speed up the computation of End(E) in practice. 7 . Computing End(E) via pathfinding in the ℓ-isogeny graph

In this section, we give a reduction from the endomorphism ring problem to the problem of computing ℓ-power isogenies in G(p, ℓ), using ideas from [22] , [15] , and [11] . This reduction is simpler than the one in [11] , and uses only one call to a pathfinding oracle (rather than poly log p calls to an oracle for cycles in G(p, ℓ), as in [11] ). We apply this reduction in two ways, noting that it gives an algorithm for computing the endomorphism ring, and that it breaks second preimage resistance of the variable-length version of the hash function in [8] . 7 . 1 . Reduction from computing End(E) to pathfinding in the ℓ-isogeny graph. We first define the pathfinding problem in the supersingular ℓ-isogeny graph G(p, ℓ):

Problem 2 (ℓ-PowerIsogeny). Given a prime p, along with two supersingular elliptic curves E and E ′ over F p 2 , output an isogeny from E to E ′ represented as a chain of ℓ-isogenies of length k with k polynomial in log p.

Computing the endomorphism ring of a supersingular elliptic curve via an oracle for ℓ-PowerIsogeny proceeds as follows. On input p, Algorithm 3 of [11] returns a supersingular elliptic curve E 0 defined over F p 2 and a maximal order O 0 ⊆ B p,∞ with an explicit Z-basis {x 1 , . . . , x 4 }. Proposition 3 of [11] gives an explicit isomorphism g : O 0 → End(E 0 ) with the property that we can efficiently evaluate g(x i ) at points of E 0 . From this, the endomorphism ring of any supersingular elliptic curve E defined over F p 2 can be computed, given a path in G(p, ℓ) from E 0 to E, with ℓ = p a small prime.

The following algorithm gives a polynomial time reduction from computing endomorphism rings to the path-finding problem, which uses only one call to the pathfinding oracle. It assumes the heuristics of [15] and GRH (to compute E 0 ):

Proof. The attack works as follows: Given a path from E 0 to E, use Algorithm 7.1 above to compute End(E). Then use Algorithm 7 of [11] to compute new paths from E 0 to E. We note that Algorithm 7 uses the main algorithm of [22] to compute a connecting ideal of ℓ-power norm, whose output can be randomized. Then for each such ideal, a corresponding path also hashes to j(E). The running time of these algorithms is polynomial in log p. Remark 7. 3 . When a start vertex E ′ = E 0 is chosen, the resulting hash function might still admit a second preimage attack if E ′ was obtained by choosing a path of log p from E 0 to E ′ so that the endomorphism ring of E ′ is known.

Output: A maximal order O ≃ End(E), whose elements can be evaluated at any point of E, and a

e: (a) Compute I k ⊆ O k−1 , the kernel ideal of φ k

Compute J k := J k−1 I k

Compute P k , an ideal equivalent to J k of powersmooth norm

Compute an isogeny ψ k : E 0 → E k corresponding to P k

Proof sketch for correctness of reduction and running time: The kernel ideal ideal I k , which is the ideal of O k−1 of norm ℓ corresponding to φ k , can be comcombining it with algorithms from

For each supersingular elliptic curveẼ, there is an associated hash function. The input to the hash function is a binary number of k digits, and from this one computes a sequence of k 2-isogenies, starting atẼ, whose composition maps to some other supersingular curve E. The j-invariant of E is the output of the hash function. The following is an improvement over

Kristina Nelson, Travis Scholl, and Jana Sotáková. Adventures in supersingularland

Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization project

Cycles in isogeny graphs and corresponding endomorphisms

Computing Hilbert class polynomials

Computing the endomorphism ring of an ordinary elliptic curve over a finite field

On orders in quaternion algebras

On basic and Bass quaternion orders

Cryptographic hash functions from expander graphs

Report on post-quantum cryptography. NIST IR 8105

Computing isogenies between supersingular elliptic curves over Fp

Supersingular isogeny graphs and endomorphism rings: reductions and solutions

Supersingular primes for elliptic curves over real number fields

Verifiable delay functions from supersingular isogenies and pairings

On the security of supersingular isogeny cryptosystems

Identification protocols and signature schemes based on supersingular isogeny problems

On singular moduli

An introduction to the theory of numbers

Splitting full matrix algebras over algebraic number fields

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

Expander graphs based on GRH with an application to elliptic curve cryptography

Endomorphism rings of elliptic curves over finite fields

On the quaternion ℓ-isogeny path problem

An arithmetic intersection formula for denominators of Igusa class polynomials

On the Class-Number of the Corpus P ( √ −k)

Explicit representations of the endomorphism rings of supersingular elliptic curves

The arithmetic of elliptic curves

Quaternion Algebras. Version v.0.9

Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms

We would like to thank John Voight for several helpful discussions and suggestions. We thank Ben Diamond for alerting us that an algorithm similar to Algorithm 7.1 in Section 7 already appeared in [13] . Finally we would like to thank an anonymous reviewer of a previous version of this paper whose suggestions greatly simplified Section 4.