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

by Moody, Dustin, Ph.D., UNIVERSITY OF WASHINGTON, 2009, 94 pages; 3370527


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.

AdviserNeal Koblitz
Source TypeDissertation
Publication Number3370527

About ProQuest Dissertations & Theses
With nearly 4 million records, the ProQuest Dissertations & Theses (PQDT) Global database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

PQDT Global combines content from a range of the world's premier universities - from the Ivy League to the Russell Group. Of the nearly 4 million graduate works included in the database, ProQuest offers more than 2.5 million in full text formats. Of those, over 1.7 million are available in PDF format. More than 90,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - - or contact ProQuest Support.