CryptoDB
Some Applications of Lattice Based Root Finding Techniques
Authors: |
- Santanu Sarkar
- Subhamoy Maitra
|
Download: |
- URL: http://eprint.iacr.org/2010/146
- Search ePrint
- Search Google
|
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. |
BibTeX
@misc{eprint-2010-23047,
title={Some Applications of Lattice Based Root Finding Techniques},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / CRT-RSA, Greatest Common Divisor, Factorization, Integer Approximations, Lattice, LLL, RSA, Smooth Integers.},
url={http://eprint.iacr.org/2010/146},
note={ subho@isical.ac.in 14706 received 17 Mar 2010, last revised 7 Apr 2010},
author={Santanu Sarkar and Subhamoy Maitra},
year=2010
}