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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
16
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.
-
5$\begingroup$ 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$. $\endgroup$ Commented Feb 18, 2012 at 16:20
-
$\begingroup$ What does the embedding degree mean in this context? $\endgroup$ Commented Apr 11, 2017 at 5:02
-
1$\begingroup$ @Venkatesh the embedding degree is a property of an elliptic curve. Like Thomas said, it's the smallest $k \ge 2$ such that $n$ (the order of the curve, i.e. the number of points in the curve) divides $q^k - 1$ (where $q$ is the size of the underlying finite field). $\endgroup$– ConradoCommented Apr 11, 2017 at 11:19
-
$\begingroup$ @ConradoPLG Can you explain about the Frey- Ruck attack on solving ECDLP? $\endgroup$ Commented Apr 12, 2017 at 6:24
-
3$\begingroup$ As opposed to taking two points on $E(\mathbb{F}_q)$, an efficiently computable bilinear map such as the Weil Pairing would have to instead take one point from $E(\mathbb{F}_q)$ and one from a group such as $E(\mathbb{F}_{q^2})$. Otherwise the pairing would be degenerate. Weil has $e(P, P) = 1$, which implies $e(P,Q)=1$ when Q is a multiple of P. Solving the discrete log of $(1, 1^x)$ won't quite reveal x unfortunately. The actual point Q itself we don't really care about, but it is important that its not in $E(\mathbb{F}_q)$ $\endgroup$ Commented Dec 5, 2018 at 5:17
$\begingroup$
$\endgroup$
MOV stands for the authors Alfred 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.
