# Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack

The curve $E(\mathbb{F}_{47}):y^2=x^3+x+38$ has order $61$ and $61|47^3-1$ so the embedding degree of $E$ is $3$ and therefore the MOV attack, presumably using some sort of distortion map and a suitable pairing can be used to find discrete logarithms. Exactly how is this done in this case? If a larger example would better illustrate the power of the technique then $E(\mathbb{F}_{8111}):y^2=x^3+x+300$ has order $8269$ and $8269|8111^3-1$

-

Let's take your latter example. We will use the Weil pairing here, since that was the original MOV approach. Let's pick some arbitrary points in your curve:

$$\begin{eqnarray} P &=& (6116 : 2715) \\ Q &=& (3034 : 462) \end{eqnarray}$$

From now on, we'll actually work in an extension field of $\mathbb{F}_{8111}$, namely $\mathbb{F}_{8111^3}$. For concreteness, we choose the polynomial $x^3 + 4x - 11$ to define the extension field.

Now we need to find some arbitrary point that has order $8269$ but is not a multiple of $P$. We know that the group structure of the points of order $n$ in a pairing-friendly curve is $E(F_q)[n] = \mathbb{Z}_n \oplus \mathbb{Z}_n$, so there are definitely such points out there. An example point would be

$$R = (3515x^2 + 7098x + 2717 : 3745x^2 + 7258x + 4072).$$

Now all it's left is to apply the Weil pairing to both points:

$$\begin{eqnarray} w_1 &=& e(P, R) \in \mathbb{F}_{8111^3} \\ w_2 &=& e(Q, R) = e(uP, R) = e(P, R)^u \in \mathbb{F}_{8111^3} \end{eqnarray}$$

Now we can solve the log of $w_1 = 7474x^2 + 74x + 6953$ and $w_2 = 2625x^2 + 6673x + 243$ over $\mathbb{F}_{8111^3}$. It's $2634$, and it's easy to see that $2634\cdot P = Q$. For large fields, it is considerably faster to find $\log_{w1} w2$ via the number or function field sieve ($L[1/3; c]$) than the elliptic curve discrete log $\log_P Q$ via Pollard's rho ($O(n^{1/2}))$.

-
Thanks.I would upvote if I could. I can verify that P and R are have order 8269 along with w_1 and w_1^2634=w_2 and [2634]P=Q, that R is not a multiple of P, all using Pari/GP but I can't do the Weil pairing. What software did you use? Also, presumably x^3+4x-11 could be replaced with x^3+x+1 as x has order 8111^3-1 when the field is defined this way. –  Richard Jan 24 '13 at 3:16
I used SAGE, it has all kids of useful things. I've posted the code to do the above here. –  Samuel Neves Jan 24 '13 at 18:13