Santanu Sarkar

In Crypto 1996, the Hidden Number Problem was introduced by Boneh and Venkatesan. Howgrave-Graham, Nguyen and Shparlinski (Mathematics of Computation 2003) generalized this problem and called it Hidden Number Problem with Hidden Multiplier (HNPHM). It has application in security analysis of timed-release crypto. They proposed a polynomial time algorithm to solve HNPHM. They showed that one can solve it if absolute error is less than m0.20 for some positive integer m. They improved this bound up to m0.25 heuristically. It was also proved that one can not solve HNPHM if error is larger than m0.5. In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by m0.5.

In Crypto 2010, Kiltz, O’Neill and Smith used m -prime RSA modulus N with m ≥ 3 for constructing lossy RSA. The security of the proposal is based on the Multi-Prime Φ -Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lat- tice method (Asiacrypt 2008) to solve the Multi-Prime Φ -Hiding Problem when prime e > N2/3M. Further, by combining with mixed lattice tech- niques, we give an improved heuristic algorithm to solve this problem when prime e > N2/3M-1/4m2. These two results are verified by our experiments. Our bounds are better than the existing works.

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.

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.

In this paper we revisit the modular inversion hidden number problem (MIHNP) and the inversive congruential generator (ICG) and consider how to attack them more efficiently. We consider systems of modular polynomial equations of the form aij+bijxi+cijxj+xixj=0(modp) and show the relation between solving such equations and attacking MIHNP and ICG. We present three heuristic strategies using Coppersmith’s lattice-based root-finding technique for solving the above modular equations. In the first strategy, we use the polynomial number of samples and get the same asymptotic bound on attacking ICG proposed in PKC 2012, which is the best result so far. However, exponential number of samples is required in the work of PKC 2012. In the second strategy, a part of polynomials chosen for the involved lattice are linear combinations of some polynomials and this enables us to achieve a larger upper bound for the desired root. Corresponding to the analysis of MIHNP we give an explicit lattice construction of the second attack method proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. We provide better bound than that in the work of PKC 2012 for attacking ICG. Moreover, we propose the third strategy in order to give a further improvement in the involved lattice construction in the sense of requiring fewer samples.