I am reading the paper An efficient key recovery attack on SIDH and I am stuck on some things from page 5.
Clearly I am lacking some background to understand this paper and any references would be greatly appreciated :)
Let me define some things first:
- An elliptic curve $E_0/\mathbb{F}_p^2$ with $\#E_0(\mathbb{F}_p^2)=(p+1)^2$ (for some prime $p=2^a3^bf-1$)
- Generators $P_0,Q_0$ of $E_0[2^a]$
- An elliptic curve $E/\mathbb{F}_p^2$ with $\#E(\mathbb{F}_p^2)=(p+1)^2$
- Generators $P,Q$ of $E[2^a]$
Now three assumptions are made:
- We can decide whether or not there is a $3^b$-isogeny $\phi:E_0\to E$ such that $\phi(P_0)=P$ and $\phi(Q_0)=Q$
- $2^a>3^b$
- Let $c=2^a-3^b$. We can compute the images $P_c=\gamma(P_0)$ and $Q_c=\gamma(Q_0)$ for arbitrary $c$-isogeny $\gamma:E_0\to C$ to some codomain curve $C$.
Now they consider the isogeny, $$\psi=[-1]\circ \phi\circ\hat\gamma:C\to E$$ and note that $\psi(P_c)=-cP$ and $\psi(Q_c)=-cQ$. We see that for all $R,S\in C[2^a]$, $$e_{2^a}(x\psi(R),x\psi(S))=e_{2^a}(R,S)^{-1}$$ or in other words the group homomorphism $$[x]\circ \psi|_{C[2^a]}:C[2^a]\to E[2^a]$$ is an "anti-isometry" with respect to the $2^a$-weil pairing.
This is where my first question is: didn't we assume C to be an arbitrary curve? Why is it also a group, is it an elliptic curve?
Next he states that this implies (why?) that the group, $$\langle (P_c,x\psi(P_c)),(Q_c,x\psi(Q_c))\rangle=\langle (P_c,P),(Q_c,Q)\rangle$$ is maximally isotropic with respect to the $2_a$-Weil pairing on the product $C\times E$ (equipped with the product polarization). Indeed, $$e_{2^a}((P_c,x\psi(P_c)),(Q_c,x\psi(Q_c)))=e_{2^a}(P_c,Q_c)e_{2^a}(x\psi(P_c),x\psi(Q_c))=1.$$
My second question is, what is the Weil pairing on a product of curves, or product of elliptic curves?
To your first question. From context $C$ must be an elliptic curve (an isogeny $C \to E$ is a finite morphism of group varieties, so $C$ must be a dimension $1$ abelian variety).
To your second question, for higher dimensional abelian varieties one needs to start to care about polarisations. Take a product $E \times E'$, now there is a Weil pairing $$ e_{N, (E \times E')} : (E \times E')[N] \times (E \times E')^\vee[N] \to \mu_N$$ but it's with the dual abelian variety $(E \times E')^\vee$. Fortunately when $E$ had dimension $1$ we have a canonical polarisation an obtain a pairing $e_{N,E}$ on $E[N]$. Then we equip $E \times E'$ with the product of these principal polarisations, and the upshot is that $$e_{N,(E \times E')}((P,P'), (Q, Q')) = e_{N,E}(P,Q) e_{N,E'}(P',Q').$$ An anti-isometry $\phi$ is by definition so that $$e_{N,E}(P,Q) = e_{N,E'}(\phi(P), \phi(Q))^{-1}.$$ Putting this in the product, with $\phi = x\psi$ from the question, then each pair $(P, x\psi(P)), (Q, x\psi(Q)\in \mathrm{Graph}(x\psi)$ pair to $1$ under the $N$-Weil pairing on $E \times E'$ and so is maximally $N$-isotropic (this is the definition).