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 computational resources than is possible using AES. All three are based on an SPN structure and are proposed academic designs. The related GIFT-128 is a component of GIFT-COFB, which was a finalist for the recent NIST lightweight crypto competition but lost out to an algorithm known as Ascon.
PRESENT, meanwhile, can be found in the ISO/IEC 29167-11:2014 and ISO/IEC 29192-2:2019, but it isn’t used widely. It’s not clear if RECTANGLE is used at all. Because all three algorithms were academic designs, they have been widely analyzed.
Integral distinguishers: In essence, finding integral distinguishers is a type of large-scale optimization problem that, when solved, provides a powerful tool for breaking encryption schemes used in block ciphers. A 2018 paper titled Finding Integral Distinguishers with Ease reported using classical computing to find integral distinguishers for dozens of algorithms. The research included 9-round distinguishers for PRESENT, GIFT64, and RECTANGLE, the algorithms studied in the September paper.
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 in the September paper is the process the researchers used to find integral distinguishers in up to nine rounds of the three previously mentioned algorithms. According to a roughly translated version of the paper (the correct one, not the one from May), the researchers wrote:
Inspired by traditional cryptanalysis methods, we proposed a novel computational architecture for symmetric cryptanalysis: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), which combines the quantum annealing algorithm with traditional mathematical methods. Utilizing this architecture, we initially applied the division property to describe the propagation rules of the linear and nonlinear layers in SPN structure symmetric cipher algorithms.
Subsequently, the SPN structure distinguisher search problems were transformed into Mixed Integer Linear Programming (MILP) problems. These MILP models were further converted into D-Wave Constrained Quadratic Models (CQM), leveraging the quantum tunneling effect induced by quantum fluctuations to escape local minima solutions and achieve an optimal solution corresponding to the integral distinguisher for the cipher algorithms being attacked. Experiments conducted using the D-Wave Advantage quantum computer have successfully executed attacks on three representative SPN structure algorithms: PRESENT, GIFT-64, and RECTANGLE, and successfully searched integral distinguishers up to 9-round. Experimental results demonstrate that the quantum annealing algorithm surpasses 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 full-scale SPN structure symmetric cipher algorithms using a real quantum computer.
Additionally, this is the first instance where quantum computing attacks on multiple SPN structure symmetric cipher algorithms have achieved the performance of the traditional mathematical methods.
The paper 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 distinguisher. Classical attacks have had the optimized capability to find the same integral distinguishers 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:
