[Resource Topic] 2004/099: Secure Hashed Diffie-Hellman over Non-DDH Groups

Welcome to the resource topic for 2004/099

Secure Hashed Diffie-Hellman over Non-DDH Groups

Authors: Rosario Gennaro, Hugo Krawczyk, Tal Rabin


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.

ePrint: https://eprint.iacr.org/2004/099

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .