I am trying to understand the basic idea behind supersingular isogeny cryptography. With very little knowledge about the group theory and elliptic curve, I find it very hard to thoroughly understand the underlying math of this protocol. Then I read several friendly introductions, and am still confused about the following questions. To be honest, I am not sure if I am asking the right question, or maybe I have misunderstood some concepts. Any answer will be helpful.
According to the pp8 of introductions, supersingular curves $E/\mathbb{F}_{p^2}$ always have their full rational $(p-1)$ or $(p+1)$-torsion defined over $\mathbb{F}_{p^2}$. Taking $E/\mathbb{F}_{431^2}$ for example, $E/\mathbb{F}_{431^2}$ is precisely the $(p+1)$-torsion. Also, according to $$ker([p+1]) \cong \mathbb{Z}_{p+1} \times \mathbb{Z}_{p+1}$$
We have $$E/\mathbb{F}_{p^2}\cong \mathbb{Z}_{p+1} \times \mathbb{Z}_{p+1}$$
Then all $E/\mathbb{F}_{p^2}$ are isomorphic to each other, which I think should be wrong. Could anyone tell me where is wrong?
Best Answer
There are a few possible explanations to your dilemma. Without a clearer statement of what exactly your problem is, it is impossible to be more precise.
Not all supersingular elliptic curves over $\mathbb{F}_{p^2}$ are isomorphic as abelian groups over $\mathbb{F}_{p^2}$. For example, taking $p=431$, the curve $E : y^2 = x^3 + x$ has group structure $E(\mathbb{F}_{p^2}) \cong (\mathbb{Z}/(p+1)\mathbb{Z})^2$ whereas its quadratic twist $E' : y^2 = x^3 + (2+i)x$ has group structure $E'(\mathbb{F}_{p^2}) \cong (\mathbb{Z}/(p-1)\mathbb{Z})^2$.
Even if two elliptic curves are isomorphic over $\mathbb{F}_{p^2}$ as abelian groups over $\mathbb{F}_{p^2}$, this does not mean they are isomorphic as elliptic curves. An elliptic curve has more structure than just merely that of an abelian group.
Even if you are only looking at abelian groups, isomorphic abelian groups may not be equivalent for the purposes of cryptography. For example the abelian groups $G_1 = (\mathbb{Z}/p\mathbb{Z})^*$ and $G_2 = \mathbb{Z}/(p-1)\mathbb{Z}$ are isomorphic as abelian groups, but the discrete logarithm problem is believed to be hard on $G_1$ whereas the same problem is known to be easy on $G_2$. In this case the issue is that the isomorphism, though it exists, is not efficiently computable in both directions, which makes a difference in cryptography.