APPENDIX C. IDEAL TO ISOGENY ALGORITHMS IN THE SUPERSINGULAR CASE AND APPLICATIONS TO THE SQISIGN FAMILY

In this section we give more details on the ideal to isogeny algorithms in the supersingular case. Among its many cryptographic applications, we can mention the SQIsign family of signature scheme, which we describe in Appendix C.6.

C.1. **Double paths.** In Section 4.2, we gave an overview of different algorithms to convert an ideal $I$ to an isogeny $\phi_I : E_1 \to E_2$, assuming that we know an efficient representation of the endomorphism ring $\text{End}(E_1)$ of $E_1$.

Actually, what we explained is only how to convert an equivalent ideal $J$ into an isogeny $\phi_J : E_1 \to E_2$; where $J$ is a smoothening of $I$ in the first generations, and simply the smallest equivalent ideal in the fourth generation.

There remains two questions: how do we compute $\phi_I$ once we know how to compute $\phi_J$? And how can we compute an efficient representation of $\text{End}(E_2)$, which would be needed if we want to convert a new ideal $I_2$ from $E_2$?

For the first question, since we know $I$ and $J$, we know the endomorphism $\alpha = \tilde{\phi}_J \circ \phi_I$; in terms of ideal this is a generator of the principal ideal $\mathfrak{J}I$. Furthermore, by assumption we know how to evaluate it on $E_1$. And if $P \in E_1$, we have $\phi_I(\alpha(P)) = N(J)\phi_I(P)$. We can thus recover the image of $P$ by $\phi_I$ up to the factor $N(J)$. This at least allow us to evaluate $\phi_I$ on all points $P$ of torsion prime to $N(J)$. We have seen in Proposition 6.6 that we have a division algorithm which allows to evaluate $\phi_I$ efficiently when we know how to evaluate $N(J)\phi_I$ efficiently.

