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!
|
| _version_ | 1849344512499908608 |
|---|---|
| author | Abul Kalam Sudeshna Karmakar Santanu Sarkar |
| author_facet | Abul Kalam Sudeshna Karmakar Santanu Sarkar |
| author_sort | Abul Kalam |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c5a200320af84fd3bc3051c8ddfad89f |
| institution | Kabale University |
| issn | 2045-2322 |
| language | English |
| publishDate | 2025-08-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj-art-c5a200320af84fd3bc3051c8ddfad89f2025-08-20T03:42:38ZengNature PortfolioScientific Reports2045-23222025-08-011511910.1038/s41598-025-10019-9A note on the analysis of Herrmann–May lattices for small exponent RSAAbul Kalam0Sudeshna Karmakar1Santanu Sarkar2Department of Mathematics, Indian Institute of Technology MadrasDepartment of Mathematics, Indian Institute of Technology MadrasDepartment of Mathematics, Indian Institute of Technology MadrasAbstract 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.https://doi.org/10.1038/s41598-025-10019-9Lattice basis reductionLLLLinearizationSmall exponent RSAHerrmann–May lattice |
| spellingShingle | Abul Kalam Sudeshna Karmakar Santanu Sarkar A note on the analysis of Herrmann–May lattices for small exponent RSA Scientific Reports Lattice basis reduction LLL Linearization Small exponent RSA Herrmann–May lattice |
| title | A note on the analysis of Herrmann–May lattices for small exponent RSA |
| title_full | A note on the analysis of Herrmann–May lattices for small exponent RSA |
| title_fullStr | A note on the analysis of Herrmann–May lattices for small exponent RSA |
| title_full_unstemmed | A note on the analysis of Herrmann–May lattices for small exponent RSA |
| title_short | A note on the analysis of Herrmann–May lattices for small exponent RSA |
| title_sort | note on the analysis of herrmann may lattices for small exponent rsa |
| topic | Lattice basis reduction LLL Linearization Small exponent RSA Herrmann–May lattice |
| url | https://doi.org/10.1038/s41598-025-10019-9 |
| work_keys_str_mv | AT abulkalam anoteontheanalysisofherrmannmaylatticesforsmallexponentrsa AT sudeshnakarmakar anoteontheanalysisofherrmannmaylatticesforsmallexponentrsa AT santanusarkar anoteontheanalysisofherrmannmaylatticesforsmallexponentrsa AT abulkalam noteontheanalysisofherrmannmaylatticesforsmallexponentrsa AT sudeshnakarmakar noteontheanalysisofherrmannmaylatticesforsmallexponentrsa AT santanusarkar noteontheanalysisofherrmannmaylatticesforsmallexponentrsa |