Diffie–Hellman problem¶

Compute the shared exponentiation result from two public powers in a specified cyclic group.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8964
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Cryptography, Computational Complexity → Computer Science & Software Engineering

Core Idea¶

The computational Diffie–Hellman problem is an algebraic reconstruction task. In a specified cyclic group with generator g, a solver sees two public powers, g^a and g^b, and must compute g^(ab) without being given either exponent. The defining target is a group element, not the exponents themselves.

Diffie and Hellman's key-distribution scheme motivates the problem: each party knows one private exponent and can raise the other's public power to obtain the same result. For an observer with only the public pair, difficulty is an assumption about a chosen group and computational resources, not a theorem supplied by the notation. The decisional variant and discrete logarithm problem are adjacent but ask different questions.

How would you explain it like I'm…

The Secret Paint Puzzle

Two friends each pick a secret, mix it with a shared starting color, and show everyone their mixed colors. Each friend can then add their own secret to the other's mix and get the very same final color. The Diffie-Hellman problem asks: if you only see the two shown mixes, can you make that final color yourself? People hope it's too hard, but that's a hope, not something anyone has proven.

The Eavesdropper's Puzzle

The Diffie-Hellman problem is a puzzle behind a famous way for two people to agree on a secret code over a public channel. Everyone knows a starting number and a way of combining numbers. Each person picks a private number, uses it to make a public result, and shares that result. Each can then use their own private number on the other's public result, and both end up with the same shared secret. The puzzle is: if you only see the two public results, can you figure out that shared secret? The goal is the shared secret itself, not the private numbers, and whether the puzzle is hard depends on which number system is used.

Computing the Shared Secret

The computational Diffie-Hellman (CDH) problem works in a specific cyclic group with a generator g. You are given g^a and g^b and must compute g^(ab), without being told a or b. The target is the group element g^(ab), not the secret exponents. The problem comes from Diffie and Hellman's key exchange, where each party knows one exponent and raises the other's public value to it, so both arrive at g^(ab). Whether CDH is hard depends on the group chosen and on how much computing power an attacker has; it is an assumption, not a theorem. It is related to, but different from, the discrete logarithm problem, which asks for the exponent itself, and the decisional variant, which asks whether a given element equals g^(ab).

The computational Diffie-Hellman problem is defined relative to a specified cyclic group G with generator g: given g^a and g^b for unknown exponents a and b, compute g^(ab). The goal is reconstruction of a group element, not recovery of either exponent. It is motivated by Diffie-Hellman key distribution, in which each party holds one private exponent and raises the other's public power to it, so both obtain g^(ab) while an eavesdropper sees only the public pair. The hardness of CDH is an assumption about particular groups and computational resource bounds; the notation alone guarantees nothing, and in poorly chosen groups the problem may be easy. The discrete logarithm problem, recovering a from g^a, is adjacent: solving it would solve CDH, but CDH asks a different question. The decisional Diffie-Hellman problem instead asks to distinguish g^(ab) from a random group element given g^a and g^b.

Structural Signature¶

Sig role-phrases:

Specified cyclic group and generator — Fix the algebraic setting for exponentiation and the problem instance. It is constitutive. Counterfactual: Without group parameters the inputs and difficulty claim are undefined.
Two private exponents — Provide the hidden values whose product controls the target element. It is constitutive. Counterfactual: Without independent exponents there is no DH shared-power relation to reconstruct.
Public power pair — Provides g^a and g^b as the data available to a solver. It is constitutive. Counterfactual: If the solver is given an exponent, the task changes from the standard public-input problem.
Shared-power target — Specifies g^(ab) as the element to compute rather than merely identify from a candidate. It is constitutive. Counterfactual: Replace computation with a yes/no test and the problem becomes decisional DH.
Difficulty assumption — States that efficient recovery is not known for the chosen group and resource bound. It is central. Counterfactual: Without a stated group and computational model a bare word 'hard' is not a meaningful security claim.

What It Is Not¶

Not discrete logarithm itself. The target is the shared power, not an exponent.
Not decisional Diffie–Hellman. That variant tests a supplied candidate instead of computing the target.
Not the complete key-exchange protocol. Authentication, parameter choice, and implementation conditions are additional.
Not automatically hard. Small or unsuitable groups can make the problem easy.
Closest near-miss. The group operation and exponent algebra specify the mathematical task, while practical cryptographic security needs additional assumptions beyond the problem statement.

Scope of Application¶

Cryptographic assumptions. State exactly which group-specific computational difficulty a scheme relies on.
Key-agreement analysis. Separate public exchange from the third party's shared-power recovery task.
Complexity comparison. Compare CDH with discrete logarithm and decisional DH without asserting universal equivalence.
Educational algebra. Use a tiny group to verify the relation while labeling it insecure as a hardness example.

Clarity¶

Three questions must stay separate: compute g^(ab) from two public powers (computational DH), recover a from g^a (discrete log), or decide whether an offered third value equals g^(ab) (decisional DH). A toy group shows the identity but says nothing about modern security strength.

Manages Complexity¶

The formal problem isolates one algebraic challenge from a much larger key-agreement system. That isolation makes reductions and assumptions comparable, but it can hide group selection, protocol authentication, and implementation effects. The abstraction is useful precisely when those extra commitments are named as separate layers.

Abstract Reasoning¶

Fix the cyclic group, its generator, and how elements are represented.
Identify the two public powers and withhold the exponents from the solver.
Specify the output as the shared group element g^(ab).
Distinguish a computation request from a proposed-value decision test.
State hardness only relative to the selected group and computational model.
Keep protocol security claims separate from this single mathematical assumption.

Knowledge Transfer¶

The computational relation transfers literally across finite-group settings that preserve the exponent laws, although hardness must be reconsidered for each group. A generic 'shared secret from public inputs' analogy is too broad to inherit the exact DH problem. The portable skeleton is algebraic composition of hidden exponents; the domain-bound identity is the group-power computation with cryptographic difficulty interpretation.

Examples¶

Canonical¶

In Diffie and Hellman's 1976 key-distribution construction, one participant publishes g^a and the other g^b in the selected finite group. Each can raise the other public value to their own exponent to obtain g^(ab). A third party observing only the two public values faces the computational DH target. This is the motivating mathematical relation, not a claim that every implementation using it is secure.

Mapped back: Specified cyclic group and generator → the scheme's agreed group and public base g; Two private exponents → a and b retained by the two participants; Public power pair → the exchanged g^a and g^b; Shared-power target → their common g^(ab); Difficulty assumption → outside observer must solve the group-specific computational task.

Applied / In Practice¶

TLS 1.3's standards-track specification includes finite-field ephemeral Diffie–Hellman groups such as ffdhe2048. For a negotiated finite-field group, client and server transmit public key-share values of the form Y = g^X mod p and each computes the common Diffie–Hellman value for the handshake key schedule. A passive observer sees the two shares but not the private exponents; computing the common group value from only those shares is the corresponding computational Diffie–Hellman task. This is a real protocol application of the relation, not a claim that CDH alone establishes TLS security, that every TLS connection negotiates finite-field DH, or that one public exchange is an observed attack.

Mapped back: Specified cyclic group and generator → a TLS 1.3 named finite-field group such as ffdhe2048; Two private exponents → client and server ephemeral secret values; Public power pair → their exchanged key_share public values; Shared-power target → common DH value entering the TLS key schedule; Difficulty assumption → the passive observer's group-specific computational challenge, distinct from TLS's full authenticated security claim.

Structural Tensions¶

T1 — Mathematical Task versus Security Assumption. The equation defines a problem in any suitable group, but hardness is a separate, group-specific computational claim. The same notation in a tiny or weak group proves no security.

Diagnostic: Has this exact group and resource model been justified?

T2 — Compute Target versus Decide Candidate. Computing g^(ab) and recognizing it among candidates can have different complexity behavior in some group settings. Replacing one with the other silently changes the problem.

Diagnostic: Does the solver output the shared value or answer a predicate about a proposed value?

T3 — Recover Exponent versus Recover Shared Power. Solving discrete log is one path to the target, yet defining DH as discrete log itself erases an important distinction. Equivalence claims need group-specific proof.

Diagnostic: Is the output a or g^(ab)?

Structural–Framed Character¶

The computational Diffie–Hellman problem is structural-leaning within cryptography: its input–target relation is exact algebra, while its security significance depends on a chosen group and computational model. Evaluative weight: a hard instance is useful for some protocols, but hardness is not part of the equation g^(ab) itself and cannot be inferred from the word “problem.” Human-practice-bound: exponentiation laws hold once the group is specified; choosing parameters, threat models, and algorithms is a human design activity. Institutional origin: cryptographic literature defines the task and its variants, but no authority makes a particular group hard by convention. Vocabulary travels: shared output from hidden inputs is a broad idea; the generator powers g^a, g^b, and target g^(ab) are the literal DH relation. Import versus recognize: another cyclic group with those powers instantiates the computational task, whereas a generic shared-secret exchange is only analogy.

The portable skeleton is composition of hidden contributions from public transformations, a future-prime candidate rather than a current strict parent. Prime Inversion would ask for recovery of a hidden exponent, which this target does not require. Cyclic-group exponentiation and per-group hardness analysis remain the domain accent. Its character: an exact formal search task whose cryptographic relevance is conditional, not universal.

Structural Core vs. Domain Accent¶

Skeletal core. Two public transformations of hidden values determine a joint target. Domain-bound accent. Here transformations are powers of one generator in a cyclic group and the target is g^(ab), with computational difficulty considered for cryptography. Replace group exponentiation with an arbitrary shared-output task and the skeleton remains but the Diffie–Hellman problem does not. Why not a prime. Hidden-input composition is broad; this exact algebraic target is not.

Current DAG placement. Computing g^(ab) is not a kind of prime Inversion: solving CDH need not return either hidden exponent. Nor is the problem itself a general inference pattern. No strict genus for this exact formal challenge was verified, so the frozen node remains unparented.
Adjacent tasks. Discrete logarithm recovers an exponent, decisional DH tests a proposed target, and key exchange is a protocol that uses the algebraic relation.

Neighborhood in Abstraction Space¶

Diffie–Hellman problem sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Cryptographic & Combinatorial Hardness Problems (5 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Discrete logarithm problem. Tell: Recover a from g^a; it can solve CDH but is not the same output task.
Decisional Diffie–Hellman. Tell: Decide whether a candidate is the shared element rather than produce it.
Diffie–Hellman key exchange. Tell: A protocol using this relation, with additional operational requirements.
One-way function. Tell: A broader construct; group exponentiation and the joint-power target are specific here.

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem (revision 1307759835).
Primary research source: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 1976, https://cr.yp.to/bib/1976/diffie.pdf (public-power exchange and shared exponentiation).
Protocol application: E. Rescorla, RFC 8446, The Transport Layer Security (TLS) Protocol Version 1.3, §§4.2.8, 4.2.8.1, and 7.4.1, https://www.rfc-editor.org/rfc/rfc8446.html (finite-field named groups, g^X mod p key shares, and DH-derived handshake secret).
Preserved source candidate: http://eprint.iacr.org/2004/306
Preserved source candidate: https://www.di.ens.fr/~bresson/papers/BreChePoi02b.pdf
Preserved source candidate: https://archive.org/details/3rdacmconference00asso/page/31
Preserved source candidate: https://archive.org/details/3rdacmconference00asso

The Wikipedia revision supplies discovery provenance; the original paper supports the canonical shared-power relation. RFC 8446 documents a distinct standards-track finite-field application, without making the abstract CDH problem a complete TLS security proof.