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 lattice-based 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 $k-1$ queries for RSA moduli with $\alpha$-bit $q_i$, they can improve the bound on $t$ to $t\geq\frac{k}{k-1}\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}{k-1}(\alpha-1+\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.