2018/11/13 by Liu, Qipeng, Zhandry, Mark · 3 citations
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1811.05385
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, Θ(N(1)/(2)(1-(1)/(2k-1))) 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 non-trivial lower bound, completely resolving the problem.