General Distributed Quantum Key Recovery Attack on Permutation-Based Block Ciphers

The impact of quantum computing on the security of block ciphers has been widely studied. However, the research on effective quantum attacks in the noisy intermediate-scale quantum era is still insufficient because quantum resources are limited, and noise interference occurs. In this paper, we propose a general distributed quantum key recovery attack on permutation-based block ciphers and design the corresponding quantum circuit based on bilinear structure, Bernstein–Vazirani's algorithm, and Grover's algorithm. Then, we apply the proposed attack to single-permutation-based and two-permutation-based block ciphers. Finally, we evaluate the complexity of the attack and make extensive comparisons with existing key recovery attacks. Compared to existing attacks, the proposed attack reduces time complexity and enhances the robustness against circuit noise. The proposed attack is more suitable for the noisy intermediate-scale quantum era. Our work helps realize effective quantum key recovery attacks on block ciphers and provides theoretical support for designing quantum secure block ciphers.