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

Question

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$

Answer 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}))$.