Trying to understand the 2nd subgroup in the Weil Pairing used for the MOV attack

Question

EDIT: The bounty is actually to draw more attention. I accidentally chose the wrong reason.

---

• $E$ – Elliptic Curve over finite field $\mathbb F_p$.

• Let $k$ be the embedding degree of the Curve with respect to a prime $q$: The full torsion group of all $q$-torsion points lies in $E(\mathbb F_{p^k})$.

• For the MOV attack, we use 2 particular subgroups of the Full Torsion Group, $H_1$ and $H_2$, and we use the Weil Pairing $$H_1 \times H_2 \longrightarrow \mathbb F_{p^k} \text. $$

  • $H_1$ is the subgroup of the full torsion group which has all the $q$-torsion which only belong to the EC over the base field $F_p$.
  • $H_2$ is another subgroup of the full torsion group. Most books say that this is formed by the Frobenius Endomorphism.

The Frobenius Endomorphism is
$$F(r) = r^p$$ where $p$ is the prime characteristic of the ring.

Most math books refer to the Frobenius Endomorphism as something which applies only to Commutative Rings with a prime characteristic. If this is true, then obviously wouldn't apply to an Elliptic Curve Group. So if we had to apply it here, it would be applied to the coordinates of the points which lie in a Finite Field (which is also a commutative ring with prime characteristic). The map fixes points in $H_1$ — i.e. any point $R(x, y)$ in $H_1$ will always map to itself because $x^p = x$ and $y^p = y$.

However, for points on the extension group, it's a non-trivial map — i.e. a point would map to a different point.

My questions are as follows:

1. In another book, I also read that if you have a Point from the subgroup $H_2$, then the map exhibits in 2 ways — i.e. if $A=(x,y) \in H_2$, and $B=(x^p, y^p)$, then it also follows that $B$ is also $B = p*A$ (i.e. scalar multiplying $A$ by $p$).

   In other words, the map is both Multiplicative & Additive. Is this true?

2. How do we form the points of the subgroup $H_2$?

   Is it all points of the full torsion group which don't belong $H_1$? Or a subset of them?

3. Is $H_2$ the left hand side of the Endomorphism or the right hand side? Either way, what group is on the other side?

---

I understand how the MOV attack itself works — i.e. you transform the ECDH on $E(\mathbb F_p)$ to a DH on $\mathbb F_{p^k}$ which is simpler to solve because of Index Calculus if the embedding degree is small.

My question above is only about the Frobenius Endomorphism with respect to the MOV attack.

Answer 1

Firstly, I think that some terminology may be causing some problems. The Frobenius automorphism in a field of characteristic $p$ is the map $x\mapsto x^p$ and respects all of the field operations and fixes elements of the subfield $\mathbb F_p$ and other subfields are closed under the map. The Frobenius endomorphism of an elliptic curve over a field of characteristic $p$ is the map generated by applying the Frobenius automorphism co-ordinatewise: $\phi:(x,y)\mapsto (x^p,y^p)$. As the elliptic curve group law only uses field operations of coordinates and curve coefficients, $\phi$ respects both point addition: $\phi((x_1,y_1)+(x_2,y_2))=\phi(x_1,y_1)+\phi(x_2,y_2)$ and scalar multiplication: $\phi(k(x,y))=k\phi(x,y)$. The map fixes points of $E(\mathbb F_p)$ and the groups of points over other subfields are closed under the map if the curve coefficients lie in $\mathbb F_p$.

If we consider the full $q$-torsion subgroup this is defined as the set of points where $\{P:qP=\mathcal O\}$ and since $q\phi(P)=\phi(qP)$ the subgroup is closed under the Frobenius endomorphism. Similarly, it is easy to see that elements of the intersection of this subgroup with $E(\mathbb F_p)$ are fixed. However, it is not true that other subgroups are closed under this map. A numerical example might help at this point if you are familiar with sagemath. Let's take a simple example of a supersingular curve with coefficients in $GF(283)$ this has 284 points over $GF(283)$ and has a subgroup of order 71 over the base field. Over $GF(283^2)$, there are $284^2$ points and the full 71-torsion subgroup of $71^2$ points is realised. We can decompose this into a product of $H_1$ the $E(GF(283))$ subgroup and $H_2$ where $H_2$ any subgroup generated by a $q$-torsion point that does not lie in $E(GF(283))$. Note that $\# H_1=71$ and $\# H_2=71$ so that there are points of the torsion group that lie in neither $H_1$ nor $H_2$. We can find generators for $H_1$ and an arbitrary choice of $H_2$ with high probability by taking random points of $E(GF(283))$ and $E(GF(283^2)$ respectively and scalar multiplying by 4 (which is the cofactor in this case).

sage: q=71
sage: p=283
sage: E1=EllipticCurve(GF(p),[-1,0])
sage: E1.count_points()
284
sage: E2=EllipticCurve(GF(p^2),[-1,0])
sage: E2.count_points()
80656
sage: P=E2(4*E1.random_point())
sage: P
(265 : 176 : 1)
sage: Q=4*E2.random_point()
sage: Q
(136*z2 + 63 : 148*z2 + 187 : 1)
sage: q*P
(0 : 1 : 0)
sage: q*Q
(0 : 1 : 0)

Now consider applying the Frobenius map to $Q$ to produce a point $R$, we get a point that is in the full torsion subgroup, but is not the subgroup generated by $Q$:

sage: R=E2(Q[0]^p,Q[1]^p)
sage: R
(147*z2 + 199 : 135*z2 + 52 : 1)
sage: q*R
(0 : 1 : 0)
sage: for k in range(q):
....:     if(k*Q==R):
....:         print(k)
....:
sage:

In particular, $R$ is not $pQ$ and $H_2=\langle Q\rangle$ is not closed under Frobenius.