Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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