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

Available format(s)
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
Short URL
https://ia.cr/2001/003

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.