Empowering NP-Hard Problem Solving in Symmetric Cipher Attacks through the Global Optimization Capability of the Quantum Tunneling Effect

The quantum annealing algorithm leverages the global optimization capability of its unique quantum tunneling effect, making it well-suited for solving NP-hard combinatorial optimization problems. This research investigates its potential in symmetric cipher attacks, exemplified by mixed integer linear programming (MILP) problems in symmetric ciphers. None of Google’s three generations of quantum chips, including Willow, can be used for cryptographic attacks. Due to the complexity of symmetric ciphers, attacks on real quantum computers have mostly focused on simplified versions, while key NP-hard problems in full-scale versions remain untouched. Amid slow progress in quantum computing for cryptographic attacks, this study proposes a novel hybrid quantum-classical attack (HyQCA) algorithm. In HyQCA, the propagation rules of integral properties in symmetric ciphers are encoded as MILP problems, leveraging the global optimization capability of quantum tunneling to escape local minima. Using the PUFFIN algorithm to validate HyQCA’s feasibility, we designed the MILP model for PUFFIN and solved it on a real D-Wave quantum computer, successfully obtaining a 9-round integral distinguisher. It is surprising that, for the attack on the full-scale version of PUFFIN, the results achieved are comparable to traditional mathematical methods in terms of the same number rounds. This paper preliminarily validates the practical feasibility of quantum annealing in symmetric cipher attacks.