# On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves

Wouter Castryck, Marc Houben, Frederik Vercauteren, Benjamin Wesolowski

► To cite this version:

Wouter Castryck, Marc Houben, Frederik Vercauteren, Benjamin Wesolowski. On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves. Fifteenth Algorithmic Number Theory Symposium, ANTS-XV, Aug 2022, Bristol, United Kingdom. hal-03805601

HAL Id: hal-03805601

https://hal.science/hal-03805601

Submitted on 7 Oct 2022

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# ON THE DECISIONAL DIFFIE–HELLMAN PROBLEM FOR CLASS GROUP ACTIONS ON ORIENTED ELLIPTIC CURVES

WOUTER CASTRYCK, MARC HOUBEN, FREDERIK VERCAUTEREN, AND BENJAMIN WESOLOWSKI

**ABSTRACT.** We show how the Weil pairing can be used to evaluate the assigned characters of an imaginary quadratic order $\mathcal{O}$ in an unknown ideal class $[\mathfrak{a}] \in \text{cl}(\mathcal{O})$ that connects two given $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E', \iota') = [\mathfrak{a}](E, \iota)$. When specialized to ordinary elliptic curves over finite fields, our method is conceptually simpler and often somewhat faster than a recent approach due to Castryck, Sotáková and Vercauteren, who rely on the Tate pairing instead. The main implication of our work is that it breaks the decisional Diffie–Hellman problem for practically all oriented elliptic curves that are acted upon by an even-order class group. It can also be used to better handle the worst cases in Wesolowski’s recent reduction from the vectorization problem for oriented elliptic curves to the endomorphism ring problem, leading to a method that always works in sub-exponential time.

## 1. INTRODUCTION

This paper is primarily concerned with the DECISIONAL DIFFIE–HELLMAN PROBLEM (DDH) for ideal class groups acting on oriented elliptic curves through isogenies. In order to state this problem precisely, we fix an order $\mathcal{O}$ in an imaginary quadratic number field $K$ along with an algebraically closed field $k$. A (primitive) $\mathcal{O}$-orientation on an elliptic curve $E$ over $k$ is an injective ring homomorphism $\iota : \mathcal{O} \hookrightarrow \text{End}(E)$ that cannot be extended to a superorder $\mathcal{O}' \supseteq \mathcal{O}$ in $K$. The set

$$ \mathcal{E}\mathcal{l}\mathcal{O}(k) = \{ (E, \iota) \mid E \text{ an elliptic curve over } k \text{ and } \iota \text{ an } \mathcal{O}\text{-orientation on } E \} / \cong, $$
if non-empty, comes equipped with a free action

$$ (1) \qquad \text{cl}(\mathcal{O}) \times \mathcal{E}\mathcal{l}\mathcal{O}(k) \to \mathcal{E}\mathcal{l}\mathcal{O}(k) : ([\mathfrak{a}], (E, \iota)) \mapsto [\mathfrak{a}](E, \iota) $$

by the ideal class group of $\mathcal{O}$, see Section 2 for details (including what it means for two $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E', \iota')$ to be isomorphic). Now assume that a party, say Eve, has unlimited access to samples from $\mathcal{E}\mathcal{l}\mathcal{O}(k)^3$ that are consistently of either of the following two forms:

$$ \begin{aligned} & ([\mathfrak{a}](E, \iota), [\mathfrak{b}](E, \iota), [\mathfrak{a}][\mathfrak{b}](E, \iota)) \qquad [\mathfrak{a}], [\mathfrak{b}] \stackrel{\$}{\leftarrow} \text{cl}(\mathcal{O}), \\ & ([\mathfrak{a}](E, \iota), [\mathfrak{b}](E, \iota), [\mathfrak{c}](E, \iota)) \qquad [\mathfrak{a}], [\mathfrak{b}], [\mathfrak{c}] \stackrel{\$}{\leftarrow} \text{cl}(\mathcal{O}), \end{aligned} $$

for some fixed and publicly known $(E, \iota)$. Then Eve successfully solves DDH if she can guess, with non-negligible advantage, from which of these two distributions her triples were sampled.

The hardness of the decisional Diffie–Hellman problem is a natural security foundation for cryptographic constructions based on ideal class group actions, which trace back to the works of Couveignes [11] and Rostovtsev–Stolbunov [24, 28] and
which have attracted much attention lately, in the context of post-quantum cryp-
tography. Here, one lets $k$ be an algebraic closure of a finite field, in which case all
curves in $\mathcal{E}\mathcal{L}_\mathcal{O}(k)$ can be defined over a common finite subfield $F \subseteq k$. While the
initial focus was on ordinary elliptic curves, whose orientations $\iota$ are just ring iso-
morphisms, most of the latest work is concerned with supersingular elliptic curves,
whose endomorphism rings are orders in a quaternion algebra and therefore leave
room for a wide range of orientations. Here, we highlight supersingular elliptic
curves defined over a finite prime field $\mathbb{F}_p$, which are naturally oriented by an order
in $\mathbb{Q}(\sqrt{-p})$. The corresponding ideal class group actions underpin CSIDH [6] and
spin-offs such as [1, 15, 2, 20], and tend to yield more practical cryptosystems than
in the ordinary case. More generally oriented supersingular elliptic curves made
their first cryptographic appearance in the OSIDH protocol due to Colò and Ko-
hel [10]. To date, this protocol remains largely theoretical, but it has attracted a
good amount of recent interest, see e.g. [13, 22, 31].

Our paper revisits the recent work [8], which presents an efficient solution to DDH
for essentially all ordinary elliptic curves over finite fields whose endomorphism ring
has an even class number. In more detail, as soon as there exists a non-trivial
assigned character $\chi : \text{cl}(\mathcal{O}) \to \{\pm 1\}$ of sufficiently small modulus $m$, the attack
from [8] allows Eve to compute $\chi([\mathfrak{a}])$ merely from the knowledge of $(E, \iota)$ and
$(E', \iota') = [\mathfrak{a}](E, \iota)$, i.e., without knowing $[\mathfrak{a}]$ itself. This indeed suffices to break
DDH, since it allows her to check whether $\chi([\mathfrak{c}]) = \chi([\mathfrak{a}])\chi([\mathfrak{b}])$, which is true for
$[\mathfrak{c}] = [\mathfrak{a}][\mathfrak{b}]$, but for uniformly random $[\mathfrak{c}]$ it fails with probability $1/2$.

Unfortunately, the method from [8] is specific to ordinary curves: the attack
proceeds by extending the base field and navigating to the floors of the $m$-isogeny
volcanoes<fnref n="1" /> of $(E, \iota)$ and $(E', \iota')$, with the goal of enforcing non-trivial cyclic rational
$m^\infty$-torsion, and then recovering the character value using two Tate pairing compu-
tations. Beyond ordinary curves, it is generally impossible to turn the rational $m^\infty$-
torsion cyclic using an isogeny walk, so this strategy fails. For supersingular elliptic
curves over $\mathbb{F}_p$ with $p \equiv 1 \bmod 4$ equipped with their natural $\mathbb{Z}[\sqrt{-p}]$-orientation,
where it suffices to consider the assigned character of modulus $m = 4$, an ad-hoc
fix was given in [8, Thm. 10], but it is unclear how this fix would generalize.

**Contribution.** We give an alternative method for computing assigned character
values $\chi([\mathfrak{a}])$ purely from $(E, \iota)$ and $(E', \iota') = [\mathfrak{a}](E, \iota)$, using the Weil pairing rather
than the Tate pairing. Our approach deals with arbitrary orientations and works
over arbitrary fields. Moreover, it simplifies and often speeds up the attack from [8]
in the case of ordinary elliptic curves over finite fields, as it avoids the need for
navigating through isogeny volcanoes. It also naturally incorporates the previously
ad-hoc case of supersingular elliptic curves over prime fields.

The main result is easy enough to be stated right away; we recall that for an
odd prime divisor $m \mid \text{disc}(\mathcal{O})$, the assigned character of modulus $m$ is defined as

$$
(2) \qquad \chi_m : \text{cl}(\mathcal{O}) \to \{\pm 1\} : [\mathfrak{a}] \mapsto \left( \frac{N(\mathfrak{a})}{m} \right)
$$

where it is assumed that $[\mathfrak{a}]$ is represented by an ideal $\mathfrak{a}$ of norm coprime to $m$ (see
our conventions further down) and $(\frac{\cdot}{m})$ is the Legendre symbol.

<footnote n="1">¹Or rather 2-isogeny volcanoes in case $m \in \{4, 8\}$.</footnote>
**Theorem 1.** Let $\mathcal{O}$ be an imaginary quadratic order and let $(E, \iota)$, $(E', \iota')$ be $\mathcal{O}$-oriented elliptic curves connected by an ideal class $[\mathfrak{a}] \in \text{cl}(\mathcal{O})$. Let $m = \text{disc}(\mathcal{O})$ be an odd prime divisor different from $\text{char } k$ and consider the assigned character $\chi_m : \text{cl}(\mathcal{O}) \to \{\pm 1\}$ of modulus $m$. Then $\mathcal{O}$ admits a generator $\sigma$ (i.e. $\mathcal{O} = \mathbb{Z}[\sigma]$) of norm coprime to $m$, and for any such $\sigma$ there exist points $P \in E[m]$, $P' \in E'[m]$ such that $\iota(\sigma)(P)$ is not a multiple of $P$, and likewise for $P'$. Moreover

$$ \chi_m([\mathfrak{a}]) = \left(\frac{a}{m}\right) $$

with $a = \log_{e_m(P, \iota(\sigma)(P))} e_m(P', \iota'(\sigma)(P'))$, regardless of the choice of such $\sigma, P, P'$.

The condition that $\sigma$ be a generator of $\mathcal{O}$ can be relaxed to $\sigma \in \mathcal{O} \setminus (\mathbb{Z} + m\mathcal{O})$. A proof of Theorem 1, along with its adaptations covering assigned characters with even modulus, can be found in Section 3. Since these results apply to arbitrary fields, they may be of independent theoretical interest.

**Applications and implications.** From a cryptographic viewpoint, the most important consequence is that DDH should be considered broken by classical computers for essentially all elliptic curves over finite fields that are oriented by an imaginary quadratic order $\mathcal{O}$ with even class number; see Section 4 for a more in-depth discussion.

As a more surprising application, we prove in Section 5 that the new method allows to significantly improve reductions between computational problems underlying isogeny-based cryptography. On one hand, we have the problem of computing endomorphism rings of supersingular elliptic curves. It is of foundational importance to the field, as its presumed hardness is necessary for the security of essentially all isogeny-based cryptosystems [17, 7, 16]. Oriented versions of this ENDOMORPHISM RING PROBLEM were introduced in [31]. On the other hand, many cryptosystems relate directly to the presumably hard inversion problem for the action of the class group $\text{cl}(\mathcal{O})$ on oriented supersingular curves: the VECTORIZATION PROBLEM. It was proved in [31] that the vectorization problem reduces to the endomorphism ring problem in polynomial time in the length of the instance and in $\#(\text{cl}(\mathcal{O})[2])$. Unfortunately, the dependence on $\#(\text{cl}(\mathcal{O})[2])$ means that the reduction is, in the worst case, exponential in the size of the input, since $\#(\text{cl}(\mathcal{O})[2])$ could be as large as $D^{1/\log \log D}$, where $D = |\text{disc}(\mathcal{O})|$. We improve this result, by proving in Section 5 that there is a reduction from the vectorization problem to the endomorphism ring problem that, in the worst case, is sub-exponential in the length of the input.

**Conventions.** Throughout, all ideal classes $[\mathfrak{a}] \in \text{cl}(\mathcal{O})$ are assumed to be represented by an ideal $\mathfrak{a}$ of norm coprime to $p \text{disc}(\mathcal{O})$, where $p = \max\{1, \text{char } k\}$. Such a representative always exists, see e.g. [12, Cor. 7.17]. For an $\mathcal{O}$-oriented elliptic curve $(E, \iota)$ and a point $P \in E$, we will sometimes write $\sigma(P)$ instead of $\iota(\sigma)(P)$ if $\iota$ is clear from the context. Likewise, for $[\mathfrak{a}] \in \text{cl}(\mathcal{O})$ we will sometimes write $[\mathfrak{a}]E$ for the first component of $[\mathfrak{a}](E, \iota)$.

**Paper organization.** Section 2 provides background: it gives the full list of assigned characters of an imaginary quadratic order and it recalls how its ideal class group acts on oriented elliptic curves. Our main Section 3 contains a proof of Theorem 1, as well as statements and proofs for the even-modulus counterparts.
Section 4 discusses the algorithmic aspects of these results, along with their implications for the decisional Diffie-Hellman problem. Finally, in Section 5 we present our improved reduction from the vectorization problem for oriented elliptic curves to the endomorphism ring problem.

**Acknowledgements.** The first-listed and third-listed authors are supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 101020788 - Adv-ERC-ISOCRYPT) and also by CyberSecurity Research Flanders with reference number VR20192203. The second-listed author is supported by the Research Foundation - Flanders (FWO) under a PhD Fellowship Fundamental Research. The fourth-listed author is supported by the Agence Nationale de la Recherche under grants ANR MELODIA (ANR-20-CE40-0013) and ANR CIAO (ANR-19-CE48-0008). We thank the anonymous reviewers for several helpful comments, and Daniel J. Bernstein for suggesting to use Kedlaya-Umans factorization in the proof of Theorem 2.

## 2. BACKGROUND

2.1. **Assigned characters.** The following is a very brief summary of the relevant parts of [12, I. §3 & II. §7], to which we refer for more details. From genus theory, we know that each order $\mathcal{O}$ in an imaginary quadratic field comes equipped with an explicit list of group homomorphisms $\text{cl}(\mathcal{O}) \to \{\pm 1\}$, called the assigned characters, whose joint kernel is $\text{cl}(\mathcal{O})^2$. Writing

$$ \text{disc}(\mathcal{O}) = -2^f d = -2^f m_1^{f_1} m_2^{f_2} \cdots m_r^{f_r} $$

for distinct odd prime numbers $m_1, \dots, m_r$ and exponents $f \ge 0$, $f_1, \dots, f_r \ge 1$, this list consists of

<table><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}$</td><td>if $f=0$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}, \delta$</td><td>if $f=2$ and $d \equiv 1 \pmod 4$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}$</td><td>if $f=2$ and $d \equiv 3 \pmod 4$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}, \delta \epsilon$</td><td>if $f=3$ and $d \equiv 1 \pmod 4$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}, \epsilon$</td><td>if $f=3$ and $d \equiv 3 \pmod 4$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}, \delta$</td><td>if $f=4$,</td></tr><tr><td>$\chi_{m_1}, \dots, \chi_{m_r}, \delta, \epsilon$</td><td>if $f \ge 5$.</td></tr></table>

Here $\chi_{m_i}$ is defined as in (2) and

$$ \delta : \text{cl}(\mathcal{O}) \to \{\pm 1\} : [\mathfrak{a}] \mapsto (-1)^{\frac{N(a)-1}{2}}, \quad \epsilon : \text{cl}(\mathcal{O}) \to \{\pm 1\} : [\mathfrak{a}] \mapsto (-1)^{\frac{N(a)^2-1}{8}}. $$

Observe that $\delta \epsilon$ can be described in one go as

$$ \delta \epsilon : \text{cl}(\mathcal{O}) \to \{\pm 1\} : [\mathfrak{a}] \mapsto (-1)^{\frac{(N(a)+2)^2-9}{2}}. $$

We write $\mu \in \{r, r+1, r+2\}$ for the total number of assigned characters.

Because the joint kernel is $\text{cl}(\mathcal{O})^2$, any character of $\text{cl}(\mathcal{O})$ whose order divides 2 can be written as a product of pairwise distinct assigned characters. As it turns out, there is a unique non-trivial combination that produces the trivial character:

$$ (3) \qquad \chi_{m_1}^{f_1 \pmod 2} \chi_{m_2}^{f_2 \pmod 2} \cdots \chi_{m_r}^{f_r \pmod 2} \delta^{\frac{d+1}{2} \pmod 2} \epsilon^{f \pmod 2} = 1. $$

Therefore, by combining assigned characters we obtain $2^{\mu-1}$ distinct characters. Necessarily, this quantity equals the cardinality of $\text{cl}(\mathcal{O})/\text{cl}(\mathcal{O})^2 \cong \text{cl}(\mathcal{O})[2]$.
**Example 1.** For a prime number $p \equiv 1 \mod 4$, the ring $\mathbb{Z}[\sqrt{-p}]$ has two assigned characters: $\delta$ and $\chi_p$. By (3) these are in fact equal to each other, and non-trivial. If $p \equiv 3 \mod 4$ then $\mathbb{Z}[\sqrt{-p}]$ has only one assigned character, namely $\chi_p$, and it is trivial.

We often make reference to the modulus $m$ of an assigned character $\chi$, which is an important complexity parameter for our attack. This is simply defined to be

