量子科技中心_量科网

关于随机可逆置换的量子算法分析一直是密码学领域长期以来的难题。现有适用于随机预言机的技术要么在此场景下失效，要么尚未被证实能推广适用，这导致涉及置换的基础密码构造往往缺乏量子安全性证明。为填补这一空白，该团队开发并验证了压缩置换预言机的可靠性。该构造继承了Zhandry原始压缩函数预言机的诸多优势：其纯化形式以简洁的输入-输出对列表呈现，能有效反映算法对预言机的认知程度。研究团队继而运用该框架，证明七轮Feistel结构具有强量子伪随机置换性质，从而解决了（Zhandry，2012）提出的悬而未决问题。此外，该工作重新验证了随机置换模型中几乎所有已知的量子查询下界，包括Sponge与Davies-Meyer结构的碰撞阻力与原像阻力、双面零搜索与稀疏谓词搜索的困难性，并为环路发现问题及“一更多”问题给出了新的下界证明。