Cryptology ePrint Archive: Report 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.

Category / Keywords: Implicit Factoring, Lattice, RSA moduli

Publication Info: The paper hasn't been published anywhere

Date: received 21 Mar 2009, withdrawn 30 Mar 2009

Contact author: panyanbin at amss ac cn

Available formats: (-- withdrawn --)

Version: 20090330:170455 (All versions of this report)

Discussion forum: Show discussion | Start new discussion