American Institute of Mathematical Sciences

Advanced
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

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, ().   Google Scholar

[2]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

H. Cohn and N. Heninger, Approximate common divisors via lattices,, preprint, ().   Google Scholar

[2]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & 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 & 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 & 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 & 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 & Imaging, 2016, 10 (1) : 87-102. doi: 10.3934/ipi.2016.10.87
[6]

David Iglesias-Ponte, Juan Carlos Marrero, David Martín de Diego, Edith Padrón. Discrete dynamics in implicit form. Discrete & Continuous Dynamical Systems, 2013, 33 (3) : 1117-1135. doi: 10.3934/dcds.2013.33.1117
[7]

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
[8]

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
[9]

Meina Gao. Small-divisor equation with large-variable coefficient and periodic solutions of DNLS equations. Discrete & Continuous Dynamical Systems, 2015, 35 (1) : 173-204. doi: 10.3934/dcds.2015.35.173
[10]

Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems & 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 & 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 & 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 & Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563
[14]

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
[15]

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
[16]

Alain Bensoussan, John Liu, Jiguang Yuan. Singular control and impulse control: A common approach. Discrete & Continuous Dynamical Systems - B, 2010, 13 (1) : 27-57. doi: 10.3934/dcdsb.2010.13.27
[17]

Sedighe Asghariniya, Hamed Zhiani Rezai, Saeid Mehrabian. Resource allocation: A common set of weights model. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 257-273. doi: 10.3934/naco.2020001
[18]

Dan Tiba. Implicit parametrizations and applications in optimization and control. Mathematical Control & Related Fields, 2020, 10 (3) : 455-470. doi: 10.3934/mcrf.2020006
[19]

Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Dušan D. Repovš. Periodic solutions for implicit evolution inclusions. Evolution Equations & Control Theory, 2019, 8 (3) : 621-631. doi: 10.3934/eect.2019029
[20]

Lianwen Wang. Approximate controllability and approximate null controllability of semilinear systems. Communications on Pure & Applied Analysis, 2006, 5 (4) : 953-962. doi: 10.3934/cpaa.2006.5.953

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (69)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy