International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kim Nguyen

Affiliation: Bundesdruckerei GmbH

Publications

Year
Venue
Title
2007
CHES
2003
JOFC
2001
EPRINT
Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups
Antoine Joux Kim Nguyen
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.

Coauthors

Antoine Joux (2)