# Unconditional foundations for supersingular isogeny-based cryptography

Arthur Herlédan Le Merdy, Benjamin Wesolowski

► To cite this version:

Arthur Herlédan Le Merdy, Benjamin Wesolowski. Unconditional foundations for supersingular isogeny-based cryptography. 2025. hal-04954150v2

HAL Id: hal-04954150

https://hal.science/hal-04954150v2

Preprint submitted on 23 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Unconditional foundations for
supersingular isogeny-based cryptography

Arthur Herlédan Le Merdy$^{[0009-0007-6116-6863]}$ and
Benjamin Wesolowski$^{[0000-0003-1249-6077]}$

ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

**Abstract.** In this paper, we prove that the supersingular isogeny problem (ISOGENY), endomorphism ring problem (ENDRING) and maximal order problem (MAXORDER) are equivalent under probabilistic polynomial time reductions, unconditionally.

Isogeny-based cryptography is founded on the presumed hardness of
these problems, and their interconnection is at the heart of the design
and analysis of cryptosystems like the SQIsign digital signature scheme.
Previously known reductions relied on unproven assumptions such as the
generalized Riemann hypothesis. In this work, we present unconditional
reductions, and extend this network of equivalences to the problem of
computing the lattice of all isogenies between two supersingular elliptic
curves (HOMMODULE).

For cryptographic applications, one requires computational problems
to be hard on average for random instances. It is well-known that if
ISOGENY is hard (in the worst case), then it is hard for random instances.
We extend this result by proving that if any of the above-mentionned
classical problems is hard in the worst case, then all of them are hard
on average. In particular, if there exist hard instances of ISOGENY, then
all of ISOGENY, ENDRING, MAXORDER and HOMMODULE are hard on
average.

**Keywords:** Isogeny-based cryptography · Cryptanalysis · Endomorphism ring · Isogeny path · Supersingular elliptic curve

# 1 Introduction

Isogeny-based cryptography, a branch of post-quantum cryptography, rests on
the presumed hardness of a few interconnected computational problems: varia-
tions around the supersingular *isogeny problem* (ISOGENY) or the *endomorphism
ring problem* (ENDRING). A collection of “fundamental problems” has grown
with our understanding of the field and with the needs of new cryptosystems.
Some, like ONEEND are well-suited for security proofs, their hardness serving as
a lower bound on the security of cryptographic schemes. Others, like ENDRING,
are better suited for attacks, thereby serving as upper bounds on the security.
And some, like MAXORDER, reframe these problems in a radically different lan-
guage, deepening our understanding of the field.
Connecting these problems, proving computational reductions, or even equiv-
alences, has thus become a central and fruitful line of research. Most notably,
the equivalence between the isogeny problem and the endomorphism ring prob-
lem [10,28] motivated the design of *SQIsign* [9], today the most compact post-
quantum digital signature scheme.

While all these fundamental problems are considered to be equivalent, only
few of the computational reductions linking them are fully, unconditionally
proven. Almost all previously-known results rely on an unproven assumption:
the generalized Riemann hypothesis (GRH). In this paper, we prove that all
the aforementioned problems, and more, are in fact equivalent under classical,
probabilistic polynomial time reductions, unconditionally.

1.1 Contribution

The main results of this paper are Theorem 1.1 and Theorem 1.2 below. The-
orem 1.1, summarized in Figure 1, establishes the *unconditional* equivalence of
fundamental problems of isogeny-based cryptography. Theorem 1.2 establishes
their average-case hardness: if any of them is hard in the worst case, then all of
them are hard on average, for uniformly random instances.

Let us start by informally introducing the computational problems at hand.
Formal definitions are provided in Section 2.5. The central objects of interest are
so-called *supersingular elliptic curves*. *Isogenies* are morphisms between elliptic
curves. *Endomorphisms* of an elliptic curve *E* are isogenies from *E* to itself; they
form a ring, written *End(E)*.

- ONEEND (the One Endomorphism problem): Given a supersingular elliptic curve *E*, find an endomorphism that is not a scalar multiplication, i.e., an element of End(*E*) \ Z.

- ENDRING (the Endomorphism Ring problem): Given a supersingular elliptic curve *E*, compute a basis of the endomorphism ring End(*E*).

- ISOGENY (the Isogeny problem): Given two supersingular elliptic curves *E* and *E*', find an isogeny from *E* to *E*'.

- ℓ-ISOGENYPATH (the ℓ-Isogeny Path problem): Given two supersingular elliptic curves *E* and *E*', and a prime number *ℓ*, find an isogeny *E* → *E*' of degree a power of *ℓ* (i.e., an *ℓ*-isogeny path from *E* to *E*').

- HOMMODULE (the Homomorphism Module problem): Given two supersin-
gular elliptic curves *E* and *E*', compute a basis of the lattice Hom(*E*, *E*') of
all isogenies from *E* to *E*'. This problem has received very little attention so
far. It appears to have never been formally introduced in the literature, yet
has implicitly played a role.

- MAXORDER (the Maximal Order problem): Given a supersingular elliptic curve *E*, find some “abstract ring” *O* isomorphic to *End(*E*). More precisely, *End(*E* ) is known to be isomorphic to a *maximal order O* in a quaternion algebra *B*<sub>*p*,∞</sub>. The MAXORDER problem asks to find an order in *B*<sub>*p*,∞</sub> isomorphic to *End(*E*). To resolve an ambiguity in previous literature (see Section 3), we formalize two variants: MAXORDER, where the solver is free to
choose his own model for $B_{p,\infty}$, and $\text{MAXORDER}_Q$, where the solution has
to be in a model specified by an algorithm $\mathcal{Q}$.

- MOER (the Maximal Order and Endomorphism Ring problem): Given a supersingular elliptic curve $E$, compute a basis of the endomorphism ring $\text{End}(E)$, together with an isomorphism with an order in the quaternion algebra $B_{p,\infty}$.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Summary of the relations between fundamental isogeny-based problems. All arrows are unconditional classical polynomial time reductions. Thin arrows have a $O(1)$ query-complexity, and thick arrows have a polylog($p$) query-complexity. Reductions with no reference are trivial, and all others are proved in the associated reference. Reductions involving $\text{MAXORDER}_Q$ require oracle access to $\mathcal{Q}$.</figcaption></figure>

**Theorem 1.1.** *The problems ISOGENY, ENDRING, ONEEND, MOER, MAXORDER, MAXORDERQ and HOMMODULE are all equivalent under probabilistic polynomial time reductions. Reductions involving MAXORDERQ require oracle access to Q.*

**Map of the proof of Theorem 1.1** The strategy consists in proving the
computational reductions exhibited in Figure 1. Each arrow represents a com-
putational reduction, and comes with a pointer to the proof. Note that our un-
conditional reductions are substantially different from the existing conditional
reductions. To eliminate any reliance on GRH, we avoid all arguments that
rely on the “good” distribution of numbers represented by quadratic forms. This
forbids us from using the powerful tools of KLPT-type algorithms [12]. In particular, we need to construct different “paths” in the network of reductions, and develop new types of arguments. We prove the reductions in the following order.

- The novel distinction between the two computational problems MAXORDER and MAXORDERQ is discussed in Section 3. Their equivalence, proved in Proposition 3.1, hinges on a recent result [7, Proposition 4.1] to compute isomorphisms between quaternion algebras, when some maximal orders are known in each.

- The HOMMODULE problem is the object of Section 4, where we prove that it reduces to ISOGENY. Given two curves $E_1$ and $E_2$, the strategy is the following. First, we exploit the reduction from ENDRING to ISOGENY proved in [19] to compute bases of $End(E_1)$ and $End(E_2)$. Then, we solve ISOGENY again to find some $\varphi : E_1 \to E_2$. Through algebraic arguments, we prove that one can extract a basis of $Hom(E_1, E_2)$ from the data of $End(E_1)$, $End(E_2)$, and $\varphi$.

- The reduction from ONEEND to MAXORDER is the object of Section 5. Navigating between a problem which deals with endomorphisms (like ONEEND) and another which deals with purely quaternionic data (like MAXORDER) typically requires to connect instances to some special elliptic curve $E_0$ for which both $End(E_0)$ and its embedding in the quaternions are already known. This curve $E_0$ provides an “endomorphism/quaternion” dictionary. Without GRH, there is no guarantee that a special curve $E_0$ can be found. We thus need to develop a new strategy. To reduce ONEEND (say on some input $E$) to MAXORDER, we solve MAXORDER on $E$ and on a few “close neighbours” of $E$. Doing so, we construct a “local” correspondence between neighbours of $E$ and quaternionic orders, and we prove that from enough such “local” information, we can reconstruct a full “endomorphism/quaternion” dictionary.

- The reduction from ISOGENY to MOER is the object of Proposition 6.1. This reduction hinges on recent advances in isogeny-based cryptography facilitating the conversion of ideals in quaternionic orders into the corresponding isogenies [18].

- Finally, the reduction from MOER to ENDRING is the object of Proposition 6.2. Of all the reductions, this one resembles the most closely an existing reduction: the reduction from MAXORDER to ENDRING in [10,28]. However, these former reductions required GRH to provably avoid hard factorisations. Instead, we show that no factorisation is needed if we are free to choose our own model $(\mathfrak{a}, \mathfrak{b})$ for the quaternion algebra. The parameters $a$ and $b$ are possibly hard to factor, but it does not matter: the result [7, Proposition 4.1] allows one to convert the solution to more standard models without factoring.

**Discussion of Theorem 1.1 and comparison with previous work.** The former state of the art is summarized in Figure 2. We make the following observations.
- The HOMMODULE problem is absent from Figure 2: its relation to other problems was never studied before.

- The MOER problem is also absent, yet it is folklore that, assuming GRH, the reductions of [28] also extend to MOER.

- Reflecting previous litterature, Figure 2 makes no distinction between the problems MAXORDER and MAXORDERQ. Indeed, this distinction is only useful if one refuses to believe in GRH (see Section 3).

- There remains one reduction which is only known conditionally on GRH: the reduction from $\ell$-ISOGENYPATH to ENDRING (or to any other problem in our list). Indeed, by definition, $\ell$-ISOGENYPATH asks to find isogenies with degree of a prescribed form. The study of isogenies of prescribed degree closely relates to the study of integers represented by certain quadratic forms. GRH has a consequential impact on the distribution of integers represented by quadratic forms, and currently known unconditional results seem insufficient for the study of $\ell$-ISOGENYPATH.<fnref n="1" />

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Former state of the art of (conditional) reductions between foundational problems of isogeny-based cryptography. All arrows are classical polynomial time reductions. Thin arrows have a $O(1)$ query-complexity, and the thick arrow has a polylog($p$) query-complexity. Reductions with no reference are trivial, and all others are proved in the associated reference. The **GRH** label signifies that a reduction assumes the Generalized Riemann Hypothesis.</figcaption></figure>

Theorem 1.1 implies that if hard instances exist for any one of the listed problems, then hard instances must exist for all of them. However, the security of isogeny-based schemes typically relies on the presumed hardness of random instances of these problems. These random instances often follow a “natural” distribution called the *stationary distribution* (see Definition 2.15 — note that it is statistically indistinguishable from the uniform distribution). This distribution emerged from the use of random walks as early as the Charles-Goren-Lauter hash function [6], and up to the latest advances on the SQIsign digital signature scheme [8,3]. We are thus interested in the hardness of the *average case* of the

<footnote n="1">¹ Note that an attempt at replacing the GRH assumption with a factoring oracle is presented in [15]. A mistake in the proof has been reported, but if it can be fixed, it would link $\ell$-ISOGENYPATH to the other problems under unconditional polynomial time *quantum* reductions.</footnote>
fundamental problems (see Definition 2.19), with respect to the stationary (or uniform) distribution.

The following Theorem 1.2 says that there are worst-case to average-case reductions between all of these problems. In particular, if there exists even a single hard instance for any of the listed problems, then all of the problems are hard on average — a powerful statement for security analysis.

**Theorem 1.2.** For any pair of problems $(P, Q)$ chosen from the problems ISOGENY, ENDRING, ONEEND, MOER, MAXORDER, MAXORDER<sub>Q</sub>, HOMMODULE, and $\ell$-ISOGENYPATH there exists a probabilistic polynomial time worst-case to average-case reduction from $P$ to $Q$. All reductions hold unconditionally, with the two following exceptions which require the generalized Riemann hypothesis:

- if $P = \ell$-ISOGENYPATH, or

- if $Q \in \{\text{MAXORDER}, \text{MAXORDER}_Q\}$ and $p \equiv 1 \bmod 8$.

Reductions involving $\text{MAXORDER}_Q$ require oracle access to $Q$.

**Map of the proof of Theorem 1.2** The strategy, carried out in Section 7, consists in proving that the worst-case ONEEND problem reduces to the average case of any other problem in the list. The precise network of reductions is summarized in Figure 3, page 26. We conclude from the fact, established in Theorem 1.1, that the worst case of any problem in the list reduces to a worst-case ONEEND instance (except for $P = \ell$-ISOGENYPATH, which relies on the conditional reduction of [28]).

