The Red Dragon Searches for Pearls Through Quantum Tunneling – But You’ve Got the Wrong Paper
A September paper, soon hushed up, shows Chinese researchers may have discovered a class of quantum-annealing algorithm capable of attacking cryptography in a novel way
Recent media coverage has intensified discussions about quantum computing’s potential threat to modern cryptography, following a South China Morning Post (SCMP) report on a breakthrough by Chinese researchers using quantum-based techniques to compromise symmetric encryption algorithms. The SCMP article highlighted research published in the Chinese Journal of Computers (CJC) (计算机学报) on September 30; however the article did not specify the date of the Journal publication. The reported research detailed the use of the D-Wave Advantage quantum processor to attack the lightweight encryption ciphers of PRESENT, GIFT-64, and RECTANGLE.
Most news outlets mistakenly cited the same authors’ earlier paper, published in May 2024, that used D-Wave to run annealing algorithms targeting the RSA (Rivest-Shamir-Adleman) encryption system. Confusing the new research with that earlier paper, the media reports dismissed the recent SCMP claims as exaggerated and characterized the RSA decryption research as “incremental progress” rather than a new type of attack. This confusion is most likely because the May paper is still available to download from the CJC website as of this publication, whereas the September paper has disappeared. (The screenshots below, depicting portions of both the May paper and the September paper side-by-side, show they are different)
The Natto team has obtained the original September paper, titled “Research on Quantum Computing for Practical SPN Structure Symmetric Ciphers Attacks Using the D-Wave Advantage.” Looking into the research, we question: who are the Chinese researchers? Are the Chinese researchers’ findings really a breakthrough? What questions do we have for their research? Why did the September paper disappear from the website of Chinese Journal of Computers?
Looking for an answer to these questions, we also consulted with quantum security researchers aiming to clarify the Chinese researchers' findings, offering an assessment of the advances in quantum annealing algorithms and their implications for classical cryptography.
Who are the Chinese Researchers?
Both the September paper and the May paper have the same five authors. However, the listed author orders are different in the two papers. The lead author of the May paper is Wang Chao (王潮). Wang is a professor at the Shanghai University School of Communication & Information Engineering. From at least 2018 or earlier, Wang has been leading a group of researchers focusing on the research of breaking RSA encryption using a public key cipher for D-Wave quantum computers. His research was supported by the National Natural Science Foundation of China (NSFC)’s Key Projects and the Grant of the Special Zone Project of National Defense Innovation. Wang has published peer-reviewed research since 2019 on applying quantum annealing techniques to cryptography. In January 2019, Wang’s team published research in Science China: Physics, Mechanics & Astronomy, titled “Factoring larger integers with fewer qubits via quantum annealing with optimized parameters.” By comparison with the January 2019 paper, the May 2024 paper shows the team has progressed from factoring a 20-bit integer to factoring a 22-bit integer. This demonstrates modest but consistent improvements. These results align with current technological constraints, lending credibility to Wang’s research progress.
The lead author of the September paper is Pei Zhi (裴植). Pei is a PhD candidate at the Key Laboratory of Specialty Fiber Optics and Optical Access Networks of Shanghai University. It is most likely that Pei is one of the researchers in Professor Wang’s group. Wang is listed as the “communication author” of the September paper, hence it was Wang who communicated with the SCMP and declined an interview request “due to the sensitivity of the topic.”
What are the Chinese Researchers’ Findings in their September Paper?
In the September paper, Chinese researchers allegedly employed D-Wave quantum annealing technology to compromise Substitution-Permutation Network (SPN) ciphers, such as PRESENT, GIFT-64, and RECTANGLE, whereas the May paper focused on compromising RSA. The September paper demonstrates an entirely new algorithm and attack technique. The paper claims:
“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-rounds. 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.” (Emphasis added)
The research suggests that this attack method could be extended to the Advanced Encryption Standard (AES), which also relies on an SPN architecture. The researchers claim quantum annealing significantly outperformed classically simulated annealing in both speed and result quality; simulated annealing averages over 600 seconds with suboptimal results, while the quantum annealing algorithm consistently solves the problem in 2.048 seconds, yielding higher-quality results. (See chart below from the September paper)
While this demonstrates the advantage of quantum systems to exploit quantum tunneling effects, a quantum security researcher whom the Natto Team consulted, assesses that comparing quantum annealing to simulated annealing is not an ideal benchmark for attacking cryptography, as simulated annealing is unlikely to be the most efficient cryptanalysis technique for classical computers in this context.
Examining the September paper, our quantum security researcher also noted that it is possible that the Chinese researchers, with leading author Pei, have discovered a new class of quantum annealing algorithm capable of attacking cryptography in a new way other than the two well-known quantum attack algorithms: Shor’s Period Finding Function and Grover’s Quantum Search.
Shor’s algorithm, described in 1995, represented a profound leap in cryptographic attack techniques due to its utilization of the Quantum Fourier Transform (QFT), a powerful tool in quantum computing that allows for the efficient resolution of integer factorization and discrete logarithm problems. This capability directly undermined the security foundations of public-key cryptosystems, including RSA and elliptic curve cryptography (ECC). The implications of Shor’s algorithm were so severe that NIST (National Institute of Standards and Technology) officially began its Post-Quantum Cryptography (PQC) project in 2016 in response to the potential threat posed by Shor’s algorithm. The initiative was launched to develop cryptographic standards that would resist quantum computer attacks, particularly those that were vulnerable to Shor's algorithm, like RSA and ECC.
Grover’s algorithm, described in 1996, another quantum threat, operates within the class of amplitude amplification algorithms. It offers a quadratic speedup over classical brute-force search methods, making it a potent tool for attacking symmetric key cryptosystems, such as AES. While Grover’s advantage is not as drastic as Shor’s—halving the key length's effective security—its impact on cryptographic standards is nonetheless significant, causing many experts to recommend that organizations upgrade from AES-128 to AES-256 to maintain post-quantum resistance.
Pei’s algorithms introduce a new layer of concern. Pei’s approach exploits quantum tunneling effects to transition from local suboptimal solutions to globally optimal ones more efficiently than classical heuristic search algorithms. This capability, if verified, presents a direct challenge to some cryptographic systems relying on certain computational complexity approaches for security. By effectively leveraging quantum tunneling, Pei’s algorithms claim to surpass classical methods in solving complex optimization tasks, which may have future implications for cryptanalysis and Artificial Intelligence (AI). Furthermore, the paper claims, "the quantum annealing algorithm can be combined with Grover's algorithm to carry out key recovery attacks, and the quantum efficiency can be realized on a larger scale."
It is worth noting that this is not the first time this year (2024) that Chinese researchers have published claims of new quantum algorithms threatening NIST-approved cryptography believed to be quantum-resistant. One such paper, which targeted lattice problems found in CRYSTAL-KYBER published in April 2024, was later found to have a bug in its code.
Pei proposes a novel computational architecture for symmetric cryptanalysis, named QuCMC (Quantum Annealing-Classical Mixed Cryptanalysis), that transforms the attack of symmetric cipher algorithms into a difficult mathematical problem for the quantum computer to solve. (See chart below)
We provide one of Pei’s algorithms from the September paper below. (See table below) However, we were unable to validate the claims that these are a new class of quantum annealing algorithms that are bug-free and show an advantage over classical integral distinguisher search algorithms. Researchers interested in testing and validating these quantum algorithms can rent access to the D-Wave Advantage for a fee.
What are the Implications of the Chinese Researchers’ Findings?
The Chinese authors of the September paper targeted lightweight symmetric encryption algorithms, which are typical in IoT (Internet of Things) and RFID (Radio Frequency Identification) devices. The researchers focused on 9 rounds of encryption and a single 64-character block for their quantum system to perform an integral distinguisher attack. Given these limitations, our quantum security researcher assesses that the capability described in the September paper is insufficient to break "military-grade encryption" like AES-512. However, the study suggests that, with access to more advanced D-Wave systems in the future, this attack method could theoretically be extended to stronger encryption protocols, such as AES, which also rely on an SPN architecture.
If China has indeed developed a novel quantum algorithm capable in theory of compromising symmetric cryptographic systems, this could prompt an immediate response from NIST. Such a breakthrough would likely lead to a call for new candidate algorithms to potentially replace AES, alongside an exploration of techniques to fortify AES against quantum-enhanced attacks. This development signals a critical trend: accelerating quantum advances increasingly threaten classical cryptography. This also highlights the strategic need to diversify cryptographic research, prioritizing both classical post-quantum cryptography, and quantum-based cryptography to secure sensitive communications for the future.
We foresee growing interest in quantum systems optimized for annealing operations, capable of solving complex optimization problems and searching exponential solution spaces. While universal quantum and classical computers can theoretically simulate annealing, D-Wave Systems with over 5,000 flux qubits, such as the D-Wave Advantage, are uniquely specialized for this task, as demonstrated in the recent paper. This quantum annealing advantage breakthrough may have more impact in AI applications than cryptography; researchers beyond China, such as Extropic.ai, may have already recognized its potential. Although recent export bans on quantum computers exceeding 34 qubits exempted D-Wave's annealing technology, future regulations could target quantum annealing systems to limit their accessibility.
Questions for the Research Presented in the September Paper
Our quantum security researcher presents the following questions which we think the broader community may want to explore further:
1. If GIFT-64/PRESENT/RECTANGLE ciphers could be successfully compromised with a new class of quantum annealing algorithms, and the attack technique could be extended to cipher algorithms like AES and Lai-Massey...Then what other types of symmetric cipher schemes (e.g., One-Time-Pad) do/could we speculate as having the best chance at resisting the alleged attack?
2. Considering that NIST believes AES to be Quantum resistant, and there are currently no Post-Quantum Cryptography (PQC) plans to replace AES...If these attack claims are validated, then what kind of response options would NIST likely approve? (e.g., Triple encrypted AES (3AES), or releasing AES512, other options)
3. There are some views that – if there was a discovery of a quantum annealing algorithm which effectively exploited the quantum tunneling effect to gain an advantage over classical algorithms – it could be applied to artificial intelligence to enhance global optimization. Any insight on what this could mean for AI?
Why is the September Paper not Available? … at Least not Available for Readers outside of China
As we discussed previously, the September paper has disappeared from the Chinese Journal of Computers (CJC), “an authoritative academic journal in the field of computer science” published in China. (hxxp://english.ict.cas[.]cn/sp/200908/t20090819_33261.html) The Natto Team also discovered that the September paper was uploaded to the China National Knowledge Infrastructure (CNKI) database of academic journals, conference proceedings, newspapers, reference works, and patent documents on September 30, 2024. However, the September paper can no longer be accessed from CNKI, showing a “lock” status when accessed from outside of China even with a valid CNKI access license, as of this publication on October 22, 2024. (see screenshot below).
Since the same authors’ May paper is still available, this makes us question why the September paper is not available. Is it due to “the sensitivity of the topic” according to Professor Wang? Is it a real breakthrough, so China wants to keep it restricted to authenticated Chinese researchers?
For years many in the industry have claimed that China would never publicize results of breaking cryptography because the Chinese government would instead want to “maximize the informational advantage” for their own benefit. By this logic, if a government-authorized Chinese periodical does publish such research, then it must be “fake”. However, in this case, the group of Chinese researchers has been working on the projects for years. They have shown the progress of their research publicly in the past, although it might have not been huge leaps in progress. Since the projects are funded by the National Natural Science Foundation of China (NSFC)’s Key Projects and the Grant of the Special Zone Project of National Defense Innovation, researchers need to have research achievements, such as publishing research papers in reputable academic journals, in order to be funded. The September paper seems to be a showcase of their recent research progress that was published by the authoritative CJC. However, its plausible, once it was published, researchers such as Professor Wang realized this is a sensitive topic and asked for it to be removed from the journal, or it is possible the relevant Chinese government organizations requested the paper be taken down. Nevertheless, the September paper is there and the Natto Team has seen it.
Note: 紅龍尋珠 - Red Dragon Seeking for Pearls. The artist’s interpretation: The image depicts a quantum optimization algorithm as a dragon navigating a multi-dimensional landscape of peaks and valleys, symbolizing local optima. The dragon uses quantum tunneling, represented by glowing portals, to bypass suboptimal solutions and reach the global minimum, depicted as the pearl. The portals reflect the D-Wave quantum chip’s enabling more efficient exploration than classical methods and accelerating the search for the optimal solution.
Disclosure Statement: The authors have no affiliations with or involvement in any organization or entity with a financial interest in or financial conflict with the subject matter or materials discussed in this manuscript.
Yup—another banger. Chinese research using D-Wave quantum systems showcases a potential leap in quantum cryptography attacks. Do they beef up research with bullshit.... sure but there's something to this one. By effectively using quantum annealing to break through the limitations of traditional algorithms, these findings could reshape the future of lightweight cryptographic security. Advancements happen, and in this case, the adversary is figuring it out; this breakthrough does not yet signal the end of current encryption standards, but it suggests that quantum computing could become a formidable player in cryptography over time. Future research may reveal if this technique can extend to more complex cryptographic systems like AES: good job piece, and thanks for introducing the CNKI to the public. Have you ever thought of linking bids on https://www.plap.mil.cn/ to MUCDs?
Having trouble translating the shared paper in this piece. Maybe you all will be able to decide if it's better proof than the last article.