Paper 2010/146

Some Applications of Lattice Based Root Finding Techniques

Santanu Sarkar and Subhamoy Maitra

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} \bmod 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 for solving 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.

Note: Substantial extension to earlier version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
CRT-RSAGreatest Common DivisorFactorizationInteger ApproximationsLatticeLLLRSASmooth Integers.
Contact author(s)
subho @ isical ac in
History
2010-04-07: revised
2010-03-19: received
See all versions
Short URL
https://ia.cr/2010/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/146,
      author = {Santanu Sarkar and Subhamoy Maitra},
      title = {Some Applications of Lattice Based Root Finding Techniques},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/146},
      year = {2010},
      url = {https://eprint.iacr.org/2010/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.