Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient <i>h</i> and Coupling Coefficient <i>J</i> of the Ising Model by D-Wave 2000Q

Chao Wang; Qiaoyun Hu; Haonan Yao; Sumin Wang; Zhi Pei

doi:10.26599/TST.2023.9010059

Tsinghua Science and Technology 2024, 29(3): 874-882 https://doi.org/10.26599/TST.2023.9010059

Open Access | Issue | Published: 04 December 2023

Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q

Show Author's Information Hide Author's Information Chao Wang(

), Qiaoyun Hu, Haonan Yao, Sumin Wang, Zhi Pei

Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China

Keywords:

post-quantum cryptography, quantum annealing, RSA, D-Wave 2000Q

Cite this article:

Wang C, Hu Q, Yao H, et al. Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q. Tsinghua Science and Technology, 2024, 29(3): 874-882. https://doi.org/10.26599/TST.2023.9010059

Download citation

EndNote(RIS)

BibTeX

464

Views

135

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

This work is the first to determine that a real quantum computer (including generalized and specialized) can decipher million-scale RSA relying solely on quantum algorithms, showing the real attack potential of D-Wave machines. The influence of different column widths on RSA factorization results is studied on the basis of a multiplication table, and the optimal column method is determined by traversal experiments. The traversal experiment of integer factorization within 10 000 shows that the local field and coupling coefficients are 75%–93% lower than the research of Shanghai University in 2020 and more than 85% lower than that of Purdue University in 2018. Extremely low Ising model parameters are crucial to reducing the hardware requirements, prompting factoring 1245407 on the D-Wave 2000Q real machine. D-Wave advantage already has more than 5000 qubits and will be expanded to 7000 qubits during 2023–2024, with remarkable improvements in decoherence and topology. This machine is expected to promote the solution of large-scale combinatorial optimization problems. One of the contributions of this paper is the discussion of the long-term impact of D-Wave on the development of post-quantum cryptography standards.

Full text

Abstract

Full text

Outline

About this article

Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q

Show Author's information Hide Author's Information Chao Wang(

), Qiaoyun Hu, Haonan Yao, Sumin Wang, Zhi Pei

Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China

Abstract

Keywords: post-quantum cryptography, quantum annealing, RSA, D-Wave 2000Q

References(36)

[1]

R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.

DOI Google Scholar

[2]

P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annual Symp. on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134.

[3]

E. Martín-López, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O'Brien, Experimental realization of Shor’s quantum factoring algorithm using qubit recycling, Nat. Photonics, vol. 6, no. 11, pp. 773–776, 2012.

DOI Google Scholar

[4]

M. R. Geller and Z. Zhou, Factoring 51 and 85 with 8 qubits, Sci. Rep., vol. 3, p. 3023, 2013.

DOI Google Scholar

[5]

T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt, Realization of a scalable shor algorithm, Science, vol. 351, no. 6277, pp. 1068–1070, 2016.

DOI Google Scholar

[6]

D. Castelvecchi, Quantum computers ready to leap out of the lab in 2017, Nature, vol. 541, no. 7635, pp. 9–10, 2017.

DOI Google Scholar

[7]

A. Cho, DOE pushes for useful quantum computing, Science, vol. 359, no. 6372, pp. 141–142, 2018.

DOI

[8]

M. Dyakonov, When will useful quantum computers be constructed? Not in the foreseeable future, this physicist argues. Here’s why: The case against: Quantum computing, IEEE Spectr., vol. 56, no. 3, pp. 24–29, 2019.

DOI Google Scholar

[9]

E. Gibney, Physics: Quantum computer quest, Nature 516, https://doi.org/10.1038/516024a, 2014.

DOI

[10]

C. Gidney, Factoring with n+2 clean qubits and n−1 dirty qubits, arXiv preprint arXiv: 1706.07884, 2017.

[11]

C. Wang, H. Yao, B. Wang, F. Hu, H. Zhang, and X. Ji, Advances in cryptographic Attacks for quantum computing, (in Chinese), Chinese J. Comput., vol. 43, no. 9, pp. 1691–1707, 2020.

Google Scholar

[12]

N. Chancellor, Fluctuation-guided search in quantum annealing, Phys. Rev. A, vol. 102, no. 6, p. 062606, 2020.

DOI Google Scholar

[13]

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science, vol. 292, no. 5516, pp. 472–475, 2001.

DOI Google Scholar

[14]

X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, Quantum adiabatic algorithm for factorization and its experimental implementation, Phys. Rev. Lett., vol. 101, no. 22, p. 220405, 2008.

DOI Google Scholar

[15]

