Welcome to the resource topic for 2014/843
Title:
Solving a Class of Modular Polynomial Equations and its Relation to Modular Inversion Hidden Number Problem and Inversive Congruential Generator
Authors: Jun Xu, Santanu Sarkar, Lei Hu, Zhangjie Huang, 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.
ePrint: https://eprint.iacr.org/2014/843
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .