Scholarlink

<p>At PKC 2010, Herrmann and May introduced a lattice-based method using unravelled linearization to achieve the theoretical bound <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10019_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="78" /> </InlineMediaObject> <EquationSource Format="TEX">\(d &lt; N^{1- \frac{1}{\sqrt{2}}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>&lt;</mo> <msup> <mi>N</mi> <mrow> <mn>1</mn> <mo>-</mo> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound to <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10019_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">\(d &lt; N^{0.292256}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>&lt;</mo> <msup> <mi>N</mi> <mrow> <mn>0.292256</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, which is strictly lower than the Boneh–Durfee bound <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10019_Article_IEq3.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(N^{1- \frac{1}{\sqrt{2}}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>N</mi> <mrow> <mn>1</mn> <mo>-</mo> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> </msup> </math></EquationSource> </InlineEquation>. 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月5日

查看全文
  • Abul Kalam,
  • Sudeshna Karmakar,
  • Santanu Sarkar

摘要

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.