Another solution is to simply compute another “nice” ideal $J'$ equivalent to $I$, of norm prime to $N(J)$. In other words: we build a *double path* of isogenies $\phi_J, \phi_{J'} : E_1 \to E_2$ where both isogenies have an efficient representation and are of coprime degrees. In fact, the Clapotis algorithm used in the fourth generation already directly constructs a double path. From this double path, we can translate any other ideal $I$ into an isogeny $\phi_I$ efficiently, by evaluating a suitable endomorphism on $E_1$ first and then applying $\phi_J$ or $\phi_{J'}$.

The same solution works to evaluate endomorphisms on $E_2$. First we know that abstractly $\text{End}(E_2)$ is the right order of $I$. Next, given $\beta \in \text{End}(E_2)$, we can consider the endomorphism $\alpha = \tilde{\phi}_J \circ \beta \circ \phi_I$, which we know how to evaluate efficiently on $E_1$ by assumption. Since we know an efficient representation of $\phi_J$, then by Proposition 6.4 we can build an efficient representation of $\tilde{\phi}_J$. But in fact, in our setting, when $J$ is taken to be a smoothening of $I$, then it decomposes as a product of small degree isogenies so it is easy to compute its dual directly; and in the fourth generation where we use the Clapotis algorithm to embed a double path $\phi_{J_1}, \phi_{J_2} : E_1 \to E_2$ into a smooth HD isogeny $\Phi$, then $\Phi$ is also decomposed into a product of small HD isogenies; hence we can also directly compute $\tilde{\Phi}$, and so $\tilde{\phi}_{J_1}, \tilde{\phi}_{J_2}$ too. In any case we can compute $\phi_J \circ \alpha \circ \tilde{\phi}_J(Q) = N(J)^2\beta(Q)$, hence recover $\beta(Q)$ at points of order prime to $N(J)$. The general case to evaluate $\beta$ proceed by division or via a double path like for $\phi_I$ above.

In fact, it is often more practical to build everything from a special nice curve $E_0$, with particularly nice endomorphism evaluation (typically $E_0$ will be a supersingular curve defined over $\mathbb{F}_p$ and with small discriminant). Assume that we have built a isogenies $\phi_{J_1} : E_0 \to E_1$ and $\phi_{J_2} : E_0 \to E_2$ represented by ideals $J_1, J_2$. Then if $P \in E_1$, we have $N(J_1J_2)\phi_I(P) = \phi_{J_2} \circ \theta \circ \tilde{\phi}_{J_1}$, where $\theta = \tilde{\phi}_{J_2} \circ \phi_I \circ \phi_{J_1}$ is an endomorphism on $E_0$. This allows to evaluate any isogeny $\phi_I$ on points of order coprime to $N(J_1J_2)$. The same technique holds to evaluate endomorphisms on $E_1$ and $E_2$ at points of order coprime to $N(J_1)$ and $N(J_2)$ respectively. We can then invoke the division algorithm for the general case. Or, simpler, we only need
to compute a double “double path”, i.e. an efficient double path $\phi_{J_1}, \phi_{J'_1}$ between $E_0$ and $E_1$, and another $\phi_{J_2}, \phi_{J'_2}$ between $E_0$ and $E_2$ (with $N(J_1J_2)$ coprime to $N(J'_1J'_2)$).

### C.2. The KLPT algorithm and Eichler orders.

#### C.2.1. KLPT.
The first generation of an ideal to isogeny algorithm is the KLPT smoothening algorithm from [KLPT14]. The idea is to find an ideal $J$ equivalent to $I$, but of smooth norm.

If $J$ is equivalent to $I$, $\phi_I, \phi_J$ are both isogenies from $E_1$ to $E_2$, so $\tilde{\phi}_J \circ \phi_I$ is an endomorphism $\alpha \in \text{End}(E_1)$, which is in $I$ because the endomorphisms factorizes through $\phi_I$ by construction. It follows that $J = I \frac{\bar{\alpha}}{N(I)}$, which is of norm $N(\alpha)/N(I)$. So the goal is to find $\alpha \in I$ such that $N(\alpha)/N(I)$ is of smooth norm.

The KLPT algorithm shows that, if $\text{End}(E_1)$ is a special quadratic order (called special extremal order), it is heuristically always possible to find (in polynomial time!) $\alpha \in I$ such that $N(\alpha)/N(I) = N$ for any $N$ large enough: $N \gg p^3$. A proven algorithm (under GRH) was given in [Wes22], for $N = p^C$ but with no explicit bound on $C$. An example of a special extremal order is the elliptic curve $E_0: y^2 = x^3 - x$ when $p \equiv 3 \mod 4$, whose endomorphism ring contains $\mathbb{Z}[i]$.

For the general case where $E_1$ is not special extremal, one can instead build a smooth connecting ideal $J_1$ between $E_0$ and $E_1$, and another $J_2$ between $E_0$ and $E_2$. Then $J = J_2\bar{J}_1$ is a smooth connecting ideal between $E_1$ and $E_2$. But we can only expect to find such a $J$ of norm $N \gg p^6$, because $N(J_i) \gg p^3$.

Taking $N$ powersmooth, this gives an algorithm which is efficient in theory, but not in practice (but see [EPSV] for several tricks). Indeed, the size of $N$ means that we cannot expect to find rational $N$-torsion, we need to take field extensions.

#### C.2.2. Eichler orders.
The first practical algorithm to convert an arbitrary ideal to an isogeny was given in [DKLPW20]: using the theory of Eichler order, it is proven that one can (heuristically) always find a smooth ideal $J$ connecting $E_1$ and $E_2$ of norm $N \gg p^{4.5}$. More precisely, let $I_0$ be an ideal connecting $E_0$ to $E_1$. Then one can (heuristically) find an ideal $J$ equivalent to $I$ and of norm $N$ as long as $N \gg p^{1.5}N(I)^3N(I_0)^3$. By Minkowski's bound, the (reduced) norm of the smallest ideal connecting two supersingular curves is in $O(\sqrt{p})$. Replacing $I$ and $I_0$ by small equivalent ideals, we obtain the $p^{4.5}$ bound mentioned above. And the closer $E_1$ is to $E_0$ (compared to a uniform supersingular curve), the better the bound, up to $p^3$ when $E_1 = E_0$.

Let us quickly explain how Eichler orders are used. Let $E_0$ be a special extremal curve, and $I_0$ the ideal connecting $E_0$ to $E_1$, and assume that it is coprime to $I$ for simplicity. Let $I' = I_0^*I$ be the pullback ideal of $I$ (in term of isogeny this corresponds to the isogeny $\phi_I: E_1 \to E_2$ pullbacked to $\phi_{I'}: E_0 \to E_0'$ via $\phi_{I_0}: E_0 \to E_1$). Since $E_0$ is special extremal, by KLPT we can find a nice equivalent ideal $J'$ to $I'$ of norm $N$ for $N \approx p^3$. We thus have two isogenies: $\phi_{I'}, \phi_{J'}: E_0 \to E'$. But while $\phi_I: E_1 \to E_2$ is the pushforward of $\phi_{I'}$ to $E_1$, the pushforward $\phi_J$ of $\phi_{J'}$ to $E_1$ may give an isogeny $E_1 \to E_2'$ with a different codomain than $E_2$!

Let $K = E_0[I_0]$ be the kernel of $\phi_{I_0}: E_0 \to E_1$. We have an endomorphism $\alpha = \tilde{\phi}_{J'} \circ \phi_{I'}$, and in term of ideals $J' = I'\bar{\alpha}/N(I')$. One can show that the codomain of $\phi_J$ is still the same $E_2$ if and only if $\alpha(K) = K$ [Ler22b, Proposition 2.3.11]. Thus, for the above construction to work, $J'$ cannot be taken to be any ideal equivalent to $I'$, it has to come from some $\alpha$ such that $\alpha(K) = K$.

The endomorphisms of $E_0$ such that $\alpha(K) = K$ form precisely the Eichler order $O = O_0 \cap O_1$ where $O_0 = \text{End}(E_0)$ and $O_1 = \text{End}(E_1)$. We refer to [Ler22b; Arp22] for more details on Eichler order and their relationship with kernel of isogenies.
Thus the KLPT algorithm has to be adapted to sample elements $\alpha$ that are in the Eichler order $O$, in order for the pushfoward strategy to work. We refer to [Ler22b; DKLPW20] for these algorithms, which give the bound described above.

**C.3. Ideal to isogeny: splitting a large dimension one $2^e$-isogeny.** For practical instance of KLPT, we would like to:

(1) Use smooth ideals with a very small smoothness bound, ideally take $N = 2^e$

(2) Work over $\mathbb{F}_{p^2}$ and avoid taking any field extension.

Unfortunately, this cannot happen because, even with a carefully chosen $p$, $E(\mathbb{F}_{p^2}) = (\mathbb{Z}/(p \pm 1)\mathbb{Z})^2$ can fit at most the $2^f$ torsion with $2^f \mid p \pm 1$. While the KLPT algorithm (the improved version with Eichler orders) can only generate $2^e$-isogenies with $2^e \approx p^{4.5}$.

**C.3.1. Using $E_0$ to refresh the torsion.** As mentioned in Section 4.2, the first SQIsign paper [DKLPW20] introduced the idea of splitting the large $2^e$-isogeny into chunks of $2^f$-isogenies. First, select a $p$ with large available rational (over $\mathbb{F}_{p^2}$) $2^f$-torsion, and search for $J$ equivalent to $I$ of norm $2^e$, $2^e \approx p^{15/4}$ (this is better than the bound of $p^{4.5}$ above, because in the context of SQIsign $E_1$ is only at distance $p^{1/4}$ from $E_0$ and $p^3p^{3/4} = p^{15/4} = p^{3.75}$).

If we split the isogeny $\phi_I$ into chunks of $2^f$-isogenies, then $J_1 = J + (2^f)$ is the ideal corresponding to the first chunk: $\phi_{J_1}: E_1 \to E_{1,1}$. Let $J' = J_{1,*}J$ the pushforward of $J$ by $J_1$, we now need to split $J'$ into chunks to evaluate the next step $\phi_{J_2}: E_{1,1} \to E_{1,2}$ from $E_{1,1}$, where $J_2 = J' + (2^f)$. The problem is that to compute the next kernel, $E_{1,1}[J_2] = E_{1,1}[2^f, J']$, we need to evaluate $J'$ on the $2^f$-torsion, and we cannot go back to $E_1$ because $J_1$ is of reduced norm $2^f$, so we have “consumed” all our available torsion when we evaluated $\phi_{J_1}$.

We need to “refresh” the $2^f$-torsion on $E_{1,1}$. The solution in SQIsign is to build a $T$-isogeny $\phi_T: E_0 \to E_{1,1}$ with $T$ smooth and odd. We can then use this isogeny from $E_0$ to evaluate the action of $J'$ on the $2^f$-torsion of $E_{1,1}$, since it is of degree coprime to $2^f$. Since $E_0$ is special extremal we can build an isogeny $\phi_T$ as long as $T \gg p^3$. This is still bigger than the available torsion, but we are saved by two things.

The first one, is that in that case we already know the codomain $E_{1,1}$, we don't need to construct it. This means that we can split $\phi_T$ in two: write $T = T_1T_2$, $\phi_T$ as $\phi_{T_2} \circ \phi_{T_1}: E_0 \to E' \to E_{1,1}$ for some random intermediate curve $E'$. We can compute $\phi_{T_1}$ from its kernel in $E_0[T_1]$, and $\widetilde{\phi}_{T_2}$ from its kernel in $E_{1,1}[T_2]$. In that case, since $T_2$ is odd we can use $\phi_{J_1}$ to go back to $E_1$ to evaluate suitable endomorphisms on $E_{1,1}[T_2]$ to obtain Ker $\widetilde{\phi}_{T_2}$ (in practice, by also using a suitable isogeny connecting $E_0$ to $E_1$). We then just need to glue things in the middle at $E'$. This trick of splitting an isogeny in two, when both the domain and codomain are already known is very useful, and allows to get a square factor in the amount of effective available torsion (see Appendix B for the same trick for the HD representation).

So we can expect $T_1, T_2$ to be of size roughly $p^{3/2}$, which is still bigger than $p$. The next trick is to work both with the curves $E_0, E_{1,1}$ and their quadratic twists. This allows to have both the $p-1$-torsion and the $p+1$-torsion available, while still working over $\mathbb{F}_{p^2}$ (the only condition is to not use them at the same time, which would involve working over the quadratic extension $\mathbb{F}_{p^4}$).

**Example C.1.** In the original SQIsign, one use available $2^f$-torsion with $2^f \approx p^{1/8}$ (so that the response is split into $\approx 30$ blocks of $2^f$-isogenies), and $T_1^2$-torsion (i.e., $T_2 = T_1$) with $T_1 \approx p^{3/2}$, split into one part dividing $p-1$ and the other part dividing $p+1$. There remain
approximatively $\approx p^{1/4}$ available torsion not used, because it is very hard to find such smooth primes with smoothness conditions both on $p-1$ and $p+1$ already, see [BSC+23].

For a security parameter $\lambda$, $p$ has size $2\lambda$, and the signature has size around $23/2 \cdot \lambda$.

**C.3.2. Using an endomorphism to refresh the torsion.** In [DLLW23], a novel idea is to use an endomorphism $\gamma$ of reduced norm $T$ on $E_{1,1}$ instead to refresh the $2^f$-torsion. This endomorphism $\gamma$ (which need to satisfy some technical conditions) can be evaluated from the $2^f$-isogeny $\phi_{J_1} : E_1 \to E_{1,1}$ because $T$ is odd. The advantage compared to building a $T$-isogeny $E_0 \to E_{1,1}$ is that one can find a suitable endomorphism $\gamma$ of smooth norm $T$ for $T \approx p^{2.5}$, compared to $p^3$ for the isogeny; splitting it in two we only need accessible torsion of size $\approx p^{1.25}$ compared to $\approx p^{1.5}$. This leaves more room for the rest of the torsion, makes it easier to find good primes $p$, and allows to increase the available $2^f$-torsion.

We briefly explain how the algorithm works. The idea is that we know the kernel $K_1$ of the contragredient isogeny $E_{1,1} \to E_1$, it is given by $\phi_{J_1}(E_1[2^f])$. What we want is to find the kernel $K = E_{1,1}[J_2]$ of the next isogeny $E_{1,1} \to E_{1,2}$. If we can find an effective representation of any endomorphism $\gamma \in \text{End}(E_{1,1})$ such that $\gamma(K_1) \cap K_1 = 0$ (this condition can be translated into the fact that $\gamma$ should not be in some Eichler order), then by linear algebra we can find an endomorphism $\gamma' = a\gamma + b$ such that $\gamma'(K_1) = K$. Evaluating $\gamma$ on $K_1$ thus allow us to find our next kernel $K$.

**Example C.2.** For SQIsign, using an endomorphism rather than an isogeny from $E_0$ drops the requirement on the smooth accessible torsion $T$ from $T \approx p^{3/2}$ to $T \approx p^{5/4}$. The relaxed torsion requirement makes finding suitable $p$ easier and improves the signing time by enabling the use of primes $p$ with $2^f \approx p^{1/4}$ accessible torsion, which increases the size of each block of $2^f$-isogenies and reduces the number of steps to $\approx 15$. Furthermore, the signature is compressed further and has size around $17/2 \cdot \lambda$. See Appendix C.6.1 for more details.

**C.3.3. Using an endomorphism represented by a dimension 2 isogeny.** In [Ler23b], using tools from [CLP24], Leroux introduces the first version of an ideal to isogeny algorithm using the newer HD representation. Namely, rather than searching for $\gamma$ of smooth norm in order to be able to evaluate it efficiently, he uses a dimension two $2^f$-representation of $\gamma$. As we have seen in Section 5, an HD representation allows to efficiently represent any $\gamma$ of odd norm $T < 2^f$ (even non smooth), as long as we know how $\gamma$ acts on the $2^f$ torsion. In fact, by the same splitting trick as above, we can work up to $\gamma$ of norm $T < 2^{2f}$. Since we need to be able to evaluate $\gamma$ on the $2^f$-torsion to obtain this representation, the only change is that $J$ is taken to be a $3^h$-isogeny rather than a $2^e$-isogeny as previously, and it is split into chunks of $3^g$-isogenies rather than chunks of $2^f$-isogeny. For instance, one can take $p = 2^f 3^g u - 1$ for a small cofactor $u$. Since we relax the smoothness bound on $\gamma$, one can find a suitable endomorphism $\gamma$ of reduced norm $T \approx p^{2/3}$. We thus only require $2^f \approx p^{1/3}$ to represent $\gamma$, leaving ample room for the chunks of $3^g$-isogenies.

Rather than computing chunks of $3^g$-isogenies in dimension 1, and using $T$-endomorphisms embedded in $2^f$-isogenies in dimension 2, we could reverse the role of 2 and 3, but going from 2-isogenies to 3-isogenies is less expensive in dimension 1 than dimension 2.

**C.3.4. Using an HD representation for isogenies from $E_0$.** A recent alternative, in [ON24], is to go back to the original SQIsign protocol, using isogenies from $E_0$ rather than endomorphisms, but like in [Ler23b] to use an HD representation to relax the smoothness requirement on these isogenies, as was pioneered in SQIsignHD [DLRW24]. In that version, one take $p = 2^f u - 1$
for a small cofactor $u$, so that the full $2^f \approx p$ is available, and we write $f = f_1 + f_2$. The isogeny $\phi_I$ is split into chunks of $2^{f_1}$-isogenies, and the refreshing isogenies $\phi_T : E_0 \to E_{1,1}$ of degree $T$ are represented by an HD $2^{f_2}$-representation, which requires to be able to evaluate $\phi_T$ on the $2^{f_2}$-torsion.

Using a previously built isogeny $\phi'_T : E_0 \to E_1$, and the isogeny $\phi_{J_1} : E_1 \to E_{1,1}$, we can indeed recover the action of $\phi_T$ on the $2^{f_2}$-torsion: $\phi_{J_1}$ is a $2^{f_1}$-isogeny, so only consumes $2^{f_1}$ out of our available $2^{f_1+f_2}$-torsion!

One can use a dimension 4 HD representation, like in SQIsignHD. This allows to split $\phi_T$ in two and allows to use any $T$ such that $T < 2^{2f_2}$. Or we can use the fact that $E_0$ contains $\mathbb{Z}[i]$ to build a dimension two representation, which will be more efficient that the dimension four representation (see Remark 5.17); but we cannot split in two in this case, so we need $T < 2^{f_2}$. We already mentioned that Minkowski's bound show that we can always find an isogeny $\phi_T : E_0 \to E_{1,1}$ of (non smooth) norm $T$ for $T = O(\sqrt{p})$. So even the dimension 2 representation leaves ample room to split $\phi_I$ into chunks of $2^{f_1}$-isogenies.

**C.4. The Clapotis algorithm.** Another recent alternative is given in [BDD+24], inspired by the Clapoti(s) algorithm from [PR23b], see Example 6.13. It allows to directly convert any isogeny $\phi_I : E_1 \to E_2$ in one go by using a dimension 4 HD-representation embedding at the same time two isogenies $\phi_{J_1}, \phi_{J_2} : E_1 \to E_2$, with $N(J_1)$ coprime to $N(J_2)$. In other words this algorithm builds a double path from $E_1$ to $E_2$ in one go by using a dimension 4 $2^e$-isogeny. The constraint on torsion is $2^e \approx N(J_1)N(J_2)$, and taking small equivalent ideals $J_1, J_2 \sim I$ we can have $N(J_1)N(J_2) \approx p$, which is barely enough to fit into the available $2^f$-torsion (we cannot split in two in that case because we don't know $E_2$ yet). Then $\phi_I$ can be recovered from this double path and the effective endomorphism representation $\text{End}(E_1)$ on $E_1$.

In practice, it is better, as explained in [BDD+24], to build a double path between $E_0$ and $E_1$, and another between $E_0$ and $E_2$. Because $\text{End}(E_0)$ contains $\mathbb{Z}[i]$, which gives a lot of small endomorphisms, this allows to find a dimension 2 representation of the double paths (again, see Remark 5.17). This replaces the need to compute one dimension 4 isogeny by two dimension 2 isogeny, which is much faster in practice.

Of course, the parameters given in the discussions above, like splitting a big $2^e$-isogeny into chunks of $2^f$-isogeny, or using HD representations to embed $T$-isogenies into higher dimensional $2^f$-isogeny could be generalised to any $B \mid B'$ with $B, B'$ smooth (in our examples, $B = 2^f$ and $B' = 2^e$). This replaces the constraint of having accessible $2^f$-torsion to having accessible $B$-torsion. But $2^e$-isogenies are the one we prefer to use in practice, because they are the most convenient, especially in higher dimension. When we have the choice of the prime $p$, so when building protocols, we might as well choose $p$ to have large accessible $2^f$-torsion.

**C.5. Improving KLPT?** From the diameter of the supersingular $\ell$-isogeny graph, we know that there exist isogenies of norm $\ell^e \approx p$ between any two elliptic curves $E_1, E_2$. But currently the KLPT algorithm, even using the improved variant via Eichler orders, can only generate isogenies of norm $\ell^e \approx p^{4.5}$ for generic elliptic curves (for SQIsign the parameters allow to reach $\ell^e \approx p^{15/4}$). This is too big to fit into the available $2^f$-rational torsion, even taking $p = u2^f - 1$ a pseudo-Mersenne prime. So for the SQIsign signature, this large $2^e$-isogeny has to be split into chunks of $2^f$-isogenies as we have seen. And even for the verification,
taking $f$ as large as possible like in AprèsSQI [CEMR24] (which impacts the signature time), the verifier still has to compute several $2^f$-isogenies in dimension 1 with $2^f \approx p$.

By contrast, the Clapotis algorithm can directly convert the smallest ideal between $E_1$ and $E_2$, which is of norm $\approx \sqrt{p}$ (or less) by Minkowski's theorem, and this ideal can be efficiently found by the LLL algorithm. Hence the ideal can be converted into an isogeny in one step, which drastically speeds up the signature; and the verification only needs a $2^e$-isogeny in dimension 2 with $2^e \approx \sqrt{p}$. From the current state of the art, it seems that computing this smaller $2^e \approx \sqrt{p}$-isogeny for verification in dimension 2 is faster than computing a degree $2^e \approx p^{15/4}$ isogeny in dimension 1. Still, [CEMR24] gives several tricks using uncompressed signatures and hints to speed up verification in dimension 1, so SQIsign might still stay competitive with SQIsign2d for verification, thanks to AprèsSQI (but in any case the signature will be much faster in SQIsign2d, see Appendix C.6).

However, being able to generate directly an equivalent smooth ideal $J$ of norm $2^e \approx p$ would be enough to fit into the available $2^f$-torsion, and allow to convert it into an isogeny in one step, as is also currently done in the fourth generation, all the while staying in dimension 1 rather than going in dimension 2. The verification would also be faster: since we expect a factor $\approx \times 4$ (at least) slowdown between dimension 1 and 2 as explained in Section 5.1, we expect an isogeny of dimension 1 of norm $\approx p$ to be at least twice as fast to compute as a $\approx \sqrt{p}$-isogeny in dimension 2.

**C.6. The SQIsign family.** We conclude this section by comparing different versions of SQIsign (which use different generations of an ideal to isogeny algorithm), along with their concrete instantiation for NIST level 1 (which means that the security parameter is $\lambda = 128$ bits). In all cases, for a security parameter $\lambda$, we work with supersingular curves over $\mathbb{F}_{p^2}$ with $p$ of size $2\lambda$.

We recall the general structure of the SQIsign identification protocol: the Prover wants to prove the knowledge of a secret isogeny $\varphi_{sk} : E_0 \to E_{pk}$; where only the codomain $E_{pk}$ is public. He computes a secret commitment isogeny $\varphi_{com} : E_0 \to E_{com}$, and publishes $E_{com}$. The verifier challenges by an isogeny $\varphi_{chl} : E_{pk} \to E_{chl}$. The prover responds by an isogeny $\varphi_{rsp} : E_{chl} \to E_{com}$ connecting the challenge curve to the commitment curve. See for instance [BDD+24] for more details.

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

C.6.1. SQIsign. This is the version in [DKLPW20] with the improvements of [DLLW23]. This version uses dimension 1 both for the signature and the verification, and the signature takes $\approx 17/2 \cdot \lambda$ bits. The verification is reasonably fast but the signature is very slow, and is very hard to implement in constant time due to the many operations on the quaternion side required. Furthermore the security assumptions rely on many ad-hoc heuristics.

The public key is given by an isogeny of degree $\approx p^{1/4}$, which is not enough to reach the whole supersingular keyspace (this would require a degree $\approx p^{1/2}$). In particular, it is not statically uniform (a provable bound to reach the uniform distribution up to $2^{-\lambda}$ would even require a degree $\approx p^2$). The commitment is a smooth isogeny of degree $\approx p$. The response
is an isogeny of degree $2^e \approx p^{3.75}$ which is split into 15 isogenies of degree $2^f \approx \sqrt{p}$. The torsion is refreshed using 15 endomorphisms of smooth degree $T \approx p^{5/4}$.

For the NIST submission, at level 1, we have $p$ with accessible $2^f$-torsion and $T$-torsion with $f = 75$ and $T = 3^{36} \cdot 7^4 \cdot 11 \cdot 13 \cdot 23^2 \cdot 37 \cdot 59^2 \cdot 89 \cdot 97 \cdot 101^2 \cdot 107 \cdot 109^2 \cdot 131 \cdot 137 \cdot 197^2 \cdot 223 \cdot 239 \cdot 383 \cdot 389 \cdot 491^2 \cdot 499 \cdot 607 \cdot 743^2 \cdot 1033 \cdot 1049 \cdot 1193 \cdot 1913^2 \cdot 1973$. The commitment is of degree $T/3^g$ ($g = 36$), and the challenge is of degree $2^f 3^g$. The available $2^f$ torsion is enough to split the response in 14 rather than 15, so the signature needs to compute 14 $2^f$-isogenies and 13 endomorphisms of degree $T$. The verification needs to compute the challenge again along with the 14 $2^f$-isogenies in dimension 1. The signature takes 177 Bytes.

### C.6.2. SQIsignHD.
This is the version in [DLRW24], which actually describes two variants.

**FastSQIsignHD:** this version uses dimension 1 for the signature and dimension 4 for the verification, and the signature takes $\approx 13/2 \cdot \lambda$ bits. The prime $p$ is a SIDH prime of the form $p = 2^f 3^g - 1$, with $2^f \approx 3^g \approx \sqrt{p}$. The public key and commitment are generated by a double path procedure, which generates a double path of degree $2^{2f}$ and $3^{2g} \approx p$ to the same codomain. In practice, the double path is computed via three $2^f$-isogenies and three $3^g$-isogenies in dimension 1. This double path procedure is assumed to be computationally uniform. The challenge is generated by an isogeny of degree $3^g$. The response is an isogeny of degree $q \le 2^{2e}$ such that $2^{2e} - q$ is a sum of two squares, this allows to find a dimension 4 HD representation of this response. In practice, we take $2e \approx \log_2(p) + 16$.

The signature only needs to compute the commitment, the challenge is represented by its kernel, and the response by its action on the $2^f$-torsion. The verification computes the challenge from its kernel, and compute the response via its dimension 4 representation, namely it needs to compute two $2^e$-isogenies in dimension 4 with $e \approx \log_2(p)/2 + 8 \le f$.

For NIST level 1, we have $p = 13 \cdot 2^{126}3^{78} - 1$, and the signature takes 109 Bytes. The commitment needs three $2^{126}$-isogenies and three $3^{78}$-isogenies in dimension 1. The verification computes the challenge of degree $3^{78}$ and checks the response via two $2^{73}$-isogenies in dimension 4.

**RigorousSQIsignHD:** this version uses dimension 1 for the signature and dimension 8 for verification. This version is optimised for security: the public key, and commitment are provably statically uniform, and the zero knowledge property has a clean proof which relies on a RADIO oracle. However, while this protocol is polynomial time with respect to the security parameter $\lambda$, it is much too slow to be used in practice and no serious instantiation has been proposed.

Indeed, the public key, challenge and commitments are given by isogenies of degree $\approx p^3$, this requires accessible $T$-torsion with $T \approx p^3$, hence imposes to work with field extensions. The response is an isogeny of degree $q \approx p^2 \le 2^{2e}$, which will be computed during the verification via two $2^e$-isogenies in dimension 8, with $2^e \approx p$. This imposes to take $p = c2^e - 1$, and $T$ to be powersmooth. The signature thus needs to split large degree isogenies into block of $T$-isogenies with the $T$-torsion defined over extensions, so is much slower than in SQIsign. The verification needs to compute two $2^e \approx p$-isogenies in dimension 8, compared to FastSQIsignHD which only needs two $2^e \approx \sqrt{p}$-isogenies in dimension 4. A $2^n$-isogeny in dimension 8 is expected to be roughly 32 times slower than a $2^n$-isogeny in dimension 4, so the verification time of RigorousSQIsignHD would also be much slower than in FastSQIsignHD.
C.6.3. *SQIsign2d*. In this section, we will focus on the variant SQIsign2d-West of [BDD+24], but see also [NO24; DF24]. This version has faster signature and verification times than SQIsign, a shorter signature and a cleaner security proof.

The prime $p$ is chosen to be a Montgomery friendly prime of the form $p = c2^e - 1$ so that the $2^e$-torsion is accessible, with $2^e \approx p$. The signature takes $\approx 8 \cdot \lambda$ bits. The public key is provably statically uniform and computed via the Clapotis version of the ideal to isogeny algorithm applied a uniformly random ideal class. The Clapotis algorithm requires one $2^e$-isogeny in dimension 2, and between zero and two $2^f$-isogenies in dimension 2, with $2^f \approx \sqrt{p}$, depending on the chosen trade off between work on the quaternion side and on the isogeny side. The commitment is also statically uniform and use the same algorithm. Like in *Rigorous SQIsignHD*, there is a clean zero knowledge proof which relies on a slightly different oracle.

Like in *FastSQIsignHD* the signature only generates the kernel of the challenge, which is computed during the verification. This challenges is a $2^e$-isogeny in dimension 1. The verification also checks the response, via a $2^f$-isogeny in dimension 2. Compared to *FastSQI-signHD*, the signature step also needs to compute an auxiliary isogeny $\beta : E_{chl} \to E_{aux}$ of appropriate degree to embed the response into a $2^f$-isogeny $\Phi : E_{chl} \times E_{aux} \to E_{com} \times E'_{aux}$ in dimension 2, this is also done via the Clapotis version of the ideal to isogeny algorithm. More precisely, it is $\tilde{\Phi}$ which is computed first from the commitment curve and $\beta' : E_{com} \to E'_{aux}$, and then $\tilde{\Phi}$ is evaluated to recover $\Phi$. The reason we want $\Phi$ rather than $\tilde{\Phi}$ to embed the response is to compress the signature by using commitment recoverability. See [BDD+24, Figure 2] for the full diagram.

There is a slightly more heuristic version where the commitment is computed using the QFESTA algorithm (Example 6.12) rather than Clapotis (Example 6.13), which is faster but lack the provable statical uniform property. The challenge is also taken to be of degree $2^f$, this allows to compute $\beta$ hence $\Phi$ directly from $E_{chl}$.

For NIST level 1, we have $p = 5 \cdot 2^{248} - 1$ and the signature takes 148 Bytes using hints to speed up the verification. Removing hints could reduce the signature size up to 128 Bytes, at the cost of a slight increase (5 to 10 percent) to the verification time.

The signature computes the commitment via Clapotis, which uses a $2^{248}$-isogeny and two $2^{126}$-isogenies in dimension two. The auxiliary isogeny $\beta'$ is also generated by Clapotis, this gives a $2^{126}$-isogeny $\tilde{\Phi}$ in dimension 2, and computing it allows to recover $\Phi$. The verification computes the challenge, which is a $2^{248}$-isogeny in dimension one, and the response is checked via a $2^{126}$-isogeny in dimension two.

In the heuristic version the commitment only needs one $2^{248}$-isogeny in dimension 2. The challenge is a $2^{122}$-isogeny in dimension 1 which is computed during the verification. This allows to build $\Phi$ directly from $\beta$, computed via Clapotis. This heuristic version gives a signature roughly 60 percent faster than the cleaner version. The response is checked via a $2^{126}$-isogeny in dimension two too, so the verification time does not change much (only the challenge is smaller).

The verification time of SQIsign2d is the fastest out of all the variants described in this section, and the signature is only slightly slower and less compact than FastSQIsignHD and much faster than SQIsign. But as explained in [BDD+24, Remark 24], we can adapt FastSQIsignHD to the prime used in SQIsign2d, this gives an even faster signature time than the original FastSQIsignHD. That version has a signature time roughly 3× faster than the heuristic version of SQIsign2d. However, this comes at the cost of the verification time, which needs to compute an isogeny in dimension 4 rather than 2, for an expected slow down of roughly $\times 8$.
APPENDIX D. THE CLASS GROUP OF A NON MAXIMAL ORDER

Let $R$ be an order in some number field $K$, $R_0$ be the maximal order of $K$, and $f$ the conductor ideal of $R$: $f = (R : R_0)$. This is both an ideal in $R$ and in $R_0$.

The conductor square

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

is a Milnor square (also called an excision datum): it is both a pullback and a pushforward.

In particular, $\text{Spec } R = \text{Spec } R_0 \coprod_{\text{Spec } R_0/f} \text{Spec } R/f$ is given by the gluing of $\text{Spec } R_0$ and $\text{Spec } R/f$ over $\text{Spec } R_0/f$. This is a pushout in the category of schemes, and gives an explicit description of $\text{Spec } R$ as a blow down of the regular scheme $\text{Spec } R_0$.

As shown by Milnor, finitely presented vector bundles (so in particular line bundles) satisfy excision, which means that to specify a line bundle $\mathcal{L}$ on $\text{Spec } R$ is the same thing as specifying a line bundle $\mathcal{L}_0$ on $\text{Spec } R_0$ and $\mathcal{L}_f$ on $\text{Spec } R/f$, along with an isomorphism $\mathcal{L}_0 \simeq \mathcal{L}_f$ over $\text{Spec } R_0/f$. For vast generalisations of this result, see [BM21; EHIK21; AHHR24].

From this we obtain a Mayer-Vietoris exact sequence:

$$1 \to \text{U}(R) \to \text{U}(R/f) \oplus \text{U}(R_0) \to \text{U}(R_0/f) \to \text{Pic}(R) \to \text{Pic}(R_0) \oplus \text{Pic}(R_0/f) \to 0,$$

which gives the usual exact sequence between $\text{Pic}(R)$ and $\text{Cl}(R_0)$:

$$(4) \qquad 1 \to R_0^*/R^* \to (R_0/f)^*/(R/f)^* \to \text{Pic}(R) \to \text{Cl}(R_0) \to 0.$$

This geometric derivation of Equation (4) might seem overkill, but it has the following nice application for isogenies between elliptic curves. Let $\phi: E_1 \to E_2$ be an horizontal isogeny between $R$-oriented elliptic curves, so that $\phi = \phi_I$ for some invertible ideal $I \in \text{Pic}(R)$. The conductor ideal $f$ of $R \subset R_0$ gives ascending isogenies $\phi_{\tilde{f},1}: E_1 \to E'_1$ and $\phi_{\tilde{f},2}: E_2 \to E'_2$. Looking at the image $I' = IR_0 \in \text{Cl}(R_0)$ of $I$ under Equation (4), we also have an horizontal isogeny $\phi_{I'}: E'_1 \to E'_2$, which commutes with $\phi_I$ under the ascending isogenies (and in fact is a pushforward: $\text{Ker } \phi_{\tilde{f},2} = \phi_I(\text{Ker } \phi_{\tilde{f},1})$).

Conversely, take some ideal class $[I'] \in \text{Cl}(R_0)$ represented by $I'$ giving some isogeny $\phi_{I'}: E'_1 \to E'_2$. Let $K_1$ be the kernel of the descending isogeny $\tilde{\phi}_{\tilde{f},1}: E'_1 \to E_1$. If we take $I'$ to be of prime norm to the conductor of $R$, the image $K_2 = \phi_{I'}(K_1)$ of $K_1$ by $\phi_{I'}$ is the kernel of a descending isogeny $\tilde{\phi}_{\tilde{f},2}: E'_2 \to E_2$, and we obtain an isogeny $\phi_I: E_1 \to E_2$ completing the pushforward square. Changing the class of $I'$ amount to postcomposing by an endomorphism $\alpha: E'_2 \to E'_2$; in general we obtain a different isogeny $E_1 \to E_2$ unless $\alpha(K_2) = K_2$. We can thus reinterpret isogenies $E_1 \to E_2$ as isogenies $E'_1 \to E'_2$ with some extra level structure information (namely the image of the kernel $K_1$). In other words: $E'_2$ is determined from $E_2$ and $K_2$, and it is also determined by the class of $I$. From the conductor square, we know that the class of $I$ is determined by the class of some invertible ideal $I'$ in $R_0$, along with some invertible ideal in $R/f$ and some gluing data. But we know that $E_2$ is given by the class of $I'$, so this means that the data of $K_2$ should correspond to some module over $R/f$. One can make this statement rigourous by using the fact that the usual ideal to isogeny functor extends to modules, see Remark 4.1.

More generally, there are two ways to extend the usual relationship between ideals and isogenies to include level structure information. The first is to consider ideals with respect to a suborder whose conductor is related to the level structure. For instance, extending the Deuring's correspondence to keep track of the kernel of a specific isogeny $E_0 \to E_1$
corresponds to looking at ideals in the Eichler order $O_0 \cap O_1$. This is the point of view adapted in [Ler22b; Arp22].

Another approach is to use again that the ideal to isogeny functor extend to modules. For instance, if $R = \text{End}(E)$, the map associated to the module $R \hookrightarrow R/I$ is the inclusion $E[I] \subset E$; in particular $E[n]$ corresponds to the module $R/nR$. Keeping track of level structure along isogenies corresponds to looking at modules over $R$ along with modules over the endomorphism data of the level structure, with some compatible gluing conditions. Again, the conductor square allows to go back and forth between the two approaches (for sufficiently nice modules).

In other words, as argued in [PR23a], the module point of view, which extends the usual relationship between ideals and isogenies (as described in Section 4), is very fruitful since it can handle in a unified framework level structures and the higher dimensional isogeny graph starting from $E^g$. And the geometric description of Spec $R$ as an excision datum of Spec $R_0$ and Spec $R/f$ over Spec $R_0/f$ allows to better understand modules on $R$.

## APPENDIX E. THE KODAIRA-SPENCER ISOMORPHISM FOR ABELIAN VARIETIES

In this section, we briefly recall the Kodaira-Spencer isomorphism. If $A/k$ is an abelian variety, the Kodaira-Spencer map is a canonical isomorphism between $\text{Sym}^2(T_0(A))$ and the tangent $T_A A_g$ to $A$ on the moduli space of principally polarised abelian varieties $A_g$. In other words, deformations of $A$ are controlled by the $\text{Sym}^2$ of differentials on $A$.

Let $p: A \to S$ be an abelian scheme over a smooth base. Recall that we have a canonical flat connection on the De Rham (hyper)cohomology, the Gauss-Manin connection:

$$ \nabla: R^1 p_* \Omega_{A/S} \to R^1 p_* \Omega_{A/S} \otimes \Omega_S^1. $$

Combining the Gauss-Manin connection with the Hodge filtration, one can define the Kodaira-Spencer map (see [And17, § 1.4; FC90, § III.9]):

$$ \kappa: T_S \to R^1 p_* T_{A/S}, $$

where $T_{A/S}$ denotes the dual of $\Omega_{A/S}^1$. Since $\text{Lie}_S A = p_* T_{A/S} = s^* T_{A_S}$ where $s: S \to A$ is the zero section [EGM12, Prop. 3.15], by the projection formula [Stacks, Tag 0943], we have

$$ R^1 p_* T_{A/S} = \text{Lie}_S(A) \otimes_{O_S} R^1 p_* O_A. $$

Moreover, $R^1 p_* O_A$ is naturally isomorphic to $\text{Lie}_S(A^\vee)$, where $A^\vee \to S$ denotes the dual of $A$. Therefore, we can also write the Kodaira-Spencer map as

$$ \kappa: T_S \to R^1 p_* T_{A/S} \simeq \text{Lie}_S(A) \otimes_{O_S} \text{Lie}_S(A^\vee). $$

The Kodaira-Spencer map $\kappa$ is invariant by duality. A polarization $A \to A^\vee$ induces another version of the Kodaira-Spencer map:

$$ \kappa: T_S \to \text{Sym}^2 \text{Lie}_S(A) = \text{Hom}_{\text{Sym}}(\Omega_{A/S}^1, \Omega_{A^\vee/S}^{1/\vee}) = \text{Hom}_{\text{Sym}}(\text{Lie}_S(A)^\vee, \text{Lie}_S(A^\vee)). $$

If we apply this construction to the universal abelian scheme $\chi_g \to A_g$, the Kodaira-Spencer map is an isomorphism [And17, § 2.1.1]. In particular, if $x: \text{Spec } k \to A_g$ is a point represented by a principally polarised abelian variety $A/k$, we have a canonical isomorphism $T_x A_g \simeq \text{Sym}^2(T_0(A))$. Moreover, if $j$ is a modular invariant (i.e. a rational map $A_g \to A^1$), then via the Kodaira-Spencer isomorphism, its differential $dj$ becomes a Siegel modular function of weight $\text{Sym}^2$.
**Example E.1.** In [KPR24], we use the Kodaira-Spencer isomorphism to work with deformation representations of isogenies in dimension 2.

Namely, if $H : y^2 = f(x)$ is a hyperelliptic curve, with $\deg f = 6$, we can associate a canonical basis of differentials $(dx/y, xdx/y)$ on $Jac(H)$, via the canonical isomorphism $\Omega^1(Jac(C)) \simeq H^1(C)$. Then the curve equation gives a universal vectorial modular $(Jac(H), dx/y, xdx/y) \mapsto f(x)$ form of weight $\mathrm{Sym}^6$. If $(j_1, j_2, j_3)$ are the Igusa invariants, we can thus express the vectorial modular functions $dj_1, dj_2, dj_3$ of weight $\mathrm{Sym}^2$ in terms of the coefficients of the curve equation $f(x)$: explicit formulas are in [KPR24].

We can then proceed as in Section 3.3 to reconstruct an isogeny from the modular polynomial: letting $J = (j_1, j_2, j_3)$, and $\Phi_\ell$ the modular polynomial(s) in dimension 2, if $\Phi_\ell(J(A), J(B)) = 0$, differentiatig $\Phi_\ell$ gives the relationship between $dJ(A, \omega_A)$ and $dJ(B, \omega_B)$ where $\omega_A, \omega_B$ are normalised basis of differentials on $A, B$, i.e., if $\phi : A \to B$ is the associated $\ell$-isogeny, we have $\phi^*\omega_B = \omega_A$. Using the formulas expressing $dJ$ in terms of the curve equation, we can find equations for $H_A, H_B$ such that the isogeny is normalised with respect to the canonical basis $(dx/y, xdx/y)$. We can then solve a differential equation to recover $\phi$ in Mumford coordinates. See [Rob21, § 5.4.2] for a summary, and [KPR24] for all details.

In theory, the heat equation

$$2\pi i(1 + \delta_{jk}) \frac{\partial \theta_i}{\partial \tau_{jk}} = \frac{\partial^2 \theta_i}{\partial z_j \partial z_k}.$$

gives the Kodaira-Spencer isomorphism for theta functions. So we could extend the approach of [KPR24] to the theta model in higher dimension. The main problem is that the size of the modular polynomial explodes in higher dimension (see [Kie22b] for bounds on the degree and height). For instance, the Siegel modular polynomial in dimension $g$ is of size $\tilde{O}(\ell^{N(N+2)})$ where $N = g(g+1)/2$ is the dimension of the moduli space $A_g$; and the evaluated modular polynomial $\Phi_\ell(J(A), Y)$ for $A/\mathbb{F}_q$ is of size $\tilde{O}(\ell^N \log q)$. When $g = 1$, we recover that $\phi_\ell$ is of size $\tilde{O}(\ell^3)$, and the evaluated modular polynomial of size $O(\ell \log q)$. In dimension 2, the Siegel modular polynomial $\Phi_\ell$ is of size $\tilde{O}(\ell^{15})$, and the evaluated modular polynomial is of size $O(\ell^3 \log q)$, but the best algorithm we have to evaluate it [Kie20] uses analytic method and cost time $O(\ell^6 \log q)$, if $q = p$ (see also [Rob22b] for CRT and $p$-adic variants which use the HD representation). In dimension 3, the Siegel modular polynomial $\Phi_\ell$ is of a staggering size $\tilde{O}(\ell^{48})$, and even the evaluated modular polynomial of size $O(\ell^6 \log q)$.

In higher dimension, using Hilbert modular polynomials to parametrize $\beta$-isogenies, with $N(\beta) = \ell$, is more reasonable: they take space $\tilde{O}(\ell^{g+2})$ and their evaluation take space $\tilde{O}(\ell \log q)$. We refer to [Kie22a; Kie21] for applications to point counting in dimension 2.

REFERENCES

[ADMP20] N. Alamati, L. De Feo, H. Montgomery, and S. Patranabis. “Cryptographic group actions and applications”. In: *Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26*. Springer. 2020, pp. 411–439 (cit. on p. 23).
[AHHR24]
J. Alper, J. Hall, D. Halpern-Leistner, and D. Rydh. "Artin algebraization for pairs with applications to the local structure of stacks and Ferrand pushouts". In: *Forum of Mathematics, Sigma*. Vol. 12. Cambridge University Press. 2024, e20 (cit. on p. 57).

[And17]
Y. André. "On the Kodaira-Spencer map of abelian schemes". In: *Ann. Sc. Norm. Super. Pisa Cl. Sci.* (5) 17.4 (2017), pp. 1397-1416 (cit. on p. 58).

[Arp22]
S. Arpin. "Adding level structure to supersingular elliptic curve isogeny graphs". In: *arXiv preprint arXiv:2203.03531* (2022) (cit. on pp. 50, 58).

[ACL+23]
S. Arpin, C. Camacho-Navarro, K. Lauter, J. Lim, K. Nelson, T. Scholl, and J. Sotáková. "Adventures in supersingular land". In: *Experimental Mathematics* 32.2 (2023), pp. 241-268 (cit. on p. 21).

[ACL+22]
S. Arpin, M. Chen, K. E. Lauter, R. Scheidler, K. E. Stange, and H. T. Tran. "Orientations and cycles in supersingular isogeny graphs". In: *Proceedings of Women in Number Theory* 5 (2022) (cit. on p. 21).

[ACD+23]
S. Arpin, J. Clements, P. Dartois, J. K. Eriksen, P. Kutas, and B. Wesolowski. "Finding orientations of supersingular elliptic curves and quaternion orders". In: *arXiv preprint arXiv:2308.11539* (2023) (cit. on p. 1).

[BGDS23]
G. Banegas, V. Gilchrist, A. L. Dévéhat, and B. Smith. "Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields". In: *International Conference on Cryptology and Information Security in Latin America*. Springer. 2023, pp. 129-148 (cit. on pp. 18, 45).

[Bas24]
A. Basso. "POKE: A Framework for Efficient PKEs, Split KEMs, and OPRFs from Higher-dimensional Isogenies". In: *Cryptology ePrint Archive* (2024) (cit. on pp. 1, 27, 40).

[BCC+23]
A. Basso, G. Codogni, D. Connolly, L. De Feo, T. B. Fouotsa, G. M. Lido, T. Morrison, L. Panny, S. Patranabis, and B. Wesolowski. "Supersingular curves you can trust". In: *Annual International Conference on the Theory and Applications of Cryptographic Techniques*. Springer. 2023, pp. 405-437 (cit. on pp. 27, 40).

[BDD+24]
A. Basso, L. De Feo, P. Dartois, A. Leroux, L. Maino, G. Pope, D. Robert, and B. Wesolowski. "SQLsign2D-West: The Fast, the Small, and the Safer". Accepted for publication at *Asiacrypt 2024*. Aug. 2024 (cit. on pp. 1, 22, 30, 35, 39, 53, 54, 56).

[BMP23]
A. Basso, L. Maino, and G. Pope. "FESTA: fast encryption from supersingular torsion attacks". In: *International Conference on the Theory and Application of Cryptology and Information Security*. Springer. 2023, pp. 98-126 (cit. on pp. 1, 27).

[BDLS20]
D. Bernstein, L. De Feo, A. Leroux, and B. Smith. "Faster computation of isogenies of large prime degree". In: *Algorithmic Number Theory Symposium (ANTS XIV)*. Vol. 4. 1. Mathematical Sciences Publishers, 2020, pp. 39-55. arXiv: 2003.10118. URL: https://msp.org/obs/2020/4/p04.xhtml (cit. on pp. 5, 11, 31).

[BDGP23]
W. Beullens, L. De Feo, S. D. Galbraith, and C. Petit. "Proving knowledge of isogenies: a survey". In: *Designs, Codes and Cryptography* 91.11 (2023), pp. 3425-3456 (cit. on p. 41).
[BKV19] W. Beullens, T. Kleinjung, and F. Vercauteren. "CSI-FiSh: efficient isogeny based signatures through class group computations". In: *International Conference on the Theory and Application of Cryptology and Information Security*. Springer. 2019, pp. 227-247 (cit. on pp. 23, 24).

[BM21] B. Bhatt and A. Mathew. "The arc-topology". In: *Duke Mathematical Journal* 170.9 (2021), pp. 1899-1988 (cit. on p. 57).

[BCR10] G. Bisson, R. Cosset, and D. Robert. *AVIsogenies*. Magma package devoted to the computation of isogenies between abelian varieties. 2010. URL: https://www.math.u-bordeaux.fr/~damienrobert/avisogenies/. Free software (LGPLv2+), registered to APP (reference IDDN.FR.001.440011.-000.R.P.2010.000.10000). Latest version 0.7, released on 2021-03-13. (Cit. on p. 28).

[BMSS08] A. Bostan, F. Morain, B. Salvy, and E. Schost. "Fast algorithms for computing isogenies between elliptic curves". In: *Mathematics of Computation* 77.263 (2008), pp. 1755-1778 (cit. on pp. 13, 16).

[BCG+17] A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and É. Schost. *Algorithmes efficaces en calcul formel*. Published by the authors, 2017. URL: https://hal.inria.fr/hal-01431717/document (cit. on pp. 6, 12).

[BDDFS19] L. Brieulle, L. De Feo, J. Doliskani, J.-P. Flori, and É. Schost. "Computing isomorphisms and embeddings of finite fields". In: *Mathematics of Computation* 88.317 (2019), pp. 1391-1426 (cit. on p. 44).

[BLS12] R. Bröker, K. Lauter, and A. Sutherland. "Modular polynomials via isogeny volcanoes". In: *Mathematics of Computation* 81.278 (2012), pp. 1201-1231. arXiv: 1001.0402 (cit. on p. 16).

[BFT14] N. Bruin, E. V. Flynn, and D. Testa. "Descent via (3, 3)-isogeny on Jacobians of genus 2 curves". In: *Acta Arithmetica* 165.3 (2014), pp. 201-223 (cit. on p. 29).

[BSC+23] G. Bruno, M. C.-R. Santos, C. Costello, J. K. Eriksen, M. Meyer, M. Naehrig, and B. Sterner. "Cryptographic smooth neighbors". In: *International Conference on the Theory and Application of Cryptology and Information Security*. Springer. 2023, pp. 190-221 (cit. on p. 52).

[CF+96] J. W. S. Cassels, E. V. Flynn, et al. *Prolegomena to a middlebrow arithmetic of curves of genus 2*. Vol. 230. Cambridge University Press, 1996 (cit. on pp. 29, 31).

[CD21] W. Castryck and T. Decru. "Multiradical isogenies". In: *Arithmetic, Geometry, Cryptography, and Coding Theory* 779 (2021), pp. 57-89 (cit. on p. 12).

[CD22] W. Castryck and T. Decru. *An efficient key recovery attack on SIDH (preliminary version)*. Cryptology ePrint Archive, Paper 2022/975. 2022. URL: https://eprint.iacr.org/2022/975 (cit. on p. 1).

[CD23] W. Castryck and T. Decru. "An efficient key recovery attack on SIDH". In: Springer-Verlag (Eurocrypt 2023), Apr. 2023, pp. 423-447. DOI: 10.1007/978-3-031-30589-4_15 (cit. on pp. 1, 2, 26).

[CDHV22] W. Castryck, T. Decru, M. Houben, and F. Vercauteren. "Horizontal race-walking using radical isogenies". In: *International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt)*. Springer. 2022, pp. 67-96 (cit. on p. 12).
[CDM+24] W. Castryck, T. Decru, L. Maino, C. Martindale, L. Panny, G. Pope, D. Robert, and B. Wesolowski. "Interpolating isogenies and breaking the SIDH cryptosystem". June 2024 (cit. on pp. 7, 26).

[CDV20] W. Castryck, T. Decru, and F. Vercauteren. "Radical isogenies". In: *International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt)*. Lecture Notes in Computer Science 12492. Springer. 2020, pp. 493–519 (cit. on p. 12).

[CLMPR18] W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes. "CSIDH: an efficient post-quantum commutative group action". In: *International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2018)*. Springer. 2018, pp. 395–427 (cit. on pp. 19, 23).

[CLG09] D. Charles, K. Lauter, and E. Goren. "Cryptographic hash functions from expander graphs". In: *Journal of Cryptology* 22.1 (2009), pp. 93–113. ISSN: 0933-2790 (cit. on p. 11).

[CII+23] M. Chen, M. Imran, G. Ivanyos, P. Kutas, A. Leroux, and C. Petit. "Hidden stabilizers, the isogeny to endomorphism ring problem and the cryptanalysis of pSIDH". In: *International Conference on the Theory and Application of Cryptology and Information Security*. Springer. 2023, pp. 99–130 (cit. on p. 43).

[CLP24] M. Chen, A. Leroux, and L. Panny. "SCALLOP-HD: group action from 2-dimensional isogenies". In: *IACR International Conference on Public-Key Cryptography*. Springer. 2024, pp. 190–216 (cit. on pp. 1, 8, 25, 52).

[CS21] M. Chenu and B. Smith. "Higher-degree supersingular group actions". In: *arXiv preprint arXiv:2107.08832* (2021) (cit. on p. 20).

[CC86] D. Chudnovsky and G. Chudnovsky. "Sequences of numbers generated by addition in formal groups and new primality and factorization tests". In: *Advances in Applied Mathematics* 7.4 (1986), pp. 385–434. ISSN: 0196-8858. DOI: https://doi.org/10.1016/0196-8858(86)90023-0 (cit. on p. 30).

[CL23] G. Codogni and G. Lido. "Spectral theory of isogeny graphs". In: *arXiv preprint arXiv:2308.13913* (2023) (cit. on p. 27).

[CK20] L. Colo and D. Kohel. "Orienting supersingular isogeny graphs". In: *Journal of Mathematical Cryptology* 14.1 (2020), pp. 414–437 (cit. on p. 20).

[Cor07] G. Cornacchia. *Su di un metodo per la risoluzione in numeri interi dell'equazione* $\sum_{h=0}^{n} C_h x^{n-h} y^h = P$. Vol. 46. 1907, pp. 33–90 (cit. on p. 34).

[CCS24] M. Corte-Real Santos, C. Costello, and B. Smith. "Efficient (3, 3)-isogenies on fast Kummer surfaces". In: *arXiv preprint arXiv:2402.01223* (2024) (cit. on pp. 29, 30).

[CEMR24] M. Corte-Real Santos, J. K. Eriksen, M. Meyer, and K. Reijnders. "AprésSQI: extra fast verification for SQIsign using extension-field signing". In: *Annual International Conference on the Theory and Applications of Cryptographic Techniques*. Springer. 2024, pp. 63–93 (cit. on pp. 46, 54).

[CR24] M. Corte-Real Santos and K. Reijnders. *Return of the Kummer: a toolbox for genus 2 cryptography*. Cryptology ePrint Archive, Paper 2024/948. 2024. URL: https://eprint.iacr.org/2024/948 (cit. on p. 31).

[CR15] R. Cosset and D. Robert. "An algorithm for computing $(\ell, \ell)$-isogenies in polynomial time on Jacobians of hyperelliptic curves of genus 2". In: *Mathematics of Computation* 84.294 (Nov. 2015), pp. 1953–1975. DOI: 10.1090/S0025-5718-2014-02899-8 (cit. on pp. 2, 28).
[CMSV19] E. Costa, N. Mascot, J. Sijsling, and J. Voight. "Rigorous computation of the endomorphism ring of a Jacobian". In: Mathematics of Computation 88.317 (2019), pp. 1303-1339 (cit. on p. 31).

[Cos18] C. Costello. "Computing supersingular isogenies on Kummer surfaces". In: Advances in Cryptology-ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part III 24. Springer. 2018, pp. 428-456 (cit. on p. 31).

[CJL+17] C. Costello, D. Jao, P. Longa, M. Naehrig, J. Renes, and D. Urbanik. "Efficient compression of SIDH public keys". In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2017, pp. 679-706 (cit. on p. 46).

[Cou09] J. Couveignes. "Linearizing torsion classes in the Picard group of algebraic curves over finite fields". In: Journal of Algebra 321.8 (2009), pp. 2085-2118. ISSN: 0021-8693 (cit. on p. 45).

[Cou06] J. M. Couveignes. "Hard Homogeneous Spaces". In: IACR Cryptology ePrint Archive 2006 (2006), p. 291 (cit. on p. 19).

[CE14] J.-M. Couveignes and T. Ezome. "Computing functions on Jacobians and their quotients". In: LMS Journal of Computation and Mathematics 18.1 (2014), pp. 555-577. arXiv: 1409.0481 (cit. on pp. 29, 31).

[Dar24] P. Dartois. "Fast computation of 2-isogenies in dimension 4 with the theta model and cryptographic applications". 2024 (cit. on pp. 30, 48).

[DLRW24] P. Dartois, A. Leroux, D. Robert, and B. Wesolowski. "SQISignHD: New Dimensions in Cryptography". In: Lecture Notes in Computer Science 14651 (May 2024). Ed. by M. Joye and G. Leander, pp. 3-32. DOI: 10.1007/978-3-031-58716-0_1 (cit. on pp. 1, 7, 8, 22, 29, 30, 47, 48, 52, 55).

[DMPR24] P. Dartois, L. Maino, G. Pope, and D. Robert. "An Algorithmic Approach to (2, 2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography". Accepted for publication at Asiacrypt 2024. Aug. 2024 (cit. on pp. 2, 29, 30, 48).

[De 17] L. De Feo. Mathematics of Isogeny Based Cryptography. 2017. arXiv: 1711.04062 (cit. on p. 20).

[DDGZ22] L. De Feo, S. Dobson, S. D. Galbraith, and L. Zobernig. "SIDH proof of knowledge". In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2022, pp. 310-339 (cit. on pp. 40, 41).

[DDS14] L. De Feo, J. Doliskani, and É. Schost. "Fast arithmetic for the algebraic closure of finite fields". In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. 2014, pp. 122-129 (cit. on p. 43).

[DFP24] L. De Feo, T. B. Fouotsa, and L. Panny. "Isogeny problems with level structure". In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2024, pp. 181-204 (cit. on pp. 27, 41).

[DG19] L. De Feo and S. D. Galbraith. "SeaSign: compact isogeny signatures from class group actions". In: Advances in Cryptology-EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III 38. Springer. 2019, pp. 759-789 (cit. on p. 23).
[DHPS16] L. De Feo, C. Hugounenq, J. Plût, and É. Schost. "Explicit isogenies in quadratic time in any characteristic". In: *LMS Journal of Computation and Mathematics* 19.A (2016), pp. 267-282 (cit. on p. 16).

[DJP14] L. De Feo, D. Jao, and J. Plût. "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". In: *Journal of Mathematical Cryptology* 8.3 (2014), pp. 209-247 (cit. on pp. 1, 17).

[DKS18] L. De Feo, J. Kieffer, and B. Smith. "Towards practical key exchange from ordinary isogeny graphs". In: *International Conference on the Theory and Application of Cryptology and Information Security*. Springer. 2018, pp. 365-394. arXiv: 1809.07543 (cit. on p. 19).

[DKLPW20] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski. "SQISign: compact post-quantum signatures from quaternions and isogenies". In: *International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020)*. Springer. 2020, pp. 64-93 (cit. on pp. 3, 21, 50, 51, 54).

