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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi> <mml:mo><</mml:mo> <mml:msup><mml:mi>N</mml:mi> <mml:mrow><mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mfrac><mml:mn>1</mml:mn> <mml:msqrt><mml:mn>2</mml:mn></mml:msqrt> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi> <mml:mo><</mml:mo> <mml:msup><mml:mi>N</mml:mi> <mml:mrow><mml:mn>0.292256</mml:mn></mml:mrow> </mml:msup> </mml:mrow> </mml:math> , which is strictly lower than the Boneh-Durfee bound <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>N</mml:mi> <mml:mrow><mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mfrac><mml:mn>1</mml:mn> <mml:msqrt><mml:mn>2</mml:mn></mml:msqrt> </mml:mfrac> </mml:mrow> </mml:msup> </mml:math> . 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.