The Discrete Logarithm Problem - Elliptic Curves: Number Theory and Cryptography - page 153

discrete logs, the order of the group should be chosen so it contains a large
prime factor.
If N contains some small prime factors, then the Pohlig-Hellman method
can be used to obtain partial information on the value of k , namely a congru-
ence modulo a product of these small prime factors. In certain cryptographic
situations, this could be undesirable. Therefore, the group G is often chosen
to be of large prime order. This can be accomplished by starting with a group
that has a large prime q in its order. Pick a random point P 1 and compute
its order. With high probability (at least 1 1 /q ; cf. Remark 5.2), the order

of P 1 is divisible by q , so in a few tries, we can find such a point P 1 .Write
the order of P 1 as qm .Then P = mP 1 will have order q .Aslongas q is
suciently large, discrete log problems in the cyclic group generated by P
will resist the Pohlig-Hellman attack.

−

5.3 Attacks with Pairings

One strategy for attacking a discrete logarithm problem is to reduce it to an
easier discrete logarithm problem. This can often be done with pairings such
as the Weil pairing or the Tate-Lichtenbaum pairing, which reduce a discrete
logarithm problem on an elliptic curve to one in the multiplicative group of a
finite field.

5.3.1 The MOV Attack

The MOV attack, named after Menezes, Okamoto, and Vanstone [80], uses
the Weil pairing to convert a discrete log problem in E ( F q )toonein F q m .
Since discrete log problems in finite fields can be attacked by index calculus
methods, they can be solved faster than elliptic curve discrete log problems, as
long as the field F q m is not much larger than F q . For supersingular curves, we
can usually take m = 2, so discrete logarithms can be computed more easily
for these curves than for arbitrary elliptic curves. This is unfortunate from a
cryptographic standpoint since an attractive feature of supersingular curves
is that calculations can often be done quickly on them (see Section 4.6).
Recall that for an elliptic curve E defined over F q ,welet E [ N ]denotethe
set of points of order dividing N with coordinates in the algebraic closure. If
gcd( q, N )=1and S, T ∈ E [ N ], then the Weil pairing e N ( S, T )isan N th root
of unity and can be computed fairly quickly. The pairing is bilinear, and if
{S, T } is a basis for E [ N ], then e N ( S, T ) is a primitive N th root of unity. For
any S , e N ( S, S ) = 1. For more properties of the Weil pairing, see Sections 3.3
and 11.2.