The MOV Attack

Suppose we are given points \(P, xP\) of an elliptic curve and asked to recover \(x\). (This is the discrete logarithm problem.)

Let \(e()\) be the Weil pairing. Let \(m\) be the order of \(P\). Let \(Q\) be a point of order \(m\) that is linearly independent to \(P\) (in other words, there is no \(n\) such that \(Q = n P\)).

Then \(e(P,Q)\) and \(e(x P, Q) = e(P,Q)^x\) can be computed, and are both elements of a finite field. (They are \(m\)th roots of unity.) Since \(P,Q\) are linearly independent, \(e(P,Q)\) cannot be unity by the nondegeneracy of the Weil pairing. Thus we have reduced the discrete logarithm problem on the group of points on an elliptic curve to the discrete logarithm on finite fields, where subexponential attacks are known.

Ben Lynn 💡