HOME

TheInfoList



OR:

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 :(g,g^a,g^b) \, for a randomly chosen generator ''g'' and random :a,b \in \,\, 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 :g^. \,


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 :(g,g^a,g^b), \, one could efficiently compute g^ in the following way: * compute a by taking the discrete log of g^a to base g; * compute g^ by exponentiation: g^ = (g^b)^a; 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 g^ from (g,g^a,g^b) 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 g, g^x, compute g^; * Inverse computational Diffie-Hellman problem (InvCDH): On input g, g^x, compute g^; * Divisible computation Diffie-Hellman problem (DCDH): On input g, g^x, g^y, compute g^;


Variations of the Computational Diffie–Hellman assumption in product groups

Let G_1 and G_2 be two cyclic groups. * Co-Computational Diffie–Hellman (co-CDH) problem: Given g, g^a \in G_1 and h \in G_2, compute h^a \in G_2;


References

{{DEFAULTSORT:Computational Diffie-Hellman assumption Computational hardness assumptions