# SIDH cryptosystem question

I'm trying to understand the SIDH cryptosystem and got confused at this point:

Alice fixes base $$\{P_A,Q_A\}$$ so that it generates $$E_0[l_A^{e_A}]$$. Then she chooses secret parameters $$m_A,n_A$$ and computes the secret isogeny $$\phi_A: E_0 \to E_A$$ with kernel $$\langle [m_A]P_A +[n_A]Q_A\rangle$$. Further section 4 of the 2011 SIDH paper states that both $$P_A$$ and $$Q_A$$ have order $$l_A^{e_A}$$ and are independent of each other.

Doesn't that mean that $$[m_A]P_A$$ and $$[n_A]Q_A$$ also have order $$l_A^{e_A}$$ and therefore $$ker(\phi_A) = E_0[l_A^{e_A}]$$? That would mean that $$\phi_A$$ is not secret.

I invented SIDH. $$E_0[\ell_A^{e_A}]$$ has cardinality $$(\ell_A^{e_A})^2$$. Each of $$P_A$$, $$Q_A$$, and $$R$$ has order $$\ell_A^{e_A}$$ and they all generate different subgroups. This is possible because $$E_0[\ell_A^{e_A}]$$ is a non-cyclic group.

• Thank you for your answer! What I don't understand is that the SIDH paper says that $\langle P_A,Q_A\rangle = E[l^{e_A}]$ and that both points generate the whole group $E[l^{e_A}]$. How is that possible if $P_A,Q_A$ only have order $l^{e_A}$ but $E[l^{e_A}]$ has cardinality $(l^{e_A})^2$?
– jvdh
Jun 3, 2019 at 16:53
• Consider the group $G = \mathbb{Z}/2 \times \mathbb{Z}/2$, which is a group of cardinality $4 = 2^2$. The elements $P = (1,0) \in G$ and $Q = (0,1) \in G$ each have order $2 = 2^1$, but $P$ and $Q$ together generate $G$.
– djao
Jun 4, 2019 at 3:02
• Thank you very much. One further question that comes to mind is why $E_0$ divides up neatly in one $l_A^{e_A}$ subgroup of cardinality $(l_A^{e_A})^2$ and a group of analogue cardinality for $l_B^{e_B}$. What prevents the points from having order $l_A$ or $l_B$?
– jvdh
Jul 10, 2019 at 13:55

You appear to be under the impression that Elliptic Curve groups are always cyclic, and that there is only one subgroup of a given order.

That is not the case, and it is most definitely not the case in the groups we use for isogenies. There are a huge number of subgroups of the same order; hence just knowing the subgroup order doesn't tell you which subgroup we're talking about.

• However the authors state that $\langle P_A,Q_A\rangle = E_0[l_A^{e_A}]$. Doesn't that mean that $\langle [m_A]P_A + [n_A]Q_A\rangle = E_0[l_A^{e_A}]$ as well?
– jvdh
May 31, 2019 at 11:54
• Okay, I think I got it. $⟨[m_A]P_A⟩ = E_0[l_A^{e_A}]$ but $\langle R \rangle= ⟨[m_A]P_A+[n_A]Q_A⟩$ might have a totally different order because of the addition. Is that correct?
– jvdh
May 31, 2019 at 12:06