0
$\begingroup$

The article "Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies" by De Feo, Jao, and Plût contains the following statement.

Since the degree of the isogeny $\phi_A$ is $\approx p$ (much shorter than the size of the isogeny graph), it is unlikely that there will be more than one isogeny path—and thus more than one match—from $E$ to $E_A$.

In this case, $E$ is a supersingular curve over $\mathbb{F}_{p^2}$, where $p$ is of the form $\ell_A^{e_A}\ell_B^{e_B}f \pm 1$. The isogeny $\phi_A: E \to E_A$ has kernel $\langle [m]P_A + [n]Q_A \rangle$, where $\{P_A, Q_A\}$ is a basis of $E[\ell_A^{e_A}]$ and $m, n$ are chosen at random from $\mathbb{Z}/\ell_A^{e_A}\mathbb{Z}$, not both divisible by $\ell_A$. Thus the degree of $\phi_A$ is $\ell_A^{e_A}$.

The previous statement is explaining a Meet-In-The-Middle attack to recover $\phi_A$. I understand that $E$ is $\ell_A^{e_A/2}$-isogenuous to $\approx p^{1/4}$ curves and so is $E_A$, while the number of supersingular curves over $\mathbb{F}_{p^2}$ is $\approx p/12$, but how does this justify that that it is unlikely that there is more than one isogeny path?

Besides, what is the exact probability of having more than one isogeny between the two curves?

$\endgroup$
  • $\begingroup$ Please define all objects in the right order. Do we fix a specific curve? What is $p$? Is $p$ for instance $13$ and rhat's it! What is $A$, what is $\phi_A$? What is $E$, what is $E_A$? What is $\ell_A$ and what is the power decorating it? What have you tried? Is there a concrete example? Is there any available PDF source, where people could look into? $\endgroup$ – dan_fulea May 30 '19 at 0:35
  • $\begingroup$ Since any elliptic curve has infinitely many self-isogenies, I suppose you need to say something about the degree(s) of the isogenies you seek. $\endgroup$ – Lubin May 30 '19 at 5:19
  • $\begingroup$ You're right, sorry for missing out details. Added them now. $\endgroup$ – Andrea May 30 '19 at 13:10
0
$\begingroup$

We prove in our AsiaPKC 2018 paper (https://doi.org/10.1145/3197507.3197516, Lemma 3.2) that there is always exactly one isogeny satisfying the constraints of an SIDH public key. The proof proceeds by a counting argument using the degree form, as I alluded to in an earlier answer. In short, the degree of the isogeny in this case is much smaller than the coefficients of the bilinear quadratic form corresponding to the degree form, so there is only a unique solution within this range of degrees.

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