Some applications of lattice based root finding techniques

Santanu Sarkar; Subhamoy Maitra

doi:10.3934/amc.2010.4.519

Article Contents

2010, Volume 4, Issue 4: 519-531. Doi: 10.3934/amc.2010.4.519

This issue Previous Article Efficient list decoding of a class of algebraic-geometry codes Next Article Input-state-output representations and constructions of finite support 2D convolutional codes

Some applications of lattice based root finding techniques

Santanu Sarkar^1, and
Subhamoy Maitra^2,

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

Received: November 30, 2009

Revised: July 31, 2010

Published: October 2010

Abstract Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	http://www.rsa.com/rsalabs/node.asp?id=2125.
[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.