Name
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 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 $lge 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 $Oleft(c^{3/2}_N N^{frac{2^{l-1}-1}{ 2^{l}-1}}right)$ for a random function $fcolon Xto Y$ such that $|X| geq l cdot |Y| / c_N$ for any $1le 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. |
Year | Venue | DocType |
|---|---|---|
2018 | IACR Cryptology ePrint Archive | Journal |
Volume | Citations | PageRank |
abs/1811.08097 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akinori Hosoyamada | 1 | 0 | 2.70 |
| Yu Sasaki | 2 | 247 | 15.33 |
| Seiichiro Tani | 3 | 167 | 21.85 |
| Keita Xagawa | 4 | 258 | 20.51 |