多重碰撞搜索的紧凑量子算法
在随机函数中搜索碰撞是一个基础性的计算问题，在对称与非对称密码分析领域具有广泛应用。虽然已知量子算法在寻找单一碰撞时已达到查询次数下限，但这一结论并不适用于寻找多重碰撞的问题——尽管后者常作为筛分类算法的子模块频繁出现。
2019年欧洲密码学会年会上，刘与Zhandry证明了在输出为m位的随机函数中寻找2^k次碰撞的查询次数下限为Ω(2^(m/3)+2^(k/3))。2023年欧洲密码学会年会上，Bonnetain等研究者提出了一种量子算法，该算法在广大参数范围内达到此下限，但未能覆盖所有允许取值区间。与多数碰撞搜索算法类似，该方案基于MNRS量子游走框架，但通过重用输出碰撞后的状态来实现游走链式连接。
本工作提出了一种新算法，解决了剩余非最优参数区间的问题，从而完整解决了该难题。该算法在查询次数上达到严格最优（至多项式因子），在量子随机存取存储器假设下时间成本也实现严格最优。其核心创新在于将链式游走扩展至每个步骤可输出多个碰撞的新机制，且“游走”过程本身仅执行单次扩散层操作。
