Paper 2019/604
New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
Jun Xu, Santanu Sarkar, Lei Hu, Huaxiong Wang, and Yanbin Pan
Abstract
The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and HowgraveGraham 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ö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 HowgraveGraham 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.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in CRYPTO 2019
 Keywords
 Modular inversion hidden number probleminversive congruential generatorlatticeLLL algorithmthe Coppersmith technique
 Contact author(s)

xujun @ iie ac cn
sarkar santanu bir @ gmail com
hulei @ iie ac cn
HXWang @ ntu edu sg
panyanbin @ amss ac cn  History
 20190602: received
 Short URL
 https://ia.cr/2019/604
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/604, author = {Jun Xu and Santanu Sarkar and Lei Hu and Huaxiong Wang and Yanbin Pan}, title = {New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator}, howpublished = {Cryptology ePrint Archive, Paper 2019/604}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/604}}, url = {https://eprint.iacr.org/2019/604} }