Decisional Diffie-Hellman assumption

The decisional Diffie-Hellman (DDH) assumption is the assumption that a certain computational problem within a cyclic group is hard.

Consider a cyclic group G of order q. The DDH assumption states that, given (g,g^a,g^b) for a randomly-chosen generator g and random , the value g^ab "looks like" a perfectly random element of G.

This intuitive notion is formally stated by saying that the following two ensembles are computationally indistinguishable :

• (g,g^a,g^b,g^ab), where g,a,b are chosen at random as described above (this input is called a "DDH tuple");
• (g,g^a,g^b,g^c), where g,a,b are chosen at random and c is chosen at random from .

Note that, in the second ensemble, the value g^c is a random element of G (independent of g, and of course g^a,g^b) because g is a generator.

The semantic security of ElGamal encryption is equivalent to the DDH assumption.

The DDH assumption is related to the discrete log assumption. If taking discrete logs in G were easy, then the DDH assumption would be false: given (g,g^a,g^b,z), one could efficiently decide whether z = g^ab in the following way:

• compute a by taking the discrete log of g^a;
• compute g^ab by exponentiation: g^ab = (g^b)^a;
• compare g^ab to z.

It is believed that DDH is a stronger assumption than discrete log, in the following sense: there are groups for which detecting DDH tuples is easy, but computing discrete logs is believed to be hard.

The DDH assumption is also related to the computational Diffie-Hellman assumption (CDH). If computing g^ab from (g,g^a,g^b) were easy, then one could detect DDH tuples in a manner similar to the above algorithm. It is believed that DDH is a stronger assumption than CDH: there are groups for which detecting DDH tuples is easy, but computing the Diffie-Hellman value g^ab is believed to be hard.

The problem of detecting DDH tuples is random self-reducible , meaning, roughly, that if it is hard for even a small fraction of inputs, it is hard for almost all inputs; if it is easy for even a small fraction of inputs, it is easy for almost all inputs.

References

• Dan Boneh, The Decision Diffie-Hellman Problem, ANTS 1998, pp48–63 [1].