Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary?

Question

In the original SIDH paper by De Feo, Jao and Plût, the basis points $P_A$ and $Q_A$ are supposed to be independent points in $E(\mathbb{F}_{p^2})$ of order $\ell_A^{e_A}$ for some small prime $\ell_A$ on some supersingular curve $E$. To check independence, they suggest computing the Weil-pairing $e(P_A, Q_A)$ and check that the result still has order $\ell_A^{e_A}$.

My question is this: Is another valid approach to checking independence to check if some discrete logarithm exists from one point to the other? Of course, $|E[\ell_A^{e_A}]|$ is $\ell_A$-power smooth, so taking discrete logarithms is easy by Pohlig-Hellman, but I am sure if this approach is valid/equivalent with calculating the Weil-pairing.

Answer 1

No, this is not equivalent. To see why, take the example with $ℓ_A = 2$ and $e_A = 2$, then the torsion group is isomorphic to the additive group $ℤ/4ℤ × ℤ/4ℤ$. Set $P=(1,3)$ and $Q=(1,1)$, then neither is a multiple of the other, however they do not generate the whole group because $2P = 2Q$, and indeed there is no way to write $(1,0)$ (and many other vectors) as a combination of $P$ and $Q$.

Another way to see that $P$ and $Q$ are not independent is to form the matrix $\begin{pmatrix}1 & 3\\1 & 1\end{pmatrix}$ and compute its discriminant in $ℤ/4ℤ$, which is $2$. So the matrix is not invertible mod $4$, and thus the linear combinations of its rows do not generate the whole $ℤ/4ℤ×ℤ/4ℤ$. This is in a sense the analogue of computing the Weil pairing.

Note that $e_A>1$ was the key to this counter-example. If $e_A=1$, then it is indeed sufficient to check that $[i]P≠Q$ for all $0<i<ℓ$.

What is true in general is that $P_A$ and $Q_A$ are independent if and only if $P'=[ℓ_A^{e_A-1}]P_A$ and $Q'=[ℓ_A^{e_A-1}]Q_A$ are, which you can check by enumerating all multiples of $P'$, as above. This is how the pairing check is usually done in implementations of SIDH.

Answer 2

As you mentioned, computing the discrete logarithm is an easy way to check for linear dependency. The usual way to compute discrete logs over elliptic curves relies on some pairing, but there are ways to do so without any pairing. See for instance "Isogeny-based key compression without pairings" at PKC'21 (https://eprint.iacr.org/2021/272.pdf), where pairing-less discrete logs are used for key compression.