4
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Richard Jan 24 '13 at 3:16
  • $\begingroup$ I used SAGE, it has all kids of useful things. I've posted the code to do the above here. $\endgroup$ – Samuel Neves Jan 24 '13 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.