Secure Hashed Diffie-Hellman over Non-DDH Groups

Rosario Gennaro; Hugo Krawczyk; Tal Rabin

Paper 2004/099

Secure Hashed Diffie-Hellman over Non-DDH Groups

Rosario Gennaro, Hugo Krawczyk, and Tal Rabin

Abstract

We show that in applications that use the Diffie-Hellman (DH) transform but take care of hashing the DH output (as required, for example, for secure DH-based encryption and key exchange) the usual requirement to work over a DDH group (i.e., a group in which the Decisional Diffie-Hellman assumption holds) can be relaxed to only requiring that the DH group contains a large enough DDH subgroup. In particular, this implies the security of (hashed) Diffie-Hellman over non-prime order groups such as $Z_p^*$. Moreover, our results show that one can work directly over $Z_p^*$ without requiring any knowledge of the prime factorization of $p-1$ and without even having to find a generator of $Z_p^*$. These results are obtained via a general characterization of DDH groups in terms of their DDH subgroups, and a relaxation (called $t$-DDH) of the DDH assumption via computational entropy. We also show that, under the short-exponent discrete-log assumption, the security of the hashed Diffie-Hellman transform is preserved when replacing full exponents with short exponents.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Conference version in Eurocrypt'2004.
Keywords: public-key cryptography key management discrete logarithm problem
Contact author(s): hugo @ ee technion ac il
History: 2006-01-10: revised; 2004-04-30: received; See all versions
Short URL: https://ia.cr/2004/099
License: CC BY

BibTeX

@misc{cryptoeprint:2004/099,
      author = {Rosario Gennaro and Hugo Krawczyk and Tal Rabin},
      title = {Secure Hashed Diffie-Hellman over Non-{DDH} Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/099},
      year = {2004},
      url = {https://eprint.iacr.org/2004/099}
}