## CryptoDB

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

Authors: Jun Xu Santanu Sarkar Lei Hu Huaxiong Wang Yanbin Pan DOI: 10.1007/978-3-030-26948-7_11 (login may be required) Search ePrint Search Google 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ö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.
##### BibTeX
@article{crypto-2019-29864,
title={New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11692},
pages={297-321},
doi={10.1007/978-3-030-26948-7_11},
author={Jun Xu and Santanu Sarkar and Lei Hu and Huaxiong Wang and Yanbin Pan},
year=2019
}