Welcome to the resource topic for 2024/1776
Title:
An efficient collision attack on Castryck-Decru-Smith’s hash function
Authors: Ryo Ohashi, Hiroshi Onuki
Abstract: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 very “close” to the square of a supersingular elliptic curve with a known endomorphism ring.
In this paper, we introduce an algorithm for detecting 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 are smaller than the complexity \widetilde{O}(p^{3/2}) the authors claimed to be necessary to detect 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 detecting a collision in 17 hours (using 64 parallel computations) under a parameter setting which the authors had claimed to be 384-bit secure.
ePrint: https://eprint.iacr.org/2024/1776
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .