|
The decisional Diffie-Hellman (DDH) assumption is the assumption that a certain computational problem within a cyclic group is hard.
Consider a cyclic group <math>G<math> of order <math>q<math>. The DDH assumption states that, given <math>(g,g^a,g^b)<math> for a randomly-chosen generator <math>g<math> and random <math>a,b \in \{0, \ldots, q-1\}<math>, the value <math>g^{ab}<math> "looks like" a perfectly random element of <math>G<math>.
This intuitive notion is formally stated by saying that the following two ensembles are computationally indistinguishable:
- <math>(g,g^a,g^b,g^{ab})<math>, where <math>g,a,b<math> are chosen at random as described above (this input is called a "DDH tuple");
- <math>(g,g^a,g^b,g^c)<math>, where <math>g,a,b<math> are chosen at random and <math>c<math> is chosen at random from <math>\{0, \ldots, q-1\}<math>.
Note that, in the second ensemble, the value <math>g^c<math> is a random element of <math>G<math> (independent of <math>g<math>, and of course <math>g^a,g^b<math>) because <math>g<math> 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 <math>G<math> were easy, then the DDH assumption would be false: given <math>(g,g^a,g^b,z)<math>, one could efficiently decide whether <math>z=g^{ab}<math> in the following way:
- compute <math>a<math> by taking the discrete log of <math>g^a<math>;
- compute <math>g^{ab}<math> by exponentiation: <math>g^{ab} = (g^b)^a<math>;
- compare <math>g^{ab}<math> 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 <math>g^{ab}<math> from <math>(g,g^a,g^b)<math> 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 <math>g^{ab}<math> 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] (http://crypto.stanford.edu/~dabo/abstracts/DDH.html).
|
