The Diffie-Hellman problem and generalization of Verheul's theorem

Dustin Moody

Paper 2008/456

The Diffie-Hellman problem and generalization of Verheul's theorem

Dustin Moody

Abstract

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 \cite{Ver} 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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): dbm25 @ math washington edu
History: 2008-12-03: last of 2 revisions; 2008-11-02: received; See all versions
Short URL: https://ia.cr/2008/456
License: CC BY

BibTeX

@misc{cryptoeprint:2008/456,
      author = {Dustin Moody},
      title = {The Diffie-Hellman problem and generalization of Verheul's theorem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/456},
      year = {2008},
      url = {https://eprint.iacr.org/2008/456}
}