Secure Hashed Diffie-Hellman over Non-DDH Groups

The Diffie-Hellman (DH) transform is a basic cryptographic primitive used in innumerable cryptographic applications, most prominently in discrete-log based encryption schemes and in the Diffie-Hellman key exchange. In many of these applications it has been recognized that the direct use of the DH output, even over groups that satisfy the strong Decisional Diffie-Hellman (DDH) assumption, may be insecure. This is the case when the application invoking the DH transform requires a value that is pseudo-randomly distributed over a set of strings of some length rather than over the DH group in use. A well-known and general solution is to hash (using a universal hash family) the DH output; we refer to this practice as the “hashed DH transform”.The question that we investigate in this paper is to what extent the DDH assumption is required when applying the hashed DH transform. We show that one can obtain a secure hashed DH transform over a non-DDH group G (i.e., a group in which the DDH assumption does not hold); indeed, we prove that for the hashed DH transform to be secure it suffices that G contain a sufficiently large DDH subgroup. As an application of this result, we show that the hashed DH transform is secure over Z _p * for random prime p, provided that the DDH assumption holds over the large prime-order subgroups of Z _p *. In particular, we obtain the same security working directly over Z _p * as working over prime-order subgroups, without requiring any knowledge of the prime factorization of p-1 and without even having to find a generator of Z _p *.Further contributions of the paper to the study of the DDH assumption include: the introduction of a DDH relaxation, via computational entropy, which we call the “t-DDH assumption” and which plays a central role in obtaining the above results; a characterization of DDH groups in terms of their DDH subgroups; and the analysis of of the DDH (and t-DDH) assumptions when using short exponents.