Paper 2014/843

Finding Small Solutions of a Class of Simultaneous Modular Equations and Applications to Modular Inversion Hidden Number Problem and Inversive Congruential Generator

Jun Xu, Lei Hu, Zhangjie Huang, Liqiang Peng

Abstract

In this paper we revisit the modular inversion hidden number problem and the inversive congruential pseudo random number generator and consider how to more efficiently attack them in terms of fewer samples or outputs. We reduce the attacking problem to finding small solutions of systems of modular polynomial equations of the form $a_i+b_ix_0+c_ix_i+x_0x_i=0 (\mod p)$, and present two strategies to construct lattices in Coppersmith's lattice-based root-finding technique for the solving of the equations. Different from the choosing of the polynomials used for constructing lattices in previous methods, a part of polynomials chosen in our strategies are linear combinations of some polynomials generated in advance and this enables us to achieve a larger upper bound for the desired root. Applying the solving of the above equations to analyze the modular inversion hidden number problem, we put forward an explicit result of Boneh et al. which was the best result so far, and give a further improvement in the involved lattice construction in the sense of requiring fewer samples. Our strategies also give a method of attacking the inversive congruential pseudo random number generator, and the corresponding result is the best up to now.