一种新的碰撞搜索量子广播算法

摘要：在随机函数中寻找碰撞是一个基础的计算问题，其在对称和非对称密码分析中有着众多应用。对于寻找多个碰撞的问题而言，方法未尽完善。本文给出一种新的算法，在量子广播查询次数上至多使用一个多项式因子，将链式随机扩展为一种新的模式，每一步都会发生多次碰撞，随机仅执行一个扩散层。解决了剩余的非最优范围问题。

关键词：量子算法、量子广播、多碰撞搜索、量子密码。

1.背景

图1 量子多重碰撞搜索算法的参数范围和复杂度指数

本文利用了MNRS 量子随机的链式版本[6]的思路。链式量子随机的原理是将一次随机的最终状态作为新一次随机的起始状态加以重复利用。实际上，一次随机的状态是  的子集的叠加态。在一次随机结束时，期望这些子集总是会包含一个碰撞：可以提取并测量这个碰撞，使顶点坍缩为包含这些子集的叠加态，该状态仍然接近均匀分布，并且足以继续进行。

2.预备知识

2.1量子搜索

2.2 量子广播

2.3碰撞次数

3.新算法

4.结论

本文提出了在量子广播查询以及时间复杂度中将链式随机扩展为一种新模式的算法，证明了多重碰撞搜索问题的量子复杂度为 ，在某些k和m的限定范围内填补了剩余的差距问题。在新的算法目标机制中，使用量子随机作为在当前状态进行扩散的工具，而非搜索工具，使算法能够修正该状态下的预期碰撞次数，能够在后续步骤中持续提取碰撞信息。

参考文献