Full-Phase Distributed Quantum Impossible Differential Cryptanalysis

The continuous development of quantum computing technology has brought potential threats to the traditional cryptographic system, which has attracted the attention of the cryptographic community. As quantum computing enters the noisy intermediate-scale quantum era, quantum computing models are constrained by quantum resources and circuit noise. It is necessary to evaluate the security of cryptographic primitives accurately, combined with the development status of quantum computing. In this paper, we propose a full-phase distributed quantum impossible differential cryptanalysis by combining the Bernstein-Vazirani algorithm, quantum phase estimation algorithm, and quantum counting algorithm with the miss-in-the-middle technique. We rigorously analyze the correctness and complexity of the proposed cryptanalysis and design the corresponding distributed quantum circuits. Compared with the classical impossible cryptanalysis, our cryptanalysis avoids the influence of the number of encryption rounds on the cryptanalysis results and has lower complexity. Compared with the existing quantum differential cryptanalysis, the proposed cryptanalysis has lower complexity, shallower circuit depth, and stronger robustness to circuit noise.