Paper 2018/1122
Improved Quantum MulticollisionFinding Algorithm
Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, and Keita Xagawa
Abstract
The current paper improves the number of queries of the previous quantum multicollision 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 $(l1)$collisions, and it achieves the average quantum query complexity of $O(N^{(3^{l1}1) / (2 \cdot 3^{l1})})$, 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^{l1}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^{l1}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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. PQCrypto 2019
 Keywords
 postquantum cryptographyquantum algorithmmulticlawmulticollision
 Contact author(s)
 hosoyamada akinori @ lab ntt co jp
 History
 20190128: last of 6 revisions
 20181120: received
 See all versions
 Short URL
 https://ia.cr/2018/1122
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1122, author = {Akinori Hosoyamada and Yu Sasaki and Seiichiro Tani and Keita Xagawa}, title = {Improved Quantum MulticollisionFinding Algorithm}, howpublished = {Cryptology ePrint Archive, Paper 2018/1122}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/1122}}, url = {https://eprint.iacr.org/2018/1122} }