Non-Degeneracy of the Weil pairing

Question

In this YouTube video, Dan Boneh mentions that if both points are defined on the base field then the pairing is degenerate.

Why is that? And specifically is this true if I use the Weil Pairing?

Answer 1

(I write a more extensive answer with the background of all this; the result you are looking for is Theorem 3. A proof would be too long for this site, you can consult standard textbooks.)

Let $E$ be an elliptic curve over $\mathbf{F}_p$ and $P \in E(\mathbf{F}_p)$ be a point of prime order $r \ne p$. So $r$ divides the order of $E(\mathbf{F}_p)$, and suppose further that $r^2$ does not divide the order of $E(\mathbf{F}_p)$. For any extension field $K$ of $\mathbf{F}_p$, we let $E(K)[r]$ be the group of all points $Q \in E(K)$ such that $rQ = \infty$. Note that $P \in E(K)[r]$, so $\langle P\rangle$ is a subgroup of $E(K)[r]$.

Theorem 1. The group $E(\overline{\mathbf{F}_p})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

Corollary. There is an integer $k > 1$ such that $E(\mathbf{F}_{p^k})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

In the following, we let $k$ be the smallest such integer (called the embedding degree), $K = \mathbf{F}_{p^k}$, and $E[r] = E(K)[r]$. Thus all the points of $E[r]$ have coordinates in $K$.

Then the mathematician's Weil pairing $e_r$ is a map from $E[r] \oplus E[r]$ to $\mathbf{F}_{p^k}^*$ with the following properties (among others), which makes it different from the cryptographer's pairing.

Bilinearity. For all points $P,Q,R \in E[r]$ we have $$ \begin{align*} e_r(P+Q,R) &= e_r(P,R)\times e_r(Q,R), \text{and} \\ e_r(P,Q+R) &= e_r(P,Q)\times e_r(P,R). \end{align*} $$

Alternacy. For all points $P \in E[r]$, we have $e_r(P,P) = 1$.

Non-degeneracy. For all points $P \in E[r]$, if $e_r(P,Q) = 1$ for all points $Q \in E[r]$, then $P = \infty$.

The property of alternacy of the Weil pairing makes it unsuitable for cryptography, since in cryptography we require $e(P,P) \ne 1$. So the Weil pairing needs to be modified.

Theorem 3. Let $P,Q \in E[r]$. Then $e_r(P,Q) = 1$ if and only if $Q$ is a multiple of $P$.

Corollary 1. A point $Q \in E[r]$ has coordinates in $\mathbf{F}_p$ if and only if it is a multiple of $P$.

Corollary 2. The group of $r$th roots of unity in $K$ is cyclic of order $r$.

In the following, let $Q$ be a point of $E[r]$ which is not a multiple of $P$. This implies that $Q$ (which has coordinates in $\mathbf{F}_{p^k}$) does not have coordinates in $\mathbf{F}_p$. Let $G = \langle P\rangle$, and let $G_T$ be the group of $r$th roots of unity in $K$ (both groups are cyclic of order $r$).

We define the modified Weil pairing $\hat{e}_r$ as a map from $G \times G$ to $G_T$ such that $\hat{e}_r(P,P) = e_r(P,Q)$. Then $\hat{e}_r$ is a suitable cryptographic pairing: its bilinearity follows from the bilinearity of $e_r$, and its non-degeneracy (in the cryptographic sense) follows from Theorem 3 since $Q$ is not a multiple of $P$.

There are many ways to do this in practice, one is to let $p \equiv 2 \pmod 3$ and such that $(p+1)/6$ is prime. In this case the curve $Y^2 = X^3 + 1$ has $p+1$ points (it is supersingular) and we can choose a point of order $r = (p+1)/6$. It can also be shown that in this case, we have $k = 2$. Since $p^2-1$ is a multiple of $3$, there is a primitive $3$rd root of unity in $K = \mathbf{F}_{p^2}$, call it $\zeta$. Then for a point $P = (x,y)$, the point $Q$ is $(\zeta x, y)$.