Lattice basis reduction algorithms have contributed a lot to cryptanalysis of RSA systems. A typical application is Boneh-Durfee's seminal work for breaking low private key RSA (and its successors in other applications). Although it's well known that this technique is not guaranteed to succeed, there is no thorough proof yet when it fails. In this paper, we summarize the Boneh-Durfee-like algorithms using generalized terminology. We also show that when the number of solutions in given bounded range is larger than $8(w/3)^7$, where $w$ is the dimension of the lattice involved in the reduction procedure, then the algorithm always fails. As a result, it is proven that MSB (Most Significant Bits)partial key exposure attacks on low public key RSA using this technique is difficult, if we have not sufficient private key exposed.
['Haijian Zhou', 'Ping Luo', 'Daoshun Wang', 'Yiqi Dai']
Remarks on Cryptanalysis of RSA Using Lattice Basis Reduction