International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Antoine Joux
Kim Nguyen
Download:
URL: http://eprint.iacr.org/2001/003
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2001-11415,
  title={Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / number theory, elliptic curve},
  url={http://eprint.iacr.org/2001/003},
  note={ Antoine.Joux@ens.fr 11331 received 9 Jan 2001},
  author={Antoine Joux and Kim Nguyen},
  year=2001
}