# How does the MOV attack work?

What exactly is the MOV attack, how does it actually work, and what is it used for?

It's explained briefly here and I'd like to know what it is more / what is it fully used for.

-

Most cryptosystems based on elliptic curves can be broken if you can solve the discrete logarithm problem, that is, given the point $P$ and $rP$, find the integer $r$.

The MOV attack uses a bilinear pairing, which (roughly speaking) is a function $e$ that maps two points in an elliptic curve $E(\mathbb{F}_q)$ to a element in the finite field $\mathbb{F}_{q^k}$, where $k$ is the embedding degree associated with the curve. The bilinearity means that $e(rP,sQ) = e(P,Q)^{rs}$ for points $P, Q$. Therefore, if you want to compute the discrete logarithm of $rP$, you can instead compute $u = e(P,Q)$ and $v = e(rP,Q)$ for any $Q$. Due to bilinearity, we have that $v = e(P,Q)^r = u^r$. Now you can solve the discrete logarithm in $\mathbb{F}_{q^k}$ (given $u^r$ and $u$, find $r$) in order to solve the discrete logarithm in the elliptic curve!

Usually, the embedding degree $k$ is very large (the same size as $q$), therefore transfering the discrete logarithm to $\mathbb{F}_{q^k}$ won't help you. But for some curves the embedding degree is small enough (specially supersingular curves, where $k <= 6$), and this enables the MOV attack. For example, a curve with a 256-bit $q$ usually offers 128 bits of security (i.e. can be attacked using $2^{128}$ steps); but if it has an embedding degree $2$, then we can map the discrete logarithm to the field $\mathbb{F}_{q^2}$ which offers only 60 bits of security.

In practice the attack can be simply avoided by not using curves with small embedding degree; standardized curves are safe. Since pairings also have many constructive applications, it is possible to carefully choose curves where the cost of attacking the elliptic curve itself or the mapped finite field is the same.

-
Actually, X9.62 (the standard for ECDSA) specifies some verifications when generating your own curve, include verifying that the embedding degree $k$ is greater than $100$. If you want to work over a subgroup of size $n$ (a prime) which divides the curve order, then the embedding degree is the smallest $k \geq 2$ such that $n$ divides $q^k-1$. It then suffices to check that $n$ does not divide $q^k-1$ for all values $k$ from $2$ to $100$. – Thomas Pornin Feb 18 '12 at 16:20

MOV stands for the authors Albert Menezes, Tatsuaki Okamoto and Scott Vanstone who wrote Reducing elliptic curve logarithms to logarithms in a finite field. The method has been considerably generalized by Gerhard Frey and Hans-Georg Rück.

As is common with mathematical concepts, there's no better way to understand it than to work through the maths yourself. However, one can think that the method revolves around the existence of a magic function that takes an elliptic curve point as an input and outputs an element of a finite field. The discrete logarithm problem can now be solved in the finite field where it is considerably easier. The issues to consider are now whether these functions exists for all curves and exactly how big the finite field is. The magic functions are very closely related to the Weil and Tate pairings which are independently fascinating and extensively used in some very new, exciting and fruitful areas of cryptography.

-