Scholarlink

In 2020, Castryck-Decru-Smith constructed a hash function using the (2, 2)-isogeny graph of superspecial principally polarized abelian surfaces. In their construction, the initial surface was chosen from vertices quite “close” to the square of a supersingular elliptic curve with a known endomorphism ring. In this paper, we propose an algorithm for recovering a collision on their hash function. Under some heuristic assumptions, the time complexity and space complexity of our algorithm are estimated to be \(\widetilde{O}(p^{3/10})\) which is smaller than the complexity \(\widetilde{O}(p^{3/2})\) the authors had claimed necessary to recover such a collision, where p is the characteristic of the base field. In particular case where p has a special form, then both the time and space complexities of our algorithm are polynomial in \(\log {p}\) . We implemented our algorithm in Magma, and succeeded in recovering a collision in 17 h (using 64 parallel computations) under a parameter setting the authors had claimed to be 384-bit secure. Finally, we propose a simple countermeasure against our attack, which is expected to restore the complexity required to recover a collision to \(\widetilde{O}(p)\) currently.

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

An Efficient Collision Attack on Castryck-Decru-Smith’s Hash Function

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Ryo Ohashi,
  • Hiroshi Onuki

摘要

In 2020, Castryck-Decru-Smith constructed a hash function using the (2, 2)-isogeny graph of superspecial principally polarized abelian surfaces. In their construction, the initial surface was chosen from vertices quite “close” to the square of a supersingular elliptic curve with a known endomorphism ring. In this paper, we propose an algorithm for recovering a collision on their hash function. Under some heuristic assumptions, the time complexity and space complexity of our algorithm are estimated to be \(\widetilde{O}(p^{3/10})\) which is smaller than the complexity \(\widetilde{O}(p^{3/2})\) the authors had claimed necessary to recover such a collision, where p is the characteristic of the base field. In particular case where p has a special form, then both the time and space complexities of our algorithm are polynomial in \(\log {p}\) . We implemented our algorithm in Magma, and succeeded in recovering a collision in 17 h (using 64 parallel computations) under a parameter setting the authors had claimed to be 384-bit secure. Finally, we propose a simple countermeasure against our attack, which is expected to restore the complexity required to recover a collision to \(\widetilde{O}(p)\) currently.