MOV attack in various subgroups on elliptic curves
type: Item
instance of: scholarly article
title: MOV attack in various subgroups on elliptic curves
zbMATH Open document ID: 1072.11094
author: Florian Luca
author: David Jose Mireles
author: Igor E. Shparlinski
published in: Illinois Journal of Mathematics
publication date: 2005-03-01T00:00:00Z
review text: \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.
reviewed by: Tanja Lange
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11N25
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 2140265
zbMATH Keywords: MOV attack
zbMATH Keywords: elliptic curves
zbMATH Keywords: embedding degree
MaRDI profile type: Publication
Recommended article: Q3149772
Recommended article: On the Minimal Embedding Field
Recommended article: Comparing the MOV and FR Reductions in Elliptic Curve Cryptography
Recommended article: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm
Recommended article: Q4314052
Recommended article: Q3044320
Recommended article: Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝
Recommended article: Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
Recommended article: Non Supersingular Elliptic Curves for Public Key Cryptosystems
Recommended article: Pairing-Friendly Elliptic Curves of Prime Order
description: scientific article; zbMATH DE number 2140265