AI & ML
A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm
arXiv cs.CR0 views
arXiv:2611.22290v1 Announce Type: cross Abstract: 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 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$-smooth integers in every interval $[x,x+x^\theta]$ with $\theta>17/30$. With smoothness this small the saddle point of the counting integral lies just to the left of the line $\mathrm{Re}\,s=1$, and a zero-free strip of any fixed width absorbs the shift once $K$ 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.
Source:https://arxiv.org/abs/2611.22290PreviousConfGuard: a physics-grounded reference monitor for predictive-maintenance large-language-model agentsNextFast and Strong Image Protection against Diffusion Personalization
Related posts

Debugging Claude Fable 5.2 Code Art: Truncated SVG, Broken Canvas, Working Render
0dev.to
Hydra · Coeziune OM–IA — the complete DOI registry (2026-11-18): 76 published works
0dev.to OpenSource
Your Rust Code Sets an Environment Variable and the 2024 Edition Calls That Unsafe
0dev.to Rust
Your Go Function Returned a Nil Error and the Caller Saw an Error Anyway
0dev.to Go
Kengele: an alarm for when an activist goes missing, that nobody can switch off
0dev.to Go
How OpenAI scales PostgreSQL to 800 million users
0dev.to Database