$$ \left\{ \begin{array}{ll} m_i & \text{if } \chi = \chi_{m_i}, \\ 4 & \text{if } \chi = \delta, \\ 8 & \text{if } \chi = \epsilon, \delta\epsilon. \end{array} \right. $$

Note that $\chi([\mathfrak{a}]) = \chi([\mathfrak{a}'])$ as soon as $N(\mathfrak{a}) \equiv N(\mathfrak{a}') \mod m$. Typically $m$ is the smallest positive integer with this property, but not always (e.g., as in the case of $m_i = p$ in both examples above).

**2.2. Class group action.** We now recall how the ideal class group of $\mathcal{O}$ acts on $\mathcal{O}\mathcal{L}_{\mathcal{O}}(k)$. This is part of the theory of complex multiplication, which is classical for $k = \mathbb{C}$, while for $k$ an algebraic closure of a finite field this was elaborated in [30, §3.9-12]; see also [22] for the specifics of the supersingular case. For arbitrary $k$, we refer to Milne's course notes [21, §7].

If $\iota$ is an $\mathcal{O}$-orientation on an elliptic curve $E$ over $k$, then we can linearly extend it to a map $K \hookrightarrow \text{End}^0(E)$, where $\text{End}^0(E) = \text{End}(E) \otimes_{\mathbb{Z}} \mathbb{Q}$ denotes the endomorphism algebra. To each isogeny $\varphi : E \to E'$ we can naturally attach an embedding

$$ \iota_{\mathcal{Q}} : K \hookrightarrow \text{End}^0(E') : \sigma \mapsto \frac{1}{\deg \varphi} \varphi \circ \iota(\sigma) \circ \hat{\varphi}, $$

whose restriction to the preimage $\mathcal{O}'$ of $\text{End}(E')$ is an orientation that is called the *induced orientation*, denoted by $\varphi_{*\iota}$. We are primarily interested in isogenies $\varphi$ for which $\mathcal{O}' = \mathcal{O}$, in which case $\varphi$ is said to be *horizontal* with respect to $\iota$. Two $\mathcal{O}$-oriented elliptic curves $(E, \iota)$, $(E', \iota')$ are called *isomorphic*, denoted $(E, \iota) \cong (E', \iota')$, if there exists an isomorphism $\varphi : E \to E'$ such that $\iota' = \varphi_{*\iota}$.

The default way to construct a horizontal isogeny is by considering an invertible ideal $\mathfrak{a} \subseteq \mathcal{O}$ of norm coprime to $\max\{1, \text{char } k\}$ and attaching to it the finite subgroup

$$ E[\mathfrak{a}] = \bigcap_{\alpha \in \mathfrak{a}} \ker \iota(\alpha). $$

Then the separable degree-$N(\mathfrak{a})$ isogeny $\varphi_{\mathfrak{a}} : E \to E'$ with kernel $E[\mathfrak{a}]$ is horizontal. In particular $E'$ comes naturally equipped with an $\mathcal{O}$-orientation $\iota' = \varphi_{\mathfrak{a}*\iota}$. The pair $(E', \iota')$ is well-defined up to isomorphism and only depends on the class of $\mathfrak{a}$ inside $\text{cl}(\mathcal{O})$; we write $[\mathfrak{a}](E, \iota) := (E', \iota')$. This defines the map (1), which turns out to be a free group action.

**Remark 1.** In general the action is not transitive, where one subtlety is reflected in [22, Prop. 3.3]; see also the example in [22, §3.1] and the proof of [26, Thm. 4.5]. This has no consequences for the current paper, since we are working in a single orbit, namely that of the starting curve $(E, \iota)$.

### 3. EVALUATING CHARACTERS USING THE WEIL PAIRING

In this section we prove Theorem 1 and discuss its analogues for the assigned characters $\delta, \epsilon, \delta\epsilon$. In all cases it is assumed that $p = \max\{1, \text{char } k\}$ is coprime to
the modulus of the character under consideration. If $p$ is an odd prime then $\chi_p$, if it appears in the list of assigned characters, can be computed from the other characters using the relation (3); see for instance Example 1 where we had $\chi_p = \delta$. If $p = 2$ then the same conclusion holds for $\delta$, $\epsilon$ or $\delta\epsilon$, because in even characteristic at most one of these three characters can appear in the list of assigned characters.<fnref n="2" />

### 3.1. Preliminaries.

**Lemma 1.** Let $\mathcal{O}$ be an imaginary quadratic order and let $m$ be an odd prime number. Then $\mathcal{O} = \mathbb{Z}[\sigma]$ for some $\sigma \in \mathcal{O}$ of norm coprime to $m$.

*Proof.* Let $\tau \in \mathcal{O}$ be a generator of $\mathcal{O}$, suppose of norm divisible by $m$. Then for any $k \in \mathbb{Z}$,

$$N(\tau + k) = N(\tau) + k(\mathrm{tr}(\tau) + k) \equiv k(\mathrm{tr}(\tau) + k) \mod m.$$

Since $m \ge 3$ we can thus always find $k \in \mathbb{Z}$ such that $m \nmid N(\tau + k)$. □

**Lemma 2.** Let $\mathcal{O}$ be an imaginary quadratic order of even discriminant. Then $\mathcal{O} = \mathbb{Z}[\sigma]$ for some $\sigma \in \mathcal{O}$ of odd norm.

*Proof.* Let $\tau \in \mathcal{O}$ be a purely imaginary generator of $\mathcal{O}$, e.g. $\tau = \sqrt{\mathrm{disc}(\mathcal{O})/4}$, where $\mathrm{disc}(\mathcal{O})$ is the discriminant of $\mathcal{O}$. Then $N(\tau + 1) = N(\tau) + \mathrm{tr}(\tau) + 1 = N(\tau) + 1$, hence we can take $\sigma = \tau$ or $\sigma = \tau + 1$. □

**Lemma 3.** Let $\mathcal{O}$ be an imaginary quadratic order, let $(E, \iota)$ be an $\mathcal{O}$-oriented elliptic curve over $k$, let $m \neq \mathrm{char} k$ be a prime number, and let $\sigma \in \mathcal{O}$ be a generator. Then there exists a $P \in E[m]$ such that $\iota(\sigma)(P)$ is not a multiple of $P$.

*Proof.* The endomorphism $\iota(\sigma)$ of $E$ induces an $\mathbb{F}_m$-linear map $E[m] \to E[m]$. Suppose to the contrary that every $P \in E[m]$ is an eigenvector. This can only happen if the map has the full $m$-torsion $E[m]$ as an eigenspace. Thus there exists $\lambda \in \mathbb{Z}$ such that $E[m] \subseteq \ker(\iota(\sigma - \lambda))$. It then follows that $\iota_Q((\sigma - \lambda)/m) \in \mathrm{End}(E)$, and hence that $\sigma - \lambda \in m\mathcal{O}$ by the fact that $\iota$ is a primitive embedding, i.e. it cannot be extended to a strict superorder of $\mathcal{O}$. Since $\mathbb{Z} + m\mathcal{O} \subsetneq \mathcal{O}$ this contradicts the assumption that $\sigma$ generates $\mathcal{O}$. □

### 3.2. Evaluating the characters $\chi_m$. We now prove Theorem 1.

*Proof of Theorem 1.* The existence of $\sigma, P, P'$ follows from Lemma 1 and Lemma 3. The endomorphism $\iota(\sigma)$ of $E$ induces an $\mathbb{F}_m$-linear map $E[m] \to E[m]$. Since $m \mid \mathrm{disc}(\mathcal{O}) = \mathrm{tr}(\sigma)^2 - 4N(\sigma)$ and $m \nmid N(\sigma)$, its characteristic polynomial has a nonzero double root, say $\alpha \in \mathbb{F}_m^\times$. Consequently, we can extend to a basis $P_0, P$ of $E[m]$ for which the matrix of $\sigma$ is in upper-triangular form $(\alpha \beta)$ for some $\beta \in \mathbb{F}_m^\times$. With respect to this basis any $Q \in E[m]$ that is not an eigenvector of $\sigma$ is of the form $Q = \lambda P_0 + \mu P$ where $\mu \neq 0$. We see that

$$e_m(Q, \sigma(Q)) = e_m(\lambda P_0 + \mu P, (\alpha\lambda + \beta\mu)P_0 + \alpha\mu P) = e_m(P, \beta P_0)^{\mu^2} = e_m(P, \sigma(P))^{\mu^2},$$

<footnote n="2">²If $(E, \iota)$ is an $\mathcal{O}$-oriented elliptic curve over an algebraically closed field $k$ with $\mathrm{char} k = 2$, then $2^5 \nmid \mathrm{disc}(\mathcal{O})$. Indeed, if we would have $2^5 \mid \mathrm{disc}(\mathcal{O})$ then $E$ is necessarily supersingular, hence it concerns $y^2 + y = x^3$, the unique supersingular elliptic curve in characteristic 2. Its endomorphism ring is isomorphic to the ring of Hurwitz quaternions $H$, and it is easy to check that every embedding $\mathcal{O} \hookrightarrow H$ can be extended to an embedding $\mathcal{O}' \hookrightarrow H$ with $\mathrm{disc}(\mathcal{O}') = \mathrm{disc}(\mathcal{O})/4$. See [22, Prop. 3.2] for a generalization of this observation.</footnote>
showing that $e_m(P, \sigma(P))$ is independent of the choice of $P$, up to raising to powers that are nonzero squares modulo $m$. Then, of course, the same conclusion applies to $e_m(P', \sigma(P'))$.

Recall our convention from the introduction, namely that we assume that the norm of $\mathfrak{a}$, which equals the degree of the corresponding isogeny $\varphi = \varphi_{\mathfrak{a}} : E \to E'$, is coprime to $m$. In particular, $P_0 \not\in \ker \varphi$. By definition of the class group action, $\iota' = \varphi_*\iota$ satisfies

$$ \iota'(\sigma)(\varphi(P)) = \left( \frac{1}{\deg \varphi} \varphi\iota(\sigma)\hat{\varphi} \right) (\varphi(P)) = \varphi(\iota(\sigma)(P)) = \beta\varphi(P_0) + \alpha\varphi(P), $$

