Computational Diffie-Hellman assumption
Encyclopedia
The computational Diffie–Hellman (CDH assumption) is the assumption that a certain computational problem
within a cyclic group
is hard.
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
The security of many cryptosystem
s is based on the CDH assumption, including notably the Diffie–Hellman key agreement scheme. Also, the confidentiality of ElGamal encryption
is equivalent to the CDH assumption (though the semantic security
of the scheme is based on the decisional Diffie–Hellman assumption).
The CDH assumption is related to the discrete logarithm assumption, which holds that computing the discrete logarithm
of a value base a generator
is hard. If taking discrete logs in 
were easy, then the CDH assumption would be false: given
one could efficiently compute
in the following way:
It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case.
The CDH assumption is also related to the decisional Diffie–Hellman assumption (DDH), which holds that it is hard to distinguish tuples of the form
from random tuples. If computing 
from 
were easy, then one could detect DDH tuples trivially. It is believed that CDH is a weaker assumption than DDH: there are groups for which detecting DDH tuples is easy, but solving CDH problems is believed to be hard.
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
within a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
is hard.
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
The security of many cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
s is based on the CDH assumption, including notably the Diffie–Hellman key agreement scheme. Also, the confidentiality of ElGamal encryption
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
is equivalent to the CDH assumption (though the semantic security
Semantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
of the scheme is based on the decisional Diffie–Hellman assumption).
The CDH assumption is related to the discrete logarithm assumption, which holds that computing the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
of a value base a generator
is hard. If taking discrete logs in were easy, then the CDH assumption would be false: givenone could efficiently compute
in the following way:
- compute
by taking the discrete log of 
to base 
; - compute
by exponentiation: 
;
It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case.
The CDH assumption is also related to the decisional Diffie–Hellman assumption (DDH), which holds that it is hard to distinguish tuples of the form
from random tuples. If computing from were easy, then one could detect DDH tuples trivially. It is believed that CDH is a weaker assumption than DDH: there are groups for which detecting DDH tuples is easy, but solving CDH problems is believed to be hard.