2
$\begingroup$

There already is this pretty big post about the MOV-attack. It states, that the discrete logarithm problem on elliptic curves can be transformed to a discrete logarithm problem over a finite field. This is possible by using a mapping to a field extension.

The attack is not useful, if the resulting field extension $F_{p^m}$ has a large $m$. But if $m$ is small, e.g. $m = 2$, the complexity of solving the DLP is singificantly smaller than solving the ECDLP. ( e.g. if $m=2$ the security of a $256$ Bit ECC can be reduced to $60$ Bit )

My questions:

  1. Why is solving the DLP instead of ECDLP easy, when $m$ is small? How to compute the resulting security Bits?
  2. Can someone provide me a simple example including the important steps, in which the MOV attack is useful? ( Input: ECC with $Q = n\cdot P$ -> contructing the bilinear function $e$ -> using $e$ to transform the ECDLP to DLP -> solving DLP )? The main points I don't understand are constructing $e$ and how to solve the DLP faster than ECDLP.
Improve this question
$\endgroup$
1
  • $\begingroup$ There's a step by step example of a MOV attack here, and here is the complexity to solve the discrete logarithm over $\mathbb{F}_{p^m}$ (replace $p$ by $p^m$ everywhere, it still applies, for the most part). $\endgroup$
    – Samuel Neves
    Aug 6 '20 at 19:25

Your Answer

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

Browse other questions tagged or ask your own question.