Remarks on Cryptanalysis of RSA Using Lattice Basis Reduction

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)⁷, 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.