Improved bounds for the implicit factorization problem

Yao Lu; Rui Zhang; Dongdai Lin

doi:10.3934/amc.2013.7.243

Article Contents

2013, Volume 7, Issue 3: 243-251. Doi: 10.3934/amc.2013.7.243

This issue Previous Article Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation Next Article On codes over rings invariant under affine groups

Improved bounds for the implicit factorization problem

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093

Received: October 31, 2011

Revised: March 31, 2013

Published: July 2013

Abstract Related Papers Cited by

Abstract

We study the problem of integer factoring with implicit hints. This problem is described as follows: Let $N_{1}=p_{1}q_{1},\dots,N_{k}=p_{k}q_{k}$ be $k$ different RSA moduli of same bit-size, where $q_1,\dots,q_k$ are of the same bit-size too. Given the implicit information that $p_{1},\dots,p_{k}$ share some certain portions of bit pattern, under what condition is it possible to factorize $N_{1},\dots,N_{k}$ efficiently? This problem has been studied in many references recently and many interesting results have been obtained. In this paper, we modify the previous algorithm presented by Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011). We show that our result achieves an improved generalized bounds in the cases where $p_{1},\dots,p_{k}$ share some amount of 1) most significant bits (MSBs); 2) least significant bits (LSBs); 3) MSBs and LSBs together. As far as we are aware, our result is better than all known results.

Keywords:

Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.

Citation:

Related Papers

Cited by

References

[1]	H. Cohn and N. Heninger, Approximate common divisors via lattices, preprint, arXiv:1108.2714
[2]	D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.doi: 10.1007/s001459900030.
[3]	J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, in "Public Key Cryptography-PKC 2010,'' (2010), 70-87.doi: 10.1007/978-3-642-13013-7_5.
[4]	M. Herrmann and A. May, Solving linear equations modulo divisors: On factoring given any bits in "Advances in Cryptology-ASIACRYPT 2008,'' (2008), 406-424.doi: 10.1007/978-3-540-89255-7_25.
[5]	N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Crytography and Coding,'' Springer, Berlin, (1997), 131-142.doi: 10.1007/BFb0024458.
[6]	A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen, 261 (1982), 515-534.doi: 10.1007/BF01457454.
[7]	A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003.
[8]	A. May and M. Ritzenhofen, Implicit factoring: On polynomial time factoring given only an implicit hint, in "Public Key Cryptography-PKC 2009,'' (2009), 1-14.doi: 10.1007/978-3-642-00468-1_1.
[9]	S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, IEEE Trans. Inform. Theory, 57 (2011), 4002-4013.doi: 10.1109/TIT.2011.2137270.
[10]	S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time, Adv. Math. Commun., 3 (2009), 205-217.doi: 10.3934/amc.2009.3.205.