International Association for Cryptologic Research

International Association
for Cryptologic Research

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
Download:
DOI: 10.1007/978-3-030-26948-7_11
Search ePrint
Search Google
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ö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.
Video from CRYPTO 2019
Video provided under Creative Commons / CC BY 3.0
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
}