AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (878.1 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

An Innovative Algorithm for Attacking Symmetric Ciphers Using D-Wave Quantum Annealing

Key Laboratory of Specialty Fiber Optics and Optical Access Networks, Shanghai University, Shanghai 200444, China
Show Author Information

Abstract

Quantum computing is generally considered non-threatening to symmetric ciphers. Quantum attacks on symmetric ciphers require a thorough analysis of their internal structures, posing considerable difficulties and challenges. As of 2023, Google’s quantum supremacy chip, Sycamore, is still incapable of cryptanalysis. Leveraging D-Wave’s quantum annealing exploits the unique quantum tunneling effect, providing an edge in solving combinatorial optimization problems. It can be regarded as a class of artificial intelligence algorithm that can achieve global optimization. We propose a quantum heuristic symmetric cipher attack algorithm for substitution-permutation network (SPN) symmetric ciphers, which transforms the plaintext-ciphertext propagation rules within SPN structure into the problem of solving a constrained quadratic model (CQM). A novel reduction algorithm is employed to eliminate redundant constraint conditions. The D-Wave Advantage quantum computer is used to recover the encryption sub-keys. Using the quantum approximate optimization algorithm, IBM Q Experience can only recover two rounds of the Heys Cipher sub-key, whereas D-Wave Advantage achieves complete key recovery, validating its potential in quantum symmetric cipher attacks.

Keywords

quantum computingquantum annealingD-Wavesymmetric cipher

References

[1]

Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature, vol. 614, no. 7949, pp. 676–681, 2023.
Crossref Google Scholar
[2]
P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annu. Symp. Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134.
Crossref
[3]
L. K. Grover, A fast quantum mechanical algorithm for database search, in Proc. 28th Annu. ACM Symp. Theory of Computing, Philadelphia, PA, USA, 1996, pp. 212–219.
Crossref
[4]

D. R. Simon, On the power of quantum computation, SIAM J. Comput., vol. 26, no. 5, pp. 1474–1483, 1997.
Crossref Google Scholar
[5]

Y. Y. Luo, H. L. Yan, L. Wang, H. G. Hu, and X. B. Lai, Study on block cipher structures against Simon’s quantum algorithm, (in Chinese), J. Cryptol. Res., vol. 6, no. 5, pp. 561–573, 2019.
Google Scholar
[6]

J. Preskill, Quantum computing in the NISQ era and beyond, Quantum, vol. 2, p. 79, 2018.
Crossref Google Scholar
[7]

Z. Wang, S. Wei, G. L. Long, and L. Hanzo, Variational quantum attacks threaten advanced encryption standard based symmetric cryptography, Sci. China Inf. Sci., vol. 65, no. 10, p. 200503, 2022.
Crossref Google Scholar
[8]
B. Aizpurua, P. Bermejo, J. E. Martinez, and R. Orus, Hacking cryptographic protocols with advanced variational quantum attacks, arXiv preprint arXiv: 2311.02986, 2023.
[9]
L. Phab, S. Louise, and R. Sirdey, A first attempt at cryptanalyzing a (toy) block cipher by means of QAOA, in Proc. 22nd Int. Conf. Computational Science, London, UK, 2022, pp. 218–232.
Crossref
[10]
A. Kulshrestha and I. Safro, BEINIT: Avoiding barren plateaus in variational quantum algorithms, in Proc. 2022 IEEE Int. Conf. Quantum Computing and Engineering, Broomfield, CO, USA, 2022, pp. 197–203.
Crossref
[11]

R. D. Somma, D. Nagaj, and M. Kieferová, Quantum speedup by quantum annealing, Phys. Rev. Lett., vol. 109, no. 5, p. 050501, 2012.
Crossref Google Scholar
[12]

S. Morita and H. Nishimori, Convergence theorems for quantum annealing, J. Phys. A: Math. Gen., vol. 39, no. 45, p. 13903, 2006.
Crossref Google Scholar
[13]

A. D. King, J. Raymond, T. Lanting, R. Harris, A. Zucca, F. Altomare, A. J. Berkley, K. Boothby, S. Ejtemaee, C. Enderud, et al., Quantum critical dynamics in a 5,000-qubit programmable spin glass, Nature, vol. 617, no. 7959, pp. 61–66, 2023.
Crossref Google Scholar
[14]

C. Wang and H. Zhang, Impact of Canadian commercial quantum computers on cryptography, (in Chinese), Inf. Secur. Commun. Priv., no. 2, pp. 31–32&35, 2012.
Google Scholar
[15]

B. Wang, F. Hu, H. Zhang, and C. Wang, From evolutionary cryptography to quantum artificial intelligent cryptography, (in Chinese), J. Comput. Res. Dev., vol. 56, no. 10, pp. 2112–2134, 2019.
Google Scholar
[16]

W. Peng, B. Wang, F. Hu, Y. Wang, X. Fang, X. Chen, and C. Wang, Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China Phys. Mech. Astron., vol. 62, no. 6, p. 60311, 2019.
Crossref Google Scholar
[17]

B. Wang, F. Hu, H. Yao, and C. Wang, Prime factorization algorithm based on parameter optimization of Ising model, Sci. Rep., vol. 10, no. 1, p. 7106, 2020.
Crossref Google Scholar
[18]

C. Hong, Z. Pei, Q. Wang, S. Yang, J. Yu, and C. Wang, Quantum attack on RSA by D-Wave Advantage: A first break of 80-bit RSA, Sci. China Inf. Sci., vol. 68, no. 2, p. 129501, 2025.
Crossref Google Scholar
[19]
M. Wroński, Index calculus method for solving elliptic curve discrete logarithm problem using quantum annealing, in Proc. 21st Int. Conf. Computational Science, Krakow, Poland, 2021, pp. 149–155.
Crossref
[20]

A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J.D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett., vol. 219, nos. 5–6, pp. 343–348, 1994.
Crossref Google Scholar
[21]
S. Sinno, T. Groß, A. Mott, A. Sahoo, D. Honnalli, S. Thuravakkath, and B. Bhalgamiya, Performance of commercial quantum annealing solvers for the capacitated vehicle routing problem, arXiv preprint arXiv: 2309.05564, 2023.
[22]

Z. Bian, F. Chudak, W. Macready, A. Roy, R. Sebastiani, and S. Varotti, Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results, Inf. Comput., vol. 275, p. 104609, 2020.
Crossref Google Scholar
[23]

M. H. Amin, Searching for quantum speedup in quasistatic quantum annealers, Phys. Rev. A, vol. 92, no. 5, p. 052323, 2015.
Crossref Google Scholar
[24]

S. Mukherjee and B. K. Chakrabarti, Multivariable optimization: Quantum annealing and computation, Eur. Phys. J. Spec. Top., vol. 224, no. 1, pp. 17–24, 2015.
Crossref Google Scholar
[25]

H. M. Heys, A tutorial on linear and differential cryptanalysis, Cryptologia, vol. 26, no. 3, pp. 189–221, 2002.
Crossref Google Scholar
[26]
N. Mouha, Q. Wang, D. Gu, and B. Preneel, Differential and linear cryptanalysis using mixed-integer linear programming, in Proc. 7th Int. Conf. Information Security and Cryptology, Beijing, China, 2012, pp. 57–76.
Crossref
[27]

A. Glos, A. Kundu, and Ö. Salehi, Optimizing the production of test vehicles using hybrid constrained quantum annealing, SN Comput. Sci., vol. 4, no. 5, p. 609, 2023.
Crossref Google Scholar
[28]
S. Sun, L. Hu, P. Wang, K. Qiao, X. Ma, and L. Song, Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers, in Proc. 20th Int. Conf. Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014, pp. 158–178.
Crossref
[29]
Y. Sasaki and Y. Todo, New algorithm for modeling S-box in MILP based differential and division trail search, in Proc. 10th Int. Conf. Information Technology and Communications Security, Bucharest, Romania, 2017, pp. 150–165.
Crossref
Tsinghua Science and Technology
Volume 30 Issue 5,
October 2025
Pages 2184-2194
DOI: 10.26599/TST.2024.9010231
Cite this article:
Pei Z, Hong C, Xia F, et al. An Innovative Algorithm for Attacking Symmetric Ciphers Using D-Wave Quantum Annealing. Tsinghua Science and Technology, 2025, 30(5): 2184-2194. https://doi.org/10.26599/TST.2024.9010231

134

Views

13

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 20 March 2024
Revised: 07 July 2024
Accepted: 12 November 2024
Published: 29 April 2025
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return