Breaking the Decisional Diffie–Hellman Problem for Class Group Actions Using Genus Theory: Extended Version

Abstract

In this paper, we use genus theory to analyze the hardness of the decisional Diffie–Hellman problem for ideal class groups of imaginary quadratic orders acting on sets of elliptic curves through isogenies (DDH–CGA). Such actions are used in the Couveignes–Rostovtsev–Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $\mathcal {O}$ with a set of assigned characters $\chi : {\text {cl}}(\mathcal {O}) \rightarrow \{ \pm 1\}$, and for each such character and every secret ideal class $[\mathfrak {a}]$ connecting two public elliptic curves E and $E' = [\mathfrak {a}] \star E$, we show how to compute $\chi ([\mathfrak {a}])$ given only E and $E'$, i.e., without knowledge of $[\mathfrak {a}]$. In practice, this breaks DDH–CGA as soon as the class number is even, which is true for a density 1 subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $\mathbb {F}_p$ with $p \equiv 1 \bmod 4$. Our method relies on computing Tate pairings and walking down isogeny volcanoes. We also show that these ideas carry over, at least partly, to abelian varieties of arbitrary dimension. This is an extended version of the paper that was presented at Crypto 2020.

Not Walking to the Floor

As explained in Sect. 3, our approach to computing $\chi (E, E')$ is to take an arbitrary walk to the floor of the respective m-isogeny volcanoes of E and $E'$. In fact, one can stop walking down as soon as one reaches a level where the $m^\infty$-torsion is sufficiently unbalanced. We illustrate this by means of the following modification of Theorem 8 (for $n=1$), which is likely to admit further generalizations. Here, we should mention recent follow-up work [15], which shows that one can avoid walking to the floor by resorting to the Weil pairing instead of the Tate pairing (although this approach may come with extra costs [15, §4]).

Theorem 16

Let $E / \mathbb {F}_q$ be an ordinary elliptic curve and let m be a prime divisor of $q-1$. Assume that E is not located on the crater of its m-volcano and that

$$\begin{aligned} E(\mathbb {F}_q)[m^\infty ] \cong \frac{\mathbb {Z}}{(m^r)} \times \frac{\mathbb {Z}}{(m^s)} \end{aligned}$$

for some $r > s + 1$. Let $P \in E(\mathbb {F}_q)[m] \setminus \{ \mathbf {0}\}$ be such that there exists a point $Q \in E(\mathbb {F}_q)$ for which $m^{r-1}Q = P$. Then the reduced Tate pairing

$$\begin{aligned} T_m(P, \cdot ) : E(\mathbb {F}_q) / mE(\mathbb {F}_q) \rightarrow \mu _m : X \mapsto T_m(P,X) \end{aligned}$$

(11)

is trivial if and only if X belongs to $E[m^s] \bmod mE(\mathbb {F}_q)$. In particular, $T_m(P,Q)$ is a primitive m-th root of unity which, for a fixed P, does not depend on the choice of Q.

Proof

The assumption $m \mid (q-1)$ implies that $\mu _m \subset \mathbb {F}_q$. As explained in [2, IX.7.1], the kernel of $T_m(P, \cdot )$ is a codimension 1 subspace of $E(\mathbb {F}_q) / mE(\mathbb {F}_q)$, when viewed as a vector space over $\mathbb {F}_m$. Therefore it suffices to prove that $T_m(P, \cdot )$ is trivial on $E[m^s] \bmod mE(\mathbb {F}_q)$, because the latter space indeed has codimension 1. More precisely, it has dimension 0 if $s = 0$ and dimension 1 if $s \ge 1$.

Now, since we are not on the crater, we know from Theorem 7 that there exists an elliptic curve $E' / \mathbb {F}_q$ and an $\mathbb {F}_q$-rational m-isogeny $\varphi : E' \rightarrow E$ such that $E'(\mathbb {F}_q)[m^\infty ] \cong \mathbb {Z}/(m^{r-1}) \times \mathbb {Z}/(m^{s+1})$. We note:

• $E[m^s] \subset \varphi (E'[m^{s+1}]) \subset \varphi (E'(\mathbb {F}_q))$, hence each $X \in E[m^s]$ can be written as $\varphi (X')$ for some $X' \in E'(\mathbb {F}_q)$.

• The kernel of the dual isogeny $\hat{\varphi }: E \rightarrow E'$ equals $\langle P \rangle$, as otherwise $E'$ would admit $\mathbb {F}_q$-rational $m^r$-torsion. Therefore P is the image of a point $P' \in E'[m] \subset E'(\mathbb {F}_q)$.

We conclude that

$$\begin{aligned} T_m(P,X) = T_m(\varphi (P'), \varphi (X')) = T_m(P',X')^{\deg (\varphi )} = T_m(P',X')^m = 1, \end{aligned}$$

as wanted. $\square$