Paper 2017/864
Quantum MulticollisionFinding Algorithm
Akinori Hosoyamada, Yu Sasaki, and Keita Xagawa
Abstract
The current paper presents a new quantum algorithm for finding multicollisions, often denoted by $l$collisions, where an $l$collision for a function is a set of $l$ distinct inputs having the same output value. Although it is fundamental in cryptography, the problem of finding multicollisions has not received much attention \emph{in a quantum setting}. The tight bound of quantum query complexity for finding $2$collisions of random functions has been revealed to be $\Theta(N^{1/3})$, where $N$ is the size of a codomain. However, neither the lower nor upper bound is known for $l$collisions. The paper first integrates the results from existing research to derive several new observations, e.g.~$l$collisions can be generated only with $O(N^{1/2})$ quantum queries for a small constant $l$. Then a new quantum algorithm is proposed, which finds an $l$collision of any function that has a domain size $l$ times larger than the codomain size. A rigorous proof is given to guarantee that the expected number of quantum queries is $O\left( N^{(3^{l1}1)/(2 \cdot 3^{l1})} \right)$ for a small constant $l$, which matches the tight bound of $\Theta(N^{1/3})$ for $l=2$ and improves the known bounds, say, the above simple bound of $O(N^{1/2})$.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in ASIACRYPT 2017
 Keywords
 postquantum cryptographymulticollisionquantum algorithmGroverBHTrigorous complexity evaluationstateofart
 Contact author(s)
 hosoyamada akinori @ lab ntt co jp
 History
 20170913: received
 Short URL
 https://ia.cr/2017/864
 License

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