[DLLW23] L. De Feo, A. Leroux, P. Longa, and B. Wesolowski. "New algorithms for the Deuring correspondence: towards practical and secure SQISign signatures". In: *Annual International Conference on the Theory and Applications of Cryptographic Techniques*. Springer. 2023, pp. 659-690 (cit. on pp. 3, 22, 52, 54).

[Dec24] T. Decru. "Radical Vélu N-Isogeny Formulae". In: *Annual International Cryptology Conference (Eurocrypt)*. Springer. 2024, pp. 107-128 (cit. on p. 12).

[DK23] T. Decru and S. Kunzweiler. "Efficient Computation of (3 n, 3 n)-Isogenies". In: *International Conference on Cryptology in Africa*. Springer. 2023, pp. 53-78 (cit. on p. 30).

[DMS23] T. Decru, L. Maino, and A. Sanso. "Towards a quantum-resistant weak verifiable delay function". In: *International Conference on Cryptology and Information Security in Latin America*. Springer. 2023, pp. 149-168 (cit. on p. 1).

[DHK+23] J. Duman, D. Hartmann, E. Kiltz, S. Kunzweiler, J. Lehmann, and D. Riepel. "Generic models for group actions". In: *IACR International Conference on Public-Key Cryptography*. Springer. 2023, pp. 406-435 (cit. on p. 23).

