Improved bounds for the implicit factorization problem

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

August 2013, 7(3): 243-251. doi: 10.3934/amc.2013.7.243

Improved bounds for the implicit factorization problem

Yao Lu ^1, , Rui Zhang ^1, and Dongdai Lin ^1,

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

Received November 2011 Revised April 2013 Published July 2013

Abstract
Related Papers

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: lattice., approximate integer common divisor, Implicit factorization.

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

Citation: Yao Lu, Rui Zhang, Dongdai Lin. Improved bounds for the implicit factorization problem. Advances in Mathematics of Communications, 2013, 7 (3) : 243-251. doi: 10.3934/amc.2013.7.243

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.

show all references

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.

[1]	Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[2]	Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems and Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[3]	Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems and Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123
[4]	Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems and Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016
[5]	Raluca Felea, Venkateswaran P. Krishnan, Clifford J. Nolan, Eric Todd Quinto. Common midpoint versus common offset acquisition geometry in seismic imaging. Inverse Problems and Imaging, 2016, 10 (1) : 87-102. doi: 10.3934/ipi.2016.10.87
[6]	Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002
[7]	Laurent Imbert, Michael J. Jacobson, Jr.. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$. Advances in Mathematics of Communications, 2013, 7 (4) : 485-502. doi: 10.3934/amc.2013.7.485
[8]	Meina Gao. Small-divisor equation with large-variable coefficient and periodic solutions of DNLS equations. Discrete and Continuous Dynamical Systems, 2015, 35 (1) : 173-204. doi: 10.3934/dcds.2015.35.173
[9]	David Iglesias-Ponte, Juan Carlos Marrero, David Martín de Diego, Edith Padrón. Discrete dynamics in implicit form. Discrete and Continuous Dynamical Systems, 2013, 33 (3) : 1117-1135. doi: 10.3934/dcds.2013.33.1117
[10]	Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems and Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123
[11]	Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
[12]	Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems and Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263
[13]	Xiaodong Liu. The factorization method for scatterers with different physical properties. Discrete and Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563
[14]	Lianwen Wang. Approximate controllability and approximate null controllability of semilinear systems. Communications on Pure and Applied Analysis, 2006, 5 (4) : 953-962. doi: 10.3934/cpaa.2006.5.953
[15]	Dan Tiba. Implicit parametrizations and applications in optimization and control. Mathematical Control and Related Fields, 2020, 10 (3) : 455-470. doi: 10.3934/mcrf.2020006
[16]	Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Dušan D. Repovš. Periodic solutions for implicit evolution inclusions. Evolution Equations and Control Theory, 2019, 8 (3) : 621-631. doi: 10.3934/eect.2019029
[17]	Konstantinos Drakakis, Roderick Gow, Scott Rickard. Common distance vectors between Costas arrays. Advances in Mathematics of Communications, 2009, 3 (1) : 35-52. doi: 10.3934/amc.2009.3.35
[18]	Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial and Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[19]	Luigi Ambrosio, Gianluca Crippa, Philippe G. Lefloch. Leaf superposition property for integer rectifiable currents. Networks and Heterogeneous Media, 2008, 3 (1) : 85-95. doi: 10.3934/nhm.2008.3.85
[20]	Ryusuke Kon. Dynamics of competitive systems with a single common limiting factor. Mathematical Biosciences & Engineering, 2015, 12 (1) : 71-81. doi: 10.3934/mbe.2015.12.71

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Yao Lu Rui Zhang Dongdai Lin
on Google Scholar
Yao Lu Rui Zhang Dongdai Lin

[Back to Top]