There is an elliptic curve. $y^2 = x^3 +ax+b \pmod p$ ($p$ is prime number)

To solve DLP, need to find $r$ from given points $G$, $rG$. ($G$'s order is $q$ and $q$ is prime number)

The MOV attack uses a Weil Pairing, which is a function $e$ that maps two points in an elliptic curve $E(\mathbb{F}_p)$ to a element in the finite field $\mathbb{F}_{p^k}$.

Q1. integer $k$ is minimum integer that divides $p^k-1$ by $q$. for example when $(p^2-1)/q$ then $k$=2 is it right??

and MOV attack need Weil Pairing $e$.

compute $u=e(P,Q), v=e(rP,Q)$

$v=e(rP,Q)=e(P,Q)^r =u^r$

Now solve the discrete logarithm in $\mathbb{F}_{p^k}$

$v\equiv u^r \pmod{\mathbb{F}_{p^k}}$

Q2. point $Q$ may be any point on the elliptic curve ?? ($Q=nP$ , $n!=r$)

Q3. Is it sequence of MOV attacks, right?

Thank you for read!


Q1: that's right. $k$ is called the embedding degree.

Q2: the Weil pairing works on a prime-order subgroup of the elliptic curve. So $Q$ must have order $n$, for prime $n$. And it can't be the point at infinity. Thus the point $Q$ can be any point matching this criteria.

Q3: that's right.


Your Answer

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