    November  2010, 4(4): 519-531. doi: 10.3934/amc.2010.4.519

## Some applications of lattice based root finding techniques

 1 Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India 2 Indian Statistical Institute, 203 B T Road,, Kolkata 700 108

Received  December 2009 Revised  August 2010 Published  November 2010

In this paper we present some problems and their solutions exploiting lattice based root finding techniques.
In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q$-1 mod $p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA.
In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique to solve the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.
Citation: Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519
##### References:
  , , \url{http://www.rsa.com/rsalabs/node.asp?id=2125}., ().   Google Scholar  D. Boneh, Finding smooth integers in short intervals using CRT decoding,, in, (2000), 265. Google Scholar  D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits,, in, (1998), 25.   Google Scholar  D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities,, Journal of Cryptology, 10 (1997), 223.  doi: 10.1007/s001459900030.  Google Scholar  J.-S. Coron, Finding small roots of bivariate integer equations revisited,, in, (2004), 492.  doi: 10.1007/978-3-540-24676-3_29. Google Scholar  J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring,, Journal of Cryptology, 20 (2007), 39.  doi: 10.1007/s00145-006-0433-6.  Google Scholar  J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70.  doi: 10.1007/978-3-642-13013-7_5. Google Scholar  N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits,, in, (2009), 1.   Google Scholar  N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131. Google Scholar  N. Howgrave-Graham, Approximate integer common divisors,, in, (2001), 51. Google Scholar  E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants,, in, (2006), 267. Google Scholar  A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'', Springer-Verlag, (1993).  doi: 10.1007/BFb0091534.  Google Scholar  A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients,, Mathematische Annalen, 261 (1982), 513.  doi: 10.1007/BF01457454.  Google Scholar  A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring,, in, (2004), 213.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar  A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint,, in, (2009), 1. Google Scholar  C. Pomerance, The quadratic sieve factoring algorithm,, in, (1985), 169. Google Scholar  J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem,, Electronic Letters, 18 (1982), 905.  doi: 10.1049/el:19820617. Google Scholar  R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems,, Communications of ACM, 21 (1978), 120.  doi: 10.1145/359340.359342.  Google Scholar  S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time,, Advances in Mathematics of Communications, 3 (2009), 205.  doi: 10.3934/amc.2009.3.205.  Google Scholar  S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization,, available online at \url{http://eprint.iacr.org/2009/626}., ().   Google Scholar  M. Wiener, Cryptanalysis of short RSA secret exponents,, IEEE Transactions on Information Theory, 36 (1990), 553.  doi: 10.1109/18.54902.  Google Scholar

show all references

##### References:
  , , \url{http://www.rsa.com/rsalabs/node.asp?id=2125}., ().   Google Scholar  D. Boneh, Finding smooth integers in short intervals using CRT decoding,, in, (2000), 265. Google Scholar  D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits,, in, (1998), 25.   Google Scholar  D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities,, Journal of Cryptology, 10 (1997), 223.  doi: 10.1007/s001459900030.  Google Scholar  J.-S. Coron, Finding small roots of bivariate integer equations revisited,, in, (2004), 492.  doi: 10.1007/978-3-540-24676-3_29. Google Scholar  J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring,, Journal of Cryptology, 20 (2007), 39.  doi: 10.1007/s00145-006-0433-6.  Google Scholar  J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70.  doi: 10.1007/978-3-642-13013-7_5. Google Scholar  N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits,, in, (2009), 1.   Google Scholar  N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131. Google Scholar  N. Howgrave-Graham, Approximate integer common divisors,, in, (2001), 51. Google Scholar  E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants,, in, (2006), 267. Google Scholar  A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'', Springer-Verlag, (1993).  doi: 10.1007/BFb0091534.  Google Scholar  A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients,, Mathematische Annalen, 261 (1982), 513.  doi: 10.1007/BF01457454.  Google Scholar  A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring,, in, (2004), 213.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar  A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint,, in, (2009), 1. Google Scholar  C. Pomerance, The quadratic sieve factoring algorithm,, in, (1985), 169. Google Scholar  J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem,, Electronic Letters, 18 (1982), 905.  doi: 10.1049/el:19820617. Google Scholar  R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems,, Communications of ACM, 21 (1978), 120.  doi: 10.1145/359340.359342.  Google Scholar  S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time,, Advances in Mathematics of Communications, 3 (2009), 205.  doi: 10.3934/amc.2009.3.205.  Google Scholar  S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization,, available online at \url{http://eprint.iacr.org/2009/626}., ().   Google Scholar  M. Wiener, Cryptanalysis of short RSA secret exponents,, IEEE Transactions on Information Theory, 36 (1990), 553.  doi: 10.1109/18.54902.  Google Scholar
  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  Michele Barbi, Angelo Di Garbo, Rita Balocchi. Improved integrate-and-fire model for RSA. Mathematical Biosciences & Engineering, 2007, 4 (4) : 609-615. doi: 10.3934/mbe.2007.4.609  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  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  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  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  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  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  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  Andreas Kirsch, Albert Ruiz. The Factorization Method for an inverse fluid-solid interaction scattering problem. Inverse Problems & Imaging, 2012, 6 (4) : 681-695. doi: 10.3934/ipi.2012.6.681  Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601  Dinh-Liem Nguyen. The factorization method for the Drude-Born-Fedorov model for periodic chiral structures. Inverse Problems & Imaging, 2016, 10 (2) : 519-547. doi: 10.3934/ipi.2016010  Bastian Gebauer, Nuutti Hyvönen. Factorization method and inclusions of mixed type in an inverse elliptic boundary value problem. Inverse Problems & Imaging, 2008, 2 (3) : 355-372. doi: 10.3934/ipi.2008.2.355  Anahita Eslami Rad, Enrique G. Reyes. The Kadomtsev-Petviashvili hierarchy and the Mulase factorization of formal Lie groups. Journal of Geometric Mechanics, 2013, 5 (3) : 345-364. doi: 10.3934/jgm.2013.5.345  Lorenzo Audibert. The Generalized Linear Sampling and factorization methods only depends on the sign of contrast on the boundary. Inverse Problems & Imaging, 2017, 11 (6) : 1107-1119. doi: 10.3934/ipi.2017051  Sangye Lungten, Wil H. A. Schilders, Joseph M. L. Maubach. Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 227-239. doi: 10.3934/naco.2014.4.227  Nuutti Hyvönen, Harri Hakula, Sampsa Pursiainen. Numerical implementation of the factorization method within the complete electrode model of electrical impedance tomography. Inverse Problems & Imaging, 2007, 1 (2) : 299-317. doi: 10.3934/ipi.2007.1.299  Guanghui Hu, Andreas Kirsch, Tao Yin. Factorization method in inverse interaction problems with bi-periodic interfaces between acoustic and elastic waves. Inverse Problems & Imaging, 2016, 10 (1) : 103-129. doi: 10.3934/ipi.2016.10.103  Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019123  Houssem Haddar, Alexander Konschin. Factorization method for imaging a local perturbation in inhomogeneous periodic layers from far field measurements. Inverse Problems & Imaging, 2020, 14 (1) : 133-152. doi: 10.3934/ipi.2019067

2018 Impact Factor: 0.879