You are looking at a specific version 20171027:050353 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Designs, Codes and Cryptography (to appear)
Contact author(s)
xujun @ iie ac cn
History
2017-10-27: revised
2014-10-20: received
See all versions
Short URL
https://ia.cr/2014/843
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.