Cryptology ePrint Archive: Report 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.

Category / Keywords: Elliptic curves \and Pairings \and Public key cryptography \and Diffie-Hellman problem \and Distortion maps \and pairing inversion

Date: received 30 Oct 2008, last revised 3 Dec 2008

Contact author: dbm25 at math washington edu

Available format(s): PDF | BibTeX Citation

Version: 20081203:195104 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]