Cryptology ePrint Archive: Report 2004/099
Secure Hashed Diffie-Hellman over Non-DDH Groups
Rosario Gennaro and 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.
Category / Keywords: public-key cryptography / public-key cryptography, key management, discrete logarithm problem
Publication Info: Conference version in Eurocrypt'2004.
Date: received 29 Apr 2004, last revised 10 Jan 2006
Contact author: hugo at ee technion ac il
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20060110:192925 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]