Secure Hashed Diffie-Hellman over Non-DDH Groups

Tal Rabin
IBM T.J. Watson

Monday, November 29, 2:00PM
Burchard 124
Computer Science Department
Stevens Institute of Technology
 

Abstract


It is generally accepted that for securing common applications of Diffie-Hellman (DH), such as key exchange and encryption, one needs to ensure that the group over which the DH is computed satisfies the Decisional Diffie-Hellman (DDH) assumption. Motivated by practical considerations, we study a relaxation of this basic premise.

We show that the requirement to work over DDH groups (that is, groups that satisfy the DDH assumption) can be relaxed to the sole assumption that the group over which DH is computed contains a large enough DDH subgroup. This justifies the common use in practice of non-DDH groups such as Zp*. Moreover, we show that one can work directly over Zp* without requiring any knowledge of the prime factorization of p-1 and without even having to find a generator of Zp*. These results are obtained via a general characterization of DDH groups in terms of their DDH subgroups, and a relaxation of the DDH assumption (called t-DDH) via computational entropy.

Joint work with with Rosario Gennaro and Hugo Krawczyk