# Efficient post-quantum commutative group actions from orientations of large discriminant

Marc Houben

► To cite this version:

Marc Houben. Efficient post-quantum commutative group actions from orientations of large discriminant. ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Dec 2025, Melbourne (AUS), Australia. pp.141-173, 10.1007/978-981-95-5113-2_5. hal-05527402

HAL Id: hal-05527402

https://inria.hal.science/hal-05527402v1

Submitted on 25 Feb 2026

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 CC BY 4.0 - Attribution - International License
Efficient post-quantum commutative group
actions from orientations of large discriminant

Marc Houben

Inria Bordeaux, Institut de Mathématiques de Bordeaux, France

marc.houben@math.u-bordeaux.fr

**Abstract.** We describe an algorithm to efficiently evaluate class group actions on supersingular elliptic curves that are oriented by an imaginary quadratic order of arbitrarily large discriminant. Contrary to CSIDH, this allows to increase the post-quantum security of the group action without increasing the size of the base field. In particular, we describe instances where Kuperberg's algorithm loses to generic supersingular isogeny path finding. Our algorithm is fully deterministic, strictly constant time, dummy free, and can be implemented without conditional branches. We show that the (restricted effective) group action can be employed in a non-interactive key exchange protocol, that we argue is asymptotically more efficient than CSIDH.

**Keywords:** Isogeny-based cryptography, orientations, class group actions

# 1 Introduction

Isogeny-based cryptography is an area of post-quantum cryptography. At the origin of the field lies CRS [39,75], a key exchange scheme based on class group actions on ordinary elliptic curves. CSIDH [22] replaces ordinary curves with supersingular ones, giving rise to the first efficient variant of the protocol. Compared to other post-quantum candidates, CSIDH's main selling points are its small public keys and that it is *non-interactive*. The latter feature is especially compelling; the only practical lattice-based scheme providing a non-interactive key exchange is SWOOSH [48], but it uses public keys that are several orders of magnitude larger. CSIDH's main flaw is that it admits subexponential quantum attacks, due to Kuperberg's algorithm [54,55,72]. Although the precise post-quantum security of CSIDH is still subject of debate [8,10,70], recent analyses [26] are rather unfavorable. This has led to present-day work adopting large parameter choices [12,13], severely impacting estimates of the practical performance. The analysis [12, Sec. 7] concludes that — unless significant practical improvements are made — CSIDH is unlikely to be practical in real-world applications, except from niche cases where a non-interactive protocol is required. This despite an already large body of existing research dedicated to practical optimizations of the protocol [64,18,17,29,44,63,68,8,25,50,30,28,4,12,13].
The main problem is that the subexponential quantum attacks force us to sig-
nificantly increase the size of the base field $\mathbf{F}_p$. In CSIDH, we act on supersin-
gular elliptic curves over $\mathbf{F}_p$ by the class group $\text{Cl}(\mathcal{O})$ of the imaginary order
$\mathcal{O} = \mathbf{Z}[\pi]$, where $\pi$ denotes the $p$-Frobenius endomorphism. The size of $\text{Cl}(\mathcal{O})$
is roughly proportional to $|\text{Disc}(\mathcal{O})|^{1/2}$, where $\text{Disc}(\mathcal{O}) = \text{Disc}(\pi) = -4p$. Since
Kuperberg's algorithm is subexponential in $\#\text{Cl}(\mathcal{O})$, this forces the value of $p$
to be large. Recent estimates [26,12] of the required size to attain NIST level 1
range from 2048 to 4096 bits. A crucial factor as to CSIDH's inefficiency is that
arithmetic over fields of such large size comes at a significant cost, cf. [12, Sec.
5.2].

In the more general framework of class group actions on oriented elliptic curves, there are methods employing imaginary quadratic orders $\mathcal{O}$ different from the one generated by Frobenius, most notably (PEARL)-SCALLOP [41,27,3]. These schemes work with supersingular elliptic curves over $\mathbf{F}_{p^2}$ instead of over $\mathbf{F}_p$, but — by the method through which the orientation is represented — they are restricted by the similar upper bound $|\text{Disc}(\mathcal{O})| \le 4p^2$. A recent approach [21] manages to improve on this constraint, essentially by combining the CSIDH and (a generalization of) SCALLOP orientations. Concretely, they consider an orientation by $\mathcal{O} = \mathbf{Z}[\sqrt{-dp}]$, where $d \le p^2$. Although there are practical limitations, this allows for discriminants asymptotically of size $p^3$ (still over a base field of size $p^2$).

## Our Contributions.

(i) We describe a method to efficiently represent orientations that allows for the discriminant to be arbitrarily large, without increasing the size of the base field. We give a practical method to generate such representations on a supersingular base curve.

(ii) We describe an efficient algorithm for computing the associated restricted effective class group action. It is based on an extension of a recent technique [49] for the CSIDH group action. In particular, the algorithm is fully deterministic, strictly constant time, dummy free, does not have conditional branches, and allows for the evaluation of arbitrary exponent vectors. Moreover, increasing the bitsize of the discriminant by a factor $r$ comes at a cost factor $r$ that parallelizes perfectly across $r$ processors.

(iii) Employing the class group action, we instantiate a non-interactive key exchange protocol which is asymptotically more efficient than CSIDH. We provide a practical example for a 4096-bit discriminant. Our unoptimized proof-of-concept SageMath [81] implementation outperforms an unoptimized SageMath implementation of dCSIDH-4096 [12] by a factor 7 (both running on a single core of a laptop CPU).

**Main idea.** We will now describe the main ideas behind our approach. Let $p$ be a prime number for which $p+1$ has many small prime divisors. For example,
the CSIDH-512 prime

$$p = 4 \cdot \underbrace{(3 \cdot 5 \cdots 373)}_{73 \text{ consecutive primes}} \cdot 587 - 1 \approx 2^{511}.$$

Let $\mathbf{F}_q = \mathbf{F}_{p^2}$ and let $E/\mathbf{F}_q$ be a supersingular elliptic curve for which $E(\mathbf{F}_q) \cong (\mathbf{Z}/(p+1)\mathbf{Z})^2$. Say that we want to represent a (primitive) orientation on $E$ by an imaginary quadratic order $\mathcal{O} = \mathbf{Z}[\sigma]$ of large discriminant. That is, we want to represent a (cyclic) endomorphism $\sigma$ of $E$ for which

$$|\mathrm{Disc}(\sigma)| = 4 \deg(\sigma) - \mathrm{tr}(\sigma)^2$$

is large. It should be stressed that, in what follows, we will only be concerned with how to represent such an orientation. How to find one (on a given elliptic curve $E$) is a different question (and in practice requires knowledge of the endomorphism ring of $E$); this will be discussed in Section 4. The main goal for now is to describe a representation that can be efficiently carried through the class group action.

Assuming that the trace of $\sigma$ can be chosen small, we are concerned with representing endomorphisms of large degree. A natural first approach would be to represent such an endomorphism by its kernel $K$. However, if we want that $\langle K \rangle \subseteq E(\mathbf{F}_q)$ (for example, if we want to use Vélu isogeny formulae to evaluate the endomorphism using $\mathbf{F}_q$-arithmetic), then this restricts the degree by $\deg(\sigma) \le p+1$. A trick appearing in (PEARL)-SCALLOP [41,3] is to represent $\sigma$ as a composition of two isogenies $\tilde{\varphi}_2 \circ \varphi_1$, where we are given the kernels of $\varphi_1$ and $\varphi_2$; this allows for a degree up to $(p+1)^2$.

The first crucial observation is that nothing stops us from decomposing the endomorphism into even more isogenies. Write $M = \prod_{i=1}^n \ell_i = (p+1)/4$ for the product of the odd prime divisors of $p+1$, so that $E[M] \subseteq E(\mathbf{F}_q)$. Let $\sigma$ be an endomorphism of degree $M^r$, represented as a chain of $r$ isogenies

$$E = E_1 \xrightarrow{\varphi_1} E_2 \xrightarrow{\varphi_2} \dots \xrightarrow{\varphi_{r-1}} E_r \xrightarrow{\varphi_r} E_{r+1} = E,$$

each of degree $M$, where $\mathrm{ker} \varphi_j = \langle P_j \rangle$ for $P_j \in E_j(\mathbf{F}_q)$. By choosing $r$ large enough, this allows for a representation of an endomorphism of arbitrarily large degree. Note that such endomorphisms can be efficiently evaluated using only $\mathbf{F}_q$-arithmetic, by computing them as chains of $\ell_i$-isogenies whose kernels are generated by $\mathbf{F}_q$-rational points.

We are now going to describe how to evaluate the class group action coming from $\mathcal{O}$-ideals, in such a way that we can always keep track of the orientation. The main idea is based on [49, Algorithm 2], which handles the case $r = 2$. Let us denote by $Q_j \in E_j(\mathbf{F}_q)$ a point generating the kernel of the dual isogeny $\tilde{\varphi}_{j-1}$; see Figure 1. Let $\ell_i | M$ be one of the small primes. The principal $\mathcal{O}$-ideal generated by $\ell_i$ factors as

$$(\ell_i) = (\ell_i, \sigma)(\ell_i, \hat{\sigma}) = \ell_i \overline{\ell_i}.$$
<figure><img src="image_2.png" /><figcaption>Fig. 1: Graphical representation of a full kernel representation of an endomorphism of length $r = 4$.</figcaption></figure>

Note that the isogeny $\varphi_1 : E_1 \to E_2$ corresponds to an action by the $O$-ideal $\prod_{i=1}^n \mathfrak{l}_i = (M, \sigma)$, because the kernel $\langle P_1 \rangle$ of $\varphi_1$ is $\ker \sigma \cap E_1[M]$. In CSIDH's exponent vector notation, where the vector $(s_1, \dots, s_n)$ corresponds to the ideal $\prod_{i=1}^n \mathfrak{l}_i^{s_i}$, this corresponds to $(1, \dots, 1)$. Similarly, the isogeny $\widehat{\varphi}_1$, whose kernel is generated by $Q_2$, corresponds to the action by the ideal $\prod_{i=1}^n \bar{\mathfrak{l}}_i$ on $E_2$, with exponent vector $(-1, \dots, -1)$.

Suppose now that we want to evaluate the action on $E_1$ by an ideal of the form $\mathfrak{a} = \prod_{i=1}^n \mathfrak{l}_i^{s_i}$, where the exponent vector $(s_1, \dots, s_n) \in \{0, 1\}^n$ is binary. The ideal corresponds to an isogeny $\varphi_1^+ : E_1 \to E_1'$ of degree $d = \prod_{i=1}^n \ell_i^{s_i}$, and its kernel is generated by the point $[M/d] P_1 \in E_1$. Note that the codomain can also be expressed as $E_1' = \prod_{i=1}^n \bar{\mathfrak{l}}_i^{1-s_i} E_2$, corresponding to the action by the ideal with exponent vector $(s_1-1, \dots, s_n-1)$ on $E_2$. The latter corresponds to an isogeny $\varphi_1^- : E_2 \to E_1'$ with kernel generated by $[d]Q_2$.

Now, under the crucial assumption that $\langle P_j \rangle \cap \langle Q_j \rangle = \{0\},^1$ we find that $Q_1' := \varphi_1^+(Q_1) \in E_1'$ has order $M$, and similarly for $P_1' := \varphi_1^-(P_2) \in E_1'$. In fact, as we will see, we have that $\langle P_1' \rangle = E_1'[M, \sigma]$ and $\langle Q_1' \rangle = E_1'[M, \hat{\sigma}]$, for the induced $O$-orientation on $E_1'$ (Proposition 2.1).

We have essentially “factored” the isogeny $\varphi_1 : E_1 \to E_2$ as $E_1 \xrightarrow{\varphi_1^+} E_1' \xleftarrow{\varphi_1^-} E_2$. Applying the same trick to every isogeny $\varphi_j : E_j \to E_{j+1}$ in the chain, we recover a representation of an $O$-orientation on $E' = \mathfrak{a}*E$; see Figure 2. Iterating the procedure we can compute the action by any ideal class $(s_1, \dots, s_n) \in \mathbb{Z}_{\ge 0}^n$.

Assuming every isogeny $\varphi_j^\pm$ is computed as a chain of $\ell_i$-isogenies, the cost of acting by a binary ideal class is essentially one evaluation of the endomorphism $\sigma$. Since $\sigma$ has degree $M^r$, it is $r$ times the cost of a CSIDH-512 group action.<fnref n="2" /> This method of increasing the discriminant is asymptotically cheaper than increasing the size of the base field, because finite field arithmetic scales at best quasi-

<footnote n="1">¹ This turns out to be equivalent to the statement that none of the $\ell_i$ ramify in the class group; this holds in particular when $\deg(\sigma)$ and $\text{tr}(\sigma)$ are coprime.</footnote>

<footnote n="2">² If we use dCSIDH [12] or [49, Algorithm 3]. This does not (yet) take into account the crucial caveat that we are required to work over $\mathbb{F}_{p^2}$ instead of over $\mathbb{F}_p$.</footnote>
linearly in the size of the field (in practice, the cost increases significantly, see [12, Sec. 5.2]). Theoretically, we can choose $r$ large enough for Kuperberg's algorithm to lose to generic supersingular isogeny path finding algorithms; a precise trade-off will be discussed in Sections 5.2 and 6.

