Join Log in
Score:2
avatar Crypto

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

et flag
user93353

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.

159
1 + 0
Score:3
Daniel S avatar Crypto
ru flag
Daniel S

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.

+ 5
et flag
user93353
Thank you for the answer. It will probably take some time for me to understand it fully, so please don't mind
0
Reply
et flag
user93353
This is what I get from your answer which has answered quite a few of my questions. 1) $H1 U H2$ is not the full torsion subgroup. 2) $P({Q_x}^p, {Q_y}^p) \ne p*Q$. Some questions follow.
0
Reply
et flag
user93353
However, I am confused as to how Frobenius morphism (auto or endo) is related at all to the Weil Pairings. I am getting the feeling that it is not. I think I got the idea that the Weil Pairing involves Frobenius morphism because I probably misread some text on Pairing Groups in general which may not have been talking about Weil Pairings in Particular
0
Reply
et flag
user93353
There are multiple q-torsion subgroups in $E(F_{p^k})$. As far as the Weil Pairing & the MOV attack are concerned, does it matter which of these subgroups $H_2$ is as long as it's not the one in $E(F_p)$?
0
Reply
Daniel S avatar
ru flag
Daniel S
That's correct; we can choose any $H_2$ generated by an element from the larger field and provided that we are consistent in this choice, the attack will work.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.