Paper 2009/132
A New Lattice for Implicit Factoring
Yanbin Pan and Yingpu Deng
Abstract
In PKC 2009, Alexander May and Maike Ritzenhofen\cite{MR} proposed an ingenious latticebased method to factor the RSA moduli $N_1=p_1q_1$ with the help of the oracle which outputs $N_2=p_2q_2$, where $p_1$ and $p_2$ share the $t$ least significant bits and $t$ is large enough when we query it with $N_1$. They also showed that when asking $k1$ queries for RSA moduli with $\alpha$bit $q_i$, they can improve the bound on $t$ to $t\geq\frac{k}{k1}\alpha$. In this paper, we propose a new lattice for implicit factoring in polynomial time, and $t$ can be a little smaller than in \cite{MR}. Moreover, we also give a method in which the bound on $t$ can also be improved to $t\geq\frac{k}{k1}(\alpha1+\frac{1}{2}\log{\frac{k+3}{k}})$ but with just only one query. Moreover we can show that our method reduces the running time of the implicit factoring for balanced RSA moduli much efficiently and makes it practical.
Metadata
 Available format(s)
  withdrawn 
 Publication info
 Published elsewhere. The paper hasn't been published anywhere
 Keywords
 Implicit FactoringLatticeRSA moduli
 Contact author(s)
 panyanbin @ amss ac cn
 History
 20090330: withdrawn
 20090327: received
 See all versions
 Short URL
 https://ia.cr/2009/132
 License

CC BY