So I was implementing the $2$-point method described here[1], which requires to samples two points $P_0, P_1$ in the Frobenius eigenspace initially. It uses a method called Elligator, which seems to me only samples $\mathbb F_p$ rational points.

Suppose one is given a supersingular curve $E$ defined over $\mathbb F_p$ with Elkies prime $\ell$. Since the $\ell$-torsion $E[\ell]$ is a $\mathbb F_\ell$-linear space of rank 2 and the Frobenius mapping $\pi$ is linear. Let $\lambda$ be one of the eigenvalue in $\mathbb F_\ell$. How would one sample from its corresponding eigenspace $E[\pi-\lambda]$?

For $\lambda=1$ we simply take $\mathbb F_p$-rational points, but what about cases where $\lambda \neq 1$, say $\lambda=-1$?

[1]"A Faster Constant-time Algorithm of CSIDH keeping Two Points," page 10, Algorithm 3.


The Frobenius eigenspace of $-1$ is, by definition, the kernel of the map $π+1$. Typically, this is further restricted to some torsion group $E[ℓ]$, so we are really talking about $E[ℓ] ∩ E[π+1]$, i.e., those points of $E[ℓ]$ such that $π(P)=-P$.

If the curve is expressed in Weierstrass form $y^2=f(x)$ (or Montgomery, or similar), letting $P=(x,y)$ we have $-P=(x,-y)$. Thus the Frobenius eigenspace is made by those points $(x,y)$ such that $x^p=x$ and $y^p=-y$. A little theory shows that this is the set of rational points of the twist of $E/𝔽_p$.

So, the obvious way to sample the points is to

  1. Choose a random $x\in 𝔽_p$;
  2. Check that $f(x)$ is not a square, i.e., that $y=\sqrt{f(x)}$ is not in $𝔽_p$, i.e., that $y^p=\sqrt{f(x)}f(x)^{(p-1)/2}=-\sqrt{f(x)}=-y$
  3. See $(x,y)$ as a point in $E/𝔽_{p^2}$, multiply by an appropriate cofactor to obtain a point in $E[ℓ]$.

¹To see why this works, note that $f(x)$ is not a square in $𝔽_p$, thus its Legendre symbol is $-1$. By the way, saying $x$ is in $𝔽_p$ and $y$ is not is equivalent to saying that $x$ is the abscissa of a rational point on the twist.

If $\#E(𝔽_p)=p+1-t$, where $t$ is the trace of $π$, then the twist has order $p+1+t$, thus the "appropriate cofactor" above is $(p+1+t)/ℓ$. Note that $E[π+1]∩E[π-1]=E[2]$ (because $1=-1\mod 2$), thus for $ℓ=2$ the two ℓ-restricted eigenspaces are indistinguishable, and you would get a random point of order $2$; however for any other prime $ℓ$ there are two distinct eigenspaces, and step 3. will stay in the twist.

Steps 1. and 2. above can be replaced by Elligator 2, which samples simultaneously in both the eigenspace of $+1$ and that of $-1$. The original Elligator 2 was explained as a map to $E[π-1]$, but the generalization to a map to $E[π-1]×E[π+1]$ is easy and has been hinted at in several papers. For an explicit description, see Section 3, and Algorithm 3 in particular, here: https://eprint.iacr.org/2019/837.

All this can be generalized to arbitrary eigenvalues $λ$, not just $±1$. The multiplicative order of $λ$ in $ℤ/ℓℤ$ determines the degree of the extension of $𝔽_p$ where the points $E[π-λ]$ are defined.

  • $\begingroup$ Hi, thanks for your reply! But I am confused at the following. How do we make sure the obtained point $(x,y)\in E(\mathbb F_{p^2})$, after multiplying an appropriate co-factor, would be sitting in $E[\pi\pm 1]$ instead of their linear combination? $\endgroup$ Feb 24 '20 at 8:10
  • $\begingroup$ Also, by the appropriate co-factor is it simply $(p+1)^2/\ell$? $\endgroup$ Feb 24 '20 at 12:57
  • $\begingroup$ I edited the answer to address your questions. Hopefully it is clearer now. $\endgroup$ Feb 25 '20 at 10:00
  • 1
    $\begingroup$ Yes, you got it exactly right. As for the theory, these are mostly simple consequences of the general principles you can find in any introductory book on e.c., such as Silverman, Milne, etc. I can't think of any reference specifically dedicated to e.c. and their twists, but maybe this gets close: arxiv.org/pdf/1703.01863.pdf. $\endgroup$ Feb 26 '20 at 9:02
  • 1
    $\begingroup$ Well, the map $ι$ maps $(x,y)$ to $(-x,iy)$, so you answered your own question. But this fact is unimportant here, it is just a useful optimization trick. If you sample a point $P∈E[π+1]$, be it over $𝔽_p$ or over $𝔽_{p^2}$, and then you compute $Q=cP$, then $Q$ is still in $E[π+1]$, necessarily. $\endgroup$ Feb 27 '20 at 10:52

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.