The computational Diffie–Hellman (CDH) assumption is a
computational hardness assumption
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (uncondition ...
about the
Diffie–Hellman problem
The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use one-way functions: mathematical o ...
.
The CDH assumption involves the problem of computing the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
in
cyclic groups
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
. The CDH problem illustrates the attack of an eavesdropper in the
Diffie–Hellman key exchange
Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include:
* Diffie–Hellman–Merkle key exchange
* Diffie–Hellman key agreement
* Diffie–Hellman key establishment
* Diffie–Hellman key negotiation
* Exponential key exc ...
protocol to obtain the exchanged secret key.
Definition
Consider a
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
''G'' of order ''q''. The CDH assumption states that, given
:
for a randomly chosen generator ''g'' and random
:
it is
computationally intractable
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved b ...
to compute the value
:
Relation to Discrete Logarithms
The CDH assumption is strongly related to the
discrete logarithm assumption
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...
. If computing the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
(base ''g'' ) in ''G'' were easy, then the CDH problem could be solved easily:
Given
:
one could efficiently compute
in the following way:
* compute
by taking the discrete log of
to base
;
* compute
by exponentiation:
;
Computing the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. 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 (DDH assumption). If computing
from
was easy (CDH problem), 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 In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciph ...
of the
Diffie-Hellman Key Exchange as well as the security of the
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 1985. ElGamal encryption is used in th ...
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:
* Square computational Diffie-Hellman problem (SCDH): On input
, compute
;
* Inverse computational Diffie-Hellman problem (InvCDH): On input
, compute
;
* Divisible computation Diffie-Hellman problem (DCDH): On input
, compute
;
Variations of the Computational Diffie–Hellman assumption in product groups
Let
and
be two cyclic groups.
* Co-Computational Diffie–Hellman (co-CDH) problem: Given
and
, compute
;
References
{{DEFAULTSORT:Computational Diffie-Hellman assumption
Computational hardness assumptions