Paper 2026/2686

Provable Recovery from Integer Quotients: Improved Bounds for Nonlinear Hidden Number Problems

Abstract

The hidden number problem (HNP) asks whether a secret can be recovered from partial information about values linked to it by known algebraic relations. It underlies analyses of Diffie-Hellman bit security and key-recovery attacks exploiting partial leakage of signing randomness. For HNPs with nonlinear relations, known heuristic-free recovery guarantees require a large fraction of the leading bits to be revealed. We extend the provable recovery ranges for the modular inversion HNP (MIHNP), elliptic-curve HNP (EC-HNP), and HNP with hidden multipliers (HNPHM), all modulo a prime $p$. For any sufficiently small constant $\varepsilon > 0$, we increase the tolerable fraction of unrevealed lower bits: for MIHNP, from $1/3-\varepsilon$ to $1/2-\varepsilon$; for EC-HNP, from $1/6-\varepsilon$ to $1/5-\varepsilon$; and for HNPHM, from $1/5-\varepsilon$ to $1/3-\varepsilon$. For every valid input, our algorithms return the exact set of secret candidates consistent with the revealed information. For randomly sampled inputs, we establish an expected running time polynomial in $\log p$ and unique recovery with probability $1-o(1)$ as $p \to \infty$. Both guarantees hold for every fixed secret, with the randomness taken over the sampled inputs.