Delphi.science

A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm

Source: arxiv.org/abs/2611.22290

Yuwen Zhou

arXivarxiv/2611.22290Nov 17, 2026math.NTscore 0

Is computing a Diffie-Hellman key as hard as computing a discrete logarithm? Maurer showed that it is, given a few bits of advice, provided that short intervals contain enough integers with only small prime factors; that proviso has stood for thirty years. We remove it. For every prime $p$ there is an advice string of $O(\log p)$ bits, depending only on $p$, with which discrete logarithms in every group of order $p$ are computed in polynomial time from a Diffie-Hellman oracle. The reduction is the classical one; what was missing was a proof that short intervals contain polylogarithmically…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.22290
curl -X POST /api/v1/records/arxiv/2611.22290/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.22290/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'