Computational Diffie–Hellman assumption


The computational Diffie–Hellman assumption is a computational hardness assumption about the Diffie–Hellman problem.
The CDH assumption involves the problem of computing the discrete logarithm in cyclic groups.
The CDH problem illustrates the attack of an eavesdropper in the Diffie–Hellman key exchange protocol to obtain the exchanged secret key.

Definition

Consider a cyclic group G of order q. The CDH assumption states that, given
for a randomly chosen generator g and random
it is computationally intractable to compute the value

Relation to Discrete Logarithms

The CDH assumption is strongly related to the discrete logarithm assumption.
If computing the discrete logarithm in G was easy, then the CDH problem can be solved easily:
Given
one could efficiently compute in the following way:
So far, computing the discrete logarithm to solve the CDH problem is the only known method.
But there is no proof that it is, in fact, the only method to solve the CDH problem.
It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to be the case.

Relation to Decisional Diffie–Hellman Assumption

The CDH assumption is a weaker assumption than the Decisional Diffie–Hellman assumption.
If computing from was easy, then one could solve the DDH problem trivially.
Many cryptographic schemes that are constructed from the CDH problem rely in fact on the hardness of the DDH problem.
The semantic security of the Diffie-Hellman Key Exchange as well as the security of the ElGamal encryption rely on the hardness of the DDH problem.
There are concrete constructions of groups where the stronger DDH assumption does not hold but the weaker CDH assumption still seems to be a reasonable hypothesis.

Variations of the Computational Diffie–Hellman assumption

The following variations of the CDH problem have been studied and proven to be equivalent to the CDH problem :
Let and be two cyclic groups.