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

Question

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?

Answer 1

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.