The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm

The security of elliptic curve cryptosystems is based on the presumed intractability of the discrete logarithm problem on the curve. Other than algorithms that work in an arbitrary group and are exponential in the general case, the only general-purpose algorithm that has ever been proposed for the elliptic curve discrete Logarithm is that of Menezes-Okamoto-Vanstone (MOV). The MOV algorithm, which embeds an elliptic curve group of prime order I in the multiplicative group of a field F-qk, is subexponential only under special circumstances, however. In this paper we first prove that, under a mild condition that always holds in practical applications, the condition that l\(q(k) - 1), which is obviously necessary for realizing the MOV algorithm, is also sufficient. We next give an improved upper bound for the frequency of occurrence of pairs of primes l, p such that l\(p(k) - 1) for k small, where l is in the Hasse interval [p + 1 - 2 root p, p + 1 + 2 root p].