**Discussion of Theorem 1.2 and comparison with previous work.** Some of the worst-case to average-case reductions between the problems of interest are already folklore. It is well known, for instance, that random walks in $\ell$-isogeny graphs can be used to re-randomize an instance of the $\ell$-ISOGENYPATH, leading naturally to a self-reduction. This straightforward approach extends to other cases, but is not sufficient to obtain the full network of reductions proved in Theorem 1.2. For instance, the reduction from the worst-case ONEEND problem to the average case ISOGENY, HOMMODULE or $\ell$-ISOGENYPATH problems is obtained by modifying a worst-case reduction proposed in [19]. The reduction from the worst-case ONEEND problem to the average case MAXORDER or MAXORDER<sub>Q</sub> problems relies on recent advances facilitating the conversion between ideals and isogenies and the division of isogenies.

## 1.2 Acknowledgements

The authors would like to thank Travis Morrison for fruitful discussions, and for bringing our attention to [7, Proposition 4.1], which simplified and improved some of the results of this paper. The authors were supported by the Agence Nationale de la Recherche under grants ANR-22-PETQ-0008 (PQ-TLS) and ANR-22-PNCQ-0002 (HQI), and the European Research Council under grant No. 101116169 (AGATHA CRYPTY).
# 2 Preliminaries

## 2.1 Notation

We write $\mathbb{Z}$ for the ring of integers and $\mathbb{Q}$ for the field of rational numbers. For any prime power $q$, we write $\mathbb{F}_q$ for the finite field with $q$ elements. For any set $S$, we denote by $\#S$ its cardinality. For any field $K$, we write $\overline{K}$ for its algebraic closure. We write $f = O(g)$ for the classic big O notation, and use the soft O notation $\tilde{O}(g) = \log(g)^{O(1)} \cdot O(g)$. We also write $\text{poly}(f_1, \dots, f_n) = (f_1 + \dots + f_n)^{O(1)}$. The function $\log$ is in base 2. For any ring $R$, we write $R^\times$ for its group if invertible elements, and $M_2(R)$ for the ring of $2 \times 2$ matrices with coefficients in $R$.

## 2.2 Quaternion algebras

See [26] for a detailed reference on quaternion algebras. For any $a, b \in \mathbb{Q}^\times$, the quaternion algebra $B = (\frac{a}{b} \mathbb{Q})$ is a ring generated by a $\mathbb{Q}$-basis $(1, i, j, k)$ satisfying the multiplication rules

$$i^2 = a, j^2 = b, k = ij = -ji.$$

In this article, we only consider quaternion algebra of this form. For any prime $p$, we say that $B$ is ramified at $p$ if $B \otimes \mathbb{Q}_p \not\cong M_2(\mathbb{Q}_p)$. It is ramified at $\infty$ if $B \otimes \mathbb{R} \not\cong M_2(\mathbb{R})$. We write $B_{p,\infty}$ for a quaternion algebra (unique up to isomorphism) ramified at $p$ and $\infty$ (and unramified at all other primes).

**Lemma 2.1 ([20]).** Let $p > 2$ be a prime. Then, $B_{p,\infty} \cong (\frac{-q; -p}{\mathbb{Q}})$, where

$$q = \begin{cases} 1 & \text{if } p \equiv 3 \mod 4, \\ 2 & \text{if } p \equiv 5 \mod 8, \\ q_p & \text{if } p \equiv 1 \mod 8, \end{cases}$$

where $q_p$ is any prime such that $q_p \equiv 3 \mod 4$ and $(\frac{p}{q_p}) = -1$.

Note that if GRH is true, when $p \equiv 1 \mod 8$, the smallest suitable $q_p$ satisfies $q_p = O((\log p)^2)$ (this follows from [13], see also [10, Proposition 1]).

Let $B$ be a quaternion algebra. The canonical involution

$$\overline{a + ib + jc + kd} \mapsto a - ib - jc - kd$$

induces the reduced trace $\text{Trd}(\alpha) = \alpha + \bar{\alpha}$ and the reduced norm $\text{Nrd}(\alpha) = \alpha \bar{\alpha}$. The reduced norm is a quadratic form on $B$, with the associated bilinear form

$$\langle \alpha, \beta \rangle = \frac{1}{2} \text{Trd}(\alpha \bar{\beta}) = \frac{1}{2} (\text{Nrd}(\alpha + \beta) - \text{Nrd}(\alpha) - \text{Nrd}(\beta)).$$

When $B$ is ramified at $\infty$, the reduced norm is positive definite.
A quadratic space is a $\mathbb{Q}$-vector space $V$ of finite dimension $d$ together with a (positive definite) quadratic form $f: V \to \mathbb{Q}$. A lattice in $V$ is a subgroup $\Lambda \subset V$ of rank $d$ such that $V = \mathbb{Q}\Lambda$. Given a $\mathbb{Z}$-basis $(b_i)_{i=1}^d$ of a lattice $\Lambda$, its Gram matrix is $G = ((b_i, b_j))_{i,j=1}^d$. The volume of the lattice is $\mathrm{Vol}(\Lambda) = \sqrt{|\mathrm{det}(G)|}$, where $G$ is the Gram matrix of any basis of $\Lambda$. The discriminant of $\Lambda$ is $\mathrm{disc}(\Lambda) = 16\mathrm{Vol}(\Lambda)^2$.

An order in a quaternion algebra $B$ is a subring $\mathcal{O} \subset B$ that is also a lattice. It is a maximal order if it is not contained in any other order. Maximal orders in $B_{p,\infty}$ have $\mathrm{Vol}(\mathcal{O}) = p/4$.

The following proposition shows that given maximal orders, one can efficiently compute an isomorphism between different models of $B_{p,\infty}$.

**Proposition 2.2.** [7, Proposition 4.1] Let $A, B$ be quaternion algebras isomorphic to $B_{p,\infty}$. Given $\mathcal{O}_A$ a maximal order in $A$ and $\mathcal{O}_B$ a maximal order in $B$, one can compute an isomorphism between $A$ and $B$ in polynomial time.

For any lattice $\Lambda \subset B$, its left order and right order are the orders

$$ \mathcal{O}_L(\Lambda) = \{\alpha \in B \mid \alpha\Lambda \subseteq \Lambda\}, \quad \text{and} \quad \mathcal{O}_R(\Lambda) = \{\alpha \in B \mid \Lambda\alpha \subseteq \Lambda\}. $$

If $\mathcal{O}$ is a maximal order, and $I$ is a left ideal in $\mathcal{O}$, then $\mathcal{O}_L(I) = I$, and $\mathcal{O}_R(I)$ is another maximal order. The connecting ideal of two maximal order $\mathcal{O}_1$ and $\mathcal{O}_2$ is the lattice

$$ I(\mathcal{O}_1, \mathcal{O}_2) = \{\alpha \in B \mid \alpha\mathcal{O}_2\bar{\alpha} \subseteq [\mathcal{O}_2 : \mathcal{O}_1 \cap \mathcal{O}_2]\mathcal{O}_1\}. $$

It is a left $\mathcal{O}_1$-ideal and a right $\mathcal{O}_2$-ideal.

Let $I$ be a left ideal in a maximal order $\mathcal{O}$. Its reduced norm is $\mathrm{Nrd}(I) = \mathrm{gcd}(\mathrm{Nrd}(\alpha) \mid \alpha \in I) = \sqrt{\#(\mathcal{O}/I)}$. Its normalized quadratic form is the integral quadratic form

$$ q_I : I \to \mathbb{Z} : \alpha \mapsto \frac{\mathrm{Nrd}(\alpha)}{\mathrm{Nrd}(I)}. $$

In $B_{p,\infty}$, the volume of $I$ with respect to this quadratic form is $p/4$.

## 2.3 Elliptic curves

See [24] for a detailed reference on elliptic curves. An elliptic curve is an abelian variety of dimension 1. Given a field $k$ of characteristic $p > 3$, an elliptic curve $E$ can be described by a short Weierstrass equation $y^2 = x^3 + ax + b$ for $a, b \in k$ with $4a^3 + 27b^2 \neq 0$. The $k$-rational points of $E$ is the set $E(k)$ of pairs $(x, y) \in k^2$ satisfying the curve equation, together with a point $\infty_E$ 'at infinity'. They form an abelian group, written additively, where $\infty_E$ is the neutral element.

Given two elliptic curves $E_1$ and $E_2$ defined over $k$, an isogeny $\varphi: E_1 \to E_2$ is a non-constant rational map which is also a group homomorphism from $E_1(\bar{k})$ to $E_2(\bar{k})$. The kernel $\mathrm{ker}(\varphi)$ is a finite subgroup of $E_1(\bar{k})$. The degree $\mathrm{deg}(\varphi)$ is its degree as a rational map. An isomorphism is an isogeny of degree 1.
For any integer $m$, the multiplication-by-$m$ map $[m] : E \to E$ is an isogeny. For any isogeny $\varphi : E \to E'$, its dual is the unique isogeny $\hat{\varphi} : E' \to E$ such that $\hat{\varphi} \circ \varphi = [\deg(\varphi)]$.

The isogeny $\varphi$ is separable if $\deg(\varphi) = \#\ker(\varphi)$, and inseparable otherwise. The isogeny is purely inseparable if $\ker(\varphi)$ is trivial (note that an isogeny is an isomorphism if and only if it is both separable and purely inseparable). For any finite subgroup $G \subset E(\bar{k})$, there exists a separable isogeny $\varphi : E \to E/G$ with $\ker(\varphi) = G$ (and $\varphi$ is unique up to an isomorphism of the target).

If $k$ has characteristic $p > 0$, the map $\phi_{p^n}^E : E \to E(p^n) : (x, y) \mapsto (x^{p^n}, y^{p^n})$ is the $p^n$-Frobenius isogeny. For any isogeny $\varphi : E \to E'$, there is a maximal integer $n$ such that $\varphi$ factors as $\varphi = \psi \circ \phi_{p^n}^E$. Then, $\psi$ is separable. The isogenies $\phi_{p^n}^E$ are purely inseparable.

If $\varphi$ is separable and $\deg(\varphi) = \ell$ is prime, we say that $\varphi$ is an $\ell$-isogeny.

An endomorphism of $E$ is an isogeny $E \to E$. Endomorphisms, together with the zero morphism, form the endomorphism ring $\text{End}(E)$. The curve $E$ is supersingular when $\text{End}(E)$ is a lattice of rank 4. Then, $\text{End}(E) \otimes \mathbb{Q}$ is isomorphic to the quaternion algebra $B_{p,\infty}$, and $\text{End}(E)$ is a maximal order. The degree map $\text{deg} : \text{End}(E) \to \mathbb{Z}$ coincides with the reduced norm of the algebra.

We write $\text{SS}_p$ for the set of $\mathbb{F}_p$-isomorphism classes of supersingular elliptic curves over $\mathbb{F}_p$. We have $\#\text{SS}_p = \lfloor p/12 \rfloor + \varepsilon$, with $\varepsilon \in \{0, 1, 2\}$, and all supersingular elliptic curves have a model over $\mathbb{F}_{p^2}$.

The Deuring correspondence highlights a deep connection between supersingular elliptic curves and maximal orders in the quaternion algebra $B_{p,\infty}$. Indeed, for any supersingular $E/\mathbb{F}_{p^2}$, we have that $\text{End}(E)$ is a maximal order in the algebra $\text{End}(E) \otimes \mathbb{Q} \simeq B_{p,\infty}$. For any isogeny $\varphi : E \to E'$, we have a left ideal

$$I_{\varphi} = \operatorname{Hom}(E', E) \circ \varphi \subseteq \operatorname{End}(E),$$

and the right order $\mathcal{O}_R(I_\varphi)$ is isomorphic to $\text{End}(E')$. Any non-zero left ideal $I$ in $\text{End}(E)$ is of this form, and we write $\varphi_I : E \to E_I$ for the corresponding isogeny. We thus have a bijection $\varphi \mapsto I_\varphi$ (with inverse $I \mapsto \varphi_\varphi$) between

- Isogenies from $E$ (up to isomorphism of the target), and

- Left ideals in $\text{End}(E)$.

Furthermore, for any $\varphi : E \to E'$, the lattice $I_\varphi$ (with its normalized quadratic form $q_{I_\varphi}$) is isomorphic to $\operatorname{Hom}(E, E')$ (with the quadratic form $\deg$).

## 2.4 Isogeny algorithms

There are several ways to encode an isogeny. In computational questions involving isogenies, we typically do not care how an isogeny is encoded, at long as it is an *efficient representation*: an encoding that allows to store and evaluate the isogeny $\varphi$ in polynomial time in $\log(\deg(\varphi))$.
**Definition 2.3 (Efficient representation, following [29, Definition 1.3]).**

Let $\mathcal{A}$ be a polynomial time algorithm. It is an efficient isogeny evaluator if for any $D \in \{0, 1\}^*$ such that $\mathcal{A}(\text{validity}, D)$ outputs $\top$, there exists an isogeny $\varphi : E \to E'$ (defined over some finite field $\mathbb{F}_q$) such that:

1. on input (curves, D), $\mathcal{A}$ returns $(E, E')$,

2. on input (degree, D), $\mathcal{A}$ returns $\deg(\varphi)$,

3. on input (eval, D, P) with $P \in E(\mathbb{F}_{q^k})$, $\mathcal{A}$ returns $\varphi(P)$.

If furthermore $D$ is of polynomial size in $\log(\deg \varphi)$ and $\log q$, then $D$ is an efficient representation of $\varphi$ (with respect to $\mathcal{A}$).

The break of SIDH [5,14,22] had a major consequence on the computation of isogenies: they can be interpolated. More precisely, one can compute an efficient representation of an isogeny given only its image on a sufficiently large subgroup of its domain. In this paper, we will use the following simplified version of this result.

**Proposition 2.4 (IsogenyInterpolation [23, Theorem 5.19]).** Let $\varphi : E \to E'$ be an $n$-isogeny between supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. Let $N > n$ be an integer coprime to $p$ with prime power decomposition $\prod_{i=1}^r \ell_r^{e_i}$. Let $(P_1, Q_1, \dots, P_r, Q_r)$ be a set of generators of the $N$-torsion $E[N]$ such that $(P_i, Q_i)$ is a basis of $E[\ell_i^{e_i}]$, for $i = 1, \dots, r$.

Then, given $(P_1, Q_1, \dots, P_r, Q_r, \varphi(P_1), \varphi(Q_1), \dots, \varphi(P_r), \varphi(Q_r))$, one can compute an efficient representation of $\varphi$ in polynomial time in the length of the input and in the largest prime factor of $N$.

Using this interpolation result, it was then proved that there is an efficient algorithm to divide isogenies. This application was first presented in [21] is some particular case, and later generalised in [16].

**Proposition 2.5 (IsogenyDivision, [21] and [16, Theorem 3]).** Given an isogeny $\varphi : E_1 \to E_2$, where $E_1$ and $E_2$ are supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, and an integer $n < \deg \varphi$, one can return an efficient representation of $\varphi/n$ if it is a well-defined isogeny, and return *False* otherwise, in time polynomial in $\log p$ and $\log \deg \varphi$.

Finally, we will use a recent unconditional polynomial-time algorithm to translate $\mathcal{O}$-left ideals to corresponding isogenies, where $\mathcal{O}$ is a maximal order in a quaternion algebra isomorphic to $B_{p,\infty}$. It is a direct generalisation of the CLAPOTI algorithm [18] for computing class group action on oriented elliptic curves in polynomial time, even if the norm of the acting ideal is not smooth.

Translating CLAPOTI into a general IDEALTOISOGENY algorithm has been done in prior work, such as [3]. Notice that, for the sake of efficiency, the authors of [3] chose to use isogenies in dimension 2, which required assuming heuristics. In contrast, to obtain a rigorous polynomial-time algorithm, we consider the most direct generalisation of CLAPOTI, using abelian varieties of dimension 8.
**Proposition 2.6 (IdealToIsogeny [18]).** Let $E$ be a supersingular elliptic curve defined over $\mathbb{F}_q$ such that an isomorphism $\varepsilon : \text{End}(E) \simeq \mathcal{O}$ is known, where $\mathcal{O}$ is a maximal order in some quaternion algebra isomorphic to $B_{p,\infty}$. Given a left $\mathcal{O}$-ideal $I$, one can compute an efficient representation of the isogeny $\varphi_I : E \to E/E[I]$ in polynomial time in the length of the input.

## 2.5 Computational problems

We now formally define the computational problems of interest. Every isogeny in the input or output of these problems is considered to be in efficient representation 2.3. The *supersingular isogeny problem* can then be simply expressed as follows.

*Problem 2.7 (ISOGENY).* Given $E$ and $E'$ two supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, compute an isogeny $\varphi : E \to E'$.

Instead of asking for a single isogeny, one can ask for the collection of all isogenies from $E$ to $E'$. As this collection is a lattice, the following problem asks to find a basis of this lattice.

*Problem 2.8 (HOMMODULE).* Given two supersingular elliptic curves $E$ and $E'$ defined over $\mathbb{F}_{p^2}$, find four isogenies generating $\text{Hom}(E, E')$ as a $\mathbb{Z}$-module.

It is often convenient to find an isogeny of a particular form. An $\ell$-isogeny path (of length $n$) from $E$ to $E'$ is a sequence of $\ell$-isogenies $\varphi_i : E_i \to E_{i+1}$ such that $E_0 = E$ and $E_n = E'$. Such a path provides an efficient representation of the degree $\ell^n$ composition $E \to E'$. The following version of the isogeny problem appeared as early as [6], when no general method was known for the efficient representation of arbitrary isogenies.

*Problem 2.9 (ℓ-ISOGENYPATH).* Given $E$ and $E'$ two supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, compute an $\ell$-isogeny path from $E$ to $E'$.

It soon appeared that the problem of finding isogenies is closely related to the problem of finding endomorphisms. Again, there are several ways to formalize it. The first asks to find a basis of the endomorphism ring.

*Problem 2.10 (ENDRING).* Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$, find four endomorphisms generating $\text{End}(E)$ as a $\mathbb{Z}$-module.

Similarly to isogenies, we could ask to find a single endomorphism instead of the whole ring. But extra care is required: some endomorphisms are always easy to find: any scalar multiplication $[m]$ on $E$ is an endomorphism, forming the subring $\mathbb{Z} \subset \text{End}(E)$.

*Problem 2.11 (ONEEND).* Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$, find an endomorphism in $\text{End}(E) \setminus \mathbb{Z}$.
Now, computing the endomorphism ring of $E$ could be interpreted in a different way. Instead of finding actual endomorphisms of $E$ as in ENDRING, one could ask for the abstract structure of $\mathrm{End}(E)$. Indeed, this ring is always isomorphic to a maximal order in $B_{p,\infty}$, and determining which is the following problem.

**Problem 2.12 (MAXORDER).** Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$, find a quaternion algebra $B = (\frac{-a, -b}{Q}) \simeq B_{p,\infty}$, together with four quaternions in $B$ generating a maximal order isomorphic to $\mathrm{End}(E)$.

Note that in previous work such as [10,28], the problem MAXORDER does not require finding a model $(\frac{-a, -b}{Q})$ for $B_{p,\infty}$. Instead, they make the implicit assumption that a fixed model of the form $B_{p,\infty} = (\frac{-p, -q}{Q})$ is used. Since there is no “canonical” model of $B_{p,\infty}$, we include the choice of a model in the definition of the problem. We discuss this subtlety in further detail in Section 3, where we prove that it does not actually matter: it is equivalent to the following problem where a model for $B_{p,\infty}$ of the same form as [10,28] is provided.

**Problem 2.13 (MAXORDER$_Q$).** Let $Q$ be an algorithm which for any prime number $p$, outputs a prime $q = Q(p)$ such that $B_{p,\infty} \simeq (\frac{-p, -q}{Q})$. The problem MAXORDER$_Q$ is the following. Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$, find four quaternions in $(\frac{-p, -Q(p)}{Q})$ generating a maximal order isomorphic to $\mathrm{End}(E)$.

As the ENDRING problem asks to find actual endomorphisms generating $\mathrm{End}(E)$, and the MAXORDER problem asks to find the “quaternionic” structure of $\mathrm{End}(E)$, one can combine these two tasks as in the following problem.

**Problem 2.14 (MOER).** Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$, find four endomorphisms $(\alpha_i)_{i=1}^4$ generating $\mathrm{End}(E)$ as a $\mathbb{Z}$-module, a quaternion algebra $B = (\frac{-a, -b}{Q}) \simeq B_{p,\infty}$, and four quaternions $(\beta_i)_{i=1}^4$ in $B$ such that

$$ \mathrm{End}(E) \otimes \mathbb{Q} \to B : \alpha_i \mapsto \beta_i $$

is an isomorphism.

## 2.6 Random walks

We will consider random processes in the set of supersingular elliptic curves. Let $\mathbb{C}^{\mathrm{SS}_p}$ be the set of functions $\mathrm{SS}_p \to \mathbb{C}$. We consider two natural distances on $\mathbb{C}^{\mathrm{SS}_p}$. First,

$$ d_{\mathrm{TV}}(f, g) = \frac{1}{2} \|f - g\|_1 = \frac{1}{2} \sum_{E \in \mathrm{SS}_p} |f(E) - g(E)|. $$

When $f$ and $g$ are distributions on $\mathrm{SS}_p$, this is known as the total variation distance. Second, we have the scalar product

$$ \langle f, g \rangle = \sum_{E \in \mathrm{SS}_p} f(E) \overline{g(E)} \#\mathrm{Aut}(E), $$
inducing the norm $||f|| = \langle f, f \rangle^{1/2}$. Note that by the Cauchy-Schwarz inequality and Eichler's formula, for any $f, g$, we have

$$d_{\text{TV}}(f,g) \le \frac{\|f-g\|}{2} \left( \sum_{E \in \text{SS}_p} \frac{1}{\#\text{Aut}(E)} \right)^{1/2} = \frac{\|f-g\|}{2} \left( \frac{p-1}{24} \right)^{1/2}.$$

Given an elliptic curve $E$, a prime $\ell$ and an integer $k$, a random $\ell$-walk from $E$ of length $k$ is a random sequence $(\varphi_0, \dots, \varphi_{k-1})$ sampled as follows:

1. Let $E_0 = E$,

2. For each $i$, let $G_i$ be a uniformly random subgroup of order $\ell$ in $E_i$, and let $E_{i+1} = E_i / G_i$

3. For each $i$, let $\varphi_i : E_i \to E_{i+1}$ be the quotient isogeny.

The curve $E$ is the source of the walk, and the codomain of $\varphi_{k-1}$ is called the target of the walk. Let $N$ be a positive integer with prime factorization $N = \prod_{i=1}^t \ell_i^{k_i}$. A random $N$-walk from $E$ is a sequence $(w_i)_{i=1}^t$ where

1. The source of $w_1$ is $E$,

2. Each $w_i$ is a random $\ell_i$-walk of length $k_i$, and

3. For each $i$, the target of $w_i$ is the source of $w_{i+1}$.

The target of the walk is the target of $w_t$. Note that the walk itself depends on an order of the prime factors of $N$, but the distribution of the target does not.

The following proposition states that random walks rapidly converge to the so-called stationary distribution.

**Definition 2.15.** The stationary distribution on $\text{SS}_p$ is the probability distribution defined by $\mu(E) = \frac{24}{(p-1)\#\text{Aut}(E)}$.

**Remark 2.16.** For any $p > 3$, the quantity $\#\text{Aut}(E)$ is equal to 2 for all curves $E$ with two exceptions: if $j(E) = 1728$, then $\#\text{Aut}(E) = 4$, and if $j(E) = 0$, then $\#\text{Aut}(E) = 6$. Therefore, the total variation distance between the uniform distribution and the stationary distribution on $\text{SS}_p$ is $O(1/p)$. In particular, the two distributions are statistically and computationally indistinguishable.

**Proposition 2.17.** Let $N$ be a positive integer with prime factorization $N = \prod_{i=1}^t \ell_i^{k_i}$. Let $E$ be a random supersingular elliptic curve defined over $\mathbb{F}_{p^2}$, for some distribution $f$. Let $W_N(f)$ be the distribution of the target of a random $N$-walk from $E$. Then,

$$\|W_N(f) - \mu\| \le \|f - \mu\| \cdot \prod_{i=1}^{t} \left( \frac{2\sqrt{\ell_i}}{\ell_i + 1} \right)^{k_i},$$

where $\mu$ is the stationary distribution.
*Proof.* This is a folklore consequence of Pizer's proof that the supersingular $\ell$-isogeny graph is Ramanujan [20]. However, previous literature only details the case where $N$ is a prime power, so let us show that it extends to the general case. Following [19, Appendix A.1], let $W_\ell = B_\ell/(\ell+1)$ be the $\ell$-walk operator in $X$: for any distribution $f$ on $SS_p$, we have that $W_\ell^k(f)$ is the distribution of the target of a random $\ell$-walk of length $k$. From [19, Appendix A.1] and [19, Theorem 3.10], we have $\|W_\ell^k(f) - \mu\| \le \frac{2\sqrt{\ell}}{\ell+1}\|f - \mu\|$. We deduce that

$$ \|W_N(f) - \mu\| = \|(W_{\ell_1}^{k_1} \circ \cdots \circ W_{\ell_t}^{k_t})(f) - \mu\| \le \|f - \mu\| \cdot \prod_{i=1}^{t} \left( \frac{2\sqrt{\ell_i}}{\ell_i + 1} \right)^{k_i}, $$

as claimed.

□

In our applications, we only need the following corollary, where we introduce a useful notation $\tau(p, \varepsilon)$ for the subsequent proofs.

**Corollary 2.18.** Let $E$ be a random supersingular elliptic curve defined over $\mathbb{F}_{p^2}$, for some distribution $f$, and let $\varepsilon > 0$. There exists a bound $\tau(p, \varepsilon) = O(\log(p) - \log(\varepsilon))$ such that for any $N > 2^{\tau(p,\varepsilon)}$, the output distribution of a random $N$-walk is at total variation distance at most $\varepsilon$ to the stationary distribution.

*Proof.* By [2, Theorem 7, Item 5], we have $\|f - \mu\| \le \sqrt{3}$. Let $\lambda = \log(3/(2\sqrt{2}))$. From Proposition 2.17, we have

$$ \|W_N(f) - \mu\| \le \|f - \mu\| \cdot \prod_{i=1}^{t} \left( \frac{2\sqrt{\ell_i}}{\ell_i + 1} \right)^{k_i} \le \sqrt{3} \cdot \left( \frac{2\sqrt{2}}{3} \right)^{\log(N)} = \sqrt{3} \cdot 2^{-\lambda \log(N)}. $$

Now,

$$ d_{\text{TV}}(W_N(f), \mu) \le \frac{\|W_N(f) - g\|}{2} \left(\frac{p-1}{24}\right)^{1/2} \le 2^{-\lambda \log(N)} \left(\frac{p-1}{24}\right)^{1/2}. $$

The latter quantity is smaller than $\varepsilon$ if and only if

$$ \log(N) \ge \frac{\lambda}{2} (\log(p-1) - \log(24) - 2\log(\varepsilon)) = O(\log(p) - \log(\varepsilon)), $$

which proves the result.

□

Thanks to the concepts introduced in this section, we can now properly define *average-case* problems.

**Definition 2.19.** Let $P$ be a problem from the list $\ell$-ISOGENYPATH, ISOGENY, ENDRING, ONEEND, MOER, MAXORDER, MAXORDERQ and HOMMODULE. The input of the problem $P$ consists of one or two supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. We define the *average-case* for $P$ as the case where the input curves are drawn from the stationary distribution on $SS_p$.
### 3 The Maximal Order problem

In this section, we discuss the MAXORDER problem, and a subtlety in its definition when one does not assume GRH. The classical definition makes the implicit assumption that a reference quaternion algebra $B_{p,\infty}$ is provided. However, there is no “canonical” model of $B_{p,\infty}$. When $p \equiv 3 \pmod 4$ (respectively $p \equiv 5 \pmod 8$), one can argue that the algebra $(\frac{-p}{\mathbb{Q}})$ (respectively $(\frac{-p}{\mathbb{Q}})$) is a natural model for $B_{p,\infty}$. However, when $p \equiv 1 \pmod 8$, there is no uniform value of $q$ for which $B_{p,\infty} \simeq (\frac{-q}{\mathbb{Q}})$. In order to fix an algebra for each $p$, previous works fix a procedure $\mathcal{Q}$ such that on input $p$, the output $\mathcal{Q}(p)$ is a prime satisfying $B_{p,\infty} \simeq (\frac{-p}{\mathbb{Q}})$. This $\mathcal{Q}(p)$ is typically set to be the smallest prime number with the requested property. While a convenient choice, it is somewhat arbitrary. Furthermore, without GRH, there is no guarantee for this value to be small, nor easy to find.

As this model $B_{p,\infty} = (\frac{-a-b}{\mathbb{Q}})$ might be hard to compute (without GRH, when $p \equiv 1 \pmod 8$), the original definition of MAXORDER becomes ambiguous: are $a$ and $b$ provided, or are they to be computed? We settle for a definition of MAXORDER where $a$ and $b$ are left to be found. Let us show that the impact of this choice is minimal: it is equivalent to the variant MAXORDER$_Q$ where the algebra is imposed to be of the classical form $(\frac{-p}{\mathbb{Q}})$, for any procedure $\mathcal{Q}$ which returns a suitable prime. The key is Proposition 2.2, which allows one to translate solutions across different models of $B_{p,\infty}$, so the choice of a particular model matters not.

**Proposition 3.1 (MAXORDER$_Q$ is equivalent to MAXORDER).** Given access to $\mathcal{Q}$, the two problems MAXORDER and MAXORDER$_Q$ are equivalent under probabilistic polynomial time reductions. The reductions make a single query to each oracle.

*Proof.* Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve. We first prove that MAXORDER reduces to MAXORDER$_Q$. Indeed, if $\mathcal{O} \subset (\frac{-p}{\mathbb{Q}})$ is a solution of MAXORDER$_Q$, then $(p, \mathcal{Q}(p), \mathcal{O})$ is a solution of MAXORDER.

We now prove that MAXORDER$_Q$ reduces to MAXORDER. Let $\mathcal{O} \subseteq (\frac{-a-b}{\mathbb{Q}})$ be a solution of MAXORDER, and let $q = \mathcal{Q}(p)$. Let $\Lambda_0$ be the (non-maximal) order spanned by the canonical basis $(1, i, j, k)$ of $(\frac{-p}{\mathbb{Q}})$. Thanks to the orthogonality of this basis and since the discriminant of any order $\mathcal{O} = (\alpha_0, \dots, \alpha_4)$ is given by $\mathrm{disc}(\mathcal{O}) = \sqrt{|\det((\langle\alpha_i, \alpha_j\rangle)_{i,j})|}$, the discriminant of $\Lambda_0$ is $pq$. The factorisation of $\mathrm{disc}(\Lambda_0)$ being known, one can construct a maximal order $\mathcal{O}_0 \supseteq \Lambda_0$ in polynomial time with [25, Theorem 7.14].

From Proposition 2.2, one can compute an order $\mathcal{O}'$ in $(\frac{-p}{\mathbb{Q}})$ isomorphic to $\mathcal{O}$. Then, $\mathcal{O}'$ is a solution of MAXORDER$_Q$. $\square$
## 4 The Homomorphism Module problem

The HOMMODULE problem has not been formally studied in the previous literature, yet it naturally appears in isogeny-based cryptography. For instance, the homomorphism module between the commitment curve and the challenge curve in SQISign [9] is the space of all possible responses during an identification. While it is clear that ISOGENY reduces to HOMMODULE, we prove in this section that both are actually equivalent.

The relation between HOMMODULE and ISOGENY is reminiscent of the relations between ENDRING and ONEEND. The latter equivalence has been proved in [19]. In this same paper, the authors also proved that ONEEND reduces to ISOGENY, both of these reductions being unconditional. Therefore, there is a probabilistic polynomial time algorithm solving ENDRING given an ISOGENY oracle. In order to take advantage of this fact to solve HOMMODULE we prove that knowing an isogeny between two elliptic curves and their respective endomorphism rings, one can compute efficiently a basis of the homomorphism module between the said curves, Proposition 4.4 and Proposition 4.5. This leads to the main result of the section Proposition 4.6, proving that HOMMODULE reduces to ISOGENY.

**Lemma 4.1.** Let $\varphi_i : E \to E_i$, for $i \in \{1, 2\}$, be separable isogenies such that $\ker \varphi_1 \cap \ker \varphi_2 = 0$. Then,

$$ \mathrm{Hom}(E_1, E)\varphi_1 + \mathrm{Hom}(E_2, E)\varphi_2 = \mathrm{End}(E). $$

*Proof.* Let $\varphi_3 : E \to E_3$ be a separable isogeny with $\ker \varphi_3 = \ker \varphi_1 + \ker \varphi_2$. Since $\ker \varphi_1 \cap \ker \varphi_2 = 0$, we have $|\ker \varphi_3| = |\ker \varphi_1||\ker \varphi_2|$. Each

$$ I_i = \mathrm{Hom}(E_i, E)\varphi_i = \{\alpha \in \mathrm{End}(E) \mid \ker \varphi_i \subseteq \ker \alpha\} $$

is a left $\mathrm{End}(E)$-ideal of reduced norm $\mathrm{Nrd}(I_i) = |\ker \varphi_i|$. We have

$$ I_1 \cap I_2 = \{\alpha \in \mathrm{End}(E) \mid (\ker \varphi_1 + \ker \varphi_2) \subseteq \ker \alpha\} = I_3. $$

We have,

$$ \begin{aligned} |I_1/(I_1 \cap I_2)|^{1/2} &= \frac{\mathrm{Nrd}(I_3)}{\mathrm{Nrd}(I_1)} = \frac{|\ker \varphi_3|}{|\ker \varphi_1|} = \frac{|\ker \varphi_1||\ker \varphi_2|}{|\ker \varphi_1|} \\ &= \mathrm{Nrd}(I_2) = |\mathrm{End}(E)/I_2|^{1/2}. \end{aligned} $$

By the second isomorphism theorem,

$$ I_1/(I_1 \cap I_2) \cong (I_1 + I_2)/I_2 \subseteq \mathrm{End}(E)/I_2, $$

and since the leftmost and rightmost quotients have the same cardinality, we deduce $(I_1 + I_2)/I_2 = \mathrm{End}(E)/I_2$, hence $I_1 + I_2 = \mathrm{End}(E)$. $\square$

**Lemma 4.2.** Let $\varphi_i : E \to E_i$, for $i \in \{1, 2\}$, be separable isogenies such that $\ker \varphi_1 \cap \ker \varphi_2 = 0$. Then, for any elliptic curve $E'$,

$$ \mathrm{Hom}(E_1, E')\varphi_1 + \mathrm{Hom}(E_2, E')\varphi_2 = \mathrm{Hom}(E, E'). $$
*Proof.* Clearly $\text{Hom}(E_1, E')\varphi_1 + \text{Hom}(E_2, E')\varphi_2 \subseteq \text{Hom}(E, E')$, so let us prove the second inclusion. By Lemma 4.1,

$$ \begin{aligned} \text{Hom}(E, E') &= \text{Hom}(E, E')\text{End}(E) \\ &= \text{Hom}(E, E')\text{(Hom}(E_1, E)\varphi_1 + \text{Hom}(E_2, E)\varphi_2) \\ &\subseteq \text{Hom}(E_1, E')\varphi_1 + \text{Hom}(E_2, E')\varphi_2, \end{aligned} $$

which proves the result. □

**Proposition 4.3.** Let $\varphi : E \to E'$ be a separable isogeny. Then,

$$ \text{span}_{\mathbb{Z}}(\text{End}(E')\varphi\text{End}(E)) = m\text{Hom}(E, E'), $$

where $m \in \mathbb{Z}$ is the largest integer dividing $\varphi$.

*Proof.* Clearly $\text{span}_{\mathbb{Z}}(\text{End}(E')\varphi\text{End}(E)) \subseteq m\text{Hom}(E, E')$, so let us prove the other inclusion. Write $\varphi = m\psi$ with $\text{ker}\,\psi$ cyclic. Let $n = \text{deg}(\psi)$. The kernel $\text{ker}\,\psi \cong \mathbb{Z}/n\mathbb{Z}$ is a cyclic subgroup of $E[n] \cong (\mathbb{Z}/n\mathbb{Z})^2$. The action of $\text{End}(E)/n\text{End}(E)$ on $E[n]$ is isomorphic to the action of $M_2(\mathbb{Z}/n\mathbb{Z})$ on $(\mathbb{Z}/n\mathbb{Z})^2$, so there exists an endomorphism $\alpha \in \text{End}(E)$ (of degree coprime with $n$) such that $\text{ker}(\psi) \cap \alpha^{-1}(\text{ker}\,\psi) = 0$. In other words, $\text{ker}(\psi) \cap \text{ker}(\psi\alpha) = 0$. Applying Lemma 4.2, we deduce

$$ \text{End}(E')\psi + \text{End}(E')\psi\alpha = \text{Hom}(E, E'). $$

We deduce

$$ m\text{Hom}(E, E') = \text{End}(E')\varphi + \text{End}(E')\varphi\alpha \subseteq \text{span}_{\mathbb{Z}}(\text{End}(E')\varphi\text{End}(E)), $$

which proves the proposition. □

Recall that any isogeny can be factored as $\phi\varphi$ where $\varphi$ is separable, and $\phi$ is purely inseparable ($\phi$ might be an isomorphism). Then, the following proposition generalized Proposition 4.3 to arbitrary isogenies.

**Proposition 4.4.** Let $\varphi : E \to E''$ be a separable isogeny, and $\phi : E'' \to E'$ a purely inseparable isogeny $E$. Then,

$$ L = \text{span}_{\mathbb{Z}}(\text{End}(E')\phi\varphi\text{End}(E)) = m\phi\text{Hom}(E, E''), $$

where $m \in \mathbb{Z}$ is the largest integer dividing $\varphi$.

*Proof.* Since $\phi : E'' \to E'$ is purely inseparable, we have $\text{End}(E')\phi = \phi\text{End}(E'')$. The result then immediately follows from Proposition 4.3. □

**Proposition 4.5.** Let $E, E'$ and $E''$ be supersingular elliptic curves, and $\phi : E'' \to E'$ a purely inseparable isogeny $E$. Given a basis of $\phi\text{Hom}(E, E'')$, one can compute a basis of $\text{Hom}(E, E')$ in polynomial time.
Proof. Let $(b_i)_{i=1}^4$ be the provided basis of the lattice $L = \phi \operatorname{Hom}(E, E'')$. Let $p^n = \deg(\phi)$. If $n = 2m$ is even, then $\phi = p^m\alpha$ where $\alpha : E'' \to E'$ is an isomorphism. Then $(b_i/p^m)_{i=1}^4$ is a basis of $\alpha \operatorname{Hom}(E, E'') = \operatorname{Hom}(E, E')$. If $n = 2m+1$ is odd, one can similarly divide by $p^m$, and without loss of generality we now consider the case where $\phi$ is the $p$-Frobenius. Consider the quadratic form

$$q: L \to \mathbb{Z}: \varphi \mapsto \deg(\varphi)/p.$$

We have

$$p \operatorname{Hom}(E, E') = L \cap (p \operatorname{Hom}(E, E')) = \{\varphi \in L \mid q(\varphi) \equiv 0 \mod p\}.$$

The equation $q(\varphi) \equiv 0 \mod p$ defines an $\mathbb{F}_p$-linear subspace of $L/pL$ which can be computed as the kernel of the Gram matrix over $\mathbb{F}_p$. $\square$

**Algorithm 1 Reducing HOMMODULE to ISOGENY**

**Input:** Two isogeneous elliptic curves $E_1$ and $E_2$ and an access to an oracle of ISOGENY.

**Output:** Four isogenies $\varphi_i : E_1 \to E_2$, $i \in \{1, ..., 4\}$ generating $\operatorname{Hom}(E_1, E_2)$ as a $\mathbb{Z}$-module.

1: $(\alpha_1, \alpha_2, \alpha_3, \alpha_4) \leftarrow \text{a basis of } \operatorname{End}(E_1) \qquad \triangleright [19, \text{Theorem 8.6}]$

2: $(\beta_1, \beta_2, \beta_3, \beta_4) \leftarrow \text{a basis of } \operatorname{End}(E_2) \qquad \triangleright [19, \text{Theorem 8.6}]$

3: Compute an isogeny $\varphi : E_1 \to E_2 \qquad \triangleright \text{Using the ISOGENY oracle}$

4: $v \leftarrow v_p(\deg \varphi) \qquad \triangleright \text{$p$-adic valuation of } \deg \varphi$

5: $S \leftarrow \{\beta_j \circ \varphi \circ \alpha_i\} \subset \operatorname{Hom}(E_1, E_2)$

6: $(\gamma_1, \gamma_2, \gamma_3, \gamma_4) \leftarrow \text{a basis of the lattice generated by } S \qquad \triangleright [4]$

7: $m \leftarrow (16 \det((\gamma_i, \gamma_j))/p^{4v+2})^{1/8}$

8: $B_0 \leftarrow (\gamma_1/m, \gamma_2/m, \gamma_3/m, \gamma_4/m) \qquad \triangleright \text{Proposition 2.5}$

9: Extract a basis of $\operatorname{Hom}(E, E')$ from $B \qquad \triangleright \text{Proposition 4.5}$

10: **return** $B$

**Proposition 4.6 (HOMMODULE reduces to ISOGENY).** *Algorithm 1 is correct and runs in time polynomial in $\log p$ and in the length of the oracle outputs.*

*Proof.* The running time of each step is ensured by the corresponding reference. In particular, each is polynomial in $\log p$ and in the length of the oracle's outputs.

Let us prove the correctness of the algorithm by treating the cases where the isogeny $\varphi$, returned by the ISOGENY oracle at Step 3, is inseparable and separable independently.

We now assume that $\varphi = \phi \circ \psi$ where $\psi : E_1 \to E'$ is a separable isogeny and $\phi : E' \to E_2$ is a purely inseparable isogeny of degree $p^v \ge 1$, where $v := v_p(\deg \varphi)$ (when $v = 0$, the purely inseparable part $\phi$ is an isomorphism). Let $m$ be the largest integer that divides $\psi$. Then, by Proposition 4.4, the set
$S$ generates the lattice $m\phi\operatorname{Hom}(E_1, E')$. For a basis $(\gamma_1, \dots, \gamma_4)$ of the lattice generated by $S$, we have

$$ 
\begin{aligned}
\det((\gamma_i, \gamma_j)) &= \operatorname{Vol}(m\phi\operatorname{Hom}(E_1, E'))^2 \\
&= (m^4 \operatorname{deg}(\phi)^2 \operatorname{Vol}(\operatorname{Hom}(E_1, E')))^2 \\
&= m^8 p^{4\nu+2}/16,
\end{aligned}
$$

thus the computation at Step 7 gives the correct $m$. In particular, the basis $B = (\gamma_1/m, \dots, \gamma_4/m)$ generates $\phi\operatorname{Hom}(E_1, E')$. From it, one can compute a basis of $\operatorname{Hom}(E_1, E_2)$ using Proposition 4.5. $\square$

# 5 Finding endomorphisms from quaternions

In the section we develop an unconditional reduction from the ONEEND problem to the MAXORDER problem. The main difficulty is that without GRH, there is no general way to compute a “special” elliptic curve $E_0$ for which both $\operatorname{End}(E_0)$ and its embedding in the quaternions are already known. Such a curve provides an “endomorphism/quaternion” dictionary, and previous literature on MAXORDER made critical use of that fact. Without such an $E_0$, we need to develop a completely different strategy. To reduce ONEEND (say on some input $E$) to MAXORDER, we solve the MAXORDER problem on $E$, giving an order $O$, but also on a few of its “neighbours”. We thereby constructing a “local” correspondence: a canonical bijection between $\ell$-isogenies from $E$ and ideals of norm $\ell$ in the order $O$. This is done in Algorithm 2. We then prove that this information can be converted into isomorphisms $\operatorname{End}(E[\ell]) \simeq O/\ell O$ which all descend from the same implicit isomorphism $\operatorname{End}(E) \simeq O$, via Algorithm 3. Finally, from this local data, we reconstruct a full “endomorphism/quaternion” dictionary $\operatorname{End}(E) \simeq O$ in Algorithm 4.

At several steps of this process, one might fail to construct the dictionary (for instance when the isomorphism $\operatorname{End}(E) \simeq O$ is not unique). In such a scenario, a non-scalar endomorphism of $E$ is revealed, and we have solved ONEEND anyway. If no such failure occurs, we successfully obtain a dictionary, which in turn reveals (all!) non-scalar endomorphisms of $E$.

**Lemma 5.1.** *Algorithm 2 is correct and runs in time polynomial in the length of the input, in $\ell$, and in the length of the MAXORDER oracle outputs.*

*Proof.* The claim that the running time is polynomial follows from the references provided in the comments of Algorithm 2.

Let us prove that the algorithm is correct.

First, the endomorphism $\alpha = \hat{\phi}_j \circ \gamma \circ \phi_i$ returned at Line 4 is not scalar. Indeed, suppose by contradiction that $\alpha \in \mathbb{Z}$. It is of degree $\ell^2$, so $\alpha = [\ell]$. We thus have $\hat{\phi}_j \circ \phi_j = [\ell] = \hat{\phi}_j \circ \gamma \circ \phi_i$, hence $\phi_j = \gamma \circ \phi_i$, hence $\ker(\phi_j) = \ker(\phi_i)$, hence $G_i = G_j$, contradicting that $i \neq j$.

Second, the endomorphism returned at Line 8 is not scalar either. Indeed, it has degree $\ell^2 p$, which is not a square, so it cannot be scalar.
**Algorithm 2** Computing a bijection between $\ell$-isogenies and ideals, given a $\text{MAXORDER}$ oracle

**Input:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, a prime $\ell \neq p$, a list $(G_i)_{i=0}^{\ell}$ of all subgroups of order $\ell$ in $E$, an algebra $B = (\frac{-a, -b}{\mathbb{Q}}) \simeq B_{p,\infty}$, a maximal order $\mathcal{O} \simeq \text{End}(E)$ in $B$, and access to an oracle for $\text{MAXORDER}$.

**Output:** Either an endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$, or the list $(I_i)_{i=0}^{\ell}$ of left $\mathcal{O}$-ideals such that $\mathcal{O}_R(I_i) \simeq \text{End}(E/G_j)$ if and only if $i = j$.

1: Compute $\varphi_i : E \to E/G_i$ using Vélu's formulas for $i = 0, \dots, \ell$

2: **if** $E/G_i \simeq E/G_j$ for some $i \neq j$ **then**

3: $\gamma \leftarrow$ an isomorphism between $E/G_i$ and $E/G_j$

4: **return** $\hat{\varphi}_j \circ \gamma \circ \varphi_i \in \text{End}(E) \setminus \mathbb{Z}$

5: **if** $E/G_i \simeq (E/G_j)^{(p)}$ for some $i \neq j$ **then**

6: $\gamma \leftarrow$ an isomorphism between $E/G_i$ and $(E/G_j)^{(p)}$

7: $\phi_p \leftarrow$ the Frobenius isogeny $\phi_p : E/G_j \to (E/G_j)^{(p)}$

8: **return** $\hat{\phi}_j \circ \phi_p \circ \gamma \circ \varphi_i \in \text{End}(E) \setminus \mathbb{Z}$

9: **for** $i = 0, \dots, \ell$ **do**

10: $(B_i, \tilde{\mathcal{O}}_i) \leftarrow$ an algebra $B_i \simeq B_{p,\infty}$ and a maximal order $\tilde{\mathcal{O}}_i \subset B_i$ such that $\tilde{\mathcal{O}}_i \simeq \text{End}(E/G_i)$. ▷ Using the oracle for $\text{MAXORDER}$ on $E/G_i$

11: $\mathcal{O}_i \leftarrow$ an order in $B$ isomorphic to $\text{End}(E/G_i)$ ▷ Proposition 2.2 on $(B, \mathcal{O})$ and $(B_i, \tilde{\mathcal{O}}_i)$.

12: $J_i \leftarrow I(\mathcal{O}, \mathcal{O}_i)$ the connecting ideal ▷ [11, Algorithm 3.5]

13: $\langle \alpha_1, \dots, \alpha_4 \rangle \leftarrow$ a Minkowski-reduced basis of $J_i$ ▷ [17]

14: **if** $\text{Nrd}(\alpha_2) \le \ell \text{Nrd}(J_i)$ **then**

15: $\alpha \leftarrow$ a non-scalar endomorphism of $E$ of degree at most $\ell^2$ ▷ For instance, by exhaustive enumeration of isogenies of degree at most $\ell^2$ from $E$.

16: **return** $\alpha$

17: $I_i \leftarrow J_i \tilde{\alpha}_1 / \text{Nrd}(J_i)$ ▷ The unique left $\mathcal{O}$-ideal of norm $\ell$ equivalent to $J_i$.

18: **return** $(B, \mathcal{O}, (I_i)_{i=0}^{\ell})$

Note that after Line 8, the rings $\text{End}(E/G_i)$ are pairwise non-isomorphic. Indeed, by [26, Lemma 42.4.1], if $\text{End}(E/G_i) \simeq \text{End}(E/G_j)$, then $E/G_i$ is isomorphic to either $E/G_j$ or to its Galois conjugate $(E/G_j)^{(p)}$, in which case the algorithm has terminated before Line 8. In particular, the codomains of all $\ell$-isogenies from $E$ have pairwise distinct endomorphism rings, hence left ideals of norm $\ell$ in $\mathcal{O}$ are uniquely identified by the isomorphism class of their right-order.

At each iteration of the for-loop, we consider two cases.

- If $\text{Nrd}(\alpha_2) \le \ell \text{Nrd}(J_i)$, by definition of Minkowski bases, we have that $\text{Nrd}(\alpha_1) \le \frac{\ell \text{Nrd}(J_i)}{\text{Nrd}(J_i) \mathcal{O}}$. As $J_i \tilde{J}_i = \text{Nrd}(J_i) \mathcal{O}$, the element $\alpha_1 \tilde{\alpha}_2 / \text{Nrd}(J_i)$ is in $\mathcal{O}$. Furthermore, $\alpha_1 \tilde{\alpha}_2 / \text{Nrd}(J_i)$ is not a scalar, otherwise $\alpha_1$ and $\alpha_2$ would be linearly dependent. Therefore $\mathcal{O}$ (hence also $\text{End}(E)$) contains a non-scalar element of norm

$$ \text{Nrd} \left( \frac{\alpha_1 \tilde{\alpha}_2}{\text{Nrd}(J_i)} \right) = \frac{\text{Nrd}(\alpha_1) \text{Nrd}(\alpha_2)}{\text{Nrd}(J_i)^2} \le \ell^2 $$
Then, a non-trivial endomorphism of degree at most $\ell^2$ can be found in time polynomial in $\log p$ and $\ell$ by exhaustive search.

- Otherwise, Nrd($\alpha_2$) > $\ell$ Nrd($J_i$). Let us prove that in that case, the ideal $I_i = J_i \bar{\alpha}_1 / \text{Nrd}(J_i)$ is the unique left $\mathcal{O}$-ideal of norm $\ell$ with $\mathcal{O}_R(I_i) \simeq \text{End}(E/G_i)$. Recall that by the Deuring correspondence, the lattice $\text{Hom}(E, E/G_i)$ (for the quadratic form deg) is isomorphic to $J_i$ (with quadratic form $q_{J_i} : \alpha \mapsto \text{Nrd}(\alpha)/\text{Nrd}(J_i)$). Therefore, there exists an element $\beta \in J_i$ such that $q_{J_i}(\beta) = \ell$. Since $q_{J_i}(\beta) < q_{J_i}(\alpha_2)$, the element $\beta$ must be a multiple of $\alpha_1$: there exists $m \in \mathbb{Z}$ such that $\beta = m\alpha_1$. Since

$$ \ell = q_{J_i}(\beta) = q_{J_i}(m\alpha_1) = m^2 q_{J_i}(\alpha_1) $$

and $\ell$ is prime, we must have that $m = 1$ and $q_{J_i}(\alpha_1) = \ell$. This implies that $\text{Nrd}(I_i) = \ell$.

The unicity of $I_i$ follows from the previously established fact that left ideals of norm $\ell$ in $\mathcal{O}$ are uniquely identified by the isomorphism class of their right-order.

The unicity of each $I_i$ proves that if Line 18 is reached, we indeed have $\mathcal{O}_R(I_i) \simeq \text{End}(E/G_j)$ if and only if $i = j$. $\square$

**Lemma 5.2.** Let $\rho : M_2(\mathbb{F}_\ell) \to M_2(\mathbb{F}_\ell)$ be a ring automorphism. If $\ker(m) = \ker(\rho(m))$ for all $m \in M_2(\mathbb{F}_\ell)$, then $\rho$ is the identity.

*Proof.* All automorphisms of $M_2(\mathbb{F}_\ell)$ are inner, so there exists $p \in \text{GL}_2(\mathbb{F}_\ell)$ such that $\rho(m) = p^{-1}mp$ for all $m \in M_2(\mathbb{F}_\ell)$.

First, suppose there exists a line $L \subset \mathbb{F}_\ell^2$ such that $p(L) \neq L$. Then, there exists $m \in M_2(\mathbb{F}_\ell)$ such that $m(L) = p(L)$ and $m(p(L)) = \{0\}$. We obtain

$$ \rho(m)(L) = (p^{-1}mp)(L) = p^{-1}(m(p(L)) = p^{-1}(\{0\}) = \{0\}. $$

By construction, $m$ cannot be invertible or the zero matrix; consequently, both $\ker(\rho(m))$ and $\ker(m)$ have dimension 1. Therefore $L = \ker(\rho(m)) = \ker(m) = p(L)$, a contradiction. We deduce that for any line $L \subset \mathbb{F}_\ell^2$, we have $p(L) = L$. Since $p$ fixes all lines in $\mathbb{F}_\ell^2$, all vectors of $\mathbb{F}_\ell^2$ are eigenvectors of $p$, so $p$ is a scalar matrix. In particular, $\rho(m) = p^{-1}mp = m$. $\square$

**Corollary 5.3.** Consider rings $R \simeq R' \simeq M_2(\mathbb{F}_\ell)$. Let $\iota_1, \iota_2 : R \to R'$ be two ring isomorphisms. If $\iota_1(I) = \iota_2(I)$ for all left-ideals $I$ in $R$, then $\iota_1 = \iota_2$.

*Proof.* Fix two isomorphisms $g : R' \to M_2(\mathbb{F}_\ell)$ and $f : M_2(\mathbb{F}_\ell) \to R$, and define

$$ \rho_i = g \circ \iota_i \circ f : M_2(\mathbb{F}_\ell) \to M_2(\mathbb{F}_\ell). $$

Let $\rho = \rho_2^{-1} \circ \rho_1$. Let us prove that $\rho$ satisfies the condition of Lemma 5.2. Let $m \in M_2(\mathbb{F}_\ell)$. Let $J = M_2(\mathbb{F}_\ell)m = \{\tilde{m} \in M_2(\mathbb{F}_\ell) | \ker(m) \subseteq \ker(\tilde{m})\}$ be the left-ideal generated by $m$. Then, its image $f(J)$ is a left-ideal in $R$, hence $\iota_1(f(J)) = \iota_2(f(J))$, and

$$ \rho(J) = f^{-1} \circ \iota_2^{-1} \circ \iota_1 \circ f(J) = f^{-1} \circ \iota_2^{-1} \circ \iota_2 \circ f(J) = J. $$
In particular, $\rho(m) \in \rho(J) = J$, so $\ker(m) \subseteq \ker(\rho(m))$. Since $\rho$ is an isomorphism, the matrices $m$ and $\rho(m)$ have the same rank, hence $\ker(m) = \ker(\rho(m))$.

We can thus apply Lemma 5.2, and deduce that $\rho$ is the identity.

In particular, we obtain $\rho_1 = \rho_2$, therefore $\iota_1 = \iota_2$.

□

**Algorithm 3** Computing an isomorphism between quaternions and endomorphisms modulo $\ell$, given a MAXORDER oracle

**Input:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, a prime $\ell$, an algebra $B \simeq B_{p,\infty}$, a maximal order $O \simeq \text{End}(E)$ in $B$, and access to an oracle for MAXORDER.

**Output:** Either an endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$, or an isomorphism $\lambda : O/\ell O \to \text{End}(E[\ell])$.

1: $(G_i)_{i=0}^{\ell} \leftarrow$ a list of all subgroups of order $\ell$ of the elliptic curve $E$.

2: Using the oracle access, run Algorithm 2 on the list $(G_i)_{i=0}^{\ell}$ to obtain either
   - a non trivial endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$,

- or a list $(I_i)_{i=0}^{\ell}$ such that $I_i$ is the unique left $O$-ideal of norm $\ell$ with $O_R(I_i) \simeq \text{End}(E/G_i)$.

3: **if** $\alpha \in \text{End}(E) \setminus \mathbb{Z}$ was found **then**

4: **return** $\alpha$

5: $g \leftarrow$ an isomorphism from $\text{End}(E[\ell])$ to $M_2(\mathbb{F}_\ell)$.

6: $f \leftarrow$ an isomorphism $O/\ell O$ to $M_2(\mathbb{F}_\ell)$.

7: $J_i \leftarrow \{\alpha \in \text{End}(E[\ell]) | G_i \subseteq \ker \alpha\}$, for $i \in \{0, \dots, \ell\}$.

8: $h \leftarrow$ an automorphism from $M_2(\mathbb{F}_\ell)$ to $M_2(\mathbb{F}_\ell)$ such that $h(f(\tilde{I}_i)) = g(J_i)$ where $\tilde{I}_i$ is the reduction of $I_i$ modulo $\ell$.

9: $\lambda \leftarrow g^{-1} \circ h \circ f : O/\ell O \to \text{End}(E[\ell])$.

10: **return** $\lambda$.

**Lemma 5.4.** *Algorithm 3 is correct and runs in time polynomial in the length of the input, in $\ell$, and in the length of the output of the oracle for MAXORDER.*

*Proof.* Let $\iota: O \xrightarrow{\sim} \text{End}(E)$ be an isomorphism. Let us prove that the isomorphism $\lambda$ computed by Algorithm 3 is its reduction modulo $\ell$, thereby also proving the correctness of this algorithm.

Since $I_i$ is the unique left $O$-ideal of norm $\ell$ with $O_R(I_i) \simeq \text{End}(E/G_i)$, we have that

$$ \iota(I_i) = \{\alpha \in \text{End}(E) | G_i \subseteq \ker(\alpha)\}. $$

Then, reduced modulo $\ell$, the equality becomes

$$ \iota_{\ell}(\tilde{I}_i) = J_i, $$

where $\tilde{I}_i$ is the reduction of $I_i$ modulo $\ell$. On the other hand, by construction, we have $\lambda(\tilde{I}_i) = J_i$. Thus, by Corollary 5.3, the isomorphism $\lambda_\ell$ is equal to the isomorphism $\lambda$.
Now, we demonstraste the complexity of the algorithm by giving the com-
plexity of its different steps. Obtaining the list of subgroup of order $\ell$ of the
elliptic curve $E$ can be done by computing a basis of the $\ell$-torsion of $E$. This
take a polynomial time in $\ell$ and in $\log p$.

One can define the isomorphisms $g, f$ and $h$ by mapping the basis of the
domain to a basis of the codomain such that the map verified the respective
required properties. Since there are $O(\ell^4)$ ordered bases of $M_2(\mathbb{F}_\ell)$, these con-
structions can be carried out using an exhaustive search.

Finally, by Lemma 5.1, running Algorithm 2 takes a polynomial time in
the length of the input, in $\ell$ and in the length of the output of the oracle for
MAXORDER. All the previously discussed complexities are encompassed within
this running time.
□

**Algorithm 4** Computing a non-scalar endomorphism, given a MAXORDER oracle

**Input:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$ and an access to an oracle for MAXORDER.

**Output:** An endomorphism $\theta \in \text{End}(E) \setminus \mathbb{Z}$.

1: $O \leftarrow$ a maximal order in a quaternion algebra such that $O \simeq \text{End}(E) \triangleright \text{Using MAXORDER oracle}$

2: $(\beta_i)_{i=1}^4 \leftarrow$ a Minkowski-reduced basis of $O \quad \triangleright [17]$

3: $\alpha \leftarrow \beta_2 \qquad \triangleright \alpha$ is a shortest non-scalar vector in $O$

4: $\ell \leftarrow 1, N \leftarrow 1$

5: **while** $N < \text{Nrd}(\alpha)$ **do**

6: $\ell \leftarrow$ the next prime after $\ell$ which is coprime to $N\text{rd}(\alpha)$

7: $N \leftarrow \ell N$

8: $(P_{\ell}, Q_{\ell}) \leftarrow$ a basis of the $\ell$-torsion $E[\ell] \quad \triangleright [1, \text{Lemma 6.9}]$

9: $\lambda_{\ell} \leftarrow$ the isomorphism $O/\ell O \simeq \text{End}(E[\ell]) \quad \triangleright \text{Using Algorithm 3}$

10: $(P'_{\ell}, Q'_{\ell}) \leftarrow (\lambda_{\ell}(P_{\ell}), \lambda_{\ell}(Q_{\ell}))$

11: $\theta \leftarrow \text{IsogenyInterpolation}((P_{\ell}, Q_{\ell})_{\ell}, (P'_{\ell}, Q'_{\ell})_{\ell}) \quad \triangleright \text{Proposition 2.4}$

**Proposition 5.5 (ONEEND reduces to MAXORDER).** *Algorithm 4 is correct and runs in probabilistic polynomial time in the length of the instance and in the length of the oracle's output.*

*Proof.* By the references cited in the comments, each step is at most polynomial in $\log p$, in the length of the MAXORDER oracle's output and in $\ell$ (whenever a prime $\ell$ is involved in the computation). Therefore, to prove the claimed complexity, it remains only to establish bounds on the number of iterations of the loop at line 5 and on the considered primes $\ell$.

By [27], a Minkowski-reduced basis of a lattice in dimension 4 reaches all
the successive minimas. Hence, Nrd($\alpha$) is the second minima of $O$, i.e. the first
minima of $O \setminus \mathbb{Z}$. Additionally, by Minkowski's second theorem, the product of
the successive minima of $O$ is smaller than $\gamma_4^2 \text{disc}(O)$, where $\gamma_4$ is the Hermite
constant in dimension 4. Thus we have that $\text{Nrd}(\alpha) \le 2p^2$. Therefore, by the
prime number theorem, the while loop at line 5 has $O(\log p)$ iterations and the
largest $\ell$ considered is $O(\log p)$, proving the claimed complexity.

The correctness of Algorithm 4 comes from the fact that we return the output
of **IsogenyInterpolation** called on input corresponding to the evaluation of
$\iota(\alpha)$ on the $N$-torsion subgroup $E[N]$ with $N > \text{Nrd}(\alpha)$, where $\iota$ is the Deuring
isomorphism. $\square$

# 6 Reductions to the Endomorphism Ring problem

We now turn to proving that **ISOGENY** and **MOER** reduce in polynomial time
to **ENDRING**, thereby completing the equivalence of all problems presented in
Figure 1. We shall proceed by proving the following sequence of reductions:

<figure><img src="image_4.png" /></figure>

The main difficulty in reducing the **ISOGENY** problem between two curves to
the **MAXORDER** problem lies in translating a connecting ideal between two max-
imal orders, which are isomorphic to the endomorphism ring of the curves, into
an isogeny between the curves. Before the break of SIDH [5,14,22], this process
required first finding a more suitable ideal, using KLPT-type algorithms [12],
which can be proven under GRH [28], and then computing the corresponding
isogeny using an elliptic curve with known endomorphism ring as a dictionary
between endomorphisms and quaternions. Thanks to Proposition 2.6, it is now
possible to directly compute the isogeny corresponding to the connecting ideal.
However, one still needs to known an elliptic curve with an explicit basis of its
endomorphism ring. This is why, instead of reducing **ISOGENY** to **MAXORDER**,
we reduce it to the **MOER** problem, ensuring access to such a curve.

**Proposition 6.1 (ISOGENY reduces to MOER).** *Given access to a MOER oracle, one can solve the ISOGENY problem in time polynomial in the length of its input and in the length of the oracle's output.*

*Proof.* Let $E_1$ and $E_2$ be two supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. For $i \in \{1,2\}$, a MOER oracle provides a maximal order $O_i$ in a quaternion algebra $B_i \simeq B_{p,\infty}$ together with an isomorphism $\varepsilon_i : O_i \xrightarrow{\simeq} \text{End}(E_i)$. By proposition 2.2, one can compute in polynomial time an isomorphism $\varepsilon : B_2 \xrightarrow{\simeq} B_1$. Then $O'_2 := \varepsilon(O_2)$ is a maximal order in $B_1$ isomorphic to $\text{End}(E_2)$. Using [11, Algorithm 3.5], one can compute efficiently the connecting ideal $I = I(O_1, O'_2)$.
Finally, by Proposition 2.6, one can compute the isogeny $\varphi_I : E_1 \to E_2$ in polynomial time. $\square$

We reduce MOER to `ENDRING` by adapting the strategy of [10, Algorithm 6]. The freedom to chose a model for $B_{p,\infty}$ in the definition of MOER allows us to eliminate all heuristics in the proof of [10, Algorithm 6]. We recall that, using Proposition 2.2, one can always translate a MOER solution into any target quaternion algebra where a maximal order is already known.

**Proposition 6.2 (MOER reduces to ENDRING).** *Given a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ together with a basis of its endomorphism ring End$(E)$, one can solve the MOER instance corresponding to the curve $E$ in time polynomial in $\log p$ and in the length of the elements in the provided basis of End$(E)$.*

*Proof.* Let $(\gamma_i)_{i=0}^4$ be a basis of the endomorphism ring of a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$. By [10, Lemma 4 and Lemma 5], one can compute, in time polynomial in $\log p$ and in $\log \max_{i=1}^4(\deg(\gamma_i))$, a rational invertible linear transformation $F$ sending $(\gamma)_{i=1}^4$ to some orthogonal basis $(1, \alpha, \beta, \alpha\beta)$. In particular, $(1, \alpha, \beta, \alpha\beta)$ is a basis of the endomorphism algebra $\text{End}(E) \otimes \mathbb{Q}$ such that $\alpha^2 < 0$, $\beta^2 < 0$ and $\alpha\beta = -\beta\alpha$. Hence, it is isomorphic to the quaternion algebra $B = (\frac{\alpha^2, \beta^2}{\mathbb{Q}})$, with basis $(1, i, j, ij)$ such that $i^2 = \alpha^2, j^2 = \beta^2$ and $ij = -ji$. Let $\varepsilon : \text{End}(E) \otimes \mathbb{Q} \stackrel{\sim}{\to} B$ be the explicit isomorphism sending $(1, \alpha, \beta, \alpha\beta)$ to $(1, i, j, ij)$. By applying $F^{-1}$ to $(1, i, j, ij)$ we get a maximal order $\mathcal{O} = \varepsilon((\gamma_i)_{i=1}^4)$ in $B$ isomorphic to $\text{End}(E)$. Finally, since $B$ is isomorphic to $\text{End}(E) \otimes \mathbb{Q}$, which is itself isomorphic to $B_{p,\infty}$, the solution we found satisfies all the conditions of the MOER problem. $\square$

# 7 Worst-case to Average-Case reductions

The goal of this section is to prove Theorem 1.2: there are worst-case to average-case reductions between all of the listed fundamental problems of isogeny-based cryptography. Recall that all of these problems take as input one or two elliptic curves, and the average case of these problems corresponds to random instances where the curves follow the stationary distribution (Definition 2.15).

To prove Theorem 1.2, we follow the network of reductions summarized in Figure 3. Once established, this network of reductions implies that `ONEEND` (in the worst-case) reduces to the average-case of any other problem. We then conclude from Theorem 1.1, which establishes that all problems reduce to `ONEEND`.

Note that since the stationary distribution is computationally indistinguishable from the uniform distribution (Remark 2.16), the reductions also apply to the “uniform” version of the average-case problems.

**The straightforward reductions.** In Figure 3, every non-labeled arrow denotes a “trivial” reduction. To be more precise, these reductions simply forward
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Summary of worst-case to average-case reductions. Each arrow represents a probabilistic polynomial time reduction. Let “AC” label means “average-case”. All reductions are one-to-one except for the thick arrow, which requires on average fewer than 3 oracle calls. Each arrow is proved in the associated reference. Arrows without reference are trivial reductions.</figcaption></figure>

an instance for a given problem to an instance for a (at least as hard) variant of this problem. In particular, the input of the average-case problems involved in those reductions always follows the same distribution. For example, the input distribution of the average-case ISOGENY problem is a pair of two elliptic curves following the stationary distribution which is also the input distribution of the average-case HOMMODULE. In addition, the solution we get for the harder problem directly includes a solution to the weaker one. For instance, solving the MOER problem also yields a solution to the corresponding ENDRING instance. Therefore, all these reductions are trivial, and we only need to prove the reductions from worst-case ONEEND to the average-case problems to complete the figure. We shall address each proof of these non-trivial reductions in a dedicated subsection.

## 7.1 The ONEEND problem reduces to the average-case ISOGENY problem

As there exist solutions of ISOGENY of arbitrarily large degree, we ease the analysis of the reduction by making a bound explicit, as in [19].
**Definition 7.1 (ISOGENY<sub>λ</sub>).** Let $\lambda : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ be a function. The ISOGENY<sub>λ</sub> problem is a variant of the ISOGENY problem where the solution $\varphi$ needs to verify that $\log(\deg(\varphi)) \le \lambda(\log p)$.

In [19], the authors have proven that one can solve the ONEEND problem in expected polynomial time in $\log(p)$ and $\lambda(\log p)$ by calling on average at most 3 times an ISOGENY<sub>λ</sub> oracle. In this section, we adapt this reduction [19, Algorithm 6] to ensure that it produces an semi average-case ISOGENY instance, in the sense that *at least one* of the elliptic curves involved follows a distribution indistinguishable from the stationary distribution. We then prove that the semi average-case ISOGENY<sub>λ</sub> reduces to the average-case ISOGENY<sub>λ</sub>, and deduce the claimed excepted polynomial time reduction from ONEEND to ISOGENY<sub>λ</sub>.

**Proposition 7.2.** Let $c_1, c_2 > 0$, and consider the following variant of [19, Algorithm 6] where

- the parameter $\varepsilon$ is smaller than $1/p$,

- the length of the non-backtracking random walks in the 3-isogeny graph is $n$, where $n$ satisfies $n \ge c_1 \log(p) - c_2 \log(\varepsilon)$.

There exist absolute computable constants $c_1$ and $c_2$ such that this algorithm computes an endomorphism in excepted polynomial time in $\log p$, $\lambda(\log p)$ and $n$ with at most 3 calls to an ISOGENY<sub>λ</sub> oracle. In addition, these calls are done on semi average-case instances.

*Proof.* For $p > 6$, the proof of [19, Theorem 8.6] still applies to this variant of [19, Algorithm 6] $\varepsilon < \frac{1}{6}$, as we can set $c_1$ and $c_2$ such that $n$ is larger than $[2 \log_3(p) - 4 \log_3(\varepsilon)]$, as needed. In particular, the algorithm computes an endomorphism in excepted polynomial time in $\log p$, $\lambda(\log p)$ and $n$ with at most 3 calls to an ISOGENY<sub>λ</sub> oracle.

We now prove the statement about the distribution of the instances given to the oracle. Let $E$ be the ONEEND instance (a supersingular elliptic curve over $\mathbb{F}_{p^2}$). Let us denote by $\mathcal{O}_{\text{ISOGENY}}$ the ISOGENY<sub>λ</sub> oracle we have access to. Following [19, Algorithm 6], a point $P \in E[2]$ is fixed, and each call to the oracle $\mathcal{O}_{\text{ISOGENY}}$ is done on an instance $(E'', E)$ where $E''$ is the codomain of the composition of isogenies $\nu \circ \varphi$ where $\varphi : E \to E'$ is a non-backtracking random walk in the 3-isogeny graph of length $n$ and $\nu : E' \to E''$ is an isogeny of kernel $\langle \varphi(S) \rangle$. As $\nu$ and $\varphi$ have coprime degree, the distribution of $E''$ is the same as the codomain of $\varphi' \circ \nu'$ where $\nu' : E \to E/\langle S \rangle$, and $\varphi' : E/\langle S \rangle \to E''$ is a non-backtracking random walk in the 3-isogeny graph of length $n$. By [2, Theorem 11], we can set $c_1$ and $c_2$ to ensure that for any $n \ge c_1 \log(p) - c_2 \log(\varepsilon)$, the distribution of $E''$ is an statistical distance at most $\varepsilon$ from the stationary distribution. In particular, each call to the oracle $\mathcal{O}_{\text{ISOGENY}}$ is done on semi average-case instances. $\square$

**Proposition 7.3 (ONEEND reduces to average-case ISOGENY).** Solving an instance of the worst-case ONEEND problem can be reduced in excepted polynomial time in $\log p$ and $\lambda(\log p)$ to solving 3 average instances of the ISOGENY<sub>λ</sub> problem.
*Proof.* First, we show that an *semi* average instance of *ISOGENY*<sub>λ<sub>c</sub></sub> reduces to an average instance of *ISOGENY*<sub>λ</sub>, where λ<sub>c</sub>(n) := λ(n) + 2cn + 1, with c the *O*-constant of Corollary 2.18. Note that c depends only on *p* and on some positive parameter ε, which we fix to be ε := 1/p. Let *E*<sub>0</sub> and *E*<sub>1</sub> be two supersingular elliptic curves defined over *F*<sub>*p*<sup>2</sup></sub> such that *E*<sub>1</sub> is sampled from the stationary distribution. By Corollary 2.18, one can compute a random walk η : *E*<sub>0</sub> → *E*<sub>2</sub> in the 2-isogeny graph of length ⌊τ(*p*, ε)⌋ such that the distribution followed by *E*<sub>2</sub> is at total variation distance at most ε to the stationary distribution. Then, as ε = 1/p, the two distributions are computationally indistinguishable.

Moreover, since $\tau(p, \varepsilon) = O(\log(p) - \log(\varepsilon))$ and $\varepsilon = 1/p$, we have that $[\tau(p, \varepsilon)] \le 2c \log(p) + 1$. Then, the random $2^{\lceil\tau(p, \varepsilon)\rceil}$-walk isogeny $\eta$ verifies that $\log(\deg(\eta)) \le 2c \log p + 1$.

A call to an *ISOGENY*<sub>λ</sub> oracle the pair (*E*<sub>2</sub>, *E*<sub>1</sub>), which is indistinguishable from an average-case instance, returns an isogeny φ : *E*<sub>2</sub> → *E*<sub>1</sub> such that log deg(φ) ≤ λ(log *p*). Then, the isogeny ψ := φ ○ η : *E*<sub>0</sub> → *E*<sub>1</sub> verifies that log(deg ψ) ≤ 2c log(*p*) + λ(log *p*) + 1 = λ<sub>c</sub>(log(*p*)). Thus the isogeny ψ is a solution to the initial *ISOGENY*<sub>λ<sub>c</sub></sub> problem corresponding to (*E*<sub>0</sub>, *E*<sub>1</sub>). This concludes the proof that an *semi* average instance of *ISOGENY*<sub>λ<sub>c</sub></sub> reduces to an average instance of *ISOGENY*<sub>λ</sub>.

We can now conclude the proof: by Proposition 7.2 and because $\lambda_c(\log p)$ is polynomial in $\lambda(\log p)$ and $\log p$, the ONEEND worst-case problem reduces in expected polynomial time in $\log(p)$ and $\lambda(\log(p))$ to 3 *semi* average instances of *ISOGENY*<sub>λ<sub>c</sub></sub>, which itself reduces to 3 average instances of *ISOGENY*<sub>λ</sub> in polynomial time as proven above. □

**7.2 The ONEEND problem reduces to the average-case ONEEND problem**

The reduction presented in this subsection is analogous to the most folkoric meth-
ods for self-reducing the *ISOGENY* problem from the worst-case to the average-
case, leveraging the rapid mixing properties of isogeny graphs.

**Proposition 7.4 (ONEEND reduces to average-case ONEEND).** *Solving an instance of the worst-case ONEEND problem can be reduced to solving an average-case instance of the ONEEND problem in time polynomial in log p and in the length of the average-case solution.*

*Proof.* Let $E$ be a supersingular elliptic curve defined over $\mathbb{F}_{p^2}$. Let $\eta: E \to E'$ be a random-walk in the 2-isogeny graph of length $n = \lceil \tau(p, 1/p) \rceil$, so that the distribution followed by $E'$ is asymptotically indistinguishable from the stationary distribution by Corollary 2.18. Then, from a solution $\theta: E' \to E'$ to the average-case ONEEND instance corresponding to the curve $E'$, one obtains a non trivial endomorphism $\hat{\eta} \circ \theta \circ \eta: E \to E$ which is a solution to the worst-case instance of ONEEND given by $E$. Indeed, this endomorphism is non trivial; otherwise there exists $n \in \mathbb{Z}$ such that $\hat{\eta} \circ \theta \circ \eta = n$ so $[\deg \eta] \circ \theta = n$, thus $\theta$ is a scalar endomorphism which is a contradiction. $\square$
## 7.3 The MOER problem reduces to the average-case MAXORDER problem

The main challenge in proving unconditional reductions to the MAXORDER problem lies in leveraging the information obtained from the quaternion world to aid in isogeny computation, without having an access to a dictionary between endomorphisms and quaternions. Indeed, we recall that when $p \equiv 1 \mod 8$, there is currently no known polynomial time algorithm free from GRH that can compute a supersingular elliptic curve defined over $\mathbb{F}_p$ together with an embedding of its endomorphism ring into some quaternion algebra isomorphic to $B_{p,\infty}$. In Section 5, we address this difficulty by "locally" computing this embedding for sufficiently many primes, allowing us to apply the recent IsogenyInterpolation algorithm. Unfortunately, this method requires solving the MAXORDER problem for elliptic curves which are close to each other in the some isogeny graph. Thus, it cannot be turned into a reduction to the average-case MAXORDER problem. For this reason, the reduction presented below requires the construction of a curve $E_0$ for which a solution of MOERis known. This requires either $p \not\equiv 1 \mod 8$, or to assume GRH.

**Proposition 7.5 (MOER reduces to average-case MAXORDER).** An instance of the worst-case MOER can be reduced to an average instance of the MAXORDER problem in polynomial time in the length of the input. If $p \equiv 1 \mod 8$, this result assumes GRH.

*Proof.* By [10, Proposition 3], one can compute in polynomial-time a curve $E_0$ together with a quaternionic order $O_0$ and an isomorphism $\varepsilon_0 : O_0 \stackrel{\sim}{\to} \mathrm{End}(E_0)$ (i.e., a solution to MOER). This result assumes GRH in the case where $p \equiv 1 \mod 8$. We denote by $B$ the quaternion algebra containing $O_0$.

Let $E$ be a supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. Let us solve the MOER problem for the elliptic curve $E$ calling once a MAXORDER oracle on an average elliptic curve $E'$.

Let $N = \prod_{i=1}^n \ell_i$, where $\ell_i$ is the $i$-th smallest prime number, Let $\eta : E \to E'$ be a random $N$-walk. By Corollary 2.18, by choosing $n$ such that $\log(N) \ge \tau(p, 1/p)$, one can ensure that $E'$ follows a distribution statistically indistinguishable from the stationary distribution. In particular, as $\tau(p, 1/p) = O(\log p)$, by the prime number theorem, it is sufficient to consider primes up to some $\ell_n = O(\log(p))$. Thus, the computation of $\eta$ takes a time polynomial in $\log p$.

Let us now solve the worst-case MOER instance corresponding to $E$ from a solution $O'$ to the average instance given by $E'$. Thanks to Proposition 2.2, one can assume that $O'$ is a maximal order in the quaternion algebra $B$.

First, we compute a connecting ideal $I$ between $O'$ and $O_0$, [11, Algorithm 3.5], and the corresponding isogeny using Proposition 2.6. By running [8, Algorithm 8], where the final division is done using Proposition 2.5, one obtains an isomorphism between $\mathrm{End}(E')$ and a maximal order $O'$ in polynomial time. Then by using [28, Lemma 7.1] on the isogeny $\hat{\eta}$, one can compute, in polynomial time in $\log p$, the corresponding left $O'$ ideal $I_{\hat{\eta}}$ such that $O'_R(I) = O$. Hence,
thanks again to [8, Algorithm 8], we obtain an explicit isomorphism between
End($E$) and a maximal order in $B$. $\square$

7.4 Proof of Theorem 1.2

We can now turn to the proof of the main theorem of this section.

*Proof (of Theorem 1.2).* Let $P$ and $Q$ be two problems chosen from the prob-
lems $\ell$-ISOGENYPATH, ISOGENY, ENDRING, ONEEND, MOER, MAXORDER,
MAXORDERQ, and HOMMODULE.

By Theorem 1.1, if $P$ is not $\ell$-ISOGENYPATH, we have a probabilistic poly-
nomial time reduction from $P$ in the worst-case to ONEEND in the worst-case.
Otherwise, assuming the generalised Riemann hypothesis, there is a probabilistic
polynomial time reduction from $\ell$-ISOGENYPATH in the worst-case to ONEEND
in the worst-case by [28] and [19]. Then using the results summarized in Fig-
ure 3, there is a probabilistic polynomial time reduction from ONEEND in the
worst-case to $Q$ in the average-case. $\square$

References

1. Bank, E., Camacho-Navarro, C., Eisenträger, K., Morrison, T., Park, J.: Cycles in the supersingular $l$-isogeny graph and corresponding endomorphisms. In: Bajkrishnan, J.S., Folsom, A., Lalín, M., Manes, M. (eds.) Research Directions in Number Theory. pp. 41–66. Springer International Publishing, Cham (2019)

2. Basso, A., Codogni, G., Connolly, D., De Feo, L., Fouotsa, T.B., Lido, G.M., Morrison, T., Panny, L., Patranabis, S., Wesolowski, B.: Supersingular curves you can trust. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, Part II. Lecture Notes in Computer Science, vol. 14005, pp. 405–437. Springer, Cham, Switzerland, Lyon, France (Apr 23–27, 2023). https://doi.org/10.1007/978-3-031-30617-4_14

3. Basso, A., Dartois, P., De Feo, L., Leroux, A., Maino, L., Pope, G., Robert, D., Wesolowski, B.: SQIsign2D-west - the fast, the small, and the safer. In: Chung, K.M., Sasaki, Y. (eds.) Advances in Cryptology – ASIACRYPT 2024, Part III. Lecture Notes in Computer Science, vol. 15486, pp. 339–370. Springer, Singapore, Singapore, Kolkata, India (Dec 9–13, 2024). https://doi.org/10.1007/978-981-96-0891-1_11

4. Buchmann, J., Pohst, M.: Computing a lattice basis from a system of generating vectors. In: Eurocal’87: European Conference on Computer Algebra Leipzig, GDR, June 2–5, 1987 Proceedings. pp. 54–63. Springer (1989)

5. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, Part V. Lecture Notes in Computer Science, vol. 14008, pp. 423–447. Springer, Cham, Switzerland, Lyon, France (Apr 23–27, 2023). https://doi.org/10.1007/978-3-031-30589-4_15

6. Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. Journal of Cryptology **22**(1), 93–113 (Jan 2009). https://doi.org/10.1007/s00145-007-9002-x
7. Csahók, T., Kutas, P., Montessinos, M., Zábrádi, G.: Explicit isomorphisms of quaternion algebras over quadratic global fields. Research in Number Theory 8(4), 77 (2022)

8. Dartois, P., Leroux, A., Robert, D., Wesolowski, B.: SQIsignHD: New dimensions in cryptography. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024, Part I. Lecture Notes in Computer Science, vol. 14651, pp. 3–32. Springer, Cham, Switzerland, Zurich, Switzerland (May 26–30, 2024). https://doi.org/10.1007/978-3-031-58716-0_1

9. De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.: SQISign: Compact post-quantum signatures from quaternions and isogenies. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology – ASIACRYPT 2020, Part I. Lecture Notes in Computer Science, vol. 12491, pp. 64–93. Springer, Cham, Switzerland, Daejeon, South Korea (Dec 7–11, 2020). https://doi.org/10.1007/978-3-030-64837-4_3

10. Eisenträger, K., Hallgren, S., Lauter, K.E., Morrison, T., Petit, C.: Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology – EUROCRYPT 2018, Part III. Lecture Notes in Computer Science, vol. 10822, pp. 329–368. Springer, Cham, Switzerland, Tel Aviv, Israel (Apr 29 – May 3, 2018). https://doi.org/10.1007/978-3-319-78372-7_11

11. Kirschmer, M., Voight, J.: Algorithmic Enumeration of Ideal Classes for Quaternion Orders. SIAM Journal on Computing 39(5), 1714–1747 (2010). https://doi.org/10.1137/080734467, https://doi.org/10.1137/080734467

12. Kohel, D., Lauter, K., Petit, C., Tignol, J.P.: On the quaternion-isogeny path problem. LMS Journal of Computation and Mathematics 17(A), 418–432 (2014)

13. Lagarias, J.C., Odlyzko, A.M.: Effective versions of the chebotarev density theorem. In: Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975). vol. 7, pp. 409–464 (1977)

14. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, Part V. Lecture Notes in Computer Science, vol. 14008, pp. 448–471. Springer, Cham, Switzerland, Lyon, France (Apr 23–27, 2023). https://doi.org/10.1007/978-3-031-30589-4_16

15. Mamah, M.: The supersingular isogeny path and endomorphism ring problems: Unconditional reductions. Cryptology ePrint Archive, Paper 2024/1569 (2024), https://eprint.iacr.org/2024/1569

16. Merdy, A.H.L., Wesolowski, B.: The supersingular endomorphism ring problem given one endomorphism. Cryptology ePrint Archive, Report 2023/1448 (2023), https://eprint.iacr.org/2023/1448

17. Nguyen, P.Q., Stehlé, D.: Low-dimensional lattice basis reduction revisited. ACM Transactions on algorithms (TALG) 5(4), 1–48 (2009), publisher: ACM New York, NY, USA

18. Page, A., Robert, D.: Introducing clapoti(s): Evaluating the isogeny class group action in polynomial time. Cryptology ePrint Archive, Report 2023/1766 (2023), https://eprint.iacr.org/2023/1766

19. Page, A., Wesolowski, B.: The supersingular endomorphism ring and one endomorphism problems are equivalent. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024, Part VI. Lecture Notes in Computer Science, vol. 14656, pp. 388–417. Springer, Cham, Switzerland, Zurich, Switzerland (May 26–30, 2024). https://doi.org/10.1007/978-3-031-58751-1_14
20. Pizer, A.: An algorithm for computing modular forms on $\Gamma_0(N)$. Journal of Algebra **64**(2), 340–390 (1980). https://doi.org/10.1016/0021-8693(80)90151-9, https://www.sciencedirect.com/science/article/pii/0021869380901519

21. Robert, D.: Some applications of higher dimensional isogenies to elliptic curves (overview of results). Cryptology ePrint Archive, Report 2022/1704 (2022), https://eprint.iacr.org/2022/1704

22. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, Part V. Lecture Notes in Computer Science, vol. 14008, pp. 472–503. Springer, Cham, Switzerland, Lyon, France (Apr 23–27, 2023). https://doi.org/10.1007/978-3-031-30589-4_17

23. Robert, D.: On the efficient representation of isogenies (a survey). Cryptology ePrint Archive, Report 2024/1071 (2024), https://eprint.iacr.org/2024/1071

24. Silverman, J.H.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106. Springer New York, New York, NY (2009). https://doi.org/10.1007/978-0-387-09494-6, http://link.springer.com/10.1007/978-0-387-09494-6

25. Voight, J.: Identifying the Matrix Ring: Algorithms for Quaternion Algebras and Quadratic Forms. In: Alladi, K., Bhargava, M., Savitt, D., Tiep, P.H. (eds.) Quadratic and Higher Degree Forms, pp. 255–298. Springer New York, New York, NY (2013). https://doi.org/10.1007/978-1-4614-7488-3_10, https://doi.org/10.1007/978-1-4614-7488-3_10

26. Voight, J.: Quaternion Algebras, Graduate Texts in Mathematics, vol. 288. Springer International Publishing, Cham (2021). https://doi.org/10.1007/978-3-030-56694-4, https://link.springer.com/10.1007/978-3-030-56694-4

27. van der Waerden, B.L.: Die Reduktionstheorie der positiven quadratischen Formen. Acta Mathematica **96**(1), 265–309 (1956), publisher: Kluwer Academic Publishers Dordrecht

28. Wesolowski, B.: The supersingular isogeny path and endomorphism ring problems are equivalent. In: 62nd Annual Symposium on Foundations of Computer Science. pp. 1100–1111. IEEE Computer Society Press, Denver, CO, USA (Feb 7–10, 2022). https://doi.org/10.1109/F0CS52979.2021.00109

29. Wesolowski, B.: Random Walks in Number-theoretic Cryptology. HDR Thesis, ENS Lyon (2024), https://bweso.com/hdr.pdf