Cryptology ePrint Archive: Report 2019/604

New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator

Jun Xu and Santanu Sarkar and , Lei Hu and Huaxiong Wang and Yanbin Pan

Abstract: The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let ${\mathrm{MSB}}_{\delta}(z)$ refer to the $\delta$ most significant bits of $z$. Given many samples $\left(t_{i}, {\mathrm{MSB}}_{\delta}((\alpha+ t_{i})^{-1} \bmod{p})\right)$ for random $t_i \in \mathbb{Z}_p$, the goal is to recover the hidden number $\alpha \in \mathbb{Z}_p$. MIHNP is an important class of Hidden Number Problem.

In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number $\alpha$ in MIHNP. For any positive integer constant $d$, let integer $n=d^{3+o(1)}$. Given a sufficiently large modulus $p$, $n+1$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number $\alpha$ with a probability close to 1 when $\delta/\log_2 p>\frac{1}{d+1}+o(\frac{1}{d})$. The overall time complexity of attack is polynomial in $\log_2 p$, where the complexity of the LLL algorithm grows as $d^{\mathcal{O}(d)}$ and the complexity of the Gr\"{o}bner basis computation grows as $(2d)^{\mathcal{O}(n^2)}$. When $d> 2$, this asymptotic bound outperforms $\delta/\log_2 p>\frac{1}{3}$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever $\delta/\log_2 p<\frac{1}{3}$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.

Category / Keywords: Modular inversion hidden number problem, inversive congruential generator, lattice, LLL algorithm, the Coppersmith technique

Original Publication (in the same form): IACR-CRYPTO-2019

Date: received 30 May 2019

Contact author: xujun at iie ac cn, sarkar santanu bir@gmail com, hulei@iie ac cn, HXWang@ntu edu sg, panyanbin@amss ac cn

Available format(s): PDF | BibTeX Citation

Version: 20190602:113240 (All versions of this report)

Short URL: ia.cr/2019/604


[ Cryptology ePrint archive ]