李艳俊, 林 昊, 易子晗, 谢惠琴

1. 北京电子科技学院, 北京 100070

2. 密码科学技术国家重点实验室, 北京 100878

3. 桂林电子科技大学广西密码学与信息安全重点实验室, 桂林 541004

1 引言

随着量子计算机的不断发展, 密码领域将面临巨大革新. 一方面, 上世纪90 年代Shor 算法[1]的提出使得公钥密码受到量子计算的严重威胁, 这促使公钥领域寻找更多量子安全的解决方案, 后量子密码算法研究迅速崛起. 另一方面, 量子计算对对称密钥密码的影响也逐步扩大, 如Grover 算法[2]提升了二次方根的量子搜索速度, Simon 算法[3]可以构造量子区分器等.

根据Zhandry[4]给出的在量子环境中的PRF (伪随机函数, pseudorandom function) 安全性的概念, Kaplan 等人[5]提出了两种不同的模型来对对称密码进行量子密码分析:

· 标准安全性(表示为Q1 模型): 如果没有有效的量子算法能够仅通过经典查询将分组密码与PRP(伪随机置换, pseudorandom permutation) (或PRF) 区分开, 则分组密码对于量子敌手是标准安全的.

· 量子安全性(表示为Q2 模型): 如果没有有效的量子算法即使通过量子查询也无法将分组密码与PRP (或PRF) 区分开, 则分组密码对于量子敌手是量子安全的.

在Q1 模型中, 敌手使用经典方法收集数据并利用量子运算处理它们, 而在Q2 模型中, 敌手可以直接利用经典输入构造量子叠加态查询密码Oracle, 并接收相应输出的叠加态. 近年来, 许多学者在Q2 模型下评估了许多特定对称密码的安全性. 在2010 年, Kuwakado 等人基于Simon 算法[3]构造了Feistel结构的周期函数[6], 提出了对称密码算法量子分析技术, 紧接着证……