Computational Diffie–Hellman assumption

Consider a cyclic group G of order q. The CDH assumption states that, given

:$(g,g^a,g^b)\; \backslash ,$

for a randomly chosen generator g and random

:$a,b\; \backslash in\; \backslash \{0,\; \backslash ldots,\; q-1\backslash \},\backslash ,$

it is computationally intractable to compute the value

:$g^\{ab\}.\; \backslash ,$

The CDH assumption is strongly related to the discrete logarithm assumption. If computing the discrete logarithm (base g ) in G were easy, then the CDH problem could be solved easily:

Given

:$(g,g^a,g^b),\; \backslash ,$

one could efficiently compute $g^\{ab\}$ in the following way:

• compute $a$ by taking the discrete log of $g^a$ to base $g$;
• compute $g^\{ab\}$ by exponentiation: $g^\{ab\}\; =\; (g^b)^a$;

Computing the discrete logarithm 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.{{Citation | last=den Boer | first=Bert | title=Diffie–Hellman is as strong as discrete log for certain primes | volume=403 | pages=530–539 | year=1988 | url=https://link.springer.com/content/pdf/10.1007/0-387-34799-2_38.pdf| doi=10.1007/0-387-34799-2_38 | series=Lecture Notes in Computer Science | isbn=978-0-387-97196-4 | doi-access=free }}{{Citation | last=Maurer | first=Ueli M. | title=Towards the Equivalence of Breaking the Diffie–Hellman Protocol and Computing Discrete Logarithms | year=1994 | citeseerx=10.1.1.26.530 }}

The CDH assumption is a weaker assumption than the Decisional Diffie–Hellman assumption (DDH assumption). If computing $g^\{ab\}$ 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 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.{{Citation | last1=Joux | first1=Antoine | last2=Nguyen | first2=Kim | title=Separating decision Diffie–Hellman from computational Diffie–Hellman in cryptographic groups | journal=Journal of Cryptology | volume=16 | issue=4 | pages=239–247 | year=2003 | doi=10.1007/s00145-003-0052-4 | doi-access=free }}

The following variations of the CDH problem have been studied and proven to be equivalent to the CDH problem:{{Citation | last1=Bao | first1=Feng | last2=Deng | first2=Robert H. | last3=Zhu | first3=Huafei | title=Variations of the Diffie–Hellman Problem | year=2003 | url=http://pdf.aminer.org/000/314/734/variations_of_diffie_hellman_problem.pdf }}

• Square computational Diffie–Hellman problem (SCDH): On input $g,\; g^x$, compute $g^\{x^\{2\}\}$;{{Citation | last1=Burmester | first1=Mike | last2=Desmedt | first2=Yvo | last3=Seberry | first3=Jeniffer | title=Equitable key escrow with limited time span (or, how to enforce time expiration cryptographically) | volume=1514 | pages=380–391 | year=1998 | chapter-url=https://link.springer.com/content/pdf/10.1007/3-540-49649-1_30.pdf| doi=10.1007/3-540-49649-1_30 | chapter=Equitable Key Escrow with Limited Time Span (or, How to Enforce Time Expiration Cryptographically) Extended Abstract | series=Lecture Notes in Computer Science | isbn=978-3-540-65109-3 | doi-access=free }}
• Inverse computational Diffie–Hellman problem (InvCDH): On input $g,\; g^x$, compute $g^\{x^\{-1\}\}$;{{Citation | last1=Pfitzmann | first1=Brigitte | title=Advances in Cryptology — ASIACRYPT 2000 | volume=1976 | pages=401–414 | last2=Sadeghi | first2=Ahmad-Reza | chapter=Anonymous fingerprinting with direct non-repudiation | year=2000 | chapter-url=https://link.springer.com/content/pdf/10.1007/3-540-44448-3_31.pdf| doi=10.1007/3-540-44448-3_31 | series=Lecture Notes in Computer Science | isbn=978-3-540-41404-9 | doi-access=free }}
• Divisible computation Diffie–Hellman problem (DCDH): On input $g,\; g^x,\; g^y$, compute $g^\{y/x\}$;

Let $G\_1$ and $G\_2$ be two cyclic groups.

• Co-Computational Diffie–Hellman (co-CDH) problem: Given $g,\; g^a\; \backslash in\; G\_1$ and $h\; \backslash in\; G\_2$, compute $h^a\; \backslash in\; G\_2$;{{Citation | last1=Boneh | first1=Dan | last2=Lynn | first2=Ben | last3=Shacham | first3=Hovav | title=Short Signatures from the Weil Pairing | journal=Journal of Cryptology | volume=17 | pages=297–319 | year=2004 | issue=4 | doi=10.1007/s00145-004-0314-9 | s2cid=929219 | url=https://link.springer.com/content/pdf/10.1007/s00145-004-0314-9.pdf }}

{{Reflist}}

{{Computational hardness assumptions}}

{{DEFAULTSORT:Computational Diffie-Hellman assumption}}

Category:Computational hardness assumptions