Computational Diffie–Hellman problem

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Let $p$ be prime and $g$ a generator of the cyclic multiplicative group $\mathbb{F}_p^{\times}$, whose order is $p-1$. Unknown exponents $a,b$ are taken modulo $p-1$. The input consists of the binary representations of $p,g,A=g^a\bmod p$ and $B=g^b\bmod p$, and the output is the residue $g^{ab}\bmod p$. The output is independent of the representatives chosen for $a,b$. A uniform efficient algorithm has running time polynomial in the binary input length, hence polynomial in $\log p$. Computing either exponent by a discrete-logarithm algorithm is sufficient to obtain the answer, but recovering either exponent is not part of the required output.

Statement recorded in the supplied source.

Given a prime modulus $p$, a group generator $g$, and the public values $g^a$ and $g^b$ modulo $p$, can the shared value $g^{ab}\bmod p$ be computed efficiently without knowing $a$ or $b$? [S2]

Scope qualification.

The open computational question uses classical computation; quantum discrete-logarithm algorithms change its status. The original Diffie--Hellman paper presents the public powers and shared product exponent and does not prove their classical hardness. The catalogue supplies neither a distribution on primes and exponents nor a particular cryptographic hardness assumption, so a universal average-case claim is not asserted here. Some parameter families admit easier algorithms. The original primary paper was inspected on 2026-10-11; the catalogue's linked later problem page was unavailable through the browsing tool, and no complete current cryptanalytic audit is claimed.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness.

Short English statement

Can the shared Diffie--Hellman value be computed quickly from the two public powers, without either party's secret exponent?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 9300002 (AMR-092-0002). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AMR Open Problem Lists, original problem source linked by catalogue record AMR-092-0002 https://unsolvedproblems.org/index_files/DiffieHellman.htm.
• S3 Whitfield Diffie and Martin E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory 22 $1976$, pp. 644--654, Section III. https://www-ee.stanford.edu/~hellman/publications/24.pdf.
• S4 Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, FOCS 1994; reason to distinguish the computational model. https://doi.org/10.1109/SFCS.1994.365700.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 9300002 and source code AMR-092-0002 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The original Diffie--Hellman paper, Section III, was consulted. It explicitly separates computing public powers from obtaining the shared exponent product; it does not supply a converse reduction from discrete-logarithm hardness. No current cryptanalytic completeness claim is inferred from this historical source. The following elementary calculations concern classical arithmetic only.

Research attempt: An algebraic shortcut obstruction and a masking reduction

Put $m=p-1$. Consider a deliberately restricted, branch-free program which starts from $g,A=g^a,B=g^b$ and uses multiplication, inversion and exponentiation by publicly fixed integers. Induction on its instructions shows that every intermediate group element is \[ g^{\alpha+\beta a+\gamma b}\qquad(\alpha,\beta,\gamma\in\mathbb Z/m\mathbb Z). \] Multiplication adds triples, inversion negates them, and fixed exponentiation multiplies them by a public scalar. For $m>1$ no such expression equals $g^{ab}$ for all $a,b$. Evaluate at $(0,0),(1,0),(0,1)$ to obtain $\alpha=\beta=\gamma=0$, but $(1,1)$ then requires $0=1\pmod m$. Thus simply combining public powers by these operations cannot implement the missing multiplication of secret exponents. Input-dependent branching, arithmetic on the field representatives, and collision searches are outside this proof; it is emphatically not a classical complexity lower bound.

One possible escape was to solve a convenient fraction of exponent pairs and randomly translate every instance into that fraction. This translation is valid: choose independent uniform $r,s\in\mathbb Z/m\mathbb Z$ and form $A'=Ag^r$, $B'=Bg^s$. If a subroutine returns the correct product for this pair, its answer is \[ C'=g^{(a+r)(b+s)}=g^{ab}A^sB^r g^{rs}. \] All factors after $g^{ab}$ are computable, so division recovers the desired answer. The pair $(a+r,b+s)$ is exactly uniform for each fixed original instance. Consequently a subroutine's average success fraction for a fixed group becomes the same success probability on each target after masking. This algebra is independent of the primality of $m$.

The reduction is conditional on such a useful subroutine; it does not create one. Furthermore an unverified wrong answer remains unverified after removing the mask. Repetition alone does not identify which output is correct. A majority argument would need a success probability greater than one half and an explicit error model; a bare positive fraction or an unrecognizable success set is not enough. Thus the attempted shortcut stops at precisely the unavailable average-case solver or correctness witness, rather than establishing CDH.

For $p=2$, $m=1$ and the group is trivial, so the affine obstruction correctly does not apply and the answer is $1$. Public exponent zero or other easy instances do not contradict a question over all primes and inputs.

Verification and adversarial audit

The masking identity was exhaustively checked for all $22^2=484$ masks for $p=23$, $g=5$, $a=6$, $b=15$. The public values are $8,19$ and every unmasked answer was $2$. The symbolic identity is the proof; this finite test does not establish an algorithm at growing input length. The four-corner argument works for composite group orders as well as prime orders.

Audit corrections.

A restricted algebraic obstruction was not promoted to CDH hardness; conditional masking was not promoted to an unconditional algorithm.

External computation.

Python 3.14.2 modular integer arithmetic: all 484 masks for the listed p=23 instance passed; no random seed or external package used.

Scope and remaining gaps

No uniform polynomial-time classical solver, average-case solver, or general lower bound was obtained. The first gap in the masking route is an actual algorithm succeeding on a quantitatively useful set with the claimed guarantee. The restricted straight-line obstruction cannot be extended to unrestricted classical computation by assertion.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://www-ee.stanford.edu/~hellman/publications/24.pdf (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved. This is a research attempt with an explicit failed route or restricted calculation, not a full solution, not a current-status certification, and not a claim that the elementary material is new. The catalogue's original source-status label is preserved independently of this attempt status.