Welcome to the resource topic for 2017/864
Title:
Quantum Multicollision-Finding Algorithm
Authors: Akinori Hosoyamada, Yu Sasaki, 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^{l-1}-1)/(2 \cdot 3^{l-1})} \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}).
ePrint: https://eprint.iacr.org/2017/864
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 .