Cryptology ePrint Archive: Report 2001/003

Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups

Antoine Joux and Kim Nguyen

Abstract: In many cases, the security of a cryptographic scheme based on Diffie--Hellman does in fact rely on the hardness of the Diffie--Hellman Decision problem. In this paper, we show that the hardness of Decision Diffie--Hellman is a much stronger hypothesis than the hardness of the regular Diffie--Hellman problem. Indeed, we describe a reasonably looking cryptographic group where Decision Diffie--Hellman is easy while Diffie--Hellman is equivalent to a -- presumably hard -- Discrete Logarithm Problem. This shows that care should be taken when dealing with Decision Diffie--Hellman, since its security cannot be taken for granted.

Category / Keywords: public-key cryptography / number theory, elliptic curve

Date: received 9 Jan 2001

Contact author: Antoine Joux at ens fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20010110:222828 (All versions of this report)

Short URL: ia.cr/2001/003

Discussion forum: Show discussion | Start new discussion