**Outline.** In Section 2 we recall the theory of orientations and their associated class group actions. In Section 3 we present our algorithm for computing the restricted effective class group action. Section 4 describes how to practically instantiate an orientation on a base curve. In Section 5 we discuss a non-interactive key exchange protocol based on the class group action, and perform a security analysis. We also describe how to compress (and decompress) public keys to bitsize $\approx (r+2)\log_2(p)$. In Section 6 we describe practical parameters for an efficient class group action. Finally, in Section 7, we present opportunities for future work.

**Acknowledgements.** We thank Damien Robert for helpful discussions, and Krijn Reijnders for feedback on an earlier version of the paper. Special thanks to Bruno Sterner for finding the prime number used in the example of Section 6.3. This work was financially supported by the France 2030 program, managed by the French National Research Agency under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

# 2 Preliminaries

Let $k$ be a perfect field. Our main references concerning the theory of orientations are [34,67].

## 2.1 Isogenies

An isogeny is a non-constant morphism of elliptic curves. Given an elliptic curve $E/k$, isogenies $\varphi$ with domain $E$ are uniquely determined up to post-composition by an isomorphism by their scheme-theoretic kernel, denoted $E[\varphi]$. For separable isogenies $\varphi: E \to E'$, this is the usual (group-theoretic) kernel, consisting of all points in $E(\bar{k})$ that map to the identity element $0 \in E'(k)$. In this case, the cardinality of the kernel equals the degree $\deg \varphi$. We often identify separable isogenies with their kernel, even though this only well-defines the underlying map up to post-composition by an isomorphism. An endomorphism of an elliptic curve $E$ is an isogeny from $E$ to itself, or the zero map. We denote by $\text{End}(E) = \text{End}_{\bar{k}}(E)$ the full endomorphism ring of $E$, consisting of all endomorphisms defined over $\bar{k}$, where the ring structure is given by point-wise addition and composition.

## 2.2 Orientations

Let $E/k$ be an elliptic curve and let $K$ be an imaginary quadratic number field. A $K$-orientation is a (necessarily injective) ring homomorphism

$$ \iota: K \to \text{End}^0(E) := \text{End}(E) \otimes_{\mathbb{Z}} \mathbb{Q}. $$
The pair $(E, \iota)$ is called a $K$-oriented elliptic curve. If $(E, \iota)$ is a $K$-oriented elliptic curve, and $\varphi : E \to E'$ is an isogeny, then the $K$-orientation induced by $\varphi$ on $E'$, denoted $\varphi_*(\iota)$, is given by

$$ \varphi_*(\iota)(\alpha) := \varphi \circ \iota(\alpha) \circ \hat{\varphi} \otimes \frac{1}{\deg(\varphi)}. \qquad (1) $$

Given two $K$-oriented elliptic curves $(E, \iota)$ and $(E', \iota')$, a $K$-oriented isogeny is an isogeny $\varphi : E \to E'$ for which $\varphi_*(\iota) = \iota'$.

If $(E, \iota)$ is a $K$-oriented elliptic curve and $O \subseteq K$ is an imaginary quadratic order, we call $\iota$ an $O$-orientation if $\iota(O) \subseteq \text{End}(E)$. If $(E, \iota)$ is an $O$-orientation, then for $\sigma \in O \setminus \{0\}$ we have $\deg \iota(\sigma) = N(\sigma)$, where $N = N_{K/Q} : K \to Q$ denotes the algebraic norm. Moreover, we have $\iota(\bar{\sigma}) = \iota(\bar{\sigma})$, where $\bar{\sigma}$ denotes the (unique) conjugate (in $K/Q$) and $\hat{\sigma}$ denotes the dual isogeny. We will also write $\hat{\sigma}$ for $\bar{\sigma}$. An $O$-orientation is called primitive if it does not extend to a strictly larger imaginary quadratic order. That is, for any strict superorder $O' \supsetneq O$ in $K$, we have that $\iota(O') \not\subseteq \text{End}(E)$. A $K$-orientation is primitive for a unique order, called the primitive order, given by $O_{\text{pr}} := \iota^{-1}(\text{End}(E))$. If $\varphi : (E, \iota) \to (E', \iota')$ is a $K$-oriented isogeny of prime degree $\ell$, then exactly one of the following is true:

(i) $O_{\text{pr}} = O'_{\text{pr}}$, in which case $\varphi$ is called horizontal;

(ii) $O_{\text{pr}} \subsetneq O'_{\text{pr}}$ and $[O'_{\text{pr}} : O_{\text{pr}}] = \ell$, in which case $\varphi$ is called ascending;

(iii) $O'_{\text{pr}} \subsetneq O_{\text{pr}}$ and $[O_{\text{pr}} : O'_{\text{pr}}] = \ell$, in which case $\varphi$ is called descending.

In general, a $K$-oriented isogeny of composite degree may be any composition of the three above types of isogenies. In case the primitive orders of the domain and codomain are comparable, in the sense that one is contained in the other, we will use the same terminologies (horizontal, ascending, descending) to describe the corresponding isogeny.

## 2.3 Class group actions

Let $O$ be an order in an imaginary quadratic number field $K$, and let $(E, \iota)$ be an $O$-oriented elliptic curve. If $a \subseteq O$ is an ideal of norm coprime to $\text{char } k$, we define its kernel by

$$ E[a] := \bigcap_{\alpha \in a} E[\iota(\alpha)], $$

and denote by $\varphi_a : E \to E'$ an isogeny with kernel $E[a]$. The codomain curve $E'/k$, unique up to isomorphism, is also denoted $a * E$. The induced $K$-oriented isogeny

$$ (E, \iota) \to (a * E, (\varphi_a)_*(\iota)) $$

is horizontal if and only if $a$ is invertible (if $a$ is not invertible, then it is ascending) [67, Prop. 3.5]. Moreover, if $b$ is an equivalent $O$-ideal, then

$$ (a * E, (\varphi_a)_*(\iota)) \cong (b * E, (\varphi_b)_*(\iota)) $$
as K-oriented elliptic curves. This induces an action

$$ \mathrm{Cl}(\mathcal{O}) \subsetneq \{(E, \iota) \mid E/\bar{k} \text{ ell. curve, } \iota \text{ an } \mathcal{O}\text{-orientation}\} / \cong $$

by the ideal class group $\mathrm{Cl}(\mathcal{O})$ of $\mathcal{O}$ on the (possibly empty) set of $\mathcal{O}$-oriented elliptic curves over $\bar{k}$ up to $K$-oriented isomorphism. If we restrict to primitive $\mathcal{O}$-orientations, then this action is free. We will frequently make use of the following proposition.

**Proposition 2.1.** Let $\mathcal{O} = \mathbb{Z}[\sigma]$ be an imaginary quadratic order and let $(E, \iota)$ be a primitively $\mathcal{O}$-oriented elliptic curve over $k$. Assume that $N(\sigma)$ is coprime to both $\mathrm{char } k$ and $\mathrm{Disc}(\mathcal{O})$ (or, equivalently, to $\mathrm{char } k$ and $\mathrm{tr}(\sigma)$).

(a) We have $E[\iota(\sigma)] \cap E[\iota(\hat{\sigma})] = \{0\}$.

(b) If $m \in \mathbb{Z}_{>0}$ such that $m \mid N(\sigma)$, then the $\mathcal{O}$-ideal $\mathfrak{a} := (m, \sigma)$ is invertible. Moreover, denoting by $\varphi_{\mathfrak{a}} : E \to \mathfrak{a} * E$ the corresponding isogeny, we have $(\mathfrak{a} * E)[\iota'(\hat{\sigma})] = \varphi_{\mathfrak{a}}(E[\iota(\hat{\sigma})])$, where $\iota'$ denotes the orientation induced by $\varphi_{\mathfrak{a}}$.

*Proof.* (a) This follows from [49, Cor. 2.2].

(b) The statement that $\mathfrak{a}$ is invertible follows from the fact that $N(\sigma)$ is coprime to the conductor $f$ of $\mathcal{O}$ (indeed, $f \mid \mathrm{Disc}(\mathcal{O})$). The second statement follows from [49, Prop. 3.4]. $\square$

Given an $\mathcal{O}$-oriented curve $(E, \iota)$ and an element $\sigma \in \mathcal{O}$, we will also write $E[\sigma] := E[\iota(\sigma)] = E[(\sigma)]$ for the kernel of $\iota(\sigma)$. Similarly, if $(m, \sigma)$ is an $\mathcal{O}$-ideal, where $m \in \mathbb{Z}_{>0}$, we denote its kernel by $E[m, \sigma] := E[(m, \sigma)]$.

## 2.4 Representing orientations

Let $E/\mathbb{F}_q$ be an elliptic curve and let $\mathcal{O}$ be an imaginary quadratic order. We say an *effective representation* of an orientation $\iota : \mathcal{O} \hookrightarrow \mathrm{End}(E)$ consists of the following data:

(i) The minimal polynomial $f \in \mathbb{Z}[X]$ of a generator $\sigma$ of $\mathcal{O}$ (or, equivalently, the norm and trace of $\sigma$);

(ii) An algorithm to evaluate $\iota(\sigma)$ on any point $P \in E(\mathbb{F}_{q^r})$ for any $r \in \mathbb{Z}_{>0}$.

A related notion that appears in the literature is that of an *efficient representation*, which additionally requires that the evaluation algorithm (ii) executes in polynomial time, see [83, p. 7-8] for a precise definition. In this paper, our main focus will be on a specific type of effective (in fact, efficient) representation, where the endomorphism $\iota(\sigma)$ is given as a composition of isogenies of smooth degree, each given by an $\mathbb{F}_q$-rational point $P$ generating the kernel. We call this a *kernel representation*.
**Kernel representations.** For the purpose of the exposition, let us momentarily return to the general case where the base field is $k$. Let $E/k$ be an elliptic curve and let $\mathcal{O} = \mathbb{Z}[\sigma]$ be an imaginary quadratic order. An $\mathcal{O}$-orientation $\iota$ on $E$ is uniquely determined by the image of $\sigma$ as an element of $\text{End}(E)$. Suppose that the endomorphism $\iota(\sigma)$ of $E$ decomposes as a chain of isogenies

$$E = E_1 \xrightarrow{\varphi_1} E_2 \xrightarrow{\varphi_2} \dots \xrightarrow{\varphi_{r-1}} E_r \xrightarrow{\varphi_r} E_{r+1} = E,$$

for some $r \in \mathbb{Z}_{>0}$. Assuming that the orientation is primitive, each $\varphi_j$ is necessarily cyclic. In case points $P_j \in E_j(k)$ are given such that $\text{ker} \varphi_j = \langle P_j \rangle$, we call the sequence $\{(E_j, P_j) | 1 \le j \le r\}$ a kernel representation of the $\mathcal{O}$-orientation on $E$. The integer $r \in \mathbb{Z}_{>0}$ is called the length of the representation. If we are also given points $Q_j \in E_j(k)$ such that $\text{ker}(\varphi_{j-1}) = \langle Q_j \rangle$,<fnref n="3" /> then $\{(E_j, P_j, Q_j) | 1 \le j \le r\}$ is called a full kernel representation. Although a full kernel representation will in practice be (computationally) recoverable from the kernel representation, we record this notion because we will require the points $Q_j$ in our algorithm to compute the class group action. In SCALLOP [41, Definition 6] and PEARL-SCALLOP [3], the orientation admits a kernel representation of length $r = 2$. CSIDH [22] and CSURF [15] can be viewed as the case $r = 1$, if we choose the generators $\sigma = \pi - 1$ and $\sigma = \frac{\pi - 1}{2}$ respectively, where $\pi$ denotes the $p$-Frobenius endomorphism, cf. [49, Sec. 2.4].

### 3 Restricted effective group actions

Let $k$ be a perfect field. The goal of this section is to describe an algorithm to evaluate the (restricted effective) class group action on primitively oriented elliptic curves over $k$, assuming that the orientation is given by a kernel representation as described in Section 2.4. This can be seen as a generalization of [49], which considers the case $r \in \{1, 2\}$. Though in practice we will always work with elliptic curves over finite fields, we will describe the algorithms over the general base field $k$; all we require is that we can (efficiently) perform elliptic curve arithmetic over $k$ and compute isogenies from their kernel (e.g. using Vélu's formulae [82]). More specifically, we assume that we have the following two black-box algorithms at our disposal.

(i) **Multiply**($E, P, N$). **Input:** an elliptic curve $E/k$, a point $P \in E(k)$, and an integer $N \in \mathbb{Z}_{>0}$. **Output:** $[N]P$.

(ii) **Isogeny**($E, \mathcal{L}, K, N$). **Input:** an elliptic curve $E/k$, a tuple of points $\mathcal{L} = (P_1, \dots, P_n)$, where $P_i \in E(k)$, and a kernel point $K \in E(k)$ of order $N \in \mathbb{Z}_{>0}$. **Output:** $E'$, $(\varphi(P_1), \dots, \varphi(P_n))$, where $E' \cong E/\langle K \rangle$ is the codomain of a cyclic isogeny $\varphi: E \to E'$ with kernel $\langle K \rangle$.

Note that the algorithm **Isogeny** depends intrinsically on $n$, the length of the evaluation tuple. We will mainly consider the case $n = 2$. In particular, if we denote by $R = (E, P, Q)$ a triple where $E/k$ is an elliptic curve an $P, Q \in E(k)$, we will

<footnote n="3">³ Here we adopt the notational convention that $\varphi_0 = \varphi_r$.</footnote>
also write $\mathrm{Isogeny}(R, K, N)$ for the function that calls $\mathrm{Isogeny}(E, (P, Q), K, N)$ and returns the triple $R' = (E', \varphi(P), \varphi(Q))$.

## 3.1 The imaginary quadratic order

Let $M, r \in \mathbb{Z}_{>0}$ and let $\mathcal{O} = \mathbb{Z}[\sigma]$ be an imaginary quadratic order generated by an element $\sigma$ of norm

$$N(\sigma) = M^r.$$

In practical instantiations, the integer $M$ will always be smooth and $r$ will always be small. We will assume throughout that

$$\gcd(M, \mathrm{Disc}(\mathcal{O})) = 1. \qquad (2)$$

This is equivalent to $\gcd(N(\sigma), \mathrm{tr}(\sigma)) = 1$. Write

$$M = \prod_{i=1}^{n} \ell_{i}^{e_{i}}$$

for the prime factorization of $M$. Then (2) implies that the principal $\mathcal{O}$-ideal generated by $\sigma$ factors as

$$(\sigma) = \prod_{i=1}^{n} (\ell_i, \sigma)^{r e_i} = \prod_{i=1}^{n} \ell_i^{r e_i} = \mathfrak{e}^r,$$

where

$$\mathfrak{e} := \prod_{i=1}^{n} \ell_i^{e_i} \qquad (3)$$

and each $\ell_i := (\ell_i, \sigma)$ is an invertible $\mathcal{O}$-ideal. We will also write $\bar{\ell}_i = (\ell_i, \bar{\sigma})$ for the conjugate ideals.

## 3.2 The kernel representation

Let $\mathcal{O} = \mathbb{Z}[\sigma]$ as above. Suppose that the characteristic of $k$ is coprime to $M$ and let $E/k$ primitively oriented by $\mathcal{O}$. The cyclic endomorphism $\iota(\sigma)$ can be decomposed into a sequence of $r$ isogenies of degree $M$. Explicitly, if $P \in E(\bar{k})$ is a generator for $E[\sigma]$, then $\iota(\sigma) = \varphi_r \circ \dots \circ \varphi_1$, where $\ker \varphi_1 = \langle M^{r-1}P \rangle$ and

$$\ker \varphi_j = \langle M^{r-j} \varphi_{j-1} \circ \dots \circ \varphi_1(P) \rangle = E[M] \cap \langle \varphi_{j-1} \circ \dots \circ \varphi_1(P) \rangle.$$

Defining $P_j := M^{r-j} \varphi_{j-1} \circ \dots \circ \varphi_1(P)$, we have that $\{(E_j, P_j) \mid 1 \le j \le r\}$ is a kernel representation of the $\mathcal{O}$-orientation on $E$. Each $\varphi_j$ is necessarily horizontal; in fact, it corresponds to the action by the ideal $\mathfrak{e}$ as in (3), that is,

$$\ker \varphi_j = \langle P_j \rangle = E_j[M, \sigma] = E_j[\mathfrak{e}].$$
### 3.3 Evaluating the class group action

Adopting the notation of the previous section, let $Q_j \in E_j(\bar{k})$ such that $\langle Q_j \rangle = \ker \tilde{\phi}_{j-1}$, so that $\{(E_j, P_j, Q_j)\}$ is a full kernel representation of the $\mathcal{O}$-orientation on $E$. Assume moreover that $P_j, Q_j \in E_j(k)$ for all $j$. Let $\mathfrak{a}$ be an ideal of the form

$$ \mathfrak{a} = \prod_{i=1}^{n} \ell_i^{s_i}, $$

where $0 \le s_i \le e_i$ for all $1 \le i \le n$. We are going to describe an algorithm to compute $E' := \mathfrak{a} * E$ together with a full kernel representation $\{(E'_j, P'_j, Q'_j)\}$ of the induced $\mathcal{O}$-orientation on $E'$ (where $E'_j = E'$). Denote by $d = \prod_{i=1}^{n} \ell_i^{s_i}$ the norm of $\mathfrak{a}$. Since $E_1[\mathfrak{a}] \subseteq E_1[\mathfrak{e}] = E_1[M, \sigma]$, the latter being cyclic and generated by $P_1$, we have

$$ E_1[\mathfrak{a}] = \langle [M/d]P_1 \rangle. $$

Denote by $\varphi_1^+ : E_1 \to E'_1$ the corresponding isogeny. Now consider the $\mathcal{O}$-ideal $\mathfrak{b} := \prod_{i=1}^{n} \ell_i^{e_i-s_i}$. Since $\mathfrak{e} = \mathfrak{a}\mathfrak{b}$, we have $[\mathfrak{b}]*E'_1 \cong [\mathfrak{e}]*E_1 \cong E_2$, hence $\bar{\mathfrak{b}}*E_2 \cong E'_1$. The isogeny $\varphi_1^- : E_2 \to E'_1$ corresponding to the action by $\bar{\mathfrak{b}}$ on $E_2$ has kernel

$$ E_2[\bar{\mathfrak{b}}] = \langle [d]Q_2 \rangle. $$

Similarly, for any $1 \le j \le r$, we define isogenies

$$ E_j \xrightarrow{\varphi_j^+} E'_j \xleftarrow{\varphi_j^-} E_{j+1}, \qquad (4) $$

with kernels $\langle[M/d]P_j\rangle$ and $\langle dQ_{j+1}\rangle$ respectively, corresponding to the action by $\mathfrak{a}$ on $E_j$ and $\bar{\mathfrak{b}}$ on $E_{j+1}$ respectively. We set $P'_j := \varphi_j^-(P_{j+1})$ and $Q'_j := \varphi_j^+(Q_j)$.<fnref n="4" />

**Proposition 3.1.** The data $\{(E'_j, P'_j, Q'_j)\}$ as defined above is a full kernel representation of the $\mathcal{O}$-orientation on $E'$ induced by the isogeny $\varphi_{\mathfrak{a}} : E \to E'$.<fnref n="4" />

*Proof.* It follows from Proposition 2.1 that

$$ \langle P'_j \rangle = E_j[M, \sigma] = E_j[\mathfrak{e}] \quad \text{and} \quad \langle Q'_j \rangle = E_j[M, \bar{\sigma}] = E_j[\bar{\mathfrak{e}}]. \qquad (5) $$

Now note that

$$ E'_{j+1} \cong [\mathfrak{a}] * E_{j+1} \cong [\mathfrak{a}] * [\mathfrak{e}] * E_j \cong [\mathfrak{e}] * [\mathfrak{a}] * E_j \cong [\mathfrak{e}] * E'_j, $$

hence $E'_{j+1} \cong E'_j/\langle P'_j \rangle$. Finally, by (5), the isogenies corresponding to $\langle P_j \rangle$ and $\langle Q_{j+1} \rangle$ are necessarily dual to each other. □

Since $M = \prod_{i=1}^{n} \ell_i^{e_i}$, any isogeny of degree dividing $M$ is a composition of some amount of $\ell_i$-isogenies for various $i$. This applies in particular to the isogenies $\varphi_j^+$ and $\varphi_j^-$, whose degrees are $d$ and $M/d$ respectively. From a computational

<footnote n="4">⁴ By notational convention, we say $E_{r+1} = E_1$, $P_{r+1} = P_1$, and $Q_{r+1} = Q_1$.</footnote>
perspective, the total number of $\ell_i$-isogenies required to compute both $\varphi_j^+$ and $\varphi_j^-$ is independent of $d$ (it is equal to $e_i$). If we call the factors of $\varphi_j^+$ and $\varphi_j^-$ positive and negative isogenies respectively, then the decomposition (4) is completely determined by the number of positive $\ell_i$-isogenies (this is $s_i$). Algorithmically, for each value of $j$, we will always perform $e_i$ isogenies of degree $\ell_i$, and switch between the sign (positive or negative) of the isogeny using a conditional swap (cswap) function. This gives rise to Algorithm 1 for computing the class group action on $O$-oriented elliptic curves. Here $R_0$ and $R_1$ represent abstract memory registers that store elliptic curves together with torsion points, and we understand $R[j]$ to mean the $j$-th element of the register, starting at zero. The function cswap$(R_0, R_1, b)$ swaps the contents of the registers if the boolean $b$ is 1.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Computing $E'_1 = [\mathfrak{a}]*E_1$ while keeping track of a full kernel representation of the orientation.</figcaption></figure>

**Algorithm 1 for humans.** Consider the algorithm as described in Algorithm 1 and graphically depicted in Figure 2. The outer loop of the algorithm iterates over the (outer) edges of the square, each corresponding to an isogeny $E_j \xrightarrow{\varphi_j} E_{j+1}$. Let us consider what happens for $j = 1$. The goal of the algorithm is to factor the isogeny $\varphi_1$ into an isogeny $\varphi_1^+$ of degree $d$ and (the dual of) an isogeny $\varphi_1^-$ of degree $M/d$.

**The setup.** The two memory registers $R_0$ and $R_1$ store elliptic curves together with torsion points. Initially, they correspond to the curves $E_1$ and $E_2$ respectively, together with a full $M$-torsion basis on each curve. The point $P_1$,
<caption>**Algorithm 1 Evaluating the class group action on full kernel representations**</caption>

**Input:** A full kernel representation $\{(E_j, P_j, Q_j) \mid 1 \le j \le r\}$ of a $\mathbb{Z}[\sigma]$-orientation on $E$, together with a vector of integers $(s_1, \dots, s_n) \in [0, e_i]^n$.

**Output:** A full kernel representation $\{(E'_j, P'_j, Q'_j)\}$ of a $\mathbb{Z}[\sigma]$-orientation on $E' = [\prod_{i=1}^n \mathfrak{S}'_i] * E$.

**for** $j = 1, \dots, r$ **do**

$R_0 \leftarrow (E_j, P_j, Q_j)$;

$R_1 \leftarrow (E_{j+1}, Q_{j+1}, P_{j+1})$;

$m \leftarrow \prod_i \ell_i^{\ell_i}$;

**for** $i = 1, \dots, n$ **do**

**for** $t = 1, \dots, e_i$ **do**

$b \leftarrow t > s_i$;

$cswap(R_0, R_1, b)$;

$m \leftarrow m/\ell_i$; $K \leftarrow \text{Multiply}(R_0[1], m)$;

$R_0 \leftarrow \text{Isogeny}(R_0, K, \ell_i)$;

$R_1[1] \leftarrow \text{Multiply}(R_1[1], \ell_i)$;

$cswap(R_0, R_1, b)$;

end for

end for

$\text{assert } R_0[0] = R_1[0]$;

$R_0[1] \leftarrow R_1[2]$;

$R'_j \leftarrow R_0$;

end for

return $R'_1, \dots, R'_r$;

which is at index 1 in $R_0$, generates the kernel of the $M$-isogeny $\varphi_1 : E_1 \to E_2$. The point $Q_2$, which is at index 1 in $R_1$, generates the kernel of the $M$-isogeny $\widehat{\varphi}_1 : E_2 \to E_1$. Informally, we say that $E_1$ and $E_2$ are at distance $M$. This distance will be represented by the cofactor $m$ (which is indeed initialized at value $M$).

**Walking along the edge.** Each value of $i$ corresponds to one isogeny degree $\ell_i$. The algorithm always computes exactly $e_i$ isogenies of degree $\ell_i$. Depending on the value of $b$, the isogeny to be computed will be either a factor of $\varphi_1$ (i.e. walking to the right in Figure 2) or of $\varphi_1$ (i.e. walking to the left in Figure 2). The `cswap` function ensures that we are computing the correct isogeny. That is, it makes sure that the domain of the isogeny to be computed is (temporarily) stored in register $R_0$.

**The kernel point.** The kernel of the isogeny is generated by the point $K$ of order $\ell_i$, which is always obtained by multiplying the point at index 1 in $R_0$ by the cofactor; this is achieved by the first execution of the function `Multiply` in of the inner-most loop.

**Isogeny and Multiply.** The $\ell_i$-isogeny step, which consists of the execution of the function `Isogeny`, consists of computing the codomain curve, and evaluating the isogeny at both torsion points stored in $R_0$. This decreases the order of the point at index 1 by a factor $\ell_i$, while the point at index 2 always remains of order $M$. We then make sure that the point at index 1 in $R_1$ (which lives on
the other curve) also decreases by a factor of $\ell_i$; this is ensured by the (second) execution of Multiply.

**After one iteration.** At the end of the inner-most loop, the orders of the points at index 1 are equal to $m$; this is new *distance* between the curves stored in $R_0$ and $R_1$.

**Completing the algorithm.** After performing all iterations, the curves the two registers are equal (i.e. they are at *distance* 1) to $E'_1$. The points at index 2 form an $M$-torsion basis, which (partially) represents the $O$-orientation on $E'_1$. We store $E'_1$, together with the $M$-torsion basis, in the output register $R'_1$.

## 3.4 Complexity analysis

From a high-level point of view, we factor the isogeny $\iota(\sigma)$ into $2r$ isogenies $\varphi_j^{\pm}$ of smaller degree, and compute each as a composition of several $\ell_i$-isogenies, where every $\ell_i$-isogeny is evaluated at two points; one generating the kernel of the isogeny chain and one additional point. Since the product of the degrees of the $\varphi_j^{\pm}$ is $M^r$, this is essentially equivalent to computing the endomorphism $\iota(\sigma)$ as a chain of $\ell_i$-isogenies, and evaluating it at one point.

**Isogeny and Multiply.** Apart from the comparison $t > s_i$, the cost of the algorithm is dominated by calls to the functions Multiply and Isogeny. Although it seems we still require some integer divisions to determine the cofactors $m$, the sequence of cofactors is actually fixed and can thus be precomputed. Assuming that the running time of Multiply($-$, $N$) depends only on $N$ and Isogeny($-$, $-$, $\ell_i$) depends only on $\ell_i$, every iteration of the outer loop (indexed by $j$) runs in strictly constant time. In fact, these iterations are independent of each other, so theoretically parallelize perfectly across $r$ processors.

Let us analyze the complexity of one such iteration. By construction, we necessarily compute $e_i$ isogenies of degree $\ell_i$ and perform $e_i$ multiplications by a factor $\ell_i$ for every $1 \le i \le n$. In addition to this, there are cofactor multiplications by a predetermined list of (larger) integers $m$. In practical instantiations, we can partially mitigate the cost of these cofactor multiplications by a trade-off known as a *strategy*; in a nutshell, by splitting up the $M$-torsion into multiple components, we can reduce the size of the cofactors at the expense of evaluating the isogenies at more points. This is a trick originally introduced in SIDH for the computation of isogenies whose degree is a power of a prime, and “optimal” strategies are known in this setting [51, Sec. 4.2.2]. In case of a general isogeny of smooth degree, determining the optimal trade-off is a more complicated problem, and a significant amount of research has been done for the special case of CSIDH [63, 68, 50, 30, 28]. We remark that the best strategy depends on the value of $M$ and the practical complexities of Isogeny and Multiply.

<footnote n="5">⁵ These assumptions can be satisfied in practice if we use (optimal) differential addition chains for Multiply and Vélu [82] or $\sqrt{\ell}$-isogeny formulae for Isogeny, provided that we can perform field arithmetic in constant time.</footnote>
**Comparison to the CSIDH group action.** Back to a high-level point of view, let us consider what happens in the special case where the base field is a finite field $F_q = F_{p^2}$, where $M = \prod_{i=1}^n \ell_i$ (that is, $e_i = 1$ for all $i$) and $M \mid (p+1)$. Assume that we are working with supersingular elliptic curves with $(p+1)^2$ points, so that the kernel representation of the orientation can be defined over the base field. As we saw above, the cost of evaluating a binary ideal class $\prod_{i=1}^n \ell_i^{s_i}$, corresponding to an exponent vector $(s_1, \dots, s_n) \in \{0, 1\}^n$, is roughly equivalent to the evaluation of the endomorphism representing the orientation as a chain of $\ell_i$-isogenies. This endomorphism has degree $M^r$.

In dCSIDH [12] — the current state of the art for dummy-free constant-time CSIDH — a binary ideal class has exponent vector in $\{-1, 1\}^n$ (as opposed to $\{0, 1\}^n$). To evaluate it requires the computation of an isogeny of degree $M$ as a chain of $\ell_i$-isogenies, which is thus computationally comparable to the case $r = 1$. As we will see below, Algorithm 1 allows in practice to use orientations with discriminants that are larger (in bitsize) by a factor of $r$. By the above discussion, this comes at a computational cost factor of exactly $r$ (which can moreover be mitigated by parallelizing across $r$ processor cores). To increase the discriminant when restricting to CSIDH is asymptotically more expensive, since it requires to increase the size of the base field, which increases the cost of finite field arithmetic; the latter scales at best quasi-linearly with $r$.<fnref n="6" /> Here we remark that, if we are allowed to use dummy operations,<fnref n="7" /> there is an additional trick for constant-time CSIDH which is incompatible with Algorithm 1, using *Matryoshka isogenies* [8,4]. These are employed in dCTIDH [13], the current state of the art for constant-time CSIDH. We leave it to future work to see how an optimized implementation of Algorithm 1 fares in comparison to both dCSIDH and dCTIDH, although we do give a practical example in Section 6.3. Lastly, we remark that a version of Algorithm 1 can also be applied to CSIDH directly, cf. [49, Algorithm 3], where it enjoys several advantages compared to dCSIDH and dCTIDH; see [49, Sec. 4.2] for a discussion.

# 4 Generating public parameters

To obtain practical instantiations of the class group action described in Section 3, we require at least one primitively oriented elliptic curve, together with a kernel representation of the orientation. The goal of this section is to describe a method to find such instantiations. Let $p \equiv 3 \pmod 4$ be a prime number and let $M \mid (p+1)$ be a positive integer. Write

$$p+1 = \prod_{i=1}^{n} \ell_i^{f_i} \quad \text{and} \quad M = \prod_{i=1}^{n} \ell_i^{e_i}, \qquad (6)$$

<footnote n="6">⁶ An important remark is that the cost of a non-Frobenius orientation is already larger to begin with, since it requires to work over $F_{p^2}$. This overhead can be partially mitigated by using points on the *twist*; see Section 6.2.</footnote>

<footnote n="7">⁷ That is, operations whose results may be discarded but whose effect is to mask a variable running time. Such operations are potentially susceptible to *fault injections* [14,57,59,5,58].</footnote>
for the respective prime factorizations, where $0 \le e_i \le f_i$ for all $1 \le i \le n$. For all practical purposes, the number $M$ will be assumed smooth.

## 4.1 Orienting a base curve

Denote by $\mathbf{F}_q = \mathbf{F}_p(\sqrt{-1})$ a field with $p^2$ elements and let $E/\mathbf{F}_q$ be the supersingular elliptic curve $E: y^2 = x^3 + x$. Denote by $\pi: E \to E, (x, y) \mapsto (x^p, y^p)$ the $p$-Frobenius endomorphism and by $i: E \to E$ the automorphism $(x, y) \mapsto (-x, \sqrt{-1}y)$. Then the endomorphism ring of $E$ is given by $\mathrm{End}(E) = \mathbb{Z}[1, i, \frac{i+\pi}{2}, \frac{1+i\pi}{2}]$. We have $\#E(\mathbf{F}_q) = (p+1)^2$ and $E[M] \subseteq E(\mathbf{F}_q)$.

**The norm equation.** Let $r \in \mathbb{Z}_{>0}$. Suppose that we want to find an orientation on $E$ by an imaginary quadratic order $\mathcal{O} = \mathbb{Z}[\sigma]$, where $\sigma$ has norm $M^r$. Given the explicit description of the endomorphism ring, this amounts to solving the norm equation

$$N(\sigma) = N \left( a + bi + c \frac{i + \pi}{2} + d \frac{1 + i\pi}{2} \right) = M^r,$$

where $a, b, c, d \in \mathbb{Z}$. After the linear change of variables $x := 2a+d$, $y := 2b+c$, we can rewrite as

$$x^2 + y^2 + p(c^2 + d^2) = 4M^r.$$

where $\mathrm{tr}(\sigma) = x$.

**The discriminant.** For our purposes, we will additionally require that $|\mathrm{Disc}(\sigma)| = 4N(\sigma) - \mathrm{tr}(\sigma)^2 = 4M^r - x^2$ be either

(i) prime; or

(ii) the product of two large (distinct) primes.

Note that the second case is best we can hope for when $r = 2s$ is even, by the factorization

$$4M^{2s} - x^2 = (2M^s + x)(2M^s - x).$$

Although this requirement on the discriminant is not strictly necessary, we will argue why such a discriminant is desirable in Section 5.2. Note that it implies in particular that any $\mathbb{Z}[\sigma]$-orientation is automatically primitive.

**Finding the orientation.** We obtain the following pseudo-algorithm for finding an element of $\mathrm{End}(E)$ with the required properties.

(i) Set $x$ to be the smallest (odd) prime number different from the $\ell_i$.

(ii) Verify that

(a) if $r$ is odd: $4M^r - x^2$ is prime;

(b) if $r$ is even: $2M^{r/2} + x$ and $2M^{r/2} - x$ are prime.

If this fails, try again with next smallest value for $x$.
(iii) Solve $x^2 + y^2 \equiv 0 \pmod{p}$ for $y$, and lift to $y \in 2\mathbb{Z}_{>0}$ minimal. If no solution exists, start over with the next smallest value of $x$.

(iv) Solve $(4M^r - (x^2 + y^2))/p = c^2 + d^2$ using Cornacchia's algorithm, where $c$ is even and $d$ is odd. If no solution exists, start over with the next value of $x$.

Note that, since the output to (iii) is expected to be of size $\approx p$, we only expect step (iv) to succeed if $4M^r$ is at least of size $\approx p^2$. This will not be a restriction for our purposes, since we are most interested in the case where $M^r > p^2$. In practice, we will only attempt (iv) after verifying that $(4M^r - (x^2 + y^2))/p$ is a (positive) prime $\equiv 1 \pmod 4$, since Cornacchia's algorithm requires a factorization of the integer that is to be represented by the quadratic form. Note that in this situation we can always guarantee a solution where $c$ is even and $d$ is odd. The latter condition is necessary to ensure that $a = (x - d)/2$ and $b = (y - c)/2$ are both integral. Finally, we remark that since $x$ is coprime to $M$ by construction, the order $\mathcal{O} = \mathbb{Z}[\sigma]$ automatically satisfies (2).

**Example 4.1.** Consider the prime number

$$p = 2^{12} \cdot 3^6 \cdot 5^4 \cdot \underbrace{(7 \cdot 11 \cdots 281)}_{57 \text{ consecutive primes}} - 1 \approx 2^{409.2}.$$

Then $E/\mathbf{F}_{p^2}: y^2 = x^3 + x$ is orientable by an order $\mathcal{O} = \mathbb{Z}[\sigma]$ for which

$$N(\sigma) = M^5 \quad \text{and} \quad \text{tr}(\sigma) = 1800301,$$

where $M = p + 1$. Moreover, the integer

$$|\text{Disc}(\mathcal{O})| = |\text{Disc}(\sigma)| = 4M^5 - 1800301^2 \approx 2^{2048}$$

is prime.

## 4.2 Obtaining a kernel representation

Now that we have obtained an element $\sigma \in \text{End}(E)$ of norm $M^r$ given as an explicit $\mathbb{Z}$-linear combination

$$\sigma = a + bi + c\frac{i + \pi}{2} + d\frac{1 + i\pi}{2} \qquad (7)$$

of the endomorphisms $1, i, \frac{i+\pi}{2}, \frac{1+i\pi}{2}$, we would like to obtain a kernel representation of the orientation. That is, we want to represent $\sigma$ as a composition of $r$ cyclic isogenies of degree $M$. Since $E[M] \subseteq E(\mathbf{F}_q)$ (and similarly for any curve isogenous to $E$), the kernel of every such isogeny is generated by an $\mathbf{F}_q$-rational point, i.e. there exists a kernel representation $\{(E_j, P_j)\}$ of the $\mathcal{O}$-orientation, where $P_j \in E_j(\mathbf{F}_q)$ of order $M$ for all $1 \le j \le r$.
**The base case.** Consider first the orientation on $E_1 = E : y^2 = x^3 + x$. The desired point $P_1 \in E_1(\mathbf{F}_q)$ is a generator for $E[M, \sigma]$. If $R \in E[M]$ is any point, then $S = \hat{\sigma}(R) \in E[M, \sigma]$, where $\hat{\sigma}$ denotes the dual endomorphism. Given $\sigma$ as in (7), the dual isogeny corresponds to the quaternion conjugate; knowing $(a, b, c, d) \in \mathbb{Z}^4$, it can be explicitly evaluated on points of $E(\mathbf{F}_q)$. We can thus sample random points $R_i \in E(\mathbf{F}_q)$, and list their images $S_i = \hat{\sigma}(R_i)$. The latter will span $E[M, \sigma]$ once the least common multiple of their orders is $M$; in this case we compute $P_1$ as a suitable linear combination of the $S_i$. A generator $Q_1 \in E_1(\mathbf{F}_q)$ for $E[M, \hat{\sigma}]$ can be obtained in an analogous manner, by evaluating random $M$-torsion points under $\sigma$.

**Pushing forward the orientation.** Given the point $P_1$, we can compute the curve $E_2 \cong E_1/\langle P_1 \rangle \cong [\mathfrak{e}] * E_1$, where we recall that $\mathfrak{e}$ is the $O$-ideal $(M, \sigma)$ (cf. (3)). Denote by $\varphi_1 : E_1 \to E_2$ the corresponding cyclic isogeny with kernel $E_1[M, \sigma]$. Since $E[\sigma] \cap E[\hat{\sigma}] = \{0\}$, the image $Q_2 := \varphi_1(Q_1)$ generates $E_2[M, \hat{\sigma}]$. In what follows, we will describe how to obtain a generator $P_2$ for $E_2[M, \sigma]$.

Consider the $O$-ideal $I := (M^{r-1}, \hat{\sigma}) = \bar{\mathfrak{c}}^{r-1}$. Since $[\mathfrak{e}] = [\bar{\mathfrak{e}}]^{-1} = [\bar{\mathfrak{c}}]^{r-1}$ in $\mathrm{Cl}(O)$, it corresponds to a (horizontal) isogeny of degree $M^{r-1}$

$$ \psi = \varphi_I : E_1 \to E_2, \quad \text{where} \quad \ker \psi = E_1[M^{r-1}, \hat{\sigma}]. $$

Note that, by the same reasoning as before, we have that $\psi(P_1)$ generates $E_2[M, \sigma]$. Unfortunately, it is not immediately clear how to efficiently evaluate $\psi$ if $r > 2$, since a generator for $\ker \psi$ may only be defined over a possibly large extension field of $\mathbf{F}_q$. Luckily, we are saved by the Deuring correspondence.

Denote by $\mathcal{D}_0 \cong \mathbb{Z}[1, i, \frac{i+\pi}{2}, \frac{1+i\pi}{2}]$ the full endomorphism ring of $E_1$, viewed as a maximal order of the quaternion algebra $B_{p,\infty}$. We can extend $I$ to a left $\mathcal{D}_0$-ideal $I_0 := \mathcal{D}_0 I$, so that $\psi = \varphi_{I_0}$ through the Deuring correspondence. Using the KLPT algorithm [53], we can compute a left $\mathcal{D}_0$-ideal $J_0$ equivalent to $I_0$. Moreover, the ideal $J_0$ can be chosen of pleasant norm, in the sense that

(i) we may require that $N(J_0)$ is coprime to $M$;

(ii) translating $J_0$ to an isogeny $\varphi_{J_0}$ via the Deuring correspondence is practical; that is, its kernel is generated by torsion points of (relatively) small order that are defined over (relatively) small field extensions of the base field $\mathbf{F}_q$.

To achieve both requirements in practice we employ the implementation<fnref n="8" /> of the KLPT algorithm in [47]. Given $J_0$, let $\beta \in \mathcal{D}_0$ such that $\bar{J}_0 I_0 = \mathcal{D}_0 \beta$, i.e.

$$ \beta = \widehat{\varphi_{J_0}} \circ \varphi_{I_0} \in \mathrm{End}(E_1). $$

Applying $\varphi_{J_0}$ to both sides, we obtain

$$ [N(J_0)] \circ \varphi_{I_0} = \varphi_{J_0} \circ \beta. $$

Since we assumed $N(J_0)$ to be coprime to $M$, we find that $P_2 := (\varphi_{J_0} \circ \beta)(P_1)$ generates $E_2[M, \sigma]$, as desired. Once $P_2$ is found, we can compute $E_3 \cong E_2/\langle P_2 \rangle$

<footnote n="8">⁸ https://github.com/friends-of-quaternions/deuring</footnote>
and repeat the process with $I = (M^{r-2}, \hat{\sigma})$ to obtain a generator $P_3$ for $E_3[M, \sigma]$, and so on. Finally, we can push the point $Q_1 \in E_1[M, \hat{\sigma}]$ through the resulting chain of isogenies to obtain generators $Q_j \in E_j[M, \hat{\sigma}]$ for the dual isogenies. We have obtained a full kernel representation $\{(E_j, P_j, Q_j) \mid 1 \le j \le r\}$ of the $\mathcal{O}$-orientation on $E$.

All algorithms described in this section are implemented in the SageMath [81] package `orientation_tools.py`, which can be found in the GitHub repository [1].

# 5 The key exchange protocol

Now that we have a method to instantiate full kernel representations of primitive orientations on a base curve, we can employ Algorithm 1 to obtain a non-interactive key exchange protocol, as follows. Let us abbreviate the full kernel representation of an $\mathcal{O}$-orientation on $E: y^2 = x^3 + x$ as found in Section 4 by $\mathcal{E} := \{(E_j, P_j, Q_j) \mid 1 \le j \le r\}$; it is part of the public parameters of the scheme. We can view Algorithm 1 as defining an action by $\mathcal{O}$-ideals of the form $\mathfrak{a} = \prod_{i=1}^{n} l_i^{s_i}$, where $0 \le s_i \le e_i$, on the set of full kernel representations of $\mathcal{O}$-orientations. Iterating this action $B$ times, we can evaluate the action by any ideal class with exponent vector $(s_1, \dots, s_n)$ for which $0 \le s_i \le Be_i$. This gives $\prod_{i=1}^{n} (1 + Be_i)$ possible options for the $s_i$, which will be the size of the key space (the bound $B$ is to be determined by the security parameter). A high-level overview of the protocol is now as follows.

(i) Alice's secret key is an exponent vector $\mathfrak{sk}_A = (a_1, \dots, a_n) \in \mathbb{Z}_{\ge 0}^n$, where $0 \le a_i \le Be_i$. She computes $\mathcal{E}_A = \prod_{i=1}^n l_i^{a_i} \mod \mathcal{E}$ using $B$ applications of Algorithm 1, and sends it to Bob.

(ii) Bob's secret key is an exponent vector $\mathfrak{sk}_B = (b_1, \dots, b_n) \in \mathbb{Z}_{\ge 0}^n$, where $0 \le b_i \le Be_i$. He computes $\mathcal{E}_B = \prod_{i=1}^n l_i^{b_i} \mod \mathcal{E}$ using $B$ applications of Algorithm 1, and sends it to Alice.

(iii) Alice computes $\mathcal{E}_{AB} = \prod_{i=1}^{n} l_i^{a_i} \mod \mathcal{E}_B$.

(iv) Bob computes $\mathcal{E}_{BA} = \prod_{i=1}^{n} l_i^{b_i} \mod \mathcal{E}_A$.

It is not obvious that the full kernel representations $\mathcal{E}_{AB}$ and $\mathcal{E}_{BA}$ are equal, and this is in fact not necessarily true. We did observe that this holds in practice when Alice and Bob both use Vêlu's formulae for the isogeny computations; a partial explanation for this phenomenon can be found in [60, Thm. 3.1]. Regardless, it is not difficult for Alice and Bob to deduce a shared secret from the protocol, a most obvious choice being the $j$-invariant of, say, the first curve in the kernel representation. We will denote this by $j(\mathcal{E}_{AB}) = j(\mathcal{E}_{BA})$.

## 5.1 Public keys

The key exchange protocol as described still has relatively large public keys. Indeed, if a public key is given as a full kernel representation, it consists of $r$
elliptic curves (say, Montgomery invariants) and 2r elliptic curve points. This overdetermines the necessary information of an O-orientation; indeed, it is not difficult to see that we can discard at least half of the points without losing the information of the orientation.

**Public key compression.** We are going to describe how to compress a full kernel representation $\mathcal{E} = \{(E_j, P_j, Q_j) | 1 \le j \le r\}$ of an orientation. Recall that the endomorphism $\iota(\sigma)$ it encodes corresponds to the chain of isogenies

$$E_1 \to E_1/\langle P_1 \rangle \cong E_2 \to \dots \to E_r/\langle P_r \rangle \cong E_1.$$

We first discard the points $Q_j$, as they can be recomputed as generators of the kernels of the duals of the isogenies. Note also that we do not require the exact points $P_j$, but only the (cyclic) subgroups of $E_j[M]$ that they generate. To express an order-$M$ cyclic subgroup of the $M$-torsion requires at least $\tilde{O}(\log M)$ bits of information. Indeed, given the prime factorization (6) of $M$, the number of such subgroups is $M \cdot \prod_{i=1}^n (1 + \frac{1}{l_i})$. We can express (a multiple of) $P_j$ in terms of a deterministically sampled basis $S_j, T_j$ for $E_j[M]$ by an element $\lambda_j \in \mathbf{P}^1(\mathbb{Z}/M\mathbb{Z})$. Lastly, we remark that we can discard the curves $E_j$ for $j > 1$, since they can be inductively recomputed from the pair $(E_{j-1}, \langle P_{j-1} \rangle)$. The compressed public key consists of the data

$$\mathbf{pk} = j(E_1), (\lambda_1, \dots, \lambda_r),$$

where $j(E_1)$ is of size $2\log_2(p)$ and $\lambda_i$ is of size $\approx \log_2(M)$. In case the $M$-torsion spans $E(\mathbf{F}_q)$, i.e. $M = p + 1$, we thus obtain a public key of (bit)size $\approx (r + 2)\log_2(p)$. In practice, there is a small overhead arising from the factor $\prod_{i=1}^n (1 + \frac{1}{l_i})$, e.g. the actual (bit)size of public keys in the situation of Example 4.1 is $2878 > 2864.5 \approx (r + 2)\log_2(p)$.

**Public key decompression.** To decompress public keys, start by sampling a deterministic basis for $E_1[M]$ and computing $P_1$ from $\lambda_1$. Since we have sampled a torsion basis for $E_1[M]$, we obtain for free a point $R_1 \in E_1[M]$ which is linearly independent of $P_1$. Next, we compute $E_1 \xrightarrow{\phi_1} E_2 \cong E_1/\langle P_1 \rangle$, and evaluate $\phi_1$ at $R_1$; the resulting point $Q_2 = \phi_1(R_2)$ generates the kernel of the dual isogeny $\tilde{\phi}_1$. Given $E_2$, we recover $P_2$ from $\lambda_2$, and repeat the procedure. In each step, we also compute $Q_{j+1} := \phi_j(Q_j) \in E_{j+1}[M, \hat{\sigma}]$. Finally, we obtain the isogeny $E_r \xrightarrow{\phi_r} E_1 \cong E_r/\langle P_r \rangle$, and evaluating it at $Q_r$ gives $Q_1 \in E[M, \hat{\sigma}]$. We have recovered a full kernel representation $\{(E_j, P_j, Q_j) | 1 \le j \le r\}$ of the O-orientation. The cost of this procedure is essentially (dominated by): $r$ computations of a deterministic $M$-torsion basis, and one evaluation of the endomorphism $\iota(\sigma)$.

## 5.2 Security analysis

**In a nutshell.** For an accurate security analysis we require to consider at least the following parameters.
(i) The class number $\#\mathrm{Cl}(\mathcal{O})$, which is roughly proportional to $|\mathrm{Disc}(\mathcal{O})|^{1/2}$.

(ii) The number of distinct supersingular elliptic curves over the base field $\mathbf{F}_q = \mathbf{F}_{p^2}$, which depends on the size of $p$.

(iii) The size of the public key space, which (under some heuristic assumptions; see below) is roughly equal to the size of the private key space $\mathcal{K}$.

The most important difference with other protocols based on class group actions on oriented elliptic curves, such as CRS [39,75], CSIDH [22], and SCAL-LOP [41,27,3], is that we are allowed to choose the size of the discriminant and the size of the base field independently. In the schemes mentioned above, the quantum security is essentially dictated by Kuberberg's algorithm, whose complexity is subexponential in the class number. However, when the characteristic of the base field is small, we also need to take generic path finding algorithms between supersingular elliptic curves into account. The resulting parameter estimates for NIST level 1 are summarized in Table 1.

<table><caption>Table 1: Parameter estimates required to achieve NIST level 1 based on the best known generic attacks, cf. [12, Table 1].</caption><thead><tr><th>Parameter</th><th>Attack</th><th>Quantum</th><th>NIST level 1 bitsize</th></tr></thead><tbody><tr><td>$|\mathrm{Disc} \mathcal{O}|$</td><td>Kuperberg [54,55,72]</td><td>Yes</td><td>2048 (aggressive)<br>4096 (conservative)</td></tr><tr><td>$p$</td><td>BJS [9]</td><td>Yes</td><td>230 (aggressive)<br>256 (conservative)</td></tr><tr><td>$\#\mathcal{K}$</td><td>vOW [69]<br>MITM [26]</td><td>No</td><td>221 (aggressive)<br>256 (conservative)</td></tr></tbody></table>

**Private vs public keys.** The private key space is the set of exponent vectors

$$ \mathcal{K} := \mathcal{K}_{\text{priv}} = \{(s_1, \dots, s_n) \mid 0 \le s_i \le Be_i\}. $$

One such exponent vector corresponds to the ideal class $[\prod_{i=1}^n [l_i^{s_i}] \in \mathrm{Cl}(\mathcal{O})]$. Similar to CSIDH, we require the heuristic assumption that there are few collisions in this correspondence; i.e. that the private key space maps roughly injectively into the class group. This can be motivated by combining the Cohen-Lenstra heuristics [32] with the Gaussian heuristic for the relationship lattice spanned by ideal classes $[l_i]$, see [22, Sec. 7.1] for a more in-depth discussion on this issue. We furthermore remark that the correspondence is (under a mild condition) provably injective, apart from the trivial collision $(0, \dots, 0) \equiv (e_1, \dots, e_n)$, if $B=1$; see [49, Prop. 3.1]. Denoting by $\mathcal{S} \subseteq \mathrm{Cl}(\mathcal{O})$ the image of the private key space in $\mathrm{Cl}(\mathcal{O})$, the public key space is the set

$$ \mathcal{K}_{\text{pub}} = \{g * \mathcal{E} \mid g \in \mathcal{S}\}, $$
where $\mathcal{E}$ represents a (primitively $\mathcal{O}$-oriented) base curve. Since the class group action is free, the association $g \mapsto g * \mathcal{E}$ is injective. However, it is not necessarily injective on the level of $j$-invariants. Indeed, if $\#\mathrm{Cl}(\mathcal{O}) > p$, the full orbit of a primitively $\mathcal{O}$-oriented supersingular elliptic curve necessarily contains curves with the same $j$-invariant (but endowed with a different orientation). In particular, when $p$ is small, we must take into account generic supersingular path-finding algorithms. Indeed, it was shown in [83] that connecting two $\mathcal{O}$-oriented elliptic curves by an ideal class is equivalent to finding any (not necessarily oriented) isogeny between them.

**Remark 5.1.** For the purpose of security analysis, a (full) kernel representation of an $\mathcal{O}$-orientation is equivalent to an *efficient* representation of an $\mathcal{O}$-orientation in the sense of [83, p. 7-8]. Indeed, a kernel representation is a specific instance of an efficient representation, and given an efficient representation of an $\mathcal{O}$-orientation, a kernel representation can be computed in polynomial time.<fnref n="9" />

Heuristically, we expect that the class group action covers the supersingular $j$-invariants roughly uniformly.

**Conjecture 5.2.** Let $p$ be a prime number and let $j \in \mathbf{F}_{p^2}$ be a supersingular $j$-invariant different from 0, 1728. Let $D$ denote a fundamental discriminant such that $D$ does not split modulo $p$, and denote by $\mathcal{O}$ the associated maximal order. Then

$$ \frac{p}{12} \lim_{D \to \infty} \frac{\#\{(E, \iota) \mid j(E) = j, \iota \text{ is an } \mathcal{O}\text{-orientation}\} / \cong}{\#\mathrm{Cl}(\mathcal{O})} = 1. $$

This is roughly motivated by equidistribution results for CM points [45,65]. A weaker, but provable, result is that if $|\mathrm{Disc}(\mathcal{O})|$ is sufficiently large then every supersingular elliptic curve is $\mathcal{O}$-orientable; see [46, Thm. 1.2] for a precise (but ineffective) statement, and [61] for a weaker (but effective) statement.

We summarize the above discussion into the following (inexact) formulation of our main heuristic assumption.

**Heuristic 5.3.** If $\#K_{\mathrm{priv}}$ and $\mathrm{Disc}(\mathcal{O})$ are sufficiently large, then acting by (the image in $\mathrm{Cl}(\mathcal{O})$ of) uniformly random elements of $K_{\mathrm{priv}}$ on a fixed primitively $\mathcal{O}$-oriented supersingular base curve yields (O-oriented curves with) statistically uniform supersingular $j$-invariants.

We now provide some experimental evidence toward this hypothesis. Note that for parameters of cryptographic size, we expect collisions between random private key pairs to be unlikely, even when the heuristic is false. In particular, we expect to be able to falsify the heuristic only for smaller values of $p$. We will restrict our experimental parameters to the case where $\#K_{\mathrm{priv}} \approx p$, which is in line with what is dictated by generic attacks according to our security analysis below.

In the first set of experiments, we use $p = 67339 \approx 2^{16}$, for which $p+1 = 2^2 \cdot 5 \cdot 7 \cdot 13 \cdot 37$ and $p-1 = 2 \cdot 3^3 \cdot 29 \cdot 43$; see Section 6.2 for why such a choice of prime is natural. We take $M = 3^3 \cdot 5 \cdot 7 \cdot 13 \cdot 29 \cdot 37 \cdot 43$ to be the odd part

<footnote n="9">⁹ Assuming that $M$ is smooth.</footnote>
of $(p+1)(p-1)$. Next, we choose the smallest possible value of $B$ for which the private key space is of size $\ge 2^{16}$; this is $B = 4$, for which $\#K_{\text{priv}} = 203125$. For various values of $r \in \mathbb{Z}_{>0}$, we compute orientations on the base curve ($E_0: y^2 = x^3 + x$) corresponding to an endomorphism of degree $M^r$ (and negligibly small trace). We then act by the first 5612 elements (this is the total number of supersingular $j$-invariants in $\mathbb{F}_{p^2}$) of $\#K_{\text{priv}}$, ordered lexicographically, and record the total number of distinct $j$-invariants encountered. Comparing the results to the uniform distribution, we report on the one-sided $p$-value, i.e. the probability that we obtain at most the observed amount of distinct $j$-invariants assuming that the distribution is uniform, in Table 2. The difference with the

<table><caption>Table 2: Experimental results for $p \approx 2^{16}$.</caption><thead><tr><th>r</th><th>1</th><th>2</th><th>3</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td># distinct j</td><td>3475</td><td>3554</td><td>3630</td><td>3547</td><td>3553</td><td>3576</td></tr><tr><td>p-value</td><td>0.0010</td><td>0.6154</td><td>0.9998</td><td>0.4975</td><td>0.5990</td><td>0.8917</td></tr></tbody></table>

uniform distribution is statistically significant for $r = 1$, which corresponds to a discriminant of size $|\text{Disc}(O)| \approx 2^{31}$; this is as expected, since this is likely too small to cover all supersingular $j$-invariants, let alone uniformly. Interestingly, for $r = 3$ we obtain significantly more distinct $j$-invariants than what would be expected from a uniform distribution. A possible explanation for this is that curves that are connected by small degree isogenies are typically not isomorphic (since few curves have small degree endomorphisms), hence there is a bias for elements of $K_{\text{priv}}$ that are close, say in $\ell^1$-norm, to correspond to distinct $j$-invariants.

In the second set of experiments, we use $p = 8 \cdot 3 \cdot 5 \cdot 7 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 - 1 \approx 2^{32}$. We take $M$ to be the odd part of $p+1$. Using $B = 16$, we obtain a key space of size $\approx 2^{32.7}$. This time, we act by $2^{16}$ uniformly random elements of $K_{\text{priv}}$, and store the 8 most significant bits of the MD5 hash of the resulting $j$-invariant. We then compare the resulting distribution with the uniform one using a $\chi^2$ distribution test. None of the obtained $p$-values indicates a statistically significant deviation.

<table><caption>Table 3: Experimental results for $p \approx 2^{32}$.</caption><thead><tr><th>r</th><th>2</th><th>3</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td>χ<sup>2</sup> statistic</td><td>231.93</td><td>231.61</td><td>233.84</td><td>259.84</td><td>246.75</td></tr><tr><td>p-value</td><td>0.847</td><td>0.851</td><td>0.825</td><td>0.404</td><td>0.633</td></tr></tbody></table>
**Classical security.** The most important classical attacks are (depth-first) meet-in-the-middle (MITM) [26] and van Oorschot-Wiener golden collision search (vOW) [69]. Given access to $O(\#K^{1/4})$ memory, the first has an asymptotic time complexity of $O(\#K^{1/4})$. vOW has a worse time complexity, but performs better when memory is limited. It was argued in [26, Sec. 5.2] and [2] that given realistic constraints on the amount of available memory, vOW is the superior algorithm for a classical attack. Using the estimates of [26], we require bitsizes of $\log_2(\#K) = 221,234,332$ for NIST levels 1, 2, 3 respectively. In [12], the more conservative choices $\log_2(\#K) = 256, 256, 348$ (for the same respective NIST levels) are also considered. Note that classical generic supersingular isogeny path finding has complexity $O(p^{1/2})$, which loses to vOW in case $\#K \le p$.

**Quantum security.** Assuming the heuristic that the ideal classes $[I_i]$ span $\text{Cl}(\mathcal{O})$, Kuperberg's algorithm [54,55,72] has time complexity subexponential in the class number $\#\text{Cl}(\mathcal{O})$, where $\#\text{Cl}(\mathcal{O})/|\text{Disc}(\mathcal{O})|^{1/2}$ is, asymptotically on average, equal to $\approx 0.46$ [33, p. 290]. Although estimates of the actual complexity of Kuperberg's algorithm for concrete parameters choices — most prominently for CSIDH — are still subject of debate [8,10,70,26], the most recent papers on the topic employ the relatively pessimistic estimates [12,13] of 2048- and 4096-bit discriminants for “aggressive” and “conservative” NIST level 1 respectively.

Like CSIDH and B-SIDH [37], the degrees of the secret isogenies are large compared to $p$, so Tani's algorithm [80,52] does not give an advantage compared to the best generic path finding algorithm BJS [9]. The latter has a time complexity of $O(p^{1/4})$, which suggests primes of bitsize $\ge 256$ for NIST level 1. However, the more aggressive value $\log_2(p) = 230$ has also been proposed [37, Sec. 5.2].

**Non-generic attacks.** In case the imaginary quadratic order $\mathcal{O}$ is not maximal, the class group can be reduced to that of a larger order if an ascending isogeny can be computed. This applies most notably to SCALLOP (and variants), where it is argued that computing such an ascending isogeny is infeasible, see e.g. [41, Sec. 7], because it has large prime degree. In OSIDH [34], the ascending isogeny is of smooth degree, which means that access to an efficient representation of the orientation renders the protocol insecure [67]; it was shown that this leads to a practical (though exponential time) attack [40]. In practice, we choose to orient only by maximal orders (we use discriminants that are squarefree), so that this attack does not apply.

In case the exponent of the class group is exceptionally small, there are quantum attacks that outperform Kuperberg's [23,31,56]. Heuristically [32], however, we expect the class group to be close to cyclic, so that these attacks do not apply.

In some cases, primes that ramify in the class group lead to attacks based on self-pairings [19], most notably for the decisional Diffie-Hellman problem [24,20]. The complexity of these attacks is polynomial in the size of the ramifying prime,
hence infeasible for discriminants that contain no small prime divisors. In practical instances, we avoid these attacks by using a discriminant that is either prime or the product of two large primes, cf. Section 4.1.

By construction, the kernel representation of the orientation on the public key curve contains images of smooth torsion points under a secret isogeny. In public key compression, this information is automatically masked, because it is reduced to the subgroup that the point generates (in fact, this subgroup is an eigenspace for the action of $\iota(\sigma)$ on the M-torsion, which could be recovered from any efficient representation of the orientation). However, torsion point attacks based on higher-dimensional isogeny interpolation [16,62,73] do not seem to apply, even if the kernel representation is sent in uncompressed form, because the degree of the secret isogeny is unknown (in fact the degree is the secret, because it is in one-to-one correspondence with the exponent vector).

# 6 Practical instances

## 6.1 A first approach

Since the main idea of representing an orientation as a chain of isogenies is that we can increase the size of the discriminant without increasing the size of the base field (and so to mitigate subexponential quantum attacks), it is tempting to consider a base field of minimal characteristic $p$, say e.g. 256 bits for “conservative” NIST level 1. For example

$$p = 2^5 \cdot 3^3 \cdot \underbrace{(5 \cdot 7 \cdot 11 \cdot \dots \cdot 193)}_{\text{skip 173}} - 1 \approx 2^{256.5}. \qquad (8)$$

We then take $M = p+1$, so that $E(\mathbf{F}_q) = E[M]$ for the base curve $E: y^2 = x^3 + x$. Next, we can use the method of Section 4 to generate a primitive orientation by an order $O = \mathbf{Z}[\sigma]$ where $N(\sigma) = M^r$ and $\text{tr}(\sigma)$ is small, where we require $r = 16$ to attain a 4096-bit discriminant. Finally, we determine the size of the exponent vector required to attain a key space of 256 bits. Note that the number of distinct prime divisors $\ell_i | M$ is $n = 43$. The smallest positive integer $B \in \mathbf{Z}_{>0}$ for which

$$2^{256} < \#\mathcal{K} = \prod_{i=1}^{n} (1 + e_i B) = (1 + 5B)(1 + 3B)(1 + B)^{41}$$

is $B = 58$. Recall that $B$ is the number of iterations of Algorithm 1 in the evaluation of the class group action to attain the desired key space. Although all isogeny computations are over a small base field and of small degree $\le 193$, this is likely suboptimal. The issue here is that the size of the key space is exponential in $n$ but only polynomial in $B$; this suggests a trade-off between minimizing the size of $p$ and maximizing the number of prime divisors $\ell_i | (p+1)$.
## 6.2 The twist trick

A well-known trick [36,43,76,6,77] when lacking torsion, is to consider points on the quadratic twist $E^t$ of $E$. It has opposite trace of Frobenius, so that $\#E^t(F_q) = (p-1)^2$. The $F_q$-rational points on the twist correspond to points on $E(F_q)$ with $x$-coordinate in $F_q$ (but $y$-coordinate in $F_{q^2} = F_{p^4}$). When using $x$-only arithmetic, such points can be handled purely using $F_q$-arithmetic. In our situation, such points may thus be part of the kernel representation of the orientation with virtually no loss of efficiency.<fnref n="10" /> In effect, this means that we can add prime divisors of $p-1$ to the set of $\ell_i$ used in the class group action computation. We remark that the analogue of this trick in the case that the base field is $F_p$ is also used in CSIDH, the difference being that in the CSIDH setting the group of $F_p$-rational points on the twist has the same order as that of the curve itself.

Finding *twin-smooth* primes, i.e. prime numbers $p$ for which $p+1$ and $p-1$ are both smooth, is a non-trivial number-theoretic problem [79,35], which has recently gained attention in isogeny-based cryptography [38,11,78,77] for its applications in B-SIDH [36], (one-dimensional) SQISign [42,43,76], and POKE [6]. For the primes that we require, the number $p^2 - 1 = (p+1)(p-1)$ need not necessarily be fully smooth (i.e. a possibly large prime divisor is allowed), since we are free to use any $M \mid (p^2 - 1)$. However, contrary to the applications mentioned above, we require *many* distinct prime divisors $\ell_i \mid (p^2 - 1)$. An example, which was communicated to us by Bruno Sterner, is the 256-bit prime

$$p = 0xaee61f0e7eb0b904142a14b1ba552ca011c6104b007e448fe6aed1f1af734f1f,$$

where the prime factorizations of $p \pm 1$ are

$$ \begin{aligned} p+1 = & 2^5 \cdot 7^2 \cdot 11 \cdot 23 \cdot 29 \cdot 37 \cdot 41 \cdot 43 \cdot 53 \cdot 61 \cdot 67 \cdot 73 \cdot 79 \cdot 83 \\ & \cdot 103 \cdot 107 \cdot 131 \cdot 137 \cdot 149 \cdot 173 \cdot 199 \cdot 211 \cdot 277 \cdot 307 \\ & \cdot 5370594787 \cdot 10398664516670979076559; \end{aligned} $$

$$ \begin{aligned} p-1 = & 2 \cdot 3^2 \cdot 5 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 47 \cdot 59 \cdot 71 \cdot 89 \cdot 97 \cdot 101 \cdot 109 \cdot 113 \cdot 127 \\ & \cdot 139 \cdot 151 \cdot 157 \cdot 163 \cdot 167 \cdot 179 \cdot 181 \cdot 191 \cdot 193 \cdot 223 \cdot 233 \cdot 269 \\ & \cdot 16793651481272952227055481. \end{aligned} $$

Finding primes that are “optimal” for evaluating the class group action depends on an optimized implementation of Algorithm 1. Both require a significant amount of non-trivial effort and are left for future work.

<footnote n="10">¹⁰ One technicality is that points on the twist must be individually pushed through every isogeny, increasing the minimum number of isogeny evaluations in the group action computation. In practice, this restricts the space of possible *strategies*; cf. Section 3.4.</footnote>
## 6.3 An example

Using the prime number $p$ above, we define $M$ to be the product of all small (i.e. $\le 307$) odd$^{11}$ prime power divisors $\ell_i^{e_i}$ of $p \pm 1$, i.e.

$$M = 3^2 \cdot 5 \cdot 7^2 \cdots 233 \cdot 277 \cdot 307 = \prod_{i=1}^{n} \ell_i^{e_i}.$$

Using the method of Section 4.1, we found an orientation on $E: y^2 = x^3 + x$ by an element $\sigma \in \text{End}(E)$ for which

$$N(\sigma) = M^{13} \quad \text{and} \quad \text{tr}(\sigma) = 29171033,$$

such that $|\text{Disc}(\sigma)| = 4M^{13} - 29171033 \approx 2^{4105}$ is prime. Next, using a minor modification of the method of Section 4.2 to include points on the quadratic twist, we generated a kernel representation of the orientation on the base curve. This (pre)computation was relatively expensive, and took about 200 core hours on a desktop CPU$^{12}$, with the vast majority taken up by the effective Deuring correspondence [47]. We obtain a key space of size 256 bits for $B = 33$. Using these parameters, our (unoptimized) proof-of-concept SageMath [81] implementation executes a class group action corresponding to the conservative NIST level 1 category (cf. Table 1) using Algorithm 1 on a single core of a laptop CPU$^{13}$ in a median 53.4 seconds (over 100 ideal classes, standard deviation $\approx 0.1$ seconds). We relied on a package by Giacomo Pope for Kummer arithmetic [71]. Using the same algorithms for isogeny computations, our SageMath implementation of the class group action from dCSIDH [12] for the 4096-bit prime given in [12, Table 1] runs in a median 370.6 seconds (over 40 ideal classes, standard deviation $\approx 2.2$ seconds), excluding random point sampling. It should be stressed that, since both benchmarks are based on heavily suboptimal implementations, future work needs to be done to accurately assess the practical performance difference. The SageMath code associated to our implementations can be found in the GitHub repository [1].

## 7 Future work

**Implementation.** There are various tricks, mostly from the CSIDH literature, to speed up the computation of class group actions on oriented elliptic curves. For an optimized implementation of Algorithm 1 in a low-level programming language we should include (at least) the following methods

<footnote>$^{11}$ Although there is no theoretical limitation preventing us from including the power $2^5$, this leads to some practical technicalities when using Kummer arithmetic for Montgomery curves; cf. the section “Future Work” in [71, README.md]. Since we are anyway far from an optimized implementation, we chose to exclude even-degree isogenies in the example (at the cost of a minor loss in efficiency).</footnote>

<footnote>$^{12}$ Intel i9-9900KS @ 4.00GHz.</footnote>

<footnote>$^{13}$ AMD Ryzen 7 PRO 8840U @ 3.30 GHz.</footnote>
(i) Optimal differential addition chains [25];

(ii) Different elliptic curve models [64];

(iii) Optimal strategies [63,68,50,30,28];

(iv) Fast constant-time finite field arithmetic [12,13].

Secondly, we would like to find good choices for the parameters, most notably the characteristic of the base field $p$. This involves a further study of twin smooth primes and — due to the unique shape of prime — likely requires new techniques. In practice, these two goals are heavily interdependent, in the sense that the optimal parameters depend on an optimal implementation and vice versa. It would be most interesting to compare to the optimized implementations of dCSIDH [12] and dCTIDH [13] in practice. Another interesting contender is the non-interactive isogeny-based key exchange protocol $\otimes$-MIKE [74], which is based on a generalization of the class group action known as the *module action*, though, at the time of writing, no implementation is publicly available.

**Public key validation.** In a non-interactive key exchange with static keys, one is required to validate public keys to prevent active attacks. Indeed, a malicious Bob could publish a representation of a “weak” orientation (e.g. with several $l_i$ ramifying in the class group) an infer information about Alice’s secret from (the success or failure of) subsequent encryptions. Note that in the public key decompression algorithm, Section 5.1, we already verify that the full kernel representation corresponds to an endomorphism $\tau \in \text{End}(E_1)$ of degree $M^r = N(\sigma)$. Indeed, every $P_j$ has order $M$ by construction, and we checked that the last isogeny $\varphi_r$ maps to $E_1$. What remains to verify is that

$$ \mathrm{tr}(\tau) = \mathrm{tr}(\sigma). \qquad (9) $$

Indeed, if this holds, then $\mathrm{Disc}(\tau) = \mathrm{Disc}(\sigma)$, and we can conclude that our kernel representation corresponds to a $\mathbb{Z}[\sigma]$-orientation. Moreover, since we chose $\mathrm{Disc}(\sigma)$ to be a fundamental discriminant, we are guaranteed that the orientation is primitive. There exist generic polynomial time algorithms that compute the trace of an endomorphism that is given as a sequence of isogenies of smooth degree [66], but these are likely not the best we can do for our particular situation, for at least two reasons.

(i) We assume that we have a large amount of smooth rational torsion. This gives a strong advantage compared to generic algorithms [66, Sec. 3.3].

(ii) We do not require to compute the trace, but merely have to verify that it is correct. In particular, this means that we may not require discrete logarithm computations [66, Sec. 3.3(3)] (cf. the discussion below).

As a partial result, it is not too difficult to see that the trace can be easily verified modulo $M$, as follows. To check the validity of (9) (mod $M$), we will use the point $R_1 \in E_1[M]$ that we computed during public key decompression. Let us write $R_1 = \lambda P_1 + \mu Q_1$, where $\lambda, \mu \in (\mathbb{Z}/M\mathbb{Z})$ are unknown to us (for now). By construction, we have

$$ Q_1 = \tau(R_1) = [\mu] \circ \tau(Q_1) = [\mu] \circ (\tau + \hat{\tau})(Q_1) = [\mu \cdot \mathrm{tr}(\tau)]Q_1. $$
Denoting by $e_M : E[M] \times E[M] \to \mu_M$ the M-Weil pairing, it follows that

$$e_M(P_1, Q_1) = e_M(P_1, R_1)^{\text{tr}(\tau)}.$$

Using two Weil-pairing computations and one exponentiation in $\mathbb{F}_q$, we can thus verify that $\text{tr}(\tau) \equiv \text{tr}(\sigma) \pmod{M}$.<fnref n="14" /> This is not sufficient, because we need to determine the trace modulo at least $4M^{r/2}$ due to the Hasse-Weil bound. We remark that knowing $\text{tr}(\tau) \pmod{M}$ does give a head start when using the generic trace computation [66], since the latter works by computing the trace modulo sufficiently many small integers and lifting via the Chinese Remainder Theorem (CRT). We leave determining the best algorithm to validate public keys as a topic for future research, the main question being whether we can verify the trace, say modulo $M^{r/2}$, without resorting to generic techniques.

## References

1. GitHub repository associated to this paper, https://github.com/houbenmr/LargeDiscriminantOrientations

2. Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson Jr., M.J. (eds.) Selected Areas in Cryptography – SAC 2018. pp. 322–343. Springer International Publishing, Cham (2019)

3. Allombert, B., Biasse, J.F., Eriksen, J.K., Kutas, P., Leonardi, C., Page, A., Scheidler, R., Bagi, M.T.: PEARL-SCALLOP: Parameter Extension Applicable in Real-Life SCALLOP. Cryptology ePrint Archive, Report 2024/1744 (2024), https://eprint.iacr.org/2024/1744

4. Banegas, G., Bernstein, D.J., Campos, F., Chou, T., Lange, T., Meyer, M., Smith, B., Sotáková, J.: CTIDH: faster constant-time CSIDH. IACR TCHES 2021 (4), 351–387 (2021). https://doi.org/10.46586/tches.v2021.i4.351-387, https://tches.iacr.org/index.php/TCHES/article/view/9069

5. Banegas, G., Krämer, J., Lange, T., Meyer, M., Panny, L., Reijnders, K., Sotáková, J., Trimoska, M.: Disorientation faults in CSIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 310–342. Springer, Cham (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_11

6. Basso, A.: POKE: A framework for efficient PKEs, split KEMs, and OPRFs from higher-dimensional isogenies. Cryptology ePrint Archive, Report 2024/624 (2024), https://eprint.iacr.org/2024/624

7. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Cryptology ePrint Archive, Report 2020/341 (2020), https://eprint.iacr.org/2020/341

8. Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: Optimizing quantum evaluation of isogenies. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 409–441. Springer, Cham (May 2019). https://doi.org/10.1007/978-3-030-17656-3_15

9. Biasse, J.F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: International Conference on Cryptology in India. pp. 428–442. Springer (2014)

<footnote n="14">¹⁴ Note that, if we were to compute the trace from scratch, we would require a discrete logarithm computation to obtain $\text{tr}(\tau) \pmod{M}$.</footnote>
10. Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 493–522. Springer, Cham (May 2020). https://doi.org/10.1007/978-3-030-45724-2_17

11. Bruno, G., Santos, M.C.R., Costello, C., Eriksen, J.K., Meyer, M., Naehrig, M., Sterner, B.: Cryptographic smooth neighbors. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part VII. LNCS, vol. 14444, pp. 190–221. Springer, Singapore (Dec 2023). https://doi.org/10.1007/978-981-99-8739-9_7

12. Campos, F., Chávez-Saab, J., Chi-Domínguez, J.J., Meyer, M., Reijnders, K., Rodríguez-Henríquez, F., Schwabe, P., Wiggers, T.: Optimizations and practicality of high-security CSIDH. CiC 1(1), 5 (2024). https://doi.org/10.62056/anjbksdja

13. Campos, F., Hellenbrand, A., Meyer, M., Reijnders, K.: dCTIDH: Fast & Deterministic CTIDH. Cryptology ePrint Archive, Report 2025/107 (2025), https://eprint.iacr.org/2025/107

14. Campos, F., Kannwischer, M.J., Meyer, M., Onuki, H., Stöttinger, M.: Trouble at the CSIDH: Protecting CSIDH with dummy-operations against fault injection attacks. Cryptology ePrint Archive, Report 2020/1005 (2020), https://eprint.iacr.org/2020/1005

15. Castryck, W., Decru, T.: CSIDH on the surface. In: Ding, J., Tillich, J.P. (eds.) Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020. pp. 111–129. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_7

16. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423–447. Springer, Cham (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_15

17. Castryck, W., Decru, T., Houben, M., Vercauteren, F.: Horizontal racewalking using radical isogenies. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part II. LNCS, vol. 13792, pp. 67–96. Springer, Cham (Dec 2022). https://doi.org/10.1007/978-3-031-22966-4_3

18. Castryck, W., Decru, T., Vercauteren, F.: Radical isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 493–519. Springer, Cham (Dec 2020). https://doi.org/10.1007/978-3-030-64834-3_17

19. Castryck, W., Houben, M., Merz, S.P., Mula, M., van Buuren, S., Vercauteren, F.: Weak instances of class group action based cryptography via self-pairings. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part III. LNCS, vol. 14083, pp. 762–792. Springer, Cham (Aug 2023). https://doi.org/10.1007/978-3-031-38548-3_25

20. Castryck, W., Houben, M., Vercauteren, F., Wesolowski, B.: On the decisional Diffie–Hellman problem for class group actions on oriented elliptic curves. Research in Number Theory 8(4), 99 (2022)

21. Castryck, W., Invernizzi, R., Lorenzon, G., Meers, J., Vercauteren, F.: Orient express: Using frobenius to express oriented isogenies. Cryptology ePrint Archive, Paper 2025/1047 (2025), https://eprint.iacr.org/2025/1047

22. Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: An efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 395–427. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-03332-3_15

23. Castryck, W., Meeren, N.V.: Two remarks on the vectorization problem. Cryptology ePrint Archive, Report 2022/1366 (2022), https://eprint.iacr.org/2022/1366
24. Castryck, W., Sotáková, J., Vercauteren, F.: Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: Extended version. Journal of Cryptology 35(4), 24 (Oct 2022). https://doi.org/10.1007/s00145-022-09435-1

25. Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.J., De Feo, L., Rodríguez-Henríquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 173–193. Springer, Cham (Oct 2019). https://doi.org/10.1007/978-3-030-30530-7_9

26. Chávez-Saab, J., Chi-Domínguez, J.J., Jaques, S., Rodríguez-Henríquez, F.: The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents. Journal of Cryptographic Engineering 12(3), 349–368 (Sep 2022). https://doi.org/10.1007/s13389-021-00271-w

27. Chen, M., Leroux, A., Panny, L.: SCALLOP-HD: Group action from 2-dimensional isogenies. In: Tang, Q., Teague, V. (eds.) PKC 2024, Part II. LNCS, vol. 14603, pp. 190–216. Springer, Cham (Apr 2024). https://doi.org/10.1007/978-3-031-57725-3_7

28. Cheng, H., Fotiadis, G., Großschädl, J., Ryan, P.Y.A., Rønne, P.B.: Batch-ing CSIDH group actions using AVX-512. IACR TCHES 2021(4), 618–649 (2021). https://doi.org/10.46586/tches.v2021.i4.618-649, https://tches.iacr.org/index.php/TCHES/article/view/9077

29. Chi-Domínguez, J.J., Reijnders, K.: Fully projective radical isogenies in constant-time. In: Galbraith, S.D. (ed.) CT-RSA 2022. LNCS, vol. 13161, pp. 73–95. Springer, Cham (Mar 2022). https://doi.org/10.1007/978-3-030-95312-6_4

30. Chi-Domínguez, J.J., Rodríguez-Henríquez, F.: Optimal strategies for CSIDH. Cryptology ePrint Archive, Report 2020/417 (2020), https://eprint.iacr.org/2020/417

31. Childs, A.M., Van Dam, W.: Quantum algorithms for algebraic problems. Reviews of Modern Physics 82(1), 1–52 (2010)

32. Cohen, H., Lenstra, H.W.: Heuristics on class groups of number fields. In: Jager, H. (ed.) Number Theory Noordwijkerhout 1983. pp. 33–62. Springer Berlin Heidelberg, Berlin, Heidelberg (1984)

33. Cohen, H.: A Course in Computational Algebraic Number Theory. Springer Publishing Company, Incorporated (2010)

34. Colò, L., Kohel, D.: Orienting supersingular isogeny graphs. Journal of Mathematical Cryptology, vol. 14, pp. 414–437 (2020). https://doi.org/10.1515/jmc-2019-0034

35. Conrey, J.B., Holmstrom, M.A., McLaughlin, T.L.: Smooth neighbors. Experimental Mathematics 22(2), 195–202 (2013)

36. Costello, C.: Computing supersingular isogenies on Kummer surfaces. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 428–456. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-03332-3_16

37. Costello, C.: B-SIDH: Supersingular isogeny Diffie-Hellman using twisted torsion. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 440–463. Springer, Cham (Dec 2020). https://doi.org/10.1007/978-3-030-64834-3_15

38. Costello, C., Meyer, M., Naehrig, M.: Sieving for twin smooth integers with solutions to the prouhet-tarry-escott problem. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 272–301. Springer, Cham (Oct 2021). https://doi.org/10.1007/978-3-030-77870-5_10
39. Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006), https://eprint.iacr.org/2006/291

40. Dartois, P., De Feo, L.: On the security of OSIDH. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022, Part I. LNCS, vol. 13177, pp. 52–81. Springer, Cham (Mar 2022). https://doi.org/10.1007/978-3-030-97121-2_3

41. De Feo, L., Fouotsa, T.B., Kutas, P., Leroux, A., Merz, S.P., Panny, L., Wesolowski, B.: SCALLOP: Scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023, Part I. LNCS, vol. 13940, pp. 345–375. Springer, Cham (May 2023). https://doi.org/10.1007/978-3-031-31368-4_13

42. 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.) ASIACRYPT 2020, Part I. LNCS, vol. 12491, pp. 64–93. Springer, Cham (Dec 2020). https://doi.org/10.1007/978-3-030-64837-4_3

43. De Feo, L., Leroux, A., Longa, P., Wesolowski, B.: New algorithms for the deuring correspondence: Towards practical and secure sqisign signatures. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 659–690. Springer (2023)

44. Decru, T.: Radical $\tilde{V}êlu$ isogeny formulae. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024, Part V. LNCS, vol. 14924, pp. 107–128. Springer, Cham (Aug 2024). https://doi.org/10.1007/978-3-031-68388-6_5

45. Duke, W.: Hyperbolic distribution problems and half-integral weight Maass forms. Invent. Math. 92(1), 73–90 (1988). https://doi.org/10.1007/BF01393993

46. Elkies, N., Ono, K., Yang, T.: Reduction of CM elliptic curves and modular function congruences. Int. Math. Res. Not. (44), 2695–2707 (2005). https://doi.org/10.1155/IMRN.2005.2695

47. Eriksen, J.K., Panny, L., Sotáková, J., Veroni, M.: Deuring for the people: supersingular elliptic curves with prescribed endomorphism ring in general characteristic. In: LuCaNT: LMFDB, computation, and number theory, Contemp. Math., vol. 796, pp. 339–373 (2024). https://doi.org/10.1090/conm/796/16008

48. Gajland, P., de Kock, B., Quaresma, M., Malavolta, G., Schwabe, P.: SWOOSH: Efficient lattice-based non-interactive key exchange. In: Balzarotti, D., Xu, W. (eds.) USENIX Security 2024. USENIX Association (Aug 2024)

49. Houben, M.: Deterministic algorithms for class group actions. Cryptology ePrint Archive, Report 2025/847 (2025), https://eprint.iacr.org/2025/847

50. Hutchinson, A., LeGrow, J.T., Koziel, B., Azarderakhsh, R.: Further optimizations of CSIDH: A systematic approach to efficient strategies, permutations, and bound vectors. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 20International Conference on Applied Cryptography and Network Security, Part I. LNCS, vol. 12146, pp. 481–501. Springer, Cham (Oct 2020). https://doi.org/10.1007/978-3-030-57808-4_24

51. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011. pp. 19–34. Springer, Berlin, Heidelberg (Nov / Dec 2011). https://doi.org/10.1007/978-3-642-25405-5_2

52. Jaques, S., Schanck, J.M.: Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE. Cryptology ePrint Archive, Report 2019/103 (2019), https://eprint.iacr.org/2019/103

53. Kohel, D., Lauter, K., Petit, C., Tignol, J.P.: On the quaternion $\ell$-isogeny path problem. LMS J. Comput. Math. 17, 418–432 (2014). https://doi.org/10.1112/S1461157014000151
54. Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing 35(1), 170–188 (2005)

55. Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), vol. 22, pp. 20–34. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2013). https://doi.org/10.4230/LIPIcs.TQC.2013.20, http://drops.dagstuhl.de/opus/volltexte/2013/4321

56. Leem, S., Jacobson Jr, M.J., Scheidler, R.: Solving norm equations in global function fields. Research in Number Theory 11(1), 17 (2025)

57. LeGrow, J., Hutchinson, A.: An analysis of fault attacks on CSIDH. Cryptology ePrint Archive, Report 2020/1006 (2020), https://eprint.iacr.org/2020/1006

58. LeGrow, J.T.: A faster method for fault attack resistance in static/ephemeral CSIDH. Journal of Cryptographic Engineering 13(3), 283–294 (Sep 2023). https://doi.org/10.1007/s13389-023-00318-0

59. LeGrow, J.T., Hutchinson, A.: (Short paper) analysis of a strong fault attack on static/ephemeral CSIDH. In: Nakanishi, T., Nojima, R. (eds.) IWSEC 21. LNCS, vol. 12835, pp. 216–226. Springer, Cham (Sep 2021). https://doi.org/10.1007/978-3-030-85987-9_12

60. Leonardi, C.: A note on the ending elliptic curve in SIDH. Cryptology ePrint Archive, Report 2020/262 (2020), https://eprint.iacr.org/2020/262

61. Leroux, A.: An effective lower bound on the number of orientable supersingular elliptic curves. In: Smith, B., Wu, H. (eds.) SAC 2022. LNCS, vol. 13742, pp. 263–281. Springer, Cham (Aug 2024). https://doi.org/10.1007/978-3-031-58411-4_12

62. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 448–471. Springer, Cham (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_16

63. Meyer, M., Campos, F., Reith, S.: On lions and elligators: An efficient constant-time implementation of CSIDH. In: Ding, J., Steinwandt, R. (eds.) Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019. pp. 307–325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_17

64. Meyer, M., Reith, S.: A faster way to the CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 137–152. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-05378-9_8

65. Michel, P.: The subconvexity problem for Rankin-Selberg *L*-functions and equidistribution of Heegner points. Ann. of Math. (2) **160**(1), 185–236 (2004). https://doi.org/10.4007/annals.2004.160.185

66. Morrison, T., Panny, L., Sotáková, J., Wills, M.: The sea algorithm for endomorphisms of supersingular elliptic curves (2025), https://arxiv.org/abs/2501.16321

67. Onuki, H.: On oriented supersingular elliptic curves. Finite Fields and Their Applications (2021), https://doi.org/10.1016/j.ffa.2020.101777

68. Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: (Short paper) A faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds.) IWSEC 19. LNCS, vol. 11689, pp. 23–33. Springer, Cham (Aug 2019). https://doi.org/10.1007/978-3-030-26834-3_2

69. van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12(1), 1–28 (Jan 1999). https://doi.org/10.1007/PL00003816
70. Peikert, C.: He gives C-sieves on the CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 463–492. Springer, Cham (May 2020). https://doi.org/10.1007/978-3-030-45724-2_16

71. Pope, G.: An implementation of isogenies between Kummer Lines of Montgomery curves using $x$-only arithmetic, https://github.com/GiacomoPope/KummerIsogeny

72. Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space (2004), https://arxiv.org/pdf/quant-ph/0406151

73. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472–503. Springer, Cham (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_17

74. Robert, D.: The module action for isogeny based cryptography. Cryptology ePrint Archive, Paper 2024/1556 (2024), https://eprint.iacr.org/2024/1556

75. Rostovtsev, A., Stolbunov, A.: Public-Key Cryptosystem Based On Isogenies. Cryptology ePrint Archive, Report 2006/145 (2006), https://eprint.iacr.org/2006/145

76. Santos, M.C.R., Eriksen, J.K., Meyer, M., Reijnders, K.: AprèsSQI: Extra fast verification for SQIsign using extension-field signing. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024, Part I. LNCS, vol. 14651, pp. 63–93. Springer, Cham (May 2024). https://doi.org/10.1007/978-3-031-58716-0_3

77. Santos, M.C.R., Eriksen, J.K., Meyer, M., Rodríguez-Henríquez, F.: Finding practical parameters for isogeny-based cryptography. CiC 1(3), 39 (2024). https://doi.org/10.62056/ayojbhey6b

78. Sterner, B.: Towards optimally small smoothness bounds for cryptographic-sized twin smooth integers and their isogeny-based applications. Cryptology ePrint Archive, Report 2023/1576 (2023), https://eprint.iacr.org/2023/1576

79. Størmer, C.: Quelques théorèmes sur l'équation de pell x² - dy² = ±1 et leurs applications. Christiania Videnskabens Selskabs Skrifter, Math. Nat. Kl,(2) 48 (1897)

80. Tani, S.: Claw finding algorithms using quantum walk. Theoretical Computer Science 410(50), 5285–5297 (2009)

81. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.6) (2025), https://www.sagemath.org

82. Vélu, J.: Isogénies entre courbes elliptiques. Comptes-Rendus de l'Académie des Sciences **273**, 238-241 (1971)

83. Wesolowski, B.: Orientations and the supersingular endomorphism ring problem. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 345–371. Springer, Cham (May / Jun 2022). https://doi.org/10.1007/978-3-031-07082-2_13