New results on modular inversion hidden number problem and inversive congruential generator

• Main Authors: Xu, Jun, Sarkar, Santanu, Hu, Lei, Wang, Huaxiong, Pan, Yanbin
• Other Authors: School of Physical and Mathematical Sciences
• Format: Conference or Workshop Item
• Language: English
• Published: 2020
• Subjects: Science::Mathematics; Modular Inversion Hidden Number Problem; Inversive Congruential Generator
• Online Access: https://hdl.handle.net/10356/138108
• Institution: Nanyang Technological University

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let MSB ( ) refer to the δ most significant bits of z. Given many samples( ,MSB (( + )−1mod ))(ti,MSBδ((α+ti)−1modp)) for random ∈ℤ , the goal is to recover the hidden number ∈ℤ . 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 α in MIHNP. For any positive integer constant d, let integer = 3+ (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 /log2 >1 +1+ (1 ). The overall time complexity of attack is polynomial in log2 , where the complexity of the LLL algorithm grows as dO(d) and the complexity of the Gröbner basis computation grows as(2d)O(n2). When >2, this asymptotic bound outperforms /log2 >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 /log2 <1/3 is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.