| Bilinear pairings on elliptic curves have been of much interest in cryptography recently. Most of the protocols involving pairings rely on the hardness of the bilinear Diffie-Hellman problem. In contrast to the discrete log (or Diffie-Hellman) problem in a finite field, the difficulty of this problem has not yet been much studied. In 2001, Verheul (Advances in Cryptology - EUROCRYPT 2001, LNCS 2045, pp. 195-210, 2001) proved that on a certain class of curves, the discrete log and Diffie-Hellman problems are unlikely to be provably equivalent to the same problems in a corresponding finite field unless both Diffie-Hellman problems are easy. In this paper we generalize Verheul's theorem and discuss the implications on the security of pairing based systems. We also include a large table of distortion maps. |
