Question about Weil Pairing & the MOV attack

Question

When I read any description of the Weil Pairing, it's described as a map between the additive groups $G1$ x $G2$ of an Elliptic Curve to a different group.

$G1$ is the r-torsion group of the EC curve over the base Field. i.e. $G1$ is the r-torsion group of $E(F_q)$.

$G2$ is a different subgroup of full r-torsion group of the same Curve but it would have points on the extension field - i.e. $G2$ will have points also in $E(F_{q^k})$ where $k$ is the embedding degree. $G2$ is formed by the Frobenius Endomorphism $(x,y)$ -> $(x^p, y^p)$

I understood upto this. I understood that the map ($e_r)$ constructed using rational functions & the output is a root of Unity in the multiplicative group of $E(F_{q^k})$.

---

Coming to the MOV attack using the Weil Pairing, the map $e_r(P,rP)$ is used to transform the ECDLP, $Q = rP$ into the DLP in the multiplicative group of $F_{q^k}$.

The question I have here is that the map takes 2 points as input. The first point in $G1$ & the 2nd point in $G2$. How do we know that $P$ is going to be in $G1$ & $Q$ is going to be in $G2$. Else this map won't work, right? What am I misunderstanding here?

Answer 1

I was never up to speed with pairing based attacks (caveat reader), but you seem to have some wrong impressions, so I will try and fix some of them, and share my impressions.

---

The idea of using the Weil pairing to solve the DLP is a lot like trying to find a point along the line by calculating inner products (in EC crypto instead of a line we have a cyclic subgroup $\langle G\rangle$). To extract information from such a calculation you need to calculate the inner products with a vector that is not orthogonal to the line (when distinct points on the line result in distinct inner products). Unlike the inner product, the Weil pairing is antisymmetric. This means that we need to use points outside the cyclic subgroup. The trouble is that those can be found only outside the group $E(\Bbb{F}_q)$. This is why the extension field is needed.

---

We fix an integer $r$. This should be selected in such a way that $E(\Bbb{F}_q)$ has quite a bit of $r$-torsion. In other words, $G_1=E[r]\cap E(\Bbb{F}_q)$ is a relatively large subgroup of $E(\Bbb{F}_q)$. I guess the normal case is that $G_1$ is cyclic of order $r$, but that is probably not strictly necessary. Furthermore, the extension degree $k$ is chosen in such a way, that the group $G_2=E[r]\cap E(\Bbb{F}_{q^k})$ is relative large. Ideally $G_2$ contains all the $r$-torsion, but that need not be strictly true. The point is that $G_2$ should be significantly larger than $G_1$. As an abstract group $G_2\simeq C_r\times C_r$ in the ideal case, but it may still be useful to use the pairing attack as long as $G_2\simeq C_r\times C_d$, where $d$ is a large divisor of $r$. Of course, if $r$ is a prime, then we need $d=r$.

The DLP problem in $G_1$ is to determine the integer $m$ such that $P=mG$, where $P$ is a given point and $G$ is the known generator referred to in the specs of the cryptosystem.

Let $e(\ ,\ )$ be the Weil pairing. It is a mapping from $E[r]\times E[r]\to \mu_r$ (from the $r$-torsion of $E$ to a subgroup of units of the extension field). Here (ideally) $E[r]=G_2$ and the group of roots of unity $\mu_r$ is a subgroup of the multiplicative group $\Bbb{F}_{q^k}$. IIRC the condition $\mu_r\le\Bbb{F}_{q^k}^*$ is a necessary condition for $E[r]$ to be contained in $E(\Bbb{F}_{q^k})$.

• We never want to calculate $e(P,G)$. This is useless, because for all points $Q$ we have $e(Q,Q)=1$. Bilinearity implies that $$e(P,G)=e(mG,G)=e(G,G)^m=1^m=1$$ for all $m$, so such a calculation does not reveal any information about the discrete logarithm $m$.
• That is why we need the extension field and the bigger group $G_2$. Ideally we want to find an element $Q\in G_2$ such that $\zeta:=e(G,Q)$ is a root of unity of order $r$. We have $$e(P,Q)=e(mG,Q)=e(G,Q)^m=\zeta^m.$$ So we can figure out the residue class of $m$ modulo $r$ by calculating the discrete logarithm of $e(P,Q)$ w.r.t. the base $\zeta$. This, then helps in figuring out $m$ (and solves it completely in the ideal case, where $r$ is the order of $G$). The hope is that the DLP in the group $\Bbb{F}_{q^k}^*$ would be easier than the DLP on $E$ (this is the case, if $k$ is "small").
• The general theory promises that such a $Q$ can always be found. Unfortunately I don't know the details on how to find one algorithmically and efficiently. If the index $\ell$ of $G_2$ as a subgroup of $E(\Bbb{F}_{q^k})$ is known, then we can first pick a random point $Q'$ from the curve $E(\Bbb{F}_{q^k})$, and then calculate $Q=\ell Q'$ which is guaranteed to be $r$-torsion (i.e., an element of $G_2$). This should give us random points of $G_2$, and a random point can be used in the role of $Q$ with a reasonably high probability (depending on the factorization of $r$). It may be possible to improve upon this.