PRESENT, GIFT64 and RECTANGLE: All three are lightweight block ciphers designed for use in ‘constrained’ environments, such as those in embedded systems that require more speed and fewer computing resources than possible with AES. All three are based on an SPN structure and are proposed academic designs. The related GIFT-128 is part of GIFT-COFB, which was a finalist for the recent NIST lightweight crypto competition but lost to an algorithm known as Ascon.
PRESENT can now be found in ISO/IEC 29167-11:2014 and ISO/IEC 29192-2:2019, but is not widely used. It is not clear whether RECTANGLE is used at all. Because all three algorithms were academic designs, they have been widely analyzed.
Integral awards: Essentially, finding integral distinctions is a type of large-scale optimization problem that, when solved, provides a powerful tool for breaking encryption schemes used in block ciphers. An article from 2018 titled Easily find integral distinguishers reported the use of classical computers to find integral distinctions for dozens of algorithms. The survey included 9-round awards for PRESENT, GIFT64 and RECTANGLE, the algorithms studied in the September article.
Mixed integer linear programming: Typically abbreviated as MILP, mixed integer linear programming is a mathematical modeling technique for solving complex problems. MILP allows some variables to be non-integers, a property that gives it flexibility, efficiency and optimization over other methods.
The experts weigh in
The main contribution of the September paper is the process the researchers used to find integral distinctions in up to nine rounds of the three algorithms mentioned earlier. According to a roughly translated version of the article (the correct one, not the May one), the researchers wrote:
Inspired by traditional cryptanalysis methods, we proposed a new computational architecture for symmetric cryptanalysis: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), which combines the quantum annealing algorithm with traditional mathematical methods. Using this architecture, we initially applied the division property to describe the propagation rules of the linear and nonlinear layers in symmetric encryption algorithms with SPN structure.
Then, the SPN structure discriminator search problems were converted into Mixed Integer Linear Programming (MILP) problems. These MILP models were further converted into D-Wave Constrained Quadratic Models (CQM), utilizing the quantum tunneling effect caused by quantum fluctuations to escape local minima solutions and achieve an optimal solution corresponding to the integral discriminator for the encryption algorithms under attack. Experiments conducted with the D-Wave Advantage quantum computer successfully attacked three representative SPN structure algorithms: PRESENT, GIFT-64, and RECTANGLE, and successfully searched for integral distinctions up to 9 rounds. Experimental results show that the quantum annealing algorithm outperforms traditional heuristic-based global optimization algorithms, such as simulated annealing, in its ability to escape local minima and in solution time. This marks the first practical attack on multiple fully SPN structure-symmetric encryption algorithms using a real quantum computer.
Moreover, this is the first time that quantum computing attacks on symmetric encryption algorithms with multiple SPN structures have achieved the performance of the traditional mathematical methods.
The article makes no reference to AES or RSA and never claims to break anything. Instead, it describes a way to use D-Wave-enabled quantum annealing to find the integral discriminator. Classical attacks have had the optimized ability to find the same integral distinctions for years. David Jao, a professor specializing in PQC at the University of Waterloo in Canada, likened the research to finding a new lock-picking technique. The end result is the same, but the method is new. He explained:
