MOV attack in various subgroups on elliptic curves (Q1766871)

\textit{A. J. Menezes, T. Okamoto} and \textit{S. A. Vanstone} [IEEE Trans. Inf. Theory 39, No. 5, 1639--1646 (1993; Zbl 0801.94011)] showed how to use the Weil pairing to map discrete logarithms in the group of points on an elliptic curve over \(F_p\) to discrete logarithms in the multiplicative group of \(F_{p^k}\) where \(k\) is minimal such that the group order \(\#E(F_p)\) divides \(p^k-1\). Clearly, \(k\) depends on the curve and in particular it is always less than or equal to 6 for supersingular curves. This result is interesting for cryptographic applications as the DLP in finite fields can be solved with subexponential algorithms. \textit{R. Balasubramanian} and \textit{N. Koblitz} [J. Cryptology 11, No. 2, 141--145 (1998; Zbl 0978.94038)] showed that for randomly chosen curves of prime order (in particular not supersingular ones) over prime fields the probability of having a small embedding degree \(k\) is exponentially small. The present paper extends this result to deal with more general elliptic curves over prime fields \(F_p\) by not restricting the considerations to prime group orders. This is of practical relevance since usually small cofactors are allowed. They estimate the probability that \(k\) is smaller than a certain \(K=O(\log p)\) for the following cases: the full order \(N=\#E(F_p)\) divides \(p^k-1\), the order of the maximal cyclic subgroup divides \(p^k-1\), the order of the maximal prime order subgroup divides \(p^k-1\) and finally that for all prime order subgroups the corresponding necessary \(k\)'s are simultaneously smaller than \(K\). The latter corresponds to the approach of solving the DLP separately in the subgroups and then combining the result via the Chinese Remainder Theorem.