showing that $\varphi(P)$ is not an eigenvector for $\iota'(\sigma)$ acting on $([\mathfrak{a}]E)[m]$. So we see that $e_m(\varphi(P), \iota'(\sigma)(\varphi(P)))$ is obtained from $e_m(P', \iota'(\sigma)(P'))$ by raising it to a nonzero square mod $m$. To conclude, we observe that

$$ e_m(\varphi(P), \iota'(\sigma)(\varphi(P))) = e_m(\varphi(P), \varphi(\iota(\sigma)(P))) = e_m(P, \iota(\sigma)(P))^{\deg \varphi}. \quad \square $$

**3.3. Evaluating $\delta, \epsilon$ or $\delta\epsilon$.** We now present the analogues of Theorem 1 for the even-modulus characters $\delta, \epsilon$ and $\delta\epsilon$. We first focus on $\delta$, which, as we saw in Section 2.1, is an assigned character if and only if we can write $\mathrm{disc}(\mathcal{O}) = -4 \cdot d$ for some $d \equiv 0, 1 \pmod 4$.

**Proposition 1.** Assume $\mathrm{char } k \neq 2$. Let $\mathcal{O}$ be an imaginary quadratic order of discriminant $-4 \cdot d$ where $d \equiv 0, 1 \pmod 4$, and let $(E, \iota)$, $(E', \iota')$ be $\mathcal{O}$-oriented elliptic curves over $k$ connected by an ideal class $[\mathfrak{a}] \in \mathrm{cl}(\mathcal{O})$. Then $\mathcal{O}$ admits an odd-norm generator $\sigma$, and for any such $\sigma$ there exist points $P \in E[4]$, $P' \in E'[4]$ such that $\iota(\sigma)(2P) \neq 2P$ and $\iota'(\sigma)(2P') \neq 2P'$. Moreover

$$ \delta([\mathfrak{a}]) = (-1)^{\frac{a-1}{2}}, $$

with $a = \log_{e_4(P, \iota(\sigma)(P))} e_4(P', \iota'(\sigma)(P'))$, for any such choice of $\sigma, P, P'$.

*Proof.* The existence of $\sigma, P, P'$ follows from Lemma 2 and Lemma 3. Note that the assumption on the discriminant of $\mathcal{O}$ shows that the character $\delta$ indeed exists, and that this implies that $N(\sigma) \equiv 1 \pmod 4$ (since the principal ideal class $[(\sigma)]$ lies in the kernel of $\delta$). By upper-triangularizing the action of $\sigma$ on $E[2]$ as in the proof of Theorem 1, we see that there exists a $P_0 \in E[4]$ such that the matrix $M_\sigma$ of $\sigma$ acting on $E[4]$ with respect to the basis $P_0, P$ is of the form

$$ M_{\sigma} \equiv \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \mod 2. $$

Since $N(\sigma) \equiv 1 \pmod 4$ this means that $M_\sigma$ is of the form either $(\alpha_0 \beta_0)$ or $(\alpha_2 \beta_{-\alpha})$, with $\alpha, \beta$ odd. Any $Q$ with the property that $\sigma(2Q) \neq 2Q$ is of the form $\lambda P_0 + \mu P$ where $\mu$ is odd. If $M_\sigma$ is of the first form we get

$$ e_4(Q, \sigma(Q)) = e_4(\lambda P_0 + \mu P, (\alpha\lambda + \beta\mu)P_0 + \alpha\mu P) = e_4(P, \beta P_0)^{\mu^2} = e_4(P, \sigma(P))^{\mu^2}. $$

If $M_\sigma$ is of the second form we again get

$$ \begin{aligned} e_4(Q, \sigma(Q)) &= e_4(\lambda P_0 + \mu P, (\alpha\lambda + \beta\mu)P_0 + (2\lambda - \alpha\mu)P) \\ &= e_4(P, \beta P_0)^{\mu^2} e_4(P, P_0)^{2(\lambda\alpha\mu - \lambda^2)} = e_4(P, \sigma(P))^{\mu^2} \end{aligned} $$

where the last equality uses that $\lambda, \mu, \alpha$ are odd. From $\mu^2 \equiv 1 \pmod 4$ it follows that $e_4(P, \sigma(P))$ does not depend on the choice of $P$. Then, of course, the same is true for $e_4(P', \sigma(P'))$.
By our convention we assume that the norm of $\mathfrak{a}$, and hence the degree of the corresponding isogeny $\varphi = \varphi_{\mathfrak{a}} : E \to E'$, is odd. In particular, $2P_0 \notin \ker \varphi$ and

$$ \iota'(\sigma)(\varphi(2P)) = \left( \frac{1}{\deg \varphi} \varphi_{\iota}(\sigma) \hat{\varphi} \right) (\varphi(2P)) = \varphi(\iota(\sigma)(2P)) = \varphi(2P_0) + \varphi(2P) $$

is different from $\varphi(2P)$. Thus we find that $e_4(P', \sigma(P'))$ equals

$$ e_4(\varphi(P), \iota'(\sigma)(\varphi(P))) = e_4(\varphi(P), \varphi(\iota(\sigma)(P))) = e_4(P, \iota(\sigma)(P))^{\deg \varphi}, $$

which concludes the proof. □

Next, we discuss the modulus-8 characters $\epsilon$ and $\delta\epsilon$. Note that by Section 2.1, we have that $\epsilon$ is an assigned character if and only if either $2^5 | \text{disc}(O)$ or $\text{disc}(O) = -2^3 \cdot d$ with $d \equiv 3 \pmod 4$. Similarly, $\delta\epsilon$ is an assigned character if and only if either $2^5 | \text{disc}(O)$ or $\text{disc}(O) = -2^3 \cdot d$ with $d \equiv 1 \pmod 4$.

**Proposition 2.** Assume $\mathfrak{k} \neq 2$, let $O$ be an imaginary quadratic order of discriminant $\text{disc}(O) = -2^f d$ with $d$ odd and $f \ge 3$, and consider $O$-oriented elliptic curves $(E, \iota)$, $(E', \iota')$ over $\mathfrak{k}$ connected by an ideal class $[\mathfrak{a}] \in \text{cl}(O)$. Assume that $\epsilon$, resp. $\delta\epsilon$, appears among the assigned characters of $O$. Then $O$ admits an odd-norm generator $\sigma$, and for any such $\sigma$ there exist points $P \in E[8]$, $P' \in E'[8]$ such that $\iota(\sigma)(4P) \neq 4P$ and $\iota'(\sigma)(4P') \neq 4P'$. Moreover $\epsilon([\mathfrak{a}])$, resp. $\delta\epsilon([\mathfrak{a}])$, can be computed as

$$ \epsilon([\mathfrak{a}]) = (-1)^{\frac{a^2-1}{8}}, \quad \text{resp.} \quad \delta\epsilon([\mathfrak{a}]) = (-1)^{\frac{(a+2)^2-9}{8}}, $$

with $a = \log_{e_8(P,\iota(\sigma)(P))} e_8(P',\iota'(\sigma)(P'))$, and for any such choice of $\sigma, P, P'$.

*Proof.* As in the previous proof, the existence of $\sigma, P, P'$ follows from Lemma 2 and Lemma 3. The main difference with the foregoing proofs is that if $Q \in E[8]$ is another point satisfying $\sigma(4Q) \neq 4Q$, then $e_8(Q, \sigma(Q))$ relates more subtly to $e_8(P, \sigma(P))$. Namely, we will argue that

$$ (4) \qquad e_8(Q, \sigma(Q)) \in \{e_8(P, \sigma(P)), e_8(P, \sigma(P))^{N(\sigma)}\}, $$

and then of course the same again applies to $e_8(P', \sigma(P'))$. This will then lead to the conclusion that

$$ e_8(P', \sigma(P')) \in \{e_8(P, \sigma(P))^{\deg \varphi}, e_8(P, \sigma(P))^{N(\sigma) \deg \varphi}\}, $$

which is indeed sufficient, since the principal ideal class $[(\sigma)]$ has trivial character values. More explicitly, if $\epsilon$ exists then we must have $N(\sigma) \pmod 8 \in \{1, 7\}$, while if $\delta\epsilon$ exists then we have $N(\sigma) \pmod 8 \in \{1, 3\}$.

In order to prove (4), note that, since $N(\sigma) \equiv 1 \pmod 2$,

$$ \text{tr}(\sigma)^2 + 4 \equiv \text{tr}(\sigma)^2 - 4 \cdot N(\sigma) = \text{disc}(O) \equiv 0 \pmod 8, $$

so that $\text{tr}(\sigma) \equiv 2 \pmod 4$. It follows that the characteristic polynomial of $\sigma$ modulo 4 is $X^2 + 2X + N(\sigma)$, hence we can extend to a basis $P_0, P$ of $E[8]$ such that the matrix of $\iota(\sigma)$ acting on $E[8]$ is of the form

$$ M_{\sigma} \equiv \begin{cases} \begin{pmatrix} \alpha & \beta \\ 0 & \alpha \end{pmatrix} \bmod 4 & \text{if } N(\sigma) \equiv 1 \bmod 4, \\ \begin{pmatrix} \alpha & \beta \\ 2 & \alpha \end{pmatrix} \bmod 4 & \text{if } N(\sigma) \equiv 3 \bmod 4, \end{cases} $$
with $\alpha, \beta$ odd. It follows that

$$ M_{\sigma}^{2} \equiv \left\{ \begin{array}{ll} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} & \mod 4 \quad \text{if } N(\sigma) \equiv 1 \mod 4, \\ \begin{pmatrix} 3 & 2 \\ 0 & 3 \end{pmatrix} & \mod 4 \quad \text{if } N(\sigma) \equiv 3 \mod 4. \end{array} \right. $$

In any case we can record that

$$ (5) \qquad e_8(P, \sigma^2(P))^2 = e_8(P, P_0)^4 = -1. $$

Now, with respect to the basis $P, \sigma(P)$, the matrix of $\iota(\sigma)$ acting on $E[8]$ is congruent to $(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}) \mod 2$. Any other $Q = \lambda P + \mu \sigma(P)$ such that $\sigma(4Q) \neq 4Q$ thus has exactly one of $\lambda, \mu$ odd. We now proceed to showing (4). If $\mu$ is odd then we can write $\sigma(Q) = \lambda'P + \mu'\sigma(P)$ with $\lambda' \text{ odd, so since}$

$$ e_8(Q, \sigma(Q))^{N(\sigma)} = e_8(\sigma(Q), \sigma^2(Q)) $$

we may reduce to the case where $\lambda$ is odd (and $\mu$ is even). For odd $\lambda$, we have

$$ e_8(Q, \sigma(Q)) = e_8(\lambda^{-1}Q, \sigma(\lambda^{-1}Q))^{\lambda^2} = e_8(\lambda^{-1}Q, \sigma(\lambda^{-1}Q)), $$

hence we may further reduce to the case where $\lambda = 1$. Now note that

$$ \begin{align*} e_8(P + \mu\sigma(P), \sigma(P) + \mu\sigma^2(P)) &= e_8(P, \sigma(P))e_8(\sigma(P), \sigma^2(P))^{\mu^2}e_8(P, \sigma^2(P))^{\mu} \\ &= e_8(P, \sigma(P))e_8(P, \sigma(P))^{4\frac{\mu^2}{4}N(\sigma)}e_8(P, \sigma^2(P))^{2\frac{\mu^2}{2}} \\ &= e_8(P, \sigma(P)) \cdot (-1)^{\frac{\mu^2}{4}} \cdot (-1)^{\frac{\mu^2}{2}} \\ &= e_8(P, \sigma(P)), \end{align*} $$

where in the third equality we used (5). $\square$

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

**Remark 2.** If $\mathcal{O}$ is an imaginary quadratic order of discriminant $\text{disc}(\mathcal{O}) \equiv 0 \mod 2^5$, then both $\epsilon$ and $\delta\epsilon$ and hence $\delta = (\delta\epsilon)\epsilon$ exist, so that $N(\sigma) \equiv 1 \mod 8$. In this case there is a well-defined group homomorphism $\gamma : \text{cl}(\mathcal{O}) \to (\mathbb{Z}/8\mathbb{Z})^\times : [\mathfrak{a}] \mapsto N(\mathfrak{a}) \mod 8$ through which $\delta, \epsilon, \delta\epsilon$ factor. This is the only situation where one can get finer-than-binary modular information about $N(\mathfrak{a})$ from $[\mathfrak{a}]$; the above proof shows that we can recover $\gamma([\mathfrak{a}])$ at once as $\log_{e_8(P,\iota(\sigma)(P))} e_8(P', \iota'(\sigma)(P'))$.

**Remark 3.** In the statements of Theorem 1, Proposition 1 and Proposition 2, the condition that $\sigma$ be a generator of $\mathcal{O}$ can in fact be relaxed to $\sigma \in \mathcal{O} \setminus (\mathbb{Z} + m\mathcal{O})$ if $m$ is odd and to $\sigma \in \mathcal{O} \setminus (\mathbb{Z} + 2\mathcal{O})$ if $m$ is even, without modifying the proofs.

Wrapping up, we have given justification for Algorithm 1 below, evaluating an assigned character $\chi : \text{cl}(\mathcal{O}) \to \{\pm 1\}$ of modulus $m$ coprime to $\max\{1, \text{char } k\}$ in an unknown ideal class $[\mathfrak{a}]$ connecting two given $\mathcal{O}$-oriented curves $(E, \iota)$ and $(E', \iota')$. Here, by the field of definition of $(E, \iota)$, $(E', \iota')$ we mean any (e.g., the smallest) subfield $F \subseteq k$ over which the curves $E, E'$ and the endomorphisms in $\iota(\mathcal{O}), \iota'(\mathcal{O})$ are defined.

## 4. COMPLEXITY AND CONSEQUENCES FOR DDH

Running Algorithm 1 in practice comes with challenges that are specific to our field of definition $F$. Nevertheless, before going into a more detailed analysis of our main case of interest, namely where $F$ is a finite field, let us add some general comments to its six numbered steps:
**Algorithm 1** Evaluating an assigned character in an unknown ideal class

**Input:**

O-oriented curves $(E, \iota)$, $(E', \iota')$ in the same orbit with field of definition $F$
an assigned character $\chi$ of $\mathrm{cl}(\mathcal{O})$ with modulus $m$ coprime to $\max\{1, \mathrm{char}\,F\}$

**Output:**

$\chi([\mathfrak{a}]) \in \{\pm 1\}$, where $[\mathfrak{a}] \in \mathrm{cl}(\mathcal{O})$ is such that $(E', \iota') = [\mathfrak{a}](E, \iota)$

1. Find a generator $\sigma$ of $\mathcal{O}$ of norm coprime to $m$.

2. Base-change to the smallest extension $\mathcal{F} \supseteq F$ over which all points in $E[m]$ are defined; necessarily, then also all of $E'[m]$ is defined over $\mathcal{F}$.

3. Find a point $P \in E(\mathcal{F})$ such that $E[m] = \langle P, \iota(\sigma)(P) \rangle$ and compute $\zeta = e_m(P, \iota(\sigma)(P))$.

4. Likewise, find a point $P' \in E'(\mathcal{F})$ such that $E'[m] = \langle P', \iota'(\sigma)(P') \rangle$ and compute $\zeta' = e_m(P', \iota'(\sigma)(P'))$.

