# What is the probability that there exists multiple distinct Isogenies between two given supersingular curves?

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?

• 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? – dan_fulea May 30 '19 at 0:35
• 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. – Lubin May 30 '19 at 5:19
• You're right, sorry for missing out details. Added them now. – Andrea May 30 '19 at 13:10