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
-
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},
url = {https://eprint.iacr.org/2001/003}
}
