In 2023, LeGrow, Ti, and Zobernig proposed a cryptographic hash function (which we refer to 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 claimed that the best-known algorithm for finding a collision in the LTZ hash function is the Pollard-rho style algorithm, whose time complexity is estimated to be \(O(p^3\log (p)^2)\) and whose space complexity is \(O(\log (p))\) , when measured in the number of multiplications over \(\mathbb {F}_p\) . 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, by finding two distinct paths leading to a vertex defined over \(\mathbb {F}_{p^2}\) , we construct a collision-finding algorithm for the LTZ hash function. Our algorithm reduces the time complexity to \(O(p^3\log (p))\) , at the cost of increasing the required memory to \(O(\log (p)^2)\) , again measured in \(\mathbb {F}_p\) -multiplications. We implemented these algorithms in Rust and confirmed experimentally that our method finds collisions, on average, 82 times faster than the Pollard-rho style algorithm for primes \(p < 1000\) .

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

A Collision Attack on the LTZ Hash Function Based on a Conjecture on Supersingular Non-superspecial Isogeny Graphs of Dimension 2

  • Ryo Ohashi,
  • Hiroshi Onuki

摘要

In 2023, LeGrow, Ti, and Zobernig proposed a cryptographic hash function (which we refer to 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 claimed that the best-known algorithm for finding a collision in the LTZ hash function is the Pollard-rho style algorithm, whose time complexity is estimated to be \(O(p^3\log (p)^2)\) and whose space complexity is \(O(\log (p))\) , when measured in the number of multiplications over \(\mathbb {F}_p\) . 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, by finding two distinct paths leading to a vertex defined over \(\mathbb {F}_{p^2}\) , we construct a collision-finding algorithm for the LTZ hash function. Our algorithm reduces the time complexity to \(O(p^3\log (p))\) , at the cost of increasing the required memory to \(O(\log (p)^2)\) , again measured in \(\mathbb {F}_p\) -multiplications. We implemented these algorithms in Rust and confirmed experimentally that our method finds collisions, on average, 82 times faster than the Pollard-rho style algorithm for primes \(p < 1000\) .