Welcome to the resource topic for 2025/1776
Title:
A collision attack on the LTZ hash function based on a conjecture on supersingular non-superspecial isogeny graphs of dimension 2
Authors: Ryo Ohashi, Hiroshi Onuki
Abstract:In 2023, LeGrow, Ti, and Zobernig proposed a cryptographic hash function (we refer to it as the LTZ hash function in this paper) based on a certain (2,2)-isogeny graph between supersingular non-superspecial abelian surfaces over \mathbb{F}_{p^4}. The authors estimated that the time and space complexities required to find a collision in the LTZ hash function are both given by \widetilde{O}(p^3).
In this paper, we first propose a mathematical conjecture on the number of vertices defined over the smaller field \mathbb{F}_{p^2} in the isogeny graphs used in the LTZ hash function. Based on this conjecture, we then construct a collision-finding algorithm for the LTZ hash function, which preserves the time complexity \widetilde{O}(p^3), while reducing the required memory to O(\log(p)^2). We implemented this algorithm in Rust, and successfully found a collision for parameters claimed to provide 35-37 bits of security, within 26.2MB of memory usage on average in 20.2 hours.
ePrint: https://eprint.iacr.org/2025/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 .