<p>We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (<i>N</i>,&#xa0;<i>N</i>)-split for each integer <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(N \le 11\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo>≤</mo> <mn>11</mn> </mrow> </math></EquationSource> </InlineEquation>. Incorporating this algorithm into the best known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime <i>p</i> is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and when the underlying prime is 1000 bits, the attack is sped up by a factor of 160. Furthermore, we describe a more general algorithm to find small degree endomorphisms of superspecial genus 2 Jacobians.</p>

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

Efficient Algorithms for the Detection of (NN)-Splittings and Endomorphisms

  • Maria Corte-Real Santos,
  • Craig Costello,
  • Sam Frengley

摘要

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (NN)-split for each integer \(N \le 11\) N 11 . Incorporating this algorithm into the best known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and when the underlying prime is 1000 bits, the attack is sped up by a factor of 160. Furthermore, we describe a more general algorithm to find small degree endomorphisms of superspecial genus 2 Jacobians.