Introduction to Cryptography with Coding Theory, 3rd Edition

22.2 The MOV Attack

Let $E$ be the elliptic curve from Section 22.1. Suppose $Q=k{P}_0\text{,}$ where $k$ is some integer and $P_0$ is the point from Section 22.1. The Elliptic Curve Discrete Log Problem asks us to find $k$. Menezes, Okamoto, and Vanstone showed the following method of reducing this problem to the discrete log problem in the field with $p^2$ elements. Observe that

$$\tilde{e}(Q\text{,}{P}_0)=\tilde{e}(k{P}_0\text{,}{P}_0)=\tilde{e}(P_0\text{,}{P}_0{)}^k\text{.}$$

Therefore, solving the discrete log problem $\tilde{e}(Q\text{,}{P}_0)=\tilde{e}(P_0\text{,}{P}_0{)}^k$ for $k$ yields the answer. Note that this latter discrete log problem is not on the elliptic curve, but instead in the finite field with $p^2$ elements. There are analogues of the index calculus for this situation, so usually this is an easier discrete log problem.

For a randomly chosen (not necessarily ...