Variants of the Diffie-Hellman Problem

Diffie-Hellman Problem

In this chapter, we are considering useful variations of Diffie-Hellman problem: square Computational (and decisional) Diffie-Hellman problem, inverse computational (and decisional) Diffie-Hellman problem and divisible computational (and decisional) Diffie-Hellman problem. We are able to show that all variations of computational Diffie-Hellman problem are equivalent to the classic computational Diffie-Hellman problem if the order of an underlying cyclic group is a large prime (Bao et al., 2003).

Let p be a large prime number such that the discrete logarithm problem defined in is hard. Let G be a cyclic group of prime order q and g is assumed to be a generator of G. It is assumed that G is prime order, and security parameters p; q are defined as the fixed form p = 2q + 1 and ord(g) = q. A remarkable computational problem has been defined on this kind of set by Diffie and Hellman (Diffie, 1976). The Diffie-Hellman assumption (CDH assumption) is stated as follows:

• •

  Computational Diffie-Hellman Problem (CDH): On input g, g^x, g^y, computing g^xy. An algorithm that solves the computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, g^x, g^y, outputs g^xy with non-negligible probability. The Computational Diffe-Hellman assumption means that such a probabilistic polynomial time Turing Machine does not exist. This assumption is believed to be true for many cyclic groups, such as the prime sub-group of the multiplicative group of finite fields.

• •

  Square Computational Diffie-Hellman Assumption: The square computational Diffie-Hellman problem, introduced in (Maurer et al., 1998) is defined as follows:

• •

  Square Computational Diffie-Hellman Problem (SCDH): On input g, g^x, computing . An algorithm that solves the square computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, g^x, outputs g^x2 with non-negligible probability. The square computational Diffie- Hellman assumption means that there no such a probabilistic polynomial time Turing machine does not exist.