跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.22290 · v1

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

首次提交 2026-11-17 14:45
版本更新 2026-11-17 14:45
雷达观测 2026-11-18 19:43
arXiv ↗PDF ↗

摘要

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 pp there is an advice string of O(log⁡p)O(\log p) bits, depending only on pp, with which discrete logarithms in every group of order pp 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 smooth integers. We show that a zero-free half-plane for the Riemann zeta function, which is now known, gives the expected number of (log⁡x)K(\log x)^K-smooth integers in every interval [x,x+xθ][x,x+x^θ] with θ>17/30θ>17/30. With smoothness this small the saddle point of the counting integral lies just to the left of the line Re s=1\mathrm{Re}\,s=1, and a zero-free strip of any fixed width absorbs the shift once KK is large. Genus-2 Jacobians, whose orders fill such intervals, then turn one of these integers into the order of an auxiliary group. The same input removes the smoothness assumption from Maurer and Raub's impossibility of field-homomorphic one-way permutations and from the yes/no-query reduction of Koblitz, Menezes and Shparlinski. It also makes Wolf's characterisation unconditional: discrete logarithm and Diffie-Hellman are generically equivalent exactly when the group order has no large repeated prime factor.

作者备注:15 pages. Developed with Claude Fable 5.2 and Claude Opus 5.5 (Anthropic); see "Use of AI". Companion paper on the hyperelliptic curve method: https://github.com/OctopusTide/hyperelliptic-curve-method

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 14:45 · 最新观测版本

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

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 pp there is an advice string of O(log⁡p)O(\log p) bits, depending only on pp, with which discrete logarithms in every group of order pp 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 smooth integers. We show that a zero-free half-plane for the Riemann zeta function, which is now known, gives the expected number of (log⁡x)K(\log x)^K-smooth integers in every interval [x,x+xθ][x,x+x^θ] with θ>17/30θ>17/30. With smoothness this small the saddle point of the counting integral lies just to the left of the line Re s=1\mathrm{Re}\,s=1, and a zero-free strip of any fixed width absorbs the shift once KK is large. Genus-2 Jacobians, whose orders fill such intervals, then turn one of these integers into the order of an auxiliary group. The same input removes the smoothness assumption from Maurer and Raub's impossibility of field-homomorphic one-way permutations and from the yes/no-query reduction of Koblitz, Menezes and Shparlinski. It also makes Wolf's characterisation unconditional: discrete logarithm and Diffie-Hellman are generically equivalent exactly when the group order has no large repeated prime factor.

查看此版本解读 →查看此版本原文 ↗