Decisional Diffie-Hellman assumption
From Wikipedia, the free encyclopedia
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,ga,gb) for a randomly-chosen generator g and random 
, the value gab "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,ga,gb,gab), where g,a,b are chosen at random as described above (this input is called a "DDH tuple");
- (g,ga,gb,gc), where g,a,b are chosen at random and c is chosen at random from
.
Note that, in the second ensemble, the value gc is a random element of G (independent of g, and of course ga,gb) 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,ga,gb,z), one could efficiently decide whether z = gab in the following way:
- compute a by taking the discrete log of ga;
- compute gab by exponentiation: gab = (gb)a;
- compare gab 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 gab from (g,ga,gb) 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 gab is believed to be hard. Or put in another way; DDH is stronger because there are fewer groups in which DDH holds than in which CDH holds.
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.