[DF24] M. Duparc and T. B. Fouotsa. "SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies". In: *Cryptology ePrint Archive* (2024) (cit. on pp. 1, 22, 30, 35, 56).

[DFV24] M. Duparc, T. B. Fouotsa, and S. Vaudenay. "Silbe: an updatable public key encryption scheme from lollipop attacks". In: *Cryptology ePrint Archive* (2024) (cit. on p. 1).

[EGM12] B. Edixhoven, G. van der Geer, and B. Moonen. *Abelian varieties*. Book project, 2012. URL: http://van-der-geer.nl/~gerard/AV.pdf (cit. on p. 58).

[ES24] K. Eisentraeger and G. Scullard. "Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings". In: (2024). arXiv: 2402.05059 (cit. on pp. 1, 37).

[EHLMP18] K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison, and C. Petit. "Supersingular isogeny graphs and endomorphism rings: reductions and solutions". In: *Advances in Cryptology-EUROCRYPT 2018: 37th Annual International*
Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part III 37. Springer. 2018, pp. 329-368 (cit. on p. 21).

[Elk92] N. Elkies. "Explicit isogenies". In: manuscript, Boston MA (1992) (cit. on p. 16).

[Elk97] N. Elkies. "Elliptic and modular curves over finite fields and related computational issues". In: Computational perspectives on number theory: proceedings of a conference in honor of AOL Atkin, September 1995, University of Illinois at Chicago. Vol. 7. Amer Mathematical Society. 1997, p. 21 (cit. on p. 16).

[EHIK21] E. Elmanto, M. Hoyois, R. Iwasa, and S. Kelly. "Cdh descent, cdarc descent, and Milnor excision". In: Mathematische Annalen 379.3 (2021), pp. 1011-1045 (cit. on p. 57).

[Eng09] A. Enge. "Computing modular polynomials in quasi-linear time". In: Math. Comp 78.267 (2009), pp. 1809-1824 (cit. on p. 16).

[EPSV] J. K. Eriksen, L. Panny, J. Sotáková, and M. Veroni. "Deuring for the people: Supersingular elliptic curves with prescribed endomorphism ring in general characteristic". In: Contempory Mathematics 796 (.). LuCaNT: LMFDB, computation, and number theory (Providence), Proceedings, pp. 339-373 (cit. on pp. 18, 46, 50).

[FC90] G. Faltings and C.-L. Chai. Degeneration of abelian varieties. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 22. Springer-Verlag, Berlin, 1990 (cit. on p. 58).

[Fe010] L. de Feo. "Algorithmes Rapides pour les Tours de Corps Finis et les Isogénies". PhD thesis. Ecole Polytechnique X, Dec. 2010. URL: http://hal.inria.fr/tel-00547034/en (cit. on p. 10).

[FFK+23] L. D. Feo, T. B. Fouotsa, P. Kutas, A. Leroux, S.-P. Merz, L. Panny, and B. Wesolowski. "SCALLOP: scaling the CSI-FiSh". In: IACR International Conference on Public-Key Cryptography. Springer. 2023, pp. 345-375 (cit. on pp. 20, 25).

