Skip to content

Back to the catalog

eprint.iacr.orgpaper

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

Provable Recovery from Integer Quotients is an IACR ePrint paper (2026/2686) that widens the proven recovery ranges for three nonlinear hidden number problems modulo a prime p. Tolerable unrevealed lower bits rise from 1/3 to 1/2 for modular inversion, 1/6 to 1/5 for the elliptic-curve HNP, and 1/5 to 1/3 for hidden multipliers. The lattice-based algorithms return the exact candidate set in expected polynomial time in log p on random inputs.

TL;DR Raises provable leakage thresholds for three nonlinear hidden number problems using lattice methods with polynomial-time exact recovery.
Open original ↗

Techniques named here

  • Lattice methods
  • lattice reduction

Concepts named here

  • Elliptic-curve HNP
  • Hidden number problem (HNP)
  • HNP with hidden multipliers
  • Modular inversion HNP
  • Recovery from integer quotients

Also named here

  • hidden number problem

Related in other