1
$\begingroup$

I am trying to understand the action of the CSIDH protocol.

Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{F}_p}(E_0)$, then $Cl(\mathcal{O})$ acts on $\mathcal{E}\ell\ell(\mathcal{O})$ as follows:

Let $I\in Cl(\mathcal{O})$ an ideal. We define $H_I=\lbrace P\in E_0 \vert \alpha(P)=\mathcal{O} \text{ for all $\alpha \in I$} \rbrace$. The action is defined as below:

$I*E_0=E'$, where $E'$ is the unique curve such that there exists a unique separable isogeny $$\phi:E_0\longrightarrow E'$$ With $\ker(\phi)=H_I$. In other words, the kernel of $\phi$ is the intersection of all $\ker(\alpha)$ where $\alpha \in I$.

In order to compute the $\phi$ and $E'$, papers on CSIDH make use of Velu's formulas. So far, I have found the following theorem which applies to Montgomery curves:

Let $K$ be a field with char($K$)$\neq$ $2$. Let $a\in K$ such that $a^2\neq 4$ and consider the Montgomery curve $E/K: y^2=x^3+ax^2+x$. Let $G\subset E(\bar{K})$ be a finit subgroup with $(0,0)\not \in G$ and let $\phi$ be a separable isogeny such that $\ker(\phi)=G$. Then, there is a curve $E'/K:y^2=x^3+Ax^2+x$ such that, up to composition with isomorphisms, \begin{align*} \phi: E &\longrightarrow E' \\ (x,y) &\mapsto (f(x),c_0yf'(x)) \end{align*}

where $$f(x)=x{ \prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \frac{xx_T-1}{x-x_T}}$$ Furthermore, if we let $$\pi=\prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} x_T, \quad \quad \sigma=\sum_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \left( x_T-\frac{1}{x_T} \right)$$

Then, we have $A=\pi(a-3\sigma)$ and $c_o^2=\pi$.

So far so good, we have a way of computing isogenies between Montgomery elliptic curves. What I do not understand is the following. In several papers and slides, they explain that we have to take ideals $I\in \mathcal{O}$ with the form $\langle \ell, \pi \pm 1 \rangle$, where $\ell$ is a prime. Analizing said ideals, we see the following: $$H_I=\lbrace P \in E/\mathbb{F}_p \text{ } \vert \text{ } [\ell](P)=\mathcal{O},\pi (P)=P\rbrace$$

Since $\pi(P)=P$, it means that $P\in \mathbb{F}_p$. So it turns out that $H_I$ is just the $\ell$-torsion points defined over $\mathbb{F}_p$. The main claim is that we have to take $I$ in such a way because in doing so, we have a Vélu-friendly computation. This is what I fail to see. Why having rational points makes the Vélu computation easier?

In the theorem stated above, the hypothesis requires us that $G\subset E(\bar{K})$. But taking our ideal as $I=\langle[\ell]\rangle$ instead of $I=\langle [\ell], \pi \pm 1 \rangle$ also gives us a $H_I\subset E(\bar{K})$, which would be $G$ in the theorem notation, and so the theorem holds. Why is it then that having $H_I$ composed of rational points $P\in E(\mathbb{F}_p)$ makes the computation Vélu-friendly?

$\endgroup$
5
$\begingroup$

You are right that Vélu's formulas also work for any extension field, but then they require arithmetic in that field. Doing computations in $\mathbb F_p$ is simply much more efficient than in extension fields.
Generally, for a "random" ideal of prime norm $\ell$, you can only expect the corresponding points to be defined over $\mathbb F_{p^k}$ for some $k\in\mathcal O(\ell)$, hence if CSIDH didn't have those rational points, one would have to compute in extension fields of degrees of a few hundred.

(In fact, the earlier variants¹ of CSIDH were, among other techniques, using subgroups that are not necessarily rational, because it seems hard to find an ordinary curve with many "good" subgroups. The core observation in CSIDH is that switching to supersingular curves makes this trivial, simply by picking the prime $p$ of a special form!)

¹ Couveignes, Rostovtsev–Stolbunov, De Feo–Kieffer–Smith

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.