# American Institute of Mathematical Sciences

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:
 [1] [2] D. Boneh, Finding smooth integers in short intervals using CRT decoding, in "Proceedings of STOC 2000,'' (2000), 265-272. [3] D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, in "Asiacrypt 1998,'' Springer, (1998), 25-34; available online at http://crypto.stanford.edu/ dabo/abstracts/bits_of_d.html. [4] D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities, Journal of Cryptology, 10 (1997), 223-260. doi: 10.1007/s001459900030. [5] J.-S. Coron, Finding small roots of bivariate integer equations revisited, in "Eurocrypt 2004,'' Springer, (2004), 492-505. doi: 10.1007/978-3-540-24676-3_29. [6] J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring, Journal of Cryptology, 20 (2007), 39-50. doi: 10.1007/s00145-006-0433-6. [7] J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, in "PKC 2010,'' Springer, (2010), 70-87. doi: 10.1007/978-3-642-13013-7_5. [8] N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits, in "Proceedings of Crypto 2009,'' Springer, (2009), 1-17; available online at http://www.iacr.org/conferences/crypto2009/slides/p001-rsa-keys.pdf. [9] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Proceedings of Cryptography and Coding,'' Springer, (1997), 131-142. [10] N. Howgrave-Graham, Approximate integer common divisors, in "Proceedings of CALC 2001,'' Springer, (2001), 51-66. [11] E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in "Asiacrypt 2006,'' Springer, (2006), 267-282. [12] A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'' Springer-Verlag, 1993. doi: 10.1007/BFb0091534. [13] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 513-534. doi: 10.1007/BF01457454. [14] A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, in "Crypto 2004,'' Springer, (2004), 213-219. doi: 10.1007/978-3-540-28628-8_13. [15] A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint, in "PKC 2009,'' Springer, (2009), 1-14. [16] C. Pomerance, The quadratic sieve factoring algorithm, in "Proceedings of Eurocrypt 1984,'' Springer, (1985), 169-182. [17] J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem, Electronic Letters, 18 (1982), 905-907. doi: 10.1049/el:19820617. [18] R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342. [19] S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time, Advances in Mathematics of Communications, 3 (2009), 205-217. doi: 10.3934/amc.2009.3.205. [20] S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, available online at http://eprint.iacr.org/2009/626. [21] M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, 36 (1990), 553-558. doi: 10.1109/18.54902.

show all references

##### References:
 [1] [2] D. Boneh, Finding smooth integers in short intervals using CRT decoding, in "Proceedings of STOC 2000,'' (2000), 265-272. [3] D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, in "Asiacrypt 1998,'' Springer, (1998), 25-34; available online at http://crypto.stanford.edu/ dabo/abstracts/bits_of_d.html. [4] D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities, Journal of Cryptology, 10 (1997), 223-260. doi: 10.1007/s001459900030. [5] J.-S. Coron, Finding small roots of bivariate integer equations revisited, in "Eurocrypt 2004,'' Springer, (2004), 492-505. doi: 10.1007/978-3-540-24676-3_29. [6] J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring, Journal of Cryptology, 20 (2007), 39-50. doi: 10.1007/s00145-006-0433-6. [7] J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, in "PKC 2010,'' Springer, (2010), 70-87. doi: 10.1007/978-3-642-13013-7_5. [8] N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits, in "Proceedings of Crypto 2009,'' Springer, (2009), 1-17; available online at http://www.iacr.org/conferences/crypto2009/slides/p001-rsa-keys.pdf. [9] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Proceedings of Cryptography and Coding,'' Springer, (1997), 131-142. [10] N. Howgrave-Graham, Approximate integer common divisors, in "Proceedings of CALC 2001,'' Springer, (2001), 51-66. [11] E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in "Asiacrypt 2006,'' Springer, (2006), 267-282. [12] A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'' Springer-Verlag, 1993. doi: 10.1007/BFb0091534. [13] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 513-534. doi: 10.1007/BF01457454. [14] A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, in "Crypto 2004,'' Springer, (2004), 213-219. doi: 10.1007/978-3-540-28628-8_13. [15] A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint, in "PKC 2009,'' Springer, (2009), 1-14. [16] C. Pomerance, The quadratic sieve factoring algorithm, in "Proceedings of Eurocrypt 1984,'' Springer, (1985), 169-182. [17] J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem, Electronic Letters, 18 (1982), 905-907. doi: 10.1049/el:19820617. [18] R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342. [19] S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time, Advances in Mathematics of Communications, 3 (2009), 205-217. doi: 10.3934/amc.2009.3.205. [20] S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, available online at http://eprint.iacr.org/2009/626. [21] M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, 36 (1990), 553-558. doi: 10.1109/18.54902.
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $\mathit{{Bx-Ay = z}}$ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076 [11] Andreas Kirsch, Albert Ruiz. The Factorization Method for an inverse fluid-solid interaction scattering problem. Inverse Problems and Imaging, 2012, 6 (4) : 681-695. doi: 10.3934/ipi.2012.6.681 [12] Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems and Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 [13] Dinh-Liem Nguyen. The factorization method for the Drude-Born-Fedorov model for periodic chiral structures. Inverse Problems and Imaging, 2016, 10 (2) : 519-547. doi: 10.3934/ipi.2016010 [14] Bastian Gebauer, Nuutti Hyvönen. Factorization method and inclusions of mixed type in an inverse elliptic boundary value problem. Inverse Problems and Imaging, 2008, 2 (3) : 355-372. doi: 10.3934/ipi.2008.2.355 [15] 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 [16] Lorenzo Audibert. The Generalized Linear Sampling and factorization methods only depends on the sign of contrast on the boundary. Inverse Problems and Imaging, 2017, 11 (6) : 1107-1119. doi: 10.3934/ipi.2017051 [17] 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 and Optimization, 2014, 4 (3) : 227-239. doi: 10.3934/naco.2014.4.227 [18] Julio Guerrero, Giuseppe Orlando. Stochastic local volatility models and the Wei-Norman factorization method. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022026 [19] Yixuan Wu, Yanzhi Zhang. Highly accurate operator factorization methods for the integral fractional Laplacian and its generalization. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 851-876. doi: 10.3934/dcdss.2022016 [20] Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial and Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123

2021 Impact Factor: 1.015