{"id":"arxiv/2611.22290","url":"https://arxiv.org/abs/2611.22290","tags":["math.NT","cs.CR"],"score":0,"title":"A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm","domain":"math.NT","source":"arxiv","authors":["Yuwen Zhou"],"reviews":0,"subject":"math.NT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}