Welcome to the resource topic for 2018/1122
Title:
Improved Quantum Multicollision-Finding Algorithm
Authors: Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa
Abstract:The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l-collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l-collision for a random function by recursively calling the algorithm for finding (l-1)-collisions, and it achieves the average quantum query complexity of O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})}), where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of O(N^{(2^{l-1}-1) / (2^{l}-1)}), which improves the previous bound for all l\ge 3 (the new and previous algorithms achieve the optimal bound for l=2). More generally, the new algorithm achieves the average quantum query complexity of O\left(c^{3/2}_N N^{\frac{2^{l-1}-1}{ 2^{l}-1}}\right) for a random function f\colon X\to Y such that |X| \geq l \cdot |Y| / c_N for any 1\le c_N \in o(N^{\frac{1}{2^l - 1}}). With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.
ePrint: https://eprint.iacr.org/2018/1122
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 .