改进的五轮Grøstl-512 的量子碰撞攻击*

董炳佑, 刘 泰, 崔玉龙, 倪博煜, 秦岭月, 董晓阳

1. 清华大学高等研究院, 北京 100084

2. 中车青岛四方机车车辆股份有限公司, 青岛 266111

3. 山东大学密码技术与信息安全教育部重点实验室, 济南 250199

4. 山东大学网络空间安全学院, 青岛 266237

1 前言

在1994 年, Shor 算法[1]的提出, 说明一个足够大的量子计算机可以在多项式时间内分解大整数、计算离散对数问题等, 对目前使用的许多公钥密码方案都带来重大安全影响. 这激起了大家对抗量子计算机攻击的密码的研究兴趣, 公钥密码学社区和标准化组织在后量子公钥密码学的研究上投入了大量的精力.相比之下, 人们普遍认为, 量子计算攻击对对称密码安全性影响有限, 因为当攻击者使用量子计算机攻击对称密码时, 优势是使用Grover 算法[2]来加速密钥的搜索, 然而将密钥长度加倍就可以解决这个问题.直到2010 年, Kuwakado 和Morii 证明了经典可证明安全的Even-Mansour 结构密码和三轮Feistel 结构可以在量子计算机的帮助下在多项式时间内被破解[3,4]. 接下来的几年, 更多的对称密码设计结构被量子计算算法攻击[5–13]. 几乎所有这些指数级加速的攻击都是通过Simon 的算法[14]来找到一个依赖于密钥的隐藏周期, 在寻找这个隐藏周期时, 需要以量子明文叠加态访问加密算法, 并获得密文叠加态. 这是一个相当强的要求, 敌手需要在线访问一个用量子电路实现的加密算法. 因此, 如果不需要对密钥原语的量子叠加预言机进行在线查询, 那么使用更高复杂度的量……