Welcome to the resource topic for 2004/099
Secure Hashed Diffie-Hellman over Non-DDH Groups
Authors: Rosario Gennaro, Hugo Krawczyk, Tal RabinAbstract:
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.
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 .