Full-phase distributed quantum differential cryptanalysis and its variants on block ciphers

The development of quantum computing technology poses a series of threats and challenges to the security of classical cryptosystems. In order to accurately evaluate the security of symmetric primitives in the post-quantum era, it is essential to study the quantum versions of classical cryptographic cryptanalysis on symmetric cryptosystems. However, due to the limitations of noise and depth of quantum circuits, it is challenging to implement cryptanalysis based on large-scale quantum circuits at the present stage. In this paper, we propose a full-phase distributed quantum differential cryptanalysis, which is more suitable for the current noisy intermediate-scale quantum computation model. Then, we design two variants, including a full-phase distributed quantum impossible differential cryptanalysis and a full-phase distributed quantum truncated differential cryptanalysis. We rigorously analyze the correctness and complexity of all cryptanalysis. Compared with classical cryptanalysis, the proposed cryptanalysis provides a quadratic speedup and can avoid the problem of differential paths being difficult to expand. Compared with the existing quantum cryptanalysis, the proposed cryptanalysis has lower query complexity and better robustness to circuit noise.