Empowering NP-Hard Problem Solving in Symmetric Cipher Attacks Through Global Optimization Capability of 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 the Mixed Integer Linear Programming (MILP) problems in symmetric ciphers. None of Google’s three generations of quantum chips 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 design the MILP model for PUFFIN and solve 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.