ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (12): 2811-2818.doi: 10.7544/issn1000-1239.2021.20200427

• 信息安全 • 上一篇    



  1. 1(中国科学院软件研究所可信计算与信息保障实验室 北京 100190);2(中国科学院大学 北京 100049);3(洛阳师范学院 河南洛阳 471934);4(福州大学数学与计算机科学学院 福州 350108) (
  • 出版日期: 2021-12-01
  • 基金资助: 

Quantum Differential Collision Key Recovery Attack of Multi-Round EM Structure

Zhang Zhongya1,2,3, Wu Wenling1,2, Zou Jian4   

  1. 1(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-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61672509, 62072445, 61902073).

摘要: 量子算法的发展和应用对密码算法的设计和分析产生了深远的影响,其中Grover量子算法和Simon量子算法在密码安全性评估中应用较多,但作为生日碰撞攻击量子化的BHT(Brassard,Hyer,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量子算法在具体密码分析中的有效性.

关键词: 量子计算, Grover量子算法, BHT量子算法, 差分分析, EM结构

Abstract: The development and application of quantum algorithms have exerted a profound influence on the design and analysis of cryptographic algorithms. Currently, the Grover search algorithm and Simon quantum period finding algorithm are the most widely used algorithms in the quantization of cryptographic analysis. However, as the quantization of birthday collision attack, BHT (Brassard, Hyer, Tapp) quantum collision search algorithm has not been applied in cryptanalysis. It is of great significance to study the BHT algorithm for the analysis and application of cryptographic algorithms. By analyzing the multi-round EM (Even, Mansour) structure, the combination of collision search algorithm and differential key recovery attack is studied under classical and quantum conditions, what is more the multi-round EM structure is attacked with differential collision key recovery, and the attack is quantified from the perspective of BHT algorithm. The results demonstrate that the time complexity of the differential key recovery attack on r-round EM structure decreases from O(2p+n) to O(2p+n/2) and the speed is 2n/2 times faster when the differential probability is 2-p≥2-n/2 as under classical conditions. In the quantum conditions, when the differential probability is 2-p>2-n/3, the time complexity of differential collision key recovery attack based on BHT collision search is better than that based on Grover search, which shows the effectiveness of BHT algorithm on specific cryptanalysis.

Key words: quantum computing, Grover quantum algorithm, BHT quantum algorithm, differential cryptanalysis, EM structure