Rumor Debunked That China Cracked Modern Cryptography With Quantum Computer

[Man]

In October 2024, the world media began spreading frightening news that Chinese scientists had allegedly managed to crack modern military cryptographic codes using the D-Wave Advantage quantum computer (pictured above).

This news was not based on empty words, but on a scientific paper from a group of researchers led by Dr. Wang Chao from Shanghai University. The paper was published in September 2024 in the Chinese Journal of Computers. The authors used D-Wave Advantage to successfully attack three algorithms - Present, Gift-64 and Rectangle - which are critical to the Advanced Encryption Standard (AES), used to protect data in the government, military and financial sectors.

Western cryptography experts studied the paper and assessed the achievements of their Chinese colleagues.
The authors of the paper note that their success revealed for the first time a “real and significant threat” to breaking the above ciphers.

The threat could extend to AES-256, a cipher that was considered completely secure. The researchers said they had failed to break AES-256, but they were “closer than ever before.”

Quantum annealing​

The Advantage quantum computer from D-Wave Systems uses quantum annealing to compute. According to Wikipedia, it is “a fairly general method for finding the global minimum of a given function among a set of candidate solutions. It is primarily used to solve problems where the search occurs over a discrete set with many local minima.”

The method is called “annealing” by analogy with metallurgy. Just as metals are strengthened and purified by repeated heating and cooling, quantum annealing takes a system through various energy states and then gradually brings it to the lowest one, which represents the best solution to the problem.

An example of an annealing schedule for two functions, source

In a sense, a quantum computer uses the laws of physics to calculate: “It has a unique quantum tunneling effect that allows it to escape from local extremes that traditional algorithms tend to fall into,” the authors write.

D-Wave Systems’ 128-qubit superconducting adiabatic processor for quantum annealing, source

Cryptography in Security​

The Present, Gift-64, and Rectangle algorithms use the Substitution-Permutation Network (SPN) structure , which is part of the AES standard. But all three are lightweight block ciphers with limited applicability to embedded systems with limited computational capabilities.

Researchers at Shanghai University have proposed a new computational architecture for symmetric cryptanalysis: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), which combines the quantum annealing algorithm with traditional mathematical methods.

Quote from the research paper:

"Using the QuCMC architecture, we first applied the division property to describe the propagation rules of linear and nonlinear layers in symmetric cipher algorithms with SPN structure.

Then, the SPN distinguisher search problems were transformed into mixed integer linear programming (MILP) problems. These MILP models were transformed into D-Wave restricted quadratic models (CQM) that use the quantum tunneling effect induced by quantum fluctuations to escape from local minima and reach the optimal solution corresponding to the integral distinguisher for the attacked encryption algorithms. Experiments conducted using the D-Wave Advantage quantum computer allowed us to successfully implement attacks on three representative SPN algorithms: PRESENT, GIFT-64 and RECTANGLE, and successfully searched for integral distinguishers up to round 9. The experimental results show that the quantum annealing algorithm outperforms traditional heuristic global optimization algorithms such as simulated annealing in local minima avoidance and solution time. This is the first practical attack on multiple full-scale SPN symmetric cipher algorithms using a real quantum computer.

In addition, this is the first time that quantum computing attacks on multiple SPN symmetric cipher algorithms have achieved the performance of traditional mathematical methods."

Abstract of a scientific article (abstract) in English

As you can see, there is nothing revolutionary about the research. However, the results of the scientific paper made headlines and raised concerns about the vulnerabilities of modern cryptography. Experts say that the hype is overblown.

“This is an intriguing study, but it will not cause a quantum apocalypse right now,” says Avesta Hojjati, head of research and development at DigiCert. “While it demonstrates the potential threat of quantum computing to classical encryption, the attack was carried out on 22-bit keys.”

22-bit keys are a string of characters with 2 22 (4,194,304) possible combinations, which is much fewer than the 2048- and 4096-bit keys widely used today.

So the suggestion that the attack poses an immediate threat to widely used encryption standards is misleading. AES-256 is considered one of the best modern ciphers and is not currently under threat.

Source