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

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.