ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (12): 2811-2818.doi: 10.7544/issn1000-1239.2021.20200427

Previous Articles    

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).

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

CLC Number: