2
$\begingroup$

Let $E$ be a supersingular elliptic curve over $\mathbb{F}_{p^2}$, where $p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$ for some primes $\ell_A, \ell_B$. Let $R \in E[\ell_A^{e_A}]$ be a point of order $\ell_A^{e_A}$ and suppose $\phi:E \to E' = E/\langle R \rangle$ is an isogeny with kernel $\langle R \rangle$. Let $\widehat{\phi}:E' \to E$ be the dual isogeny.

My question is: suppose we know the kernel of $\widehat{\phi}$, say $\langle S \rangle$. How can we recover $\langle R \rangle$?

$\endgroup$
5
  • $\begingroup$ It looks similar to some kind of homework, can you provide some a bit of background on where you encounter this problem? Also, can you explain why you feel this is more cryptography than purely mathematics? $\endgroup$
    – DannyNiu
    Oct 30, 2019 at 8:10
  • 2
    $\begingroup$ @DannyNiu This kind of questions shows up in isogeny-based cryptography, specifically SIDH/SIKE. $\endgroup$
    – yyyyyyy
    Oct 30, 2019 at 9:05
  • $\begingroup$ Hint: Consider another point $Q\in E'$ such that $\{S,Q\}$ is a basis of the $\ell_A^{e_A}$-torsion of $E'$ and look how $\phi\circ\widehat\phi$ acts on these points. $\endgroup$
    – yyyyyyy
    Oct 30, 2019 at 9:11
  • $\begingroup$ my guess (cmiiw) is that $\ker(\phi) = \langle \widehat{\phi}(Q) \rangle$ because $\phi(\widehat{\phi}(Q)) = [\ell_A^{e_A}]Q = $ identity. However, it is still unclear to me why should $\langle \widehat{\phi}(Q) \rangle = \langle R \rangle$. $\endgroup$
    – tfp
    Oct 30, 2019 at 9:24
  • $\begingroup$ @tfp You are right that $\ker(\phi)=\langle\widehat\phi(Q)\rangle$, but your argument only shows the $\supseteq$ inclusion. Re: "why should $\langle\widehat\phi(Q)\rangle=\langle R\rangle$", note that you've assumed $\ker(\phi)=\langle R\rangle$. $\endgroup$
    – yyyyyyy
    Oct 31, 2019 at 12:29

1 Answer 1

0
$\begingroup$

The comments on the question have already provided a good starting point, but I'll add an answer for completeness.

We have that $R \in E$ is a point of order $\ell_A^{e_A}$, generating the kernel of $\phi$. Because $\ell_A^{e_A}$ is coprime to $p$, the $\ell_A^{e_A}$-torsion subgroup of $E$ has the following structure:

$$E[\ell_A^{e_A}] \cong \frac{\mathbb{Z}}{\ell_A^{e_A}\mathbb{Z}} \times \frac{\mathbb{Z}}{\ell_A^{e_A}\mathbb{Z}}. $$

Thus, as we know, two independent points of order $\ell_A^{e_A}$ generate $E[\ell_A^{e_A}]$. So there are points of order $\ell_A^{e_A}$ in $E[\ell_A^{e_A}]$ which are independent of $R$ - call one of them $Q$. That is, the kernels generated by $R$ and $Q$ only intersect trivially.

Now consider what happens when $Q$ is mapped via $\phi$, giving $\phi(Q) \in E'$. Because the subgroup $\langle Q \rangle$ only intersects trivially with $\langle R \rangle = \ker \phi$, and because isogenies are group homomorphisms, $\phi(Q)$ must have order $\ell_A^{e_A}$ on $E'$.

We also have that $$\widehat{\phi} \circ \phi = [\ell_A^{e_A}],$$ which is the multiplication-by-$\ell_A^{e_A}$ endomorphism on $E$. See, for example, Silverman's "The Arithmetic of Elliptic Curves" Section III.6 for proof of this fact and other facts about the dual isogeny. By definition, the kernel of the above endomorphism $[\ell_A^{e_A}]$ must be $E[\ell_A^{e_A}]$ - all the points which when multiplied by $\ell_A^{e_A}$ give the identity $\mathcal{O}_E$. This includes $Q$. So $\phi(Q)$ must be in the kernel of $\widehat{\phi}$.

So, because $Q$ is a point of order $\ell_A^{e_A}$ in the kernel of $\widehat{\phi}$ (an isogeny of degree $\ell_A^{e_A}$), it must generate said kernel. This gives us exactly what you wanted: a generator of the kernel of the dual isogeny. Simply map an independent point of the correct order through $\phi$ to get a generator of $\ker \widehat{\phi}$.

The same applies in the other direction: Given $S$ generating the kernel of $\widehat{\phi}$, we can pick a point of order $\ell_A^{e_A}$ independent of $S$ on $E'$ and map it through $\widehat{\phi}$ to get a point of order $\ell_A^{e_A}$ on $E$, in the kernel of $\phi$. This point must generate the kernel (it won't necessarily be equal to $R$, but it will be in the subgroup generated by $R$).

$\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.