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.

  • $\begingroup$ 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$? $\endgroup$ – jvdh Jun 3 '19 at 16:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – djao Jun 4 '19 at 3:02
  • $\begingroup$ 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$? $\endgroup$ – jvdh Jul 10 '19 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.

  • $\begingroup$ 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? $\endgroup$ – jvdh May 31 '19 at 11:54
  • $\begingroup$ 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? $\endgroup$ – jvdh May 31 '19 at 12:06

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.