Revisiting modular inversion hidden number problem and its applications

Abstract

The Modular Inversion Hidden Number Problem (MIHNP), which was proposed at Asiacrypt 2001 by Boneh, Halevi, and Howgrave-Graham, is summarized as follows: Assume that the δ most significant bits of z are denoted by MSBδ(z). The goal is to retrieve the hidden number α ϵ ℤp given many samples (ti,MSBδ((α + ti)-1 mod p)) for random ti ϵ ℤp. MIHNP is a significant subset of Hidden Number Problems. Eichenauer and Lehn introduced the Inversive Congruential Generator (ICG) in 1986. It is basically characterized as follows: For iterated relations vi+1 = (avi-1 + b) mod p with a secret seed v0 ϵ ℤp, each iteration produces MSBδ(vi+1) where i ≥ 0. The ICG family of pseudorandom number generators is a significant subclass of number-theoretic pseudorandom number generators. Sakai-Kasahara scheme is an identity-based encryption (IBE) system proposed by Sakai and Kasahara. It is one of the few commercially implemented identity-based encryption schemes. We explore the Coppersmith approach for solving a class of modular polynomial equations, which is derived from the recovery issue for the hidden number α in MIHNP and the secret seed v0 in ICG, respectively. Take a positive integer n = d3+o(1) for some positive integer constant d. We propose a heuristic technique for recovering the hidden number α or secret seed v0 with a probability close to 1 when δ/log2 p > 1/d+1 +o(1/d ). The attack's total time complexity is polynomial in the order of log2 p, with the complexity of the LLL algorithm increasing as dO(d) and the complexity of the Grobner basis computation increasing as dO(n). When d > 2, this asymptotic bound surpasses the asymptotic bound δ/log2 p > 1/3 established by Boneh, Halevi, and Howgrave-Graham at Asiacrypt 2001. This is the first time a more precise constraint for solving MIHNP is established, implying that the claim that MIHNP is difficult is violated whenever δ/log2 p < 1/3 . Then we study ICG. To our knowledge, we achieve the best performance for attacking ICG to date. Finally, we provide an MIHNP-based lattice approach that recovers the signer's secret key in the Sakai-Kasahara type signatures when the most (least) significant bits of the signing exponents are exposed. This improves the existing work in this direction.