Welcome to the resource topic for 2019/604
Title:
New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
Authors: Jun Xu, Santanu Sarkar, Lei Hu, Huaxiong Wang, 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ö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.
ePrint: https://eprint.iacr.org/2019/604
Talk: https://www.youtube.com/watch?v=dLOjk7PQHAw
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .