A note on the analysis of Herrmann-May lattices for small exponent RSA

At PKC 2010, Herrmann and May introduced a lattice-based method using unravelled linearization to achieve the theoretical bound $d<N^{1-\frac{1}{\sqrt{2}}}$ for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound to $d<N^{0.292256}$ , which is strictly lower than the Boneh-Durfee bound $N^{1-\frac{1}{\sqrt{2}}}$ . This error persisted for over 15 years. We also refine the Herrmann-May lattice construction, achieving the Boneh-Durfee bound while significantly reducing the Herrmann-May lattice's dimension.