Paper 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.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
number theoryelliptic curve
Contact author(s)
Antoine Joux @ ens fr
History
2001-01-10: received
Short URL
https://ia.cr/2001/003
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/003,
      author = {Antoine Joux and Kim Nguyen},
      title = {Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups},
      howpublished = {Cryptology ePrint Archive, Paper 2001/003},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/003}},
      url = {https://eprint.iacr.org/2001/003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.