[Fly15] E. V. Flynn. "Descent via (5, 5)-isogeny on Jacobians of genus 2 curves". In: Journal of Number Theory 153 (2015), pp. 270-282 (cit. on p. 29).

[Fly93] E. V. Flynn. "The group law on the jacobian of a curve of genus 2." In: Journal für die reine und angewandte Mathematik 439 (1993), pp. 45-69 (cit. on p. 29).

[FMP23] T. B. Fouotsa, T. Moriya, and C. Petit. "M-SIDH and MD-SIDH: countering SIDH attacks by masking information". In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2023, pp. 282-309 (cit. on p. 27).

[FM02] M. Fouquet and F. Morain. "Isogeny volcanoes and the SEA algorithm". In: Algorithmic number theory (Sydney, 2002). Vol. 2369. Lecture Notes in Comput. Sci. Berlin: Springer, 2002, pp. 276-291. DOI: 10.1007/3-540-45455-1_23 (cit. on p. 18).

[FK11] G. Frey and E. Kani. "Correspondences on hyperelliptic curves and applications to the discrete logarithm". In: International Joint Conferences on Security and Intelligent Information Systems. Springer. 2011, pp. 1-19 (cit. on p. 29).
[Gal24] S. Galbraith. *Climbing and descending tall volcanos*. Cryptology ePrint Archive, Paper 2024/924. 2024. URL: https://eprint.iacr.org/2024/924 (cit. on pp. 1, 43).

