On Finding Quantum Multi-collisions
On Finding Quantum Multi-collisions
复制标题
DOI：
10.1007/978-3-030-17659-4_7
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Qipeng Liu;Mark Zhandry
中科院分区：
文献类型：
--
作者：
Qipeng Liu;Mark Zhandry
压缩哈希函数的 Ak 碰撞是一组 k 不同的输入，全部映射到相同的输出。在这项工作中，我们表明，对于任何常数 k，量子查询对于以常数概率实现 ak 碰撞都是必要且充分的。这既改进了最佳先验上限（Hosoyamada 等人，ASIACRYPT 2017），又提供了第一个非平凡的下界，完全解决了问题。
Ak-collision for a compressing hash functionHis a set ofkdistinct inputs that all map to the same output. In this work, we show that for any constantk,quantum queries are both necessary and sufficient to achieve ak-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.