Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$?
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$).
