Return to Question

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

So there seems to be 4 conditions to satisfied for the MOV attack to work

• Prime order of Generator.
• The order of the generator is coprime to the order of the Field
• The order of the genator does not divide $(q − 1)$
• Small embedding degree

So even if you do have a small embedding degree what would be probability that the $MOV$ attack would be applicable. A lot of different conditions need to be satisfied - i.e. you could choose a small embedding degree as long as one of the other conditions aren't satisfied.

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

So there seems to be 4 conditions which need to be satisfied for the MOV attack to work

• Prime order of Generator.
• The order of the generator is coprime to the order of the Field
• The order of the genarator does not divide $(q − 1)$
• Small embedding degree

So even if you do have a small embedding degree what would be probability that the $MOV$ attack would be applicable. A lot of different conditions need to be satisfied - i.e. you could choose a small embedding degree as long as one of the other conditions aren't satisfied.

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

Also re the other condition "satisfies $gcd(n,q)=1$", is that also common that the prime order of the generator is coprime to the order of the Field?

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

So there seems to be 4 conditions to satisfied for the MOV attack to work

• Prime order of Generator.
• The order of the generator is coprime to the order of the Field
• The order of the genator does not divide $(q − 1)$
• Small embedding degree

So even if you do have a small embedding degree what would be probability that the $MOV$ attack would be applicable. A lot of different conditions need to be satisfied - i.e. you could choose a small embedding degree as long as one of the other conditions aren't satisfied.

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So this would work only when in $ECDH$ problem is of they kind $nG = R$ with $G$ a point of prime order. So for ECDH, do we always chose a generator of prime order. If so, why?

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

Also re the other condition "satisfies $gcd(n,q)=1$", is that also common that the prime order of the generator is coprime to the order of the Field?