Paper 2018/1096
On Finding Quantum Multicollisions
Qipeng Liu and Mark Zhandry
Abstract
A $k$collision for a compressing hash function $H$ is a set of $k$ distinct inputs that all map to the same output. In this work, we show that for any constant $k$, $\Theta\left(N^{\frac{1}{2}(1\frac{1}{2^k1})}\right)$ quantum queries are both necessary and sufficient to achieve a $k$collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first nontrivial lower bound, completely resolving the problem.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2019
 Keywords
 quantum cryptography
 Contact author(s)
 qipengl @ cs princeton edu
 History
 20190227: revised
 20181115: received
 See all versions
 Short URL
 https://ia.cr/2018/1096
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1096, author = {Qipeng Liu and Mark Zhandry}, title = {On Finding Quantum Multicollisions}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1096}, year = {2018}, url = {https://eprint.iacr.org/2018/1096} }