5. Inside $\mu_m \subseteq \mathcal{F}^\times$, compute $a = \log_\zeta \zeta'$.

6. If $m$ is an odd prime then recover $\chi([\mathfrak{a}])$ as $(\frac{a}{m})$, else recover $\chi([\mathfrak{a}])$ as

$$(-1)^{\frac{a-1}{2}}, \quad (-1)^{\frac{a^2-1}{8}}, \quad (-1)^{\frac{(a+2)^2-9}{8}},$$

depending on whether $\chi = \delta, \epsilon, \delta\epsilon$, respectively.

1. Very easy, by following the proof of Lemma 1 or Lemma 2.

2. The degree of $\mathcal{F}/F$ is a divisor of the order of $\mathrm{GL}_2(\mathbb{Z}/m\mathbb{Z})$, which is $O(m^4)$.

3.–4. For $m$ an odd prime, the proof of Theorem 1 shows that the set of $m$-torsion points that are independent of their image under $\sigma$ has size $m^2 - m$. So it suffices to try $O(1)$ random points $P \in E[m]$, compute $\iota(\sigma)(P)$ and check whether $e_m(P, \iota(\sigma)(P))$ is a primitive $m$th root of unity (i.e., not 1).$^3$

5. Pollard-$\rho$ type algorithms allow us to compute the discrete logarithm using $O(\sqrt{m})$ operations in $\mu_m$.

6. Trivial.

The main bonus we get from working over a finite field lies in (2). In this case the degree of $\mathcal{F}/F$ equals the order of the Frobenius endomorphism $\pi_F$ acting on $E[m]$. While the order of $\mathrm{GL}_2(\mathbb{Z}/m\mathbb{Z})$ is $O(m^4)$, the order of a single element is $O(m^2)$.

**Theorem 2.** Let $\mathcal{O} = \mathbb{Z}[\sigma]$ be an imaginary quadratic order and consider two $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E', \iota')$ that belong to the same orbit under the action of $\mathrm{cl}(\mathcal{O})$, say given in Weierstrass form and connected by an unknown ideal class $[\mathfrak{a}]$. Assume that $E, E', \iota(\mathcal{O}), \iota'(\mathcal{O})$ are all defined over a finite field $\mathbb{F}_q$. Let $\chi$ be an assigned character of $\mathcal{O}$ with modulus $m$ coprime to $q$. There exists a randomized algorithm for computing $\chi([\mathfrak{a}])$ that is expected to use

$$(6) \qquad \tilde{O}(m^3 \log^2 q)$$

bit operations and $O(1)$ calls to $\iota(\sigma), \iota'(\sigma)$.

*Proof.* If we write $f_E(x, y)$ for the defining Weierstrass polynomial of $E$ and $\Psi_{E,m}(x)$ for its $m$-division polynomial, then the field $\mathcal{F}$ can be constructed as the splitting

<footnote>$^3$Alternatively, one may opt for a more deterministic approach by computing and analyzing a matrix of $\iota(\sigma)$ acting on $E[m]$, in which case two evaluations of $\iota(\sigma)$ will do. Note however that writing down a matrix of $\iota(\sigma)$ comes at the cost of computing some discrete logarithms.</footnote>
field of the resultant $r_{E,m}(x) = \text{res}_y(f_E, \Psi_{E,m})$, whose degree is $O(m^2)$. The division polynomial $\Psi_{E,m}(x)$ can be computed recursively and the resultant $r_{E,m}(x)$ can be factored using Kedlaya–Umans [19]. Using fast arithmetic, this takes a combined time of (6). Note that we obtain all points in $E[m]$ as a by-product; once we know $\mathcal{F}$ we can sample points from $E'[m]$ faster. The Weil pairings can be computed using Miller’s algorithm, taking $O(\log m)$ operations in $\mathcal{F}$, and Pollard-$\rho$ takes an expected $O(\sqrt{m})$ operations in $\mathcal{F}$, so these costs are dominated by (6), again assuming fast arithmetic. Finally, while the norm of the given generator $\sigma$ may not be coprime to $m$, from the proofs of Lemma 1 and Lemma 2 we see that we can instead work with $\sigma + k$, for some positive integer $k$ bounded by $m$. Since $\iota(\sigma + k) = \iota(\sigma) + [k]$, the overhead this causes is clearly absorbed by (6); and similarly for $\iota'(\sigma + k)$. $\square$

The effectivity of this algorithm co-depends on how easy it is to evaluate $\iota(\sigma)$ and $\iota'(\sigma)$, which is a separate discussion that is captured by the notion of *efficient representations*, see Section 5.1 and [32] for more details. One special but interesting case is where $\iota(\sigma)$ equals $\pi_{\mathbb{F}_q}$, or is easily derived from it, whose cost is quasi-quadratic in $m \log q$. So, in this case, the overall cost remains estimated by (6). This matches with the asymptotic runtime of the Tate pairing attack from [8], as estimated in [8, §5.1].$^4$

While the Weil pairing attack is conceptually simpler (no descent of the isogeny volcano needed), in general one should expect the Tate pairing attack to run faster in practice. The main reason is that there it suffices to work over a field $\mathcal{F}$ such that $E$ admits an $\mathcal{F}$-rational point of order $m$, rather than requiring all $m$-torsion to be $\mathcal{F}$-rational (in turn, this is because the Tate pairing admits non-trivial self-pairing values, in contrast with the Weil pairing). The degree of such an extension field is bounded by $O(m)$, rather than by $O(m^2)$. But the comparison turns in favour of the Weil pairing as soon as $E[m] \subseteq E(\mathbb{F}_q)$, where no field extension is needed. Note that, here, it makes more sense to measure the cost of a call to $\iota(\sigma)$, $\iota'(\sigma)$ by the cost of evaluating $(\pi_{\mathbb{F}_q} - 1)/m^s$, where $s$ is maximal such that $E[m^s] \subseteq E(\mathbb{F}_q)$; see [25, Lem. 1]. For this we need $s$ successive point divisions by $m$; the cost of such a division is dominated by that of finding a root of a polynomial of degree $m^2$, which can be done in time

$$ (7) \qquad \tilde{O}(m^2 \log^2 q), $$

see [23, §2]. This now becomes the dominant cost of the attack. The asymptotic cost of the Tate pairing also drops to (7) in this case, but the Weil pairing attack comes with less overhead.

All this aside, let us re-emphasize that the Weil pairing approach works in far greater generality: for arbitrary orientations and over any field admitting explicit computation. A proof-of-concept implementation of the new method can be found at https://github.com/KULeuven-COSIC/oriented_DDH. At the time of publication, this implementation handles the case of $\mathbb{Z}[\sqrt{-p}]$-oriented elliptic curves in characteristic $p \equiv 1 \mod 4$. We intend to extend the repository in due course, by also covering the higher-degree group actions that were described in [9].

<footnote>$^4$Here and below, for simplicity, the height $h \approx \text{val}_m(\text{tr}(\pi_{\mathcal{F}})^2 - 4\#\mathcal{F})$ of the $m$-isogeny volcano of $E$ over $\mathcal{F}$ is estimated by $O(1)$.</footnote>
**Consequences for DDH.** If $cl(O)$ admits a non-trivial assigned character whose modulus $m$ is sufficiently small, say polynomially bounded by $log disc(O)$, and if it satisfies $gcd(m, q) = 1$, then we can use this character to distinguish between random triples and Diffie-Hellman triples with probability $1/2$, as explained in the introduction. So, in this case, we can consider the decisional Diffie-Hellman problem broken for $O$-oriented elliptic curves over $F_q$. More generally, if $cl(O)$ admits $s \ge 1$ independent such characters (meaning that one cannot use the relation (3) to rewrite one of the characters in terms of the others), then we can distinguish with probability $1 - 1/2^s$.

A sufficient condition for the existence of such a character is that $disc(O)$ has at least two small odd prime factors different from $p = char F_q$.<fnref n="5" /> Heuristically, we expect that this applies to a density 1 subset of all imaginary quadratic orders when ordered by the absolute value of their discriminant. This can be backed up using Mertens' third theorem; or see [29, III.§6] for more dedicated tools.

As discussed in [8, §6], one can thwart the attack by restricting the class-group action to $cl(O)^2$, or at least to a subgroup of $cl(O)$ on which all assigned characters of small modulus have trivial evaluations. However, this may have practical consequences in terms of key generation and key validation. Moreover, we do not rule out that the attack can be modified to work for characters whose order is a larger power of 2, e.g., in view of [3, 27]. Quantumly, it is known that $2^r$-torsion subgroups, for any small fixed value of $r$, do not contribute to the hardness of the vectorization problem anyway [5]. Therefore, the cleanest way out is to follow the recommendation from [8, §6], namely to only work with orientations by imaginary quadratic orders whose class number is odd. There may be constructive reasons to deviate from this, e.g., as in the OSIDH protocol [10] where one uses orders of large prime power conductor in an imaginary quadratic field with class number one (such orders always have even class number).

*Remark 4.* It is interesting to view Theorem 2 against the classical decisional Diffie-Hellman problem, namely for exponentiation in a group $G = \langle g \rangle$ of some large prime order $m$. Note that exponentiation defines a free and transitive action of $(Z/mZ)^\times$ on the set of generators of $G$. The Legendre symbol

$$ \chi : (\mathbb{Z}/m\mathbb{Z})^\times \to \{\pm 1\} : a \mapsto \left(\frac{a}{m}\right) $$

is the unique quadratic character, of modulus $m$, and if one could cook up an efficient classical way for computing $\chi(a)$ merely from the knowledge of $g$ and $g^a$, then this would break DDH in this setting. This would be a spectacular result; in general, to the best of our knowledge, we cannot do significantly better than computing $a$ using Pollard-$\rho$ and then evaluating $\chi$ at $a$. This should be compared to steps 5. and 6. from Algorithm 1. In other words, one could say that classical DDH is not weakened by the existence of $\chi$ because its modulus is large.

<footnote n="5">⁵In serious cryptographic applications, one can ignore the phrase “different from $p = char F_q$”. Indeed, if $p | disc(O)$ then $E$ and $E'$ are necessarily supersingular, so if moreover $p$ is small then we can compute $End(E)$ and $End(E')$ by navigating through all $O(p)$ nodes of the supersingular isogeny graph. As a result, one is skating on very thin ice (see Section 5).</footnote>
## 5. REDUCTIONS TO ENDOMORPHISM RING COMPUTATION

In this section, we prove that our main result Theorem 1 allows to significantly improve reductions between computational problems underlying isogeny-based cryptography. It was proved in [31] that two such families of problems are tightly connected: there are computational reductions from action inversion problems (called EFFECTIVE $O$-VECTORIZATION or EFFECTIVE $O$-UBER) to endomorphism ring computation problems (called $O$-ENDRING and $O$-ENDRING*). However, these reductions are exponential in the worst case. In this section, we apply Theorem 1 to obtain reductions that are sub-exponential in the worst case, and even polynomial in many regimes of interest. All results in this section that start with (ERH), such as Theorem 3, assume the extended Riemann hypothesis — precisely, the Riemann hypothesis for Hecke $L$-functions.

### 5.1. The supersingular endomorphism ring problem.
In this section, we assume that the field $k$ is an algebraic closure of a finite field of characteristic $p$, and that $p$ does not split in $O$, nor does it divide the conductor of $O$. Then, the set $\mathcal{E}\ell_O(k)$ is non-empty and all curves in it are supersingular; this set is often denoted by $\text{SS}_O(p)$ in the literature [22, Prop. 3.2]. Recall that a curve $E/k$ is supersingular if and only if its endomorphism ring $\text{End}(E)$ is isomorphic to a maximal order in the quaternion algebra

$$B_{p,\infty} = \left( \frac{-q, -p}{\mathbb{Q}} \right) = \mathbb{Q} + \mathbb{Q}i + \mathbb{Q}j + \mathbb{Q}ij,$$

with the multiplication rules $i^2 = -q$, $j^2 = -p$, and $ji = -ij$, where $q$ is a positive integer that depends on $p$.

Given a supersingular elliptic curve $E$ over $k$, the endomorphism ring problem $\text{ENDRING}$ consists in computing four endomorphisms that form a basis of $\text{End}(E)$. There is flexibility in how these endomorphisms can be represented, but we always assume that it is an *efficient representation*. As in [32], we say that an isogeny $\varphi: E \to E'$ is given in an efficient representation if there is an algorithm to evaluate $\varphi(P)$ for any $P \in E(\mathbb{F}_{p^r})$ in time polynomial in the length of the representation of $\varphi$ and in $r \log(p)$. We also assume that an efficient representation of $\varphi$ has length $\Omega(\log(\deg(\varphi)))$.

This endomorphism ring problem is of foundational importance to isogeny-based cryptography: it is presumed to be hard, and this hardness is *necessary* (and sometimes sufficient) for the security of essentially all isogeny-based protocols [17, 7, 16]. It does not, however, capture well the notion of orientation, which plays an important role in many protocols. Therefore, the following oriented variants were introduced in [31]. Computationally, an $O$-orientation $\iota$ is represented by a generator $\sigma$ of $O$ (i.e., $O = \mathbb{Z}[\sigma]$) together with an efficient representation of the endomorphism $\iota(\sigma)$.

**Problem 1 (O-ENDRING).** Given $(E, \iota) \in \mathcal{E}\ell_O(k)$, find a basis of $\text{End}(E)$.

**Problem 2 (O-ENDRING*).** Given an $O$-orientable curve $E$, find a basis of $\text{End}(E)$, and an $O$-orientation of $E$ expressed in this basis.

Clearly, $\text{O-ENDRING}$ reduces to $\text{O-ENDRING*}$.
5.2. **Action inversion problems.** Many cryptosystems relate, directly or more subtly, to an inversion problem for the action of $\text{cl}(\mathcal{O})$ on $\mathcal{E}\mathcal{L}\mathcal{O}(k)$. In essence, given $(E, \iota)$ and $(E', \iota')$ in $\mathcal{E}\mathcal{L}\mathcal{O}(k)$, find a class $[\mathfrak{a}]$ such that $(E', \iota') \cong [\mathfrak{a}](E, \iota)$ (or decide that it does not exist). This is called the vectorization problem. It is too weak for many practical purposes, because knowledge of the class $[\mathfrak{a}]$ is not sufficient to efficiently apply its action on any other $\mathcal{O}$-oriented curve. Therefore, the following stronger problem was introduced in [31].

**Problem 3 (EFFECTIVE $\mathcal{O}$-VECTORIZATION).** Given three $\mathcal{O}$-oriented supersingular curves $(E, \iota), (E', \iota'), (F, j) \in \mathcal{E}\mathcal{L}\mathcal{O}(k)$, find an $\mathcal{O}$-ideal $\mathfrak{a}$ (or decide that it does not exist) such that $(E', \iota') \cong [\mathfrak{a}](E, \iota)$, and an efficient representation of $\varphi_{\mathfrak{a}} : (F, j) \to [\mathfrak{a}](F, j)$.

The security of many cryptosystems directly reduces to this problem, such as CSIDH [6], CSI-FiSh [1], CSURF [4], or other generalizations [9].

One can define a similar problem where no orientation is provided for $E'$. Then, one cannot require $(E', \iota') \cong [\mathfrak{a}](E, \iota)$ anymore, but one can still ask for $E' \cong [\mathfrak{a}]E$. The resulting *Uber isogeny problem* was introduced in [14].

**Problem 4 (EFFECTIVE $\mathcal{O}$-UBER).** Given two $\mathcal{O}$-oriented curves $(E, \iota), (F, j) \in \mathcal{E}\mathcal{L}\mathcal{O}(k)$ and an $\mathcal{O}$-orientable curve $E'$, find an $\mathcal{O}$-ideal $\mathfrak{a}$ such that $E' \cong [\mathfrak{a}]E$, and an efficient representation of $\varphi_{\mathfrak{a}} : (F, j) \to [\mathfrak{a}](F, j)$.

This EFFECTIVE $\mathcal{O}$-UBER problem is significantly harder than the EFFECTIVE $\mathcal{O}$-VECTORIZATION problem. In fact, most isogeny-based cryptosystems reduce to an instance of EFFECTIVE $\mathcal{O}$-UBER [14], even cryptosystems such as SIDH [18] which, at first sight, do not seem to involve any orientation.

5.3. **Action inversion reduces to endomorphism ring.** Strengthening and generalizing a result of [7], it was proved in [31] that EFFECTIVE $\mathcal{O}$-VECTORIZATION reduces to $\mathcal{O}$-ENDRING, and that EFFECTIVE $\mathcal{O}$-UBER reduces to $\mathcal{O}$-ENDRING*. Both reductions are in polynomial time in the length of the instance, and in $\#(\text{cl}(\mathcal{O})[2])$. Unfortunately, the dependence on $\#(\text{cl}(\mathcal{O})[2])$ means that the reduction is, in the worst case, exponential in the size of the input, since $\#(\text{cl}(\mathcal{O})[2])$ could be as large as $D^{1/\log \log D}$, where $D = |\text{disc}(\mathcal{O})|$. The issue is the following: given two oriented curves $(E, \iota)$ and $(E', \iota')$ as in the definition of EFFECTIVE $\mathcal{O}$-VECTORIZATION, the reductions first find a class $[\mathfrak{a}]^2$ such that $(E', \iota') \cong [\mathfrak{a}](E, \iota)$. Finding $[\mathfrak{a}]$ from $[\mathfrak{a}]^2$ is a square root computation. There are $\#(\text{cl}(\mathcal{O})[2])$ square roots of $[\mathfrak{a}]^2$, but only one is the correct class $[\mathfrak{a}]$. In [31], one simply does an exhaustive search. Now, thanks to Theorem 1, there is a much more efficient way to find the correct square root, which in the worst case is sub-exponential in $\text{disc}(\mathcal{O})$. This is the following proposition. Recall the L-notation

$$L_x(\alpha) = \exp\left(\mathcal{O}\left((\log x)^\alpha (\log \log x)^{1-\alpha}\right)\right)$$

for sub-exponential complexities.

**Proposition 3 (ERH).** Given $\mathcal{O}$ of discriminant $-D$, the factorization $D = \prod_{i=1}^{\omega(D)} \ell_i^{e_i}$ (with $\ell_i < \ell_{i+1}$), two $\mathcal{O}$-oriented elliptic curves $(E, \iota), (E', \iota') \in \mathcal{E}\mathcal{L}\mathcal{O}(k)$, a basis of $\text{End}(E)$, and an ideal class $[\mathfrak{c}]^2$ such that $(E', \iota') = [\mathfrak{c}](E, \iota)$, one can find
the ideal class [c] in probabilistic polynomial time in the length of the input and in$^6$

$$ \min \left( 2^{\omega(D)}, \max_i \left( \ell_i \mid \ell_i \le 2^{\omega(D)-i} \right) \right) \ll \min \left( L_D(1/2), \#(\mathrm{cl}(\mathcal{O})[2]), \ell_{\omega(D)} \right). $$

Before proving it, let us recall the following proposition from [31].

**Proposition 4 (ERH, [31, Proposition 9]).** Given $(E, \iota) \in \mathcal{E}\mathcal{L}\mathcal{O}(k)$, a basis of $\mathrm{End}(E)$, and an $\mathcal{O}$-ideal $\mathfrak{a}$, one can compute $[\mathfrak{a}](E, \iota)$ and an efficient representation of $\varphi_{\mathfrak{a}} : (E, \iota) \to [\mathfrak{a}](E, \iota)$ in probabilistic polynomial time in the length of the input.

*Proof of Proposition 3.* Let $B > 0$ be a bound to be tuned later. Consider the sets of prime numbers

$$ P_1 = \{ \ell \mid \ell \text{ is an odd prime factor of } \mathrm{disc}(\mathcal{O}) \text{ and } \ell \le B \}, \text{ and} $$

$$ P_2 = \{ \ell \mid \ell \text{ is an odd prime factor of } \mathrm{disc}(\mathcal{O}) \text{ and } \ell > B \}. $$

For each $\ell \in P_1$, compute $\chi_\ell([c])$ in time $\ell^{O(1)}$ using Theorem 2 and the fact that $(E', \iota') = [c](E, \iota)$. Now, with [3], one can compute square roots in $\mathrm{cl}(\mathcal{O})$ in polynomial time, so we get an ideal $\mathfrak{a}$ such that $[\mathfrak{a}]$ and $[c]$ differ by a two-torsion factor. From [3], one also gets a basis of $\mathrm{cl}(\mathcal{O})[2]$, so we can ensure that $\chi_\ell([\mathfrak{a}]) = \chi_\ell([c])$ for each $\ell \in P_1$. The solution is now of the form $[c] = [\mathfrak{a}][\mathfrak{b}]$ where $[\mathfrak{b}]$ is in the subgroup $G$ of $\mathrm{cl}(\mathcal{O})[2]$ of classes such that $\chi_\ell([\mathfrak{b}]) = 1$ for all $\ell \in P_1$. Therefore, the number of remaining candidates for the class $[c]$ is $\#G \le 2^{\#P_2+1}$. These can be enumerated (from the basis of $\mathrm{cl}(\mathcal{O})[2]$, deduce a basis of the subgroup $G$) and checked for correctness in polynomial time using Proposition 4 and the provided basis of $\mathrm{End}(E)$. Overall, the running time is polynomial in $\log p$, $\log \mathrm{disc}(\mathcal{O})$, $B$, and $2^{\#P_2}$. The running time follows by choosing $B = \min(2^{\omega(D)}, \max_i(\ell_i \mid \ell_i \le 2^{\omega(D)-i}))$.

Let us prove the last inequality. First, $2^{\omega(D)} \ll \#(\mathrm{cl}(\mathcal{O})[2])$, so $B \ll \#(\mathrm{cl}(\mathcal{O})[2])$. Second, if $\{\ell_i \mid \ell_i \le 2^{\omega(D)-i}\}$ is empty, then $2^{\omega(D)-1} < \ell_1 \le \ell_{\omega(D)}$ so $2^{\omega(D)} \ll \ell_{\omega(D)}$. If it is not empty, clearly $\max_i(\ell_i \mid \ell_i \le 2^{\omega(D)-i}) \ll \ell_{\omega(D)}$. In both cases, we deduce $B \ll \ell_{\omega(D)}$. Lastly, it remains to see that $B \ll L_D(1/2)$. Suppose there exists $j$ such that $\ell_j = \max_i(\ell_i \mid \ell_i \le 2^{\omega(D)-i})$. We have $\log_2(\ell_j) \le \omega(D) - j$, and

$$ \log_2(D) \ge \sum_{i=j+1}^{\omega(D)} \log_2(\ell_i) \ge (\omega(D) - j) \log_2(\ell_j) \ge \log_2(\ell_j)^2. $$

We deduce that $\ell_j \le 2^{\log_2(D)^{1/2}}$, hence $B \ll L_D(1/2)$. If there exists no such $j$, then

$$ \log_2(D) \ge \sum_{i=1}^{\omega(D)} \log_2(\ell_i) \ge \sum_{i=1}^{\omega(D)} (\omega(D) - i) = \Theta(\omega(D)^2), $$

$$ \text{so } 2^{\omega(D)} = L_D(1/2), \text{ hence } B \ll L_D(1/2). \quad \square $$

The main result of this section is the following theorem.

**Theorem 3 (ERH, reduction of EFFECTIVE $\mathcal{O}$-VECTORIZATION to $\mathcal{O}$-ENDRING).** Given an order $\mathcal{O}$ of discriminant $-D$, the factorization $D = \prod_{i=1}^{\omega(D)} \ell_i^{e_i}$ (with $\ell_i < \ell_{i+1}$), three $\mathcal{O}$-oriented elliptic curves $(E, \iota)$, $(E', \iota')$, $(F, j) \in \mathcal{E}\mathcal{L}\mathcal{O}(k)$, together with bases of $\mathrm{End}(E)$, $\mathrm{End}(E')$ and $\mathrm{End}(F)$, one can compute (or assert that it does

<footnote>$^6$With the convention that $\max(\emptyset) = +\infty$.</footnote>
not exist) an O-ideal c such that $(E', \iota') = [c](E, \iota)$ and an efficient representation of $\varphi_c : (F, j) \to [c](F, j)$ in probabilistic polynomial time in the length of the input and in

$$ \min \left( 2^{\omega(D)}, \max_i \left( \ell_i \mid \ell_i \le 2^{\omega(D)-i} \right) \right) \ll \min \left( L_D(1/2), \#(\mathrm{cl}(O)[2]), \ell_{\omega(D)} \right). $$

*Remark 5.* This improves the result of [31, Thm. 2] in two ways. First, the worst case is now sub-exponential: when $D$ is primordial, the running time of [31, Thm. 2] could reach about $D^{1/\log \log D}$, while it is now always at most $L_D(1/2)$. Second, Theorem 3 is now very efficient for a new important family of discriminants: when almost all prime divisors of $D$ are small, no matter how many there are. In particular, primordial numbers (the worst case of [31, Thm. 2]) now benefit from a polynomial time algorithm.

*Proof.* Thanks to Proposition 3, the proof is a straightforward adaptation of the proof of [31, Thm. 2]. Suppose we are given $(E, \iota), (E', \iota') \in \mathcal{E}\mathcal{E}_O(k)$, together with $\mathrm{End}(E)$ and $\mathrm{End}(E')$. Consider the involution $\tau_p : \mathcal{E}\mathcal{E}_O(k) \to \mathcal{E}\mathcal{E}_O(k)$ defined in [31, Def. 7] as $\tau_p(E, \iota) = (E^{(p)}, (\phi_p)_*\bar{\iota})$, where $\bar{\iota}$ is the conjugate of $\iota$ (i.e., $\bar{\iota}(\alpha) = \iota(\bar{\alpha})$ for any $\alpha \in O$), and $\phi_p : E \to E^{(p)}$ is the Frobenius isogeny.

Then, per [31, Prop. 11], one can compute $\mathfrak{a}$ and $\mathfrak{b}$ such that $\tau_p(E, \iota) = [\mathfrak{a}](E, \iota)$ and $\tau_p(E', \iota') = [\mathfrak{b}](E', \iota')$ in polynomial time. From [31, Lem. 10], the ideal class of $\mathfrak{c}$ is one of the $\#(\mathrm{cl}(O)[2])$ square roots of $[\mathfrak{ab}]$. Therefore, the ideal $\mathfrak{c}$ can be found by Proposition 3 within the claimed running time. Finally, compute an efficient representation of $\varphi_c : (F, j) \to [c](F, j)$ in polynomial time with Proposition 4. $\square$

**Corollary 1 (ERH).** Given an order $O$ of discriminant $-D$, and the factorization $D = \prod_{i=1}^{\omega(D)} \ell_i^{e_i}$ (with $\ell_i < \ell_{i+1}$), EFFECTIVE $O$-UBER reduces to $O$-ENDRING* in probabilistic polynomial time in the length of the instance and in

$$ \min \left( 2^{\omega(D)}, \max_i \left( \ell_i \mid \ell_i \le 2^{\omega(D)-i} \right) \right) \ll \min \left( L_D(1/2), \#(\mathrm{cl}(O)[2]), \ell_{\omega(D)} \right). $$

*Proof.* Again, this is a straightforward adaptation of [31, Cor. 4]. Suppose we are given $(E, \iota), (F, j) \in \mathcal{E}\mathcal{E}_O(k)$ and an $O$-orientable elliptic curve $E'$. Solving $O$-ENDRING*, one can find $\varepsilon$-bases of $\mathrm{End}(E)$, $\mathrm{End}(F)$ and $\mathrm{End}(E')$, and an $O$-orientation $\iota'$ of $E'$. The result follows from Theorem 3. $\square$

**Conflict of interest statement.** The authors assert that there are no conflicts of interest.

**Data availability statement.** Data sharing is not applicable to this article as no datasets were generated or analysed during the current study.

## REFERENCES

[1] Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: Efficient isogeny based signatures through class group computations. In *Asiacrypt (1)*, volume 11921 of Lecture Notes in Computer Science, pages 227–247. Springer, 2019. https://ia.cr/2018/485.

[2] Dan Boneh, Dmitry Kogan, and Katharine Woo. Oblivious pseudorandom functions from isogenies. In *Asiacrypt (2)*, volume 12492 of Lecture Notes in Computer Science, pages 520–550. Springer, 2020. https://ia.cr/2020/1532.

[3] Wieb Bosma and Peter Stevenhagen. On the computation of quadratic 2-class groups. *J. Théor. Nombres Bordeaux*, 8(2):283–313, 1996.
[4] Wouter Castryck and Thomas Decru. CSIDH on the surface. In *PQCrypto*, volume 12100 of *Lecture Notes in Computer Science*, pages 111–129. Springer, 2020. https://ia.cr/2019/1404.

[5] Wouter Castryck, Ann Dooms, Carlo Emerencia, and Alexander Lemmens. A fusion algorithm for solving the hidden shift problem in finite abelian groups. In *PQCrypto*, volume 12841 of *Lecture Notes in Computer Science*, pages 133–153. Springer, 2021. https://eprint.iacr.org/2021/562.

[6] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: An efficient post-quantum commutative group action. In *Asiacrypt (3)*, volume 11274 of *Lecture Notes in Computer Science*, pages 395–427. Springer, 2018. https://ia.cr/2018/383.

[7] Wouter Castryck, Lorenz Panny, and Frederik Vercauteren. Rational isogenies from irrational endomorphisms. In *Eurocrypt (2)*, volume 12106 of *Lecture Notes in Computer Science*, pages 523–548. Springer, 2020. https://ia.cr/2019/1202.

[8] Wouter Castryck, Jana Sotáková, and Frederik Vercauteren. Breaking the decisional Diffie-Hellman problem for class group actions using genus theory. In *Crypto (2)*, volume 12171 of *Lectures Notes in Computer Science*, pages 92–120. Springer, 2020. https://ia.cr/2020/151.

[9] Mathilde Chenu and Benjamin Smith. Higher-degree supersingular group actions. In *Math-Crypt*, J. Math. Cryptol. (to appear), 2021. https://ia.cr/2021/955.

[10] Leonardo Colò and David Kohel. Orienting supersingular isogeny graphs. *J. Math. Cryptol.*, 14(1):414–437, 2020. http://nutmic2019.imj-prg.fr/confpapers/OrientIsogGraph.pdf.

[11] Jean-Marc Couveignes. Hard homogeneous spaces, 1997. IACR Cryptology ePrint Archive 2006/291, https://ia.cr/2006/291.

[12] David A. Cox. *Primes of the form $x^2 + ny^2$: Fermat, class field theory, and complex multiplication*. Pure and Applied Mathematics. Wiley, second edition, 2013.

[13] Pierrick Dartois and Luca De Feo. On the security of OSIDH. In *PKC (1)*, volume 13177 of *Lecture Notes in Computer Science*, pages 52–81. Springer, 2022. https://ia.cr/2021/1681.

[14] Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin Wesolowski. Séta: Supersingular encryption from torsion attacks. In *Asiacrypt (4)*, volume 13093 of *Lecture Notes in Computer Science*, pages 249–278. Springer, 2021. https://ia.cr/2019/1291.

[15] Luca De Feo and Michael Meyer. Threshold schemes from isogeny assumptions. In *PKC (2)*, volume 12111 of *Lecture Notes in Computer Science*, pages 187–212. Springer, 2020. https://ia.cr/2019/1288.

[16] Tako Boris Fouotsa, Péter Kutas, Simon-Philipp Merz, and Yan Bo Ti. On the isogeny problem with torsion point information. In *PKC (1)*, volume 13177 of *Lecture Notes in Computer Science*, pages 142–161. Springer, 2022. https://ia.cr/2021/153.

[17] Steven D. Galbraith, Christophe Petit, Barak Shani, and Yan Bo Ti. On the security of supersingular isogeny cryptosystems. In *Asiacrypt (1)*, volume 10031 of *Lecture Notes in Computer Science*, pages 63–91. Springer, 2016. https://ia.cr/2016/859.

[18] David Jao and Luca De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In *PQCrypto*, volume 7071 of *Lecture Notes in Computer Science*, pages 19–34. Springer, 2011. https://ia.cr/2011/506.

[19] Kiran S. Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. In *IEEE FOCS 2008*, pages 146–155, 2008. http://users.cms.caltech.edu/~umans/papers/KU08-final.pdf.

[20] Yi-Fu Lai, Steven D. Galbraith, and Cyprien Delpech de Saint Guilhem. Compact, efficient and UC-secure isogeny-based oblivious transfer. In *Eurocrypt (1)*, volume 12696 of *Lecture Notes in Computer Science*, pages 213–241. Springer, 2021. https://ia.cr/2020/1012.

[21] James S. Milne. Complex multiplication (v0.10), 2020. https://www.jmilne.org/math/CourseNotes/cm.html.

[22] Hiroshi Onuki. On oriented supersingular elliptic curves. *Finite Fields Appl.*, 69:Paper No. 101777, 18, 2021. https://arxiv.org/abs/2002.09894.

[23] Michael Rabin. Probabilistic algorithms in finite fields. *SIAM J. Comput.*, 9(2):273–280, 1980. http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-213.pdf.

[24] Alexander Rostovtsev and Anton Stolbunov. Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive 2006/145, 2006. https://ia.cr/2006/145.

[25] Hans-Georg Rück. A note on elliptic curves over finite fields. *Math. Comp.*, 49(179):301–304, 1987.
[26] René Schoof. Nonsingular plane cubic curves over finite fields. *J. Combin. Theory Ser. A*, 46(2):183-211, 1987.

[27] Peter Stevenhagen. Rédei-matrices and applications. In *Number theory (Paris, 1992-1993)*, volume 215 of *London Math. Soc. Lecture Note Ser.*, pages 245-259. Cambridge Univ. Press, Cambridge, 1995.

[28] Anton Stolbunov. Cryptographic schemes based on isogenies. 2012. PhD thesis. https://ntnuopen.ntnu.no/ntnu-xmlui/bitstream/handle/11250/262577/529395_FULLTEXT01.pdf.

[29] Gérald Tenenbaum. *Introduction to analytic and probabilistic number theory*, volume 163 of *Graduate Studies in Mathematics*. American Mathematical Society, Providence, RI, third edition, 2015. Translated from the 2008 French edition by Patrick D. F. Ion.

[30] William C. Waterhouse. Abelian varieties over finite fields. *Ann. Sci. École Norm. Sup.*, 2:521-560, 1969.

[31] Benjamin Wesolowski. Orientations and the supersingular endomorphism ring problem. In *Eurocrypt (3)*, volume 13277 of *Lecture Notes in Computer Science*, pages 345-371. Springer, 2022. https://ia.cr/2021/1583.

[32] Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In *IEEE FOCS 2021*, pages 1100-1111, 2022. https://ia.cr/2021/919.

IMEC-COSIC, KU LEUVEN, KASTEELPARK ARENBERG 10/2452, 3001 LEUVEN, BELGIUM
DEPT. MATHEMATICS: ALGEBRA AND GEOMETRY, GHENT UNIVERSITY, KRIJGSLAAN 281, 9000
GENT, BELGIUM

Email address: wouter.castryck@esat.kuleuven.be

IMEC-COSIC, KU LEUVEN, KASTEELPARK ARENBERG 10/2452, 3001 LEUVEN, BELGIUM
DEPT. MATHEMATICS, KU LEUVEN, CELESTIJNENLAAN 200B, 3001 LEUVEN, BELGIUM
DEPT. MATHEMATICS, LEIDEN UNIV., NIELS BOHRWEG 1, 2333 CA LEIDEN, THE NETHERLANDS

Email address: marc.houben@kuleuven.be

IMEC-COSIC, KU LEUVEN, KASTEELPARK ARENBERG 10/2452, 3001 LEUVEN, BELGIUM

Email address: frederik.vercauteren@esat.kuleuven.be

UNIV. BORDEAUX, CNRS, BORDEAUX INP, IMB, UMR 5251, F-33400 TALENCE, FRANCE
INRIA, IMB, UMR 5251, F-33400 TALENCE, FRANCE

Email address: benjamin.wesolowski@math.u-bordeaux.fr