--- id: "2026-11-18-diffie-hellman-discrete-log-advice-maurer-zhou-claude" url: "https://postcutoff.com/e/2026-11-18-diffie-hellman-discrete-log-advice-maurer-zhou-claude/" as_of: "2026-11-19T22:11:00+01:00" date: "2026-11-18" date_precision: day category: science importance: 3 confidence: medium status: [Awaiting review] verification: Lean-verified sources: 1 editor: human editor human_review: null version: "2026-11-18" --- As of: 2026-11-19 22:11 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-11-18-diffie-hellman-discrete-log-advice-maurer-zhou-claude/ # Diffie–Hellman ≡ discrete log with short advice (Claude, OpenAI's quasi-RH) Full title: Diffie–Hellman is as hard as discrete logarithm with O(log p) bits of advice: Yuwen Zhou removes Maurer's 30-year smoothness proviso, building on OpenAI's 7/8 zero-free half-plane; proof developed with Claude Fable 5.2 and Opus 5.5 arXiv 2611.22290 (math.NT, submitted 17 Nov 2026), Yuwen Zhou (UBC Okanagan), "A Little Advice Suffices: Diffie–Hellman Is as Hard as Discrete Logarithm": for every prime p there is an advice string of at most 30⌈log₂ p⌉ + 12 bits, depending only on p, with which discrete logarithms in any group of order p are computed in expected polynomial time from a Diffie–Hellman oracle. The missing input, smooth integers in short intervals, is derived from a zero-free half-plane for ζ, citing OpenAI's Re s > 7/8 result. The same input makes results of Maurer–Raub, Koblitz–Menezes–Shparlinski and Wolf unconditional. Developed with Claude Fable 5.2 and Opus 5.5. ## Key facts - Claim (verbatim): 'For every prime p there is an advice string σp of at most 30⌈log2 p⌉ + 12 bits such that for every cyclic group G of order p, every generator g and every a, the algorithm A given p, σp, g^a and a Diffie–Hellman oracle for (G, g) outputs a in expected time O((log p)^c)' - Background (abstract): Maurer's reduction needed short intervals to contain polylog-smooth integers, 'that proviso has stood for thirty years'; without it the best reduction ran in exp((log p)^{2/3+o(1)}); Koblitz, Menezes and Shparlinski called a polynomial-time reduction a 'holy grail' that 'seems a long way off' - Key input: '(log x)^K-smooth integers in every interval [x, x + x^θ] with θ > 17/30' from a zero-free half-plane; the paper cites [Ope26]: 'ζ(s) ≠ 0 for Re s > 7/8', i.e. OpenAI's quasi-Riemann claim (Lean-formalized, not refereed), and Cureton–Thorner for Dedekind zeta functions; genus-2 Jacobians widen the window of group orders - Corollaries claimed: Maurer–Raub's impossibility of field-homomorphic one-way permutations and the Koblitz–Menezes–Shparlinski yes/no-query reduction without the smoothness assumption; Wolf's characterisation of generic DL/DH equivalence made unconditional - AI statement (verbatim): 'The proof presented in this paper was developed through an interactive dialogue with Claude Fable 5.2 and Claude Opus 5.5 (Anthropic). The author used them to explore multiple possible proof strategies and directions, and the AI generated the initial draft under the author's guidance. The author then critically examined the generated proof, verified each step for correctness and rigor, and revised it where necessary.' - Scope: the reduction is non-uniform (advice depends on p) and does not weaken Diffie–Hellman in practice; status unrefereed, single author ## What happened A discrete-logarithm solver breaks Diffie–Hellman at once; whether the converse holds has been asked since 1976. Den Boer and Maurer showed how a Diffie–Hellman oracle can compute discrete logarithms, provided an auxiliary group with a smooth order exists, which needs smooth numbers in short intervals, still unproved unconditionally. Yuwen Zhou's paper derives the needed count from a zero-free half-plane for the Riemann zeta function, citing OpenAI's claimed Re s > 7/8 theorem from its October release, and uses genus-2 Jacobians to widen the range of group orders. With a short advice string per prime, the reduction runs in polynomial time. The author credits Claude Fable 5.2 and Opus 5.5 with exploring strategies and drafting the proof, which he then checked and revised. ## Why it matters It is an early downstream result in cryptography built on one of the AI-generated number-theory claims, so its standing depends on that claim as well as its own unrefereed argument. It concerns the theory of the reduction, not the security of deployed systems. ## What is disputed or not yet verified - Verification: Unrefereed preprint; rests on OpenAI's Lean-formalized but unrefereed 7/8 zero-free region ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 171 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 141 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 232 days after its cutoff - Grok 4.7 (training cutoff May 2026): 171 days after its cutoff ## Sources 1. [arXiv 2611.22290: A Little Advice Suffices: Diffie–Hellman Is as Hard as Discrete Logarithm](https://arxiv.org/abs/2611.22290) (arxiv.org, paper) ## Changes - 2026-11-18 (filed): Created (science agent; arXiv PDF read) ## Related - 2026-11-18: [AI-assisted results, 18 Nov](https://postcutoff.com/e/2026-11-18-ai-assisted-results-november-18-listing/index.md) - 2026-10-12: [Cureton and Thorner, with AxiomProver, extend the quasi-Riemann zero-free half-plane to every Dedekind zeta function (Re s > 31/32, Lean-formalized)](https://postcutoff.com/e/2026-10-12-cureton-thorner-dedekind-zeta-zero-free-axiomprover/index.md) - 2026-10-06: [OpenAI model claims the quasi-Riemann hypothesis](https://postcutoff.com/e/2026-10-06-quasi-riemann-hypothesis-openai/index.md)