C. J. C. Burges, Factoring as optimization, Microsoft Res MSR-TR-200, https://www.microsoft.com/en-us/research/publication/factoring-as-optimization/, 2002.

[16]

G. Schaller and R. Schutzhold, The role of symmetries in adiabatic quantum algorithms, Quantum Inf. Comput., vol. 10, nos. 1&2, pp. 109–140, 2010.

DOI Google Scholar

[17]

N. Xu, J. Zhu, D. Lu, X. Zhou, X. Peng, and J. Du, Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system, Phys. Rev. Lett., vol. 108, no. 13, p. 130501, 2012.

DOI Google Scholar

[18]

S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, Quantum annealing for prime factorization, Sci. Rep., vol. 8, no. 1, p. 17667, 2018.

DOI Google Scholar

[19]

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, pp. 1–8, 2019.

DOI Google Scholar

[20]

C. Wang and H. G. Zhang, The impact of commercial quantum computer on cryptography, (in Chinese), Inf. Secur. Commun. Priv., vol. 2, pp. 31–32, 2012.

Google Scholar

[21]

N. S. Dattani and N. Bryans, Quantum factorization of 56153 with only 4 qubits, arXiv preprint arXiv: 1411.6758, 2014.

[22]

N. N. Hegade, K. Paul, F. Albarrán-Arriagada, X. Chen, and E. Solano, Digitized adiabatic quantum factorization, Phys. Rev. A, vol. 104, no. 5, p. L050403, 2021.

DOI Google Scholar

[23]

B. Wang, H. Yao, F. Hu, and C. Wang, Quantum annealing distributed integer decomposition study of local field coefficient h and coupling coefficient J with stability Ising model, Sci. Sin.-Phys. Mech. Astron., vol. 50, no. 3, p. 030301, 2020.

DOI Google Scholar

[24]

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.

DOI Google Scholar

[25]

C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum, vol. 5, p. 433, 2021.

DOI Google Scholar

[26]

M. Mosca and M. Piani, Quantum threat timeline, https://globalriskinstitute.org/publication/quantum-threat-timeline/, 2019.

[27]

É. Gouzien and N. Sangouard, Factoring 2048-bit RSA integers in 177 days with 13436 qubits and a multimode memory, Phys. Rev. Lett., vol. 127, no. 14, p. 140503, 2021.

DOI Google Scholar

[28]

F. X. Cui, B. Wang, Y. Liu, and Y. Li, Research status and prospect of quantum attack on public key cryptography, (in Chinese), Network Security and Data Governance, vol. 41, no. 3, pp. 3–12, 2022.

Google Scholar

[29]

S. Muthukrishnan, T. Albash, and D. A. Lidar, Tunneling and speedup in quantum optimization for permutation-symmetric problems, Phys. Rev. X, vol. 6, no. 3, p. 031010, 2016.

DOI Google Scholar

[30]

B. Yan, Z. Tan, S. Wei, H. Jiang, W. Wang, H. Wang, L. Luo, Q. Duan, Y. Liu, W. Shi, et al., Factoring integers with sublinear resources on a superconducting quantum processor, arXiv preprint arXiv: 2212.12372, 2022.

[31]

D. A. Lidar, A. T. Rezakhani, and A. Hamma, Adiabatic approximation with exponential accuracy for many-body systems and quantum computation, J. Math. Phys., vol. 50, no. 10, p. 102106, 2009.

DOI Google Scholar

[32]

V. Choi, Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Inf. Process., vol. 7, no. 5, pp. 193–209, 2008.

DOI Google Scholar

[33]

W. L. Du, B. Li, and Y. Tian, Quantum annealing algorithms: State of the art, (in Chinese), J. Comput. Res. Dev., vol. 45, no. 9, pp. 1501–1508, 2008.

Google Scholar

[34]

D-Wave systems, D-wave initiates open quantum software environment, https://www.dwavesys.com/press-releases/d-wave-initiates-open-quantum-software-environment, 2017.

[35]

R. H. Warren, Factoring on a quantum annealing computer, Quantum Inf. Comput., vol. 19, nos. 3&4, pp. 252–261, 2019.

DOI Google Scholar

[36]

Y. Q. Chen, Y. Chen, C. K. Lee, S. Zhang, and C. Y. Hsieh, Optimizing quantum annealing schedules with Monte Carlo tree search enhanced with neural networks, Nat. Mach. Intell., vol. 4, no. 3, pp. 269–278, 2022.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 26 March 2023

Revised: 12 May 2023

Accepted: 13 June 2023

Published: 04 December 2023

Issue date: June 2024

Copyright

Acknowledgements

Acknowledgment

This work was supported by the Special Zone Project of National Defense Innovation.

Rights and permissions

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