A note on the analysis of Herrmann–May lattices for small exponent RSA
Abstract 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}}}$$ d < N 1 - 1 2 for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-08-01
|
| Series: | Scientific Reports |
| Subjects: | |
| Online Access: | https://doi.org/10.1038/s41598-025-10019-9 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Abstract 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}}}$$ d < N 1 - 1 2 for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound to $$d < N^{0.292256}$$ d < N 0.292256 , which is strictly lower than the Boneh–Durfee bound $$N^{1- \frac{1}{\sqrt{2}}}$$ N 1 - 1 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. |
|---|---|
| ISSN: | 2045-2322 |