Cryptology ePrint Archive: Report 2014/843

Solving a Class of Modular Polynomial Equations and its Relation to Modular Inversion Hidden Number Problem and Inversive Congruential Generator

Jun Xu and Santanu Sarkar and Lei Hu and Zhangjie Huang and Liqiang Peng

Abstract: 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 a_{ij}+b_{ij}x_i+c_{ij}x_j+x_ix_j=0 (mod p) 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.

Category / Keywords: Modular inversion hidden number problem and inversive congruential generator and lattice and LLL algorithm and Coppersmith's technique

Original Publication (with major differences): Designs, Codes and Cryptography (to appear)

Date: received 16 Oct 2014, last revised 26 Oct 2017

Contact author: xujun at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20171027:050353 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]