[Gau07] P. Gaudry. "Fast genus 2 arithmetic based on Theta functions". In: *Journal of Mathematical Cryptology* 1.3 (2007), pp. 243-265 (cit. on p. 30).

[GL09] P. Gaudry and D. Lubicz. "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines". In: *Finite Fields and Their Applications* 15.2 (2009), pp. 246-260 (cit. on p. 28).

[GPV24] W. Ghantous, F. Pintore, and M. Veroni. "Efficiency of SIDH-based signatures (yes, SIDH)". In: *Journal of Mathematical Cryptology* 18.1 (2024), p. 20230023 (cit. on p. 40).

[HR19] H. Hisil and J. Renes. "On kummer lines with full rational 2-torsion and their usage in cryptography". In: *ACM Transactions on Mathematical Software (TOMS)* 45.4 (2019), pp. 1-17 (cit. on p. 30).

[Ill79] L. Illusie. "Complexe de de Rham-Witt et cohomologie cristalline". In: *Annales scientifiques de l'École Normale Supérieure*. Vol. 12. 4. 1979, pp. 501-661 (cit. on p. 15).

[JD11] D. Jao and L. De Feo. "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". In: *International Workshop on Post-Quantum Cryptography (PQCrypto 2011)*. Springer. 2011, pp. 19-34 (cit. on p. 1).

[JKP+18] B. W. Jordan, A. G. Keeton, B. Poonen, E. M. Rains, N. Shepherd-Barron, and J. T. Tate. "Abelian varieties isogenous to a power of an elliptic curve". In: *Compositio Mathematica* 154.5 (2018), pp. 934-959 (cit. on p. 20).

[Kan97] E. Kani. "The number of curves of genus two with elliptic differentials". In: *Journal für die reine und angewandte Mathematik* 485 (1997), pp. 93-122 (cit. on pp. 1, 7, 32).

[Kan11] E. Kani. "Products of CM elliptic curves". In: *Collectanea mathematica* 62.3 (2011), pp. 297-339 (cit. on p. 19).

[KU11] K. S. Kedlaya and C. Umans. "Fast polynomial factorization and modular composition". In: *SIAM Journal on Computing* 40.6 (2011), pp. 1767-1802 (cit. on pp. 18, 31, 44, 45).

[Kem88] G. Kempf. "Multiplication over abelian varieties". In: *American Journal of Mathematics* 110.4 (1988), pp. 765-773 (cit. on p. 28).

[Kem89a] G. Kempf. "Linear systems on abelian varieties". In: *American Journal of Mathematics* 111.1 (1989), pp. 65-94 (cit. on p. 28).

[Kem92] G. Kempf. "Equations of Kümmer Varieties". In: *American Journal of Mathematics* 114.1 (1992), pp. 229-232 (cit. on p. 28).

[Kem89b] G. Kempf. "Projective coordinate rings of abelian varieties". In: *Algebraic analysis, geometry and number theory* (1989), pp. 225-236 (cit. on p. 28).

[Kem90] G. R. Kempf. "Some wonderful rings in algebraic geometry". In: *Journal of Algebra* 134.1 (1990), pp. 222-224 (cit. on p. 28).

[Kie20] J. Kieffer. "Evaluating modular polynomials in genus 2". 2020. arXiv: 2010.10094 [math.NT]. HAL: hal-02971326. (Cit. on pp. 16, 59).

[Kie21] J. Kieffer. "Higher-dimensional modular equations, applications to isogeny computations and point counting". Thèse de doctorat dirigée par Damien Robert, Mathématiques Pures, Université de Bordeaux. PhD thesis. 2021. URL: http://www.theses.fr/2021BORD0188 (cit. on p. 59).
[Kie22a] J. Kieffer. "Counting points on abelian surfaces over finite fields with Elkies's method". In: (2022). arXiv: 2203.02009 [math.NT] (cit. on p. 59).

[Kie22b] J. Kieffer. "Degree and height estimates for modular equations on PEL Shimura varieties". 2022 (cit. on p. 59).

[KPR24] J. Kieffer, A. Page, and D. Robert. "Computing isogenies from modular equations between Jacobians of genus 2 curves". Accepted for publication at Journal of Algebra. June 2024. arXiv: 2001.04137 [math.AG] (cit. on pp. 14, 16, 31, 59).

[KR22] J. Kieffer and D. Robert. "Fast evaluation of modular polynomials and compact representation of isogenies between elliptic curves". Aug. 2022 (cit. on p. 13).

[KNRR21] M. Kirschmer, F. Narbonne, C. Ritzenthaler, and D. Robert. "Spanning the isogeny class of a power of an elliptic curve". In: Mathematics of Computation 91.333 (Sept. 2021), pp. 401-449. DOI: 10.1090/mcom/3672. arXiv: 2004.08315 (cit. on p. 16).

[Koh96] D. Kohel. "Endomorphism rings of elliptic curves over finite fields". PhD thesis. University of California, 1996 (cit. on pp. 10, 18, 19).

[KLPT14] D. Kohel, K. Lauter, C. Petit, and J.-P. Tignol. "On the quaternion-isogeny path problem". In: LMS Journal of Computation and Mathematics 17.A (2014), pp. 418-432 (cit. on pp. 3, 7, 21, 50).

[Kun22] S. Kunzweiler. "Efficient Computation of $(2^n, 2^n)$-Isogenies". In: Cryptology ePrint Archive (2022) (cit. on p. 29).

[KR24] S. Kunzweiler and D. Robert. "Computing modular polynomials by deformation". Accepted for publication at ANTS XVI Conference. June 2024 (cit. on pp. 1, 16, 38).

[Kup05] G. Kuperberg. "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem". In: SIAM Journal on Computing 35.1 (2005), pp. 170-188 (cit. on p. 19).

[LS08] R. Lercier and T. Sirvent. "On Elkies subgroups of $\ell$-torsion points in elliptic curves defined over a finite field". In: Journal de théorie des nombres de Bordeaux 20.3 (2008), pp. 783-797 (cit. on p. 13).

[Ler22a] A. Leroux. "A new isogeny representation and applications to cryptography". In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2022, pp. 3-35 (cit. on pp. 4, 7, 22).

[Ler22b] A. Leroux. "Quaternion algebras and isogeny-based cryptography". PhD thesis. LIX, 2022 (cit. on pp. 19, 22, 39, 50, 51, 58).

[Ler23a] A. Leroux. "Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves". In: Cryptology ePrint Archive (2023) (cit. on p. 16).

[Ler23b] A. Leroux. "Verifiable random function from the Deuring correspondence and higher dimensional isogenies". In: (2023) (cit. on pp. 1, 8, 22, 52).

[LR10] D. Lubicz and D. Robert. "Efficient pairing computation with theta functions". In: ed. by G. Hanrot, F. Morain, and E. Thomé. Vol. 6197. Lecture Notes in Computer Science. 9th International Symposium, Nancy, France, ANTS-IX, July 19-23, 2010, Proceedings. Springer-Verlag, July 2010. DOI: 10.1007/978-3-642-14518-6_21 (cit. on p. 28).
[LR12]
D. Lubicz and D. Robert. "Computing isogenies between abelian varieties". In: *Compositio Mathematica* 148.5 (Sept. 2012), pp. 1483–1515. DOI: 10.1112/S0010437X12000243. arXiv: 1001.2016 [math.AG] (cit. on p. 28).

[LR15a]
D. Lubicz and D. Robert. "A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties". In: *Journal of Symbolic Computation* 67 (Mar. 2015), pp. 68–92. DOI: 10.1016/j.jsc.2014.08.001 (cit. on p. 28).

[LR15b]
D. Lubicz and D. Robert. "Computing separable isogenies in quasi-optimal time". In: *LMS Journal of Computation and Mathematics* 18 (1 Feb. 2015), pp. 198–216. DOI: 10.1112/S146115701400045X. arXiv: 1402.3628 (cit. on pp. 28, 31).

[LR16]
D. Lubicz and D. Robert. "Arithmetic on Abelian and Kummer Varieties". In: *Finite Fields and Their Applications* 39 (May 2016), pp. 130–158. DOI: 10.1016/j.ffa.2016.01.009 (cit. on p. 28).

[LR22]
D. Lubicz and D. Robert. "Fast change of level and applications to isogenies". In: *Research in Number Theory (ANTS XV Conference)* 9.1 (Dec. 2022). DOI: 10.1007/s40993-022-00407-9 (cit. on pp. 7, 28).

[MM22]
L. Maino and C. Martindale. *An attack on SIDH with arbitrary starting curve*. Cryptology ePrint Archive, Paper 2022/1026. 2022. URL: https://eprint.iacr.org/2022/1026 (cit. on p. 2).

[MMPPW23]
L. Maino, C. Martindale, L. Panny, G. Pope, and B. Wesolowski. "A direct key recovery attack on SIDH". In: *Annual International Conference on the Theory and Applications of Cryptographic Techniques*. Springer. 2023, pp. 448–471 (cit. on pp. 1, 2, 26, 32).

[MW23]
A. H. L. Merdy and B. Wesolowski. "The supersingular endomorphism ring problem given one endomorphism". In: *arXiv preprint arXiv:2309.11912* (2023) (cit. on pp. 1, 37).

[Mil20]
E. Milio. "Computing isogenies between Jacobians of curves of genus 2 and 3". In: *Mathematics of Computation* 89.323 (2020), pp. 1331–1364. arXiv: 1709.06063 (cit. on p. 29).

[MR19]
E. Milio and D. Robert. "Denominators of modular polynomials on Hilbert surfaces". June 2019 (cit. on p. 2).

[Mor23]
T. Moriya. "IS-CUBE: An isogeny-based compact KEM using a boxed SIDH diagram". In: *Cryptology ePrint Archive* (2023) (cit. on pp. 1, 27).

[Mor24]
T. Moriya. "LIT-SiGamal: An efficient isogeny-based PKE based on a LIT diagram". In: *Cryptology ePrint Archive* (2024) (cit. on pp. 1, 27).

[Mum66]
D. Mumford. "On the equations defining abelian varieties. I". In: *Invent. Math.* 1 (1966), pp. 287–354 (cit. on p. 28).

[Mum67a]
D. Mumford. "On the equations defining abelian varieties. II". In: *Invent. Math.* 3 (1967), pp. 75–135 (cit. on p. 28).

[Mum67b]
D. Mumford. "On the equations defining abelian varieties. III". In: *Invent. Math.* 3 (1967), pp. 215–244 (cit. on p. 28).

[Mum83]
D. Mumford. *Tata lectures on theta I*. Vol. 28. Progress in Mathematics. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. Boston, MA: Birkhäuser Boston Inc., 1983, pp. xiii+235. ISBN: 3-7643-3109-7 (cit. on p. 28).

[Mum84]
D. Mumford. *Tata lectures on theta II*. Vol. 43. Progress in Mathematics. Jacobian theta functions and differential equations, With the collaboration
[Mum91] of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. Boston, MA: Birkhäuser Boston Inc., 1984, pp. xiv+272. ISBN: 0-8176-3110-0 (cit. on p. 28).

[NO23] D. Mumford. *Tata lectures on theta III*. Vol. 97. Progress in Mathematics. With the collaboration of Madhav Nori and Peter Norman. Boston, MA: Birkhäuser Boston Inc., 1991, pp. viii+202. ISBN: 0-8176-3440-1 (cit. on p. 28).

[NO24] K. Nakagawa and H. Onuki. "QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras". In: *Cryptology ePrint Archive* (2023) (cit. on pp. 1, 8, 39).

[NO24] K. Nakagawa and H. Onuki. "SQIsign2D-East: A New Signature Scheme Using 2-dimensional Isogenies". In: *Cryptology ePrint Archive* (2024) (cit. on pp. 1, 22, 30, 35, 39, 56).

[Nic18] C. Nicholls. "Descent methods and torsion on Jacobians of higher genus curves". PhD thesis. University of Oxford, 2018 (cit. on p. 29).

[Oda69] T. Oda. "The first de Rham cohomology group and Dieudonné modules". In: *Annales scientifiques de l'École Normale Supérieure*. Vol. 2. 1. 1969, pp. 63-135 (cit. on pp. 13, 15).

[Onu21] H. Onuki. "On oriented supersingular elliptic curves". In: *Finite Fields and Their Applications* 69 (2021), p. 101777 (cit. on p. 20).

[OM22] H. Onuki and T. Moriya. "Radical isogenies on Montgomery curves". In: *IACR International Conference on Public-Key Cryptography*. Lecture Notes in Computer Science 13177. Springer. 2022, pp. 473-497 (cit. on p. 12).

[ON24] H. Onuki and K. Nakagawa. "Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign". In: *Cryptology ePrint Archive* (2024) (cit. on pp. 1, 22, 52).

[PR23a] A. Page and D. Robert. "Clapotis: Evaluating the isogeny class group action in polynomial time". Nov. 2023 (cit. on pp. 20, 24, 58).

[PR23b] A. Page and D. Robert. "Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time". Nov. 2023 (cit. on pp. 1, 7, 8, 21-23, 39, 53).

[PW24] A. Page and B. Wesolowski. "The supersingular endomorphism ring and one endomorphism problems are equivalent". In: *Annual International Conference on the Theory and Applications of Cryptographic Techniques*. Springer. 2024, pp. 388-417 (cit. on pp. 1, 27, 37).

[Pei20] C. Peikert. "He gives C-sieves on the CSIDH". In: *Annual international conference on the theory and applications of cryptographic techniques*. Springer. 2020, pp. 463-492 (cit. on p. 19).

[PT18] P. Pollack and E. Treviño. "Finding the Four Squares in Lagrange's Theorem". In: *Integers* 18 (2018), A15 (cit. on p. 34).

[Pri24] V. Pribanic. "Radical isogenies and modular curves". In: *Advances in Mathematics of Communications* 18 (2024), pp. 1748-1767 (cit. on p. 12).

[RS86] M. O. Rabin and J. O. Shallit. "Randomized algorithms in number theory". In: *Communications on Pure and Applied Mathematics* 39.S1 (1986), S239-S256 (cit. on p. 34).

[RSSB16] J. Renes, P. Schwabe, B. Smith, and L. Batina. "$\mu$Kummer: Efficient Hyperelliptic Signatures and Key Exchange on Microcontrollers". In: *International Conference on Cryptographic Hardware and Embedded Systems*. Lecture
Notes in Computer Science 9813. Springer. 2016, pp. 301-320. DOI: 10.1007/978-3-662-53140-2_15 (cit. on p. 30).

[Ric36] F. Richelot. "Essai sur une méthode générale pour déterminer la valeur des intégrales ultra-elliptiques, fondée sur des transformations remarquables de ces transcendantes". In: C. R. Acad. Sci. Paris 2 (1836), pp. 622-627 (cit. on p. 29).

[Ric37] F. Richelot. "De transformatione Integralium Abelianorum primiordinis commentation". In: J. reine angew. Math. 16 (1837), pp. 221-341 (cit. on p. 29).

[Rob21] D. Robert. "Efficient algorithms for abelian varieties and their moduli spaces". HDR thesis. Université Bordeaux, June 2021. URL: http://www.normalesup.org/~robert/pro/publications/academic/hdr.pdf. Slides: 2021-06-HDR-Bordeaux.pdf (1h, Bordeaux). (Cit. on pp. 2, 7, 13, 16, 28, 29, 31, 45, 59).

[Rob22a] D. Robert. "Evaluating isogenies in polylogarithmic time". Aug. 2022 (cit. on pp. 3, 8, 26, 34).

[Rob22b] D. Robert. "Some applications of higher dimensional isogenies to elliptic curves (overview of results)". Dec. 2022 (cit. on pp. 1, 8, 16, 34, 37, 38, 59).

[Rob23a] D. Robert. "A note on optimising 2ⁿ-isogenies in higher dimension". June 2023. URL: http://www.normalesup.org/~robert/pro/publications/notes/2023-06-optimising_isogenies.pdf (cit. on pp. 29, 30).

[Rob23b] D. Robert. "Breaking SIDH in polynomial time". In: Eurocrypt 2023 (Apr. 2023). Ed. by C. Hazay and M. Stam, pp. 472-503. DOI: 10.1007/978-3-031-30589-4_17 (cit. on pp. 1-3, 7, 26, 27, 32, 47).

[Rob23c] D. Robert. "The geometric interpretation of the Tate pairing and its applications". Feb. 2023 (cit. on p. 12).

[RS06] A. Rostovtsev and A. Stolbunov. "Public-key cryptosystem based on isogenies". In: International Association for Cryptologic Research. Cryptology ePrint Archive (2006). eprint: http://eprint.iacr.org/2006/145 (cit. on p. 19).

[Sch95] R. Schoof. "Counting points on elliptic curves over finite fields". In: J. Théor. Nombres Bordeaux 7.1 (1995), pp. 219-254 (cit. on p. 14).

[Sh099] V. Shoup. "Efficient computation of minimal polynomials in algebraic extensions of finite fields". In: Proceedings of the 1999 international symposium on Symbolic and algebraic computation. 1999, pp. 53-58 (cit. on pp. 18, 44).

[Smio8] B. Smith. "Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves". In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2008, pp. 163-180. arXiv: 0806.2995 [math.NT] (cit. on p. 29).

[Stacks] T. Stacks Project Authors. Stacks Project. https://stacks.math.columbia.edu. 2018 (cit. on p. 58).

[Sut11] A. Sutherland. "Structure computation and discrete logarithms in finite abelian *p*-groups". In: Mathematics of Computation 80.273 (2011), pp. 477-500 (cit. on p. 45).

[Sut13a] A. Sutherland. "Isogeny volcanoes". In: The Open Book Series 1.1 (2013), pp. 507-530 (cit. on p. 18).

[Sut13b] A. Sutherland. "On the evaluation of modular polynomials". In: The Open Book Series 1.1 (2013), pp. 531-555 (cit. on p. 16).
[Tat67] J. T. Tate. "p-Divisible groups". In: *Proceedings of a conference on Local Fields*. Springer. 1967, pp. 158-183 (cit. on p. 15).

[Tia20] S. Tian. "Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with (ℓ, ℓ, ℓ)-isogenies". 2020. arXiv: 2007.03172 [math.AG] (cit. on p. 29).

[Tia24] S. Tian. "Computing gluing and splitting (ℓ, ℓ)-isogenies". In: *Designs, Codes and Cryptography* (2024), pp. 1-21 (cit. on p. 29).

[UJ18] D. Urbanik and D. Jao. "SoK: The problem landscape of SIDH". In: *Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop*. 2018, pp. 53-60 (cit. on p. 5).

[Vél71] J. Vélu. "Isogénies entre courbes elliptiques". In: *Compte Rendu Académie Sciences Paris Série A-B* 273 (1971), A238-A241 (cit. on pp. 10, 11).

[Voi21] J. Voight. *Quaternion algebras*. Springer Nature, 2021 (cit. on p. 19).

[Wat69] W. Waterhouse. "Abelian varieties over finite fields". In: *Ann. Sci. Ecole Norm. Sup.* 2.4 (1969), pp. 521-560 (cit. on p. 19).

[Wes22] B. Wesolowski. "The supersingular isogeny path and endomorphism ring problems are equivalent". In: *2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)*. IEEE. 2022, pp. 1100-1111 (cit. on pp. 7, 21, 50).

[ZSPDB18] G. H. Zanon, M. A. Simplicio, G. C. Pereira, J. Doliskani, and P. S. Barreto. "Faster isogeny-based compressed key agreement". In: *International Conference on Post-Quantum Cryptography*. Vol. 68. 5. Springer. IEEE, 2018, pp. 688-701 (cit. on p. 46).

[Zar74] J. G. Zarhin. "A remark on endomorphisms of abelian varieties over function fields of finite characteristic". In: *Mathematics of the USSR-Izvestiya* 8.3 (1974), p. 477 (cit. on p. 2).

INRIA BORDEAUX-SUD-OUEST, 200 AVENUE DE LA VIEILLE TOUR, 33405 TALENCE CEDEX FRANCE

Email address: damien.robert@inria.fr

URL: http://www.normalesup.org/~robert/

INSTITUT DE MATHÉMATIQUES DE BORDEAUX, 351 COURS DE LA LIBERATION, 33405 TALENCE CEDEX FRANCE