Programming ECC - Balasubramanian-Koblitz Theorem

Balasubramanian-Koblitz Theorem

We show that the Weil and Tate pairing are interchangeable for elliptic curves for embedding degrees greater than 1.

Theorem: Let $E$ be an elliptic curve defined over $𝔽_{q}$ and suppose $r$ is a prime dividing $N = # E (𝔽_{q})$ , and that $r$ does not divide $q - 1$ . Then $E (𝔽_{q^{k}})$ contains $r^{2}$ points of order $r$ if and only if $r$ divides $q^{k} - 1$ .

Proof: It is well-known that if $E (𝔽_{q^{k}})$ contains $E [r]$ then $r ∣ q^{k} - 1$ , even without assuming $r$ divides $N$ or $r$ does not divide $q - 1$ .

Let $Φ$ denote the Frobenius map. Consider the subgroup $T$ of $E [r]$ consisting of all points of trace zero, that is

T = {Q ∣ Q \in E [r], tr Q = O}

The group $T$ may be explicitly constructed using the map $P \mapsto P - Φ (P)$ . Now we have $Φ (T) = T$ , and also $T$ is not contained in $E (𝔽_{q})$ since we are assuming $k > 1$ .

Hence $T$ is an eigenspace of $Φ$ , but not the $1$ -eigenspace. Since the eigenvalues of $Φ$ are $1$ and $q$ , we see that $T$ must be the $q$ -eigenspace of $Φ$ and hence

Φ^{k} (Q) = q^{k} Q = Q

since $r ∣ q^{k} - 1$ . Thus $T$ , like $E (𝔽_{q})$ is fixed under $Φ^{k}$ , and since these groups are linearly independent they generate all of $E [r]$ , implying that all of $E [r]$ is fixed under $Φ^{k}$ . Hence $E [r] \subset E (𝔽_{q^{k}})$ $▪$

Example

Here is a curve where the Tate pairing can be used but the Weil pairing cannot. Let $r = 3$ . Let $E$ over $𝔽_{19}$ be given by $Y^{2} = X^{3} + X + 6$ . We may use the Tate pairing since $𝔽_{19}$ contains the cube roots of unity. However, the group of points of $E (𝔽_{19})$ is a cyclic group of order 18, so the Weil pairing cannot be used. It turns out that we must go to $𝔽_{19^{3}}$ to get all of $E [3]$ .