How to Sample from Frobenius Eigenspace?

Question

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.

Answer 1

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.