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.

Scope of Application¶

This is the computational shared-power task in a stated cyclic group, not a proof of security for a protocol.

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¶

The output is g^(ab). Recovering a is discrete logarithm; deciding whether a proposed third value equals g^(ab) is decisional DH. The same equation in a tiny group is easy and does not justify a security claim.

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¶

Specify group and generator, identify the public powers, and define the shared-power output while hiding both exponents. Then distinguish mathematical solvability from group-specific computational hardness and from full protocol security.

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.

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