Quantum Multicollision-Finding Algorithm (original) (raw)

Paper 2017/864

Quantum Multicollision-Finding Algorithm

Akinori Hosoyamada, Yu Sasaki, and Keita Xagawa

Abstract

The current paper presents a new quantum algorithm for finding multicollisions, often denoted by lll-collisions, where an lll-collision for a function is a set of lll 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 222-collisions of random functions has been revealed to be Theta(N1/3)\Theta(N^{1/3})Theta(N1/3), where NNN is the size of a codomain. However, neither the lower nor upper bound is known for lll-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(N1/2)O(N^{1/2})O(N1/2) quantum queries for a small constant lll. Then a new quantum algorithm is proposed, which finds an lll-collision of any function that has a domain size lll times larger than the codomain size. A rigorous proof is given to guarantee that the expected number of quantum queries is Oleft(N(3l−1−1)/(2cdot3l−1)right)O\left( N^{(3^{l-1}-1)/(2 \cdot 3^{l-1})} \right)Oleft(N(3l−1−1)/(2cdot3l−1)right) for a small constant lll, which matches the tight bound of Theta(N1/3)\Theta(N^{1/3})Theta(N1/3) for l=2l=2l=2 and improves the known bounds, say, the above simple bound of O(N1/2)O(N^{1/2})O(N1/2).

BibTeX

@misc{cryptoeprint:2017/864, author = {Akinori Hosoyamada and Yu Sasaki and Keita Xagawa}, title = {Quantum Multicollision-Finding Algorithm}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/864}, year = {2017}, url = {https://eprint.iacr.org/2017/864} }