1（中国科学院软件研究所可信计算与信息保障实验室 北京 100190）；2（中国科学院大学 北京 100049）；3（洛阳师范学院 河南洛阳 471934）；4（福州大学数学与计算机科学学院 福州 350108) (zzya1013@tca.iscas.ac.cn)
出版日期: 2021-12-01基金资助:国家自然科学基金项目(61672509，62072445，61902073)Quantum Differential Collision Key Recovery Attack of Multi-Round EM Structure
Zhang Zhongya1,2,3, Wu Wenling1,2, Zou Jian41（Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing 100190);2(University of Chinese Academy of Sciences, Beijing 100049);3(Luoyang Normal University, Luoyang, Henan 471934);4(College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108)
Online: 2021-12-01Supported by:This work was supported by the National Natural Science Foundation of China (61672509, 62072445, 61902073).摘要/Abstract
摘要： 量子算法的发展和应用对密码算法的设计和分析产生了深远的影响，其中Grover量子算法和Simon量子算法在密码安全性评估中应用较多，但作为生日碰撞攻击量子化的BHT(Brassard，Hyer，Tapp)量子算法，还没有得到具体应用，研究BHT量子算法对密码算法的分析具有重要意义.通过对多轮EM(Even，Mansour)结构进行分析，研究了经典条件和量子条件下的碰撞搜索算法与差分密钥恢复攻击的结合，对多轮EM结构进行了差分碰撞密钥恢复攻击，并从BHT量子算法的角度进行量子化.结果表明，经典条件下，当差分传递概率2-p≥2-n/2时，r轮EM结构的差分密钥恢复攻击时间复杂度从O(2p+n)降到O(2p+n/2)，速度快了2n/2倍.量子条件下，当差分传递概率2-p>2-n/3时，结合BHT量子算法的差分碰撞密钥恢复攻击时间复杂度要优于基于Grover量子算法的差分密钥恢复攻击，显示了BHT量子算法在具体密码分析中的有效性.
参考文献
相关文章 11
| [1] | 何键浩, 李绿周. 量子优化算法综述[J]. 计算机研究与发展, 2021, 58(9): 1823-1834. |
| [2] | 张宇鹍, 袁骁. 量子错误缓解研究进展[J]. 计算机研究与发展, 2021, 58(9): 1843-1855. |
| [3] | 窦星磊, 刘磊, 陈岳涛. 面向超导量子计算机的程序映射技术研究[J]. 计算机研究与发展, 2021, 58(9): 1856-1874. |
| [4] | 付祥, 郑宇真, 苏醒, 于锦涛, 徐炜遐, 吴俊杰. 一种面向含噪中尺度量子技术的量子-经典异构计算系统[J]. 计算机研究与发展, 2021, 58(9): 1875-1896. |
| [5] | 王永利, 徐秋亮. 量子计算与量子密码的原理及研究进展综述[J]. 计算机研究与发展, 2020, 57(10): 2015-2026. |
| [6] | 王宝楠,胡风,张焕国,王潮. 从演化密码到量子人工智能密码综述[J]. 计算机研究与发展, 2019, 56(10): 2112-2134. |
| [7] | 崔竞一,郭建胜,刘翼鹏. Crypton算法的不可能差分分析[J]. 计算机研究与发展, 2017, 54(7): 1525-1536. |
| [8] | 李盼池,周红岩. 基于受控Hadamard门的量子神经网络模型及算法[J]. 计算机研究与发展, 2015, 52(1): 211-220. |
| [9] | 席政军 李永明. 基于测量的量子线路[J]. , 2011, 48(11): 2155-2160. |
| [10] | 杜卫林 李 斌 田 宇. 量子退火算法研究进展[J]. 计算机研究与发展, 2008, 45(9): 1501-1508. |
| [11] | 李志强, 陈汉武, 徐宝文, 刘文杰,. 基于Hash表的量子可逆逻辑电路综合的快速算法[J]. , 2008, 45(12): 2162-2171. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4553
