#collision-finding

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Frédéric Magniez, Sebastian Zur

该论文研究量子算法中「查询次数与内存(量子比特)之间的权衡」这一核心问题。经典背景下,对于均匀随机函数 f:[N]→[N],BHT 算法用 O(N^{1/3}) 次查询加上一张 O(N^{1/3}) 规模的量子可访问经典表即可找到碰撞,而仅用对数空间的 Grover 搜索需要 O(√N) 次查询。介于这两个极端之间的最优查询—空间权衡长期是公开难题。作者在「标签对称算法」这一受限但自然的类中彻底解决了该问题:所谓标签对称,是指算法把函数 f 的输出标签视为可互换。作者证明,任何做出 T 次查询、使用 S 个量子比特、以常数概率在均匀随机函数上找到碰撞的标签对称算法,必须满足 T=Ω(N^{1/3}) 且 T²S=Ω(N log N)。当 M=N 时,这两个下界被一种空间高效的 BHT 实现所达到,因此在该算法类中是最优的。作为副产物,作者导出 Element Distinctness(元素唯一性判定)搜索版本的对应权衡:对 f:[n]→[n²],任何标签对称算法必须满足 T=Ω(n^{2/3}) 且 T²S=Ω(n² log n),与 Ambainis 量子游走算法的上界吻合,同样达到最优。技术路线上,作者发展了「空间敏感的压缩预言机(compressed oracle)」技术:压缩预言机以不断演化的数据库叠加态记录算法已学到的信息;借助标签对称性与表示论,作者证明使用 S 个量子比特的算法实际上只能有效保留约 O(S/log N) 条无碰撞数据库条目的信息,将该估计代入压缩预言机论证即得到上述权衡。该结果属于量子查询复杂度与时空下界的理论研究,作者未涉及任何具体密码系统的攻击实现或实验评估。

💡 推荐理由: 碰撞查找与元素唯一性判定是哈希碰撞抗性、承诺方案等密码安全参数的理论基石。该文首次在标签对称类中给出紧密的量子查询—空间权衡下界,说明量子加速受内存严格制约,为评估「攻击者仅有小规模量子内存」场景下的真实风险提供了理论标尺。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)