← All problems

Computational Diffie–Hellman problem

Let pp be a prime, and let gg generate a cyclic subgroup G=⟨g⟩G=\langle g\rangle of the multiplicative group Fp×\mathbb{F}_p^{\times}. Write n=ord⁡p(g)n=\operatorname{ord}_p(g); if gg generates all of Fp×\mathbb{F}_p^{\times}, then n=p−1n=p-1. For exponents a,b∈Z/nZa,b\in\mathbb{Z}/n\mathbb{Z}, the computational Diffie–Hellman (CDH) task is to recover the following value from the public inputs, without being given aa or bb:

(ga,gb)⟼gabin G.(g^a,g^b)\longmapsto g^{ab}\quad\text{in }G.

The efficiency question is whether a single algorithm can solve every such input, for varying pp, in time polynomial in the input bit length (in particular, in log⁡p\log p). This is a computational problem, not a claim that the shared value is impossible to compute; its difficulty depends on the group representation and the computational model. The question as stated does not impose a distribution on the exponents or specify a particular family of groups. Diffie-Hellman Problem Galbraith, Mathematics of Public Key Cryptography (2012)

Background

In the Diffie–Hellman key exchange, two parties choose secret exponents and publish their powers of a common group element. Each party can compute the shared value by exponentiating the other party’s public value; CDH asks whether someone given the public values can compute that same result. The related decision Diffie–Hellman problem (DDH) asks whether a proposed third group element is the shared value, and is a different task. There is also a distinction between fixed-base CDH, where the base is fixed across instances, and variable-base CDH, where it is part of the input. The fixed-base formulation is natural for cryptographic use, while variable-base formulations are common in computational number theory. Diffie-Hellman Problem Galbraith, Mathematics of Public Key Cryptography (2012)

A significant line of work connects CDH to the discrete logarithm problem (DLP), which asks for an exponent from a group element and a base. Galbraith’s account traces a reduction from DLP to fixed-base CDH to den Boer (1988), under a smoothness condition on the relevant group order; Maurer (1994) extended the approach using elliptic-curve groups with suitably smooth order. These are conditional reductions in specified settings, not general algorithms for CDH. Later work described there includes a subexponential reduction relying on a conjectural smoothness assumption and a genus-two-curve reduction with proven subexponential complexity, but the latter is not practical to implement. Galbraith, Mathematics of Public Key Cryptography (2012)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.