Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 229

DLP

x

X

K

K = Y x

X , Y

Figure 9.6. Reduction of DHP to DLP.

The Diffie-Hellman problem is stated as follows:

DHP (Diffie-Hellman Problem)
Parameters : a group G , an element g G .

Input : two random elements X and Y in the subgroup of G spanned by g .
Problem : compute K

∈

g xy where x = = log g X and y = log g Y .

g x

(We assume that generating an -bit integer x and computing X = correctly gener-

ates X , and the same for Y .) If this problem is hard, K is confidential.

We would like to compare this problem with other ones. We first focus on the
discrete logarithm problem (DLP) that is defined on p. 160. Obviously, if we know
how to solve DLP, then we can solve DHP by computing x as the DLP of X and then
computing K Y x . Thus DHP reduces to DLP (see Fig. 9.6). So, if the Diffie-Hellman

problem is hard, then the discrete logarithm problem in the subgroup spanned by g is
hard as well. DHP is believed to be hard for G

=

Z p with a large prime p . =

For completeness we also mention the Decisional Diffie-Hellman problem , which
can be formulated as follows.

DDHP (Decisional Diffie-Hellman Problem)
Parameters : a group G , an element g

∈ G .

, ,

Input : a triplet ( X K ) of elements in the subgroup spanned by g .

Problem : decide whether K

Y

X log g Y

=

or not.

Obviously DDHP reduces to DHP. This problem is also believed to be hard when the
subgroup of G

= Z p (for a large prime p ) which is spanned by g is large.

9.2

Experiment with NP-Completeness

Although Diffie and Hellman clearly defined the notion of public-key cryptosystem
(by the notion of trapdoor permutation), they did not suggest any example. They did
not even prove that such a primitive existed.