Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography

• Autorzy: Żołnierczyk Olgierd

Identyfikatory

DOI

10.24425/ijet.2025.153542

• Języki publikacji: EN

Abstrakty

EN

This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations, assuming the use of the best publicly available special-class quantum computer: the quantum annealer. We achieve new computational experiment results by solving the largest instance of the factorization problem ever announced as solved using quantum annealing, with a size of 29 bits. The core idea of the improved approach is to leverage known sub-exponential classical method to break the problem down into many smaller computations and perform the most critical ones on a quantum computer. This approach does not reduce the complexity class, but it assesses the pragmatic capabilities of an attacker. It also marks a step forward in the development of hybrid methods, which in practice may surpass classical methods in terms of efficiency sooner than purely quantum computations will.

Słowa kluczowe

EN

Cryptography; Integer Factorization Problem; Number Field Sieve; Hybrid quantum computations; Quantum annealing; QUBO; B-smooth numbers

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 1
• Strony: 39--46
• Opis fizyczny: Bibliogr. 30 poz., tab.

Twórcy

autor

Żołnierczyk Olgierd

• Military University of Technology

Bibliografia

• [1] R. Crandall and C. Pomerance, Prime Numbers. A Computational Perspective. Springer, 2005.
• [2] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994, pp. 124–134.
• [3] M. Amico, Z. H. Saleem, and M. Kumph, “Experimental study of shor’s factoring algorithm using the ibm q experience,” Phys. Rev. A, vol. 100, p. 012305, Jul 2019. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.100.012305
• [4] S. Pal, S. Moitra, V. S. Anjusha, A. Kumar, and T. S. Mahesh, “Hybrid scheme for factorisation: Factoring 551 using a 3-qubit NMR quantum adiabatic processor,” Pramana - J Phys, vol. 92, no. 2, Feb. 2019.
• [5] J. Ding, G. Spallitta, and R. Sebastiani, “Experimenting with D-Wave quantum annealers on prime factorization problems,” Front. Comput. Sci., vol. 6, Jun. 2024.
• [6] D. J. Bernstein, J.-F. Biasse, and M. Mosca, “A low-resource quantum factoring algorithm,” Cryptology ePrint Archive, Paper 2017/352, 2017, https://eprint.iacr.org/2017/352. [Online]. Available: https://eprint.iacr.org/2017/352
• [7] M. Wroński, Index Calculus Method for Solving Elliptic Curve Discrete Logarithm Problem Using Quantum Annealing. Springer International Publishing, 2021, p. 149–155. [Online]. Available: http://dx.doi.org/10.1007/978-3-030-77980-1 12
• [8] O. Żołnierczyk and M. Wroński, “Searching b-smooth numbers using quantum annealing: Applications to factorization and discrete logarithm problem,” in Computational Science – ICCS 2023. Springer Nature Switzerland, 2023, pp. 3–17. [Online]. Available: https://doi.org/10.1007/978-3-031-36030-5 1
• [9] A. H. Karamlou, W. A. Simon, A. Katabarwa, T. L. Scholten, B. Peropadre, and Y. Cao, “Analyzing the performance of variational quantum factoring on a superconducting quantum processor,” npj Quantum Information, vol. 7, no. 1, Oct. 2021. [Online]. Available: http://dx.doi.org/10.1038/s41534-021-00478-z
• [10] A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, “The number field sieve,” in Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, ser. STOC ’90. New York, NY, USA: Association for Computing Machinery, 1990, p. 564–572. [Online]. Available: https://doi.org/10.1145/100216.100295
• [11] F. Jarvis, Algebraic number theory. Springer, 2014.
• [12] J. P. Buhler, H. W. Lenstra, and C. Pomerance, “Factoring integers with the number field sieve,” in The development of the number field sieve, A. K. Lenstra and H. W. Lenstra, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993, pp. 50–94.
• [13] A. K. Lenstra and H. W. Lenstra, The Development of the Number Field Sieve, ser. Lecture Notes in Mathematics. Springer-Verlag, Berlin, Heidelberg, 1993, vol. 1554.
• [14] A. Guillevic and S. Singh, “On the alpha value of polynomials in the tower number field sieve algorithm,” Mathematical Cryptology, vol. 1, no. 1, p. 1–39, Feb. 2021. [Online]. Available: https://journals.flvc.org/mathcryptology/article/view/125142
• [15] E. Thomé, “Square root algorithms for the number field sieve,” in Arithmetic of Finite Fields, F. Özbudak and F. Rodríguez-Henríquez, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 208–224.
• [16] C. Bouillaguet, A. Fleury, P.-A. Fouque, and P. Kirchner, “We are on the same side. alternative sieving strategies for the number field sieve,” in Advances in Cryptology – ASIACRYPT 2023, J. Guo and R. Steinfeld, Eds. Singapore: Springer Nature Singapore, 2023, pp. 138–166.
• [17] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,” Physical Review E, vol. 58, no. 5, p. 5355–5363, Nov. 1998.
• [18] W. van Dam, M. Mosca, and U. Vazirani, “How powerful is adiabatic quantum computation?” in Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001, p. 279–287. [Online]. Available: http://dx.doi.org/10.1109/SFCS.2001.959902
• [19] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum computation by adiabatic evolution,” 2000. [Online]. Available: https://arxiv.org/abs/quant-ph/0001106
• [20] M. Wro ´nski, Practical Solving of Discrete Logarithm Problem over Prime Fields Using Quantum Annealing. Springer International Publishing, 2022, p. 93–106. [Online]. Available: http://dx.doi.org/10.1007/978-3-031-08760-8_8
• [21] M. Wronski and L. Dzierzkowski, “Base of exponent representation matters – more efficient reduction of discrete logarithm problem and elliptic curve discrete logarithm problem to the qubo problem,” Quantum Information and Computation, vol. 24, no. 7 & 8, p. 541–564, Jun. 2024. [Online]. Available: http://dx.doi.org/10.26421/QIC24.7-8-1
• [22] E. Burek, K. Mańk, and M. Wroński, “Searching for an efficient system of equations defining the aes sbox for the qubo problem,” Journal of Telecommunications and Information Technology, vol. 4, no. 2023, p. 30–37, Oct. 2023. [Online]. Available: http://dx.doi.org/10.26636/jtit.2023.4.1340
• [23] E. Burek and M. Wroński, Quantum Annealing and Algebraic Attack on Speck Cipher. Springer International Publishing, 2022, p. 143–149. [Online]. Available: http://dx.doi.org/10.1007/978-3-031-08760-8 12
• [24] M. Wroński, E. Burek, and M. Leśniak, “(in)security of stream ciphers against quantum annealing attacks on the example of the grain 128 and grain 128a ciphers,” IEEE Transactions on Emerging Topics in Computing, p. 1–14, 2024. [Online]. Available: http://dx.doi.org/10.1109/TETC.2024.3474856
• [25] M. Leśniak, E. Burek, and M. Wroński, Unsafe Mechanisms of Bluetooth, E0 Stream Cipher Cryptanalysis with Quantum Annealing. Springer Nature Switzerland, 2024, p. 389–404. [Online]. Available: http://dx.doi.org/10.1007/978-3-031-63778-0 28
• [26] S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, “Quantum annealing for prime factorization,” Scientific reports, vol. 8, no. 1, pp. 1–9, 2018.
• [27] 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,” Science China Physics, Mechanics; Astronomy, vol. 62, no. 6, Jan. 2019. [Online]. Available: http://dx.doi.org/10.1007/s11433-018-9307-1
• [28] R. Mengoni, D. Ottaviani, and P. Iorio, “Breaking rsa security with a low noise d-wave 2000q quantum annealer: Computational times, limitations and prospects,” 2020. [Online]. Available: https://arxiv.org/abs/2005.02268
• [29] D.-W. S. Inc, “Qpu-specific physical properties: Advantage system4.1, user manual.” [Online]. Available: https://docs.dwavesys.com/docs/latest/downloads/d9a3e404f2019e9f35f59c9d2ea2bcf8/09-1262A-D_QPU_Properties Advantage system4 1.pdf
• [30] R. Selvarajan, V. Dixit, X. Cui, T. S. Humble, and S. Kais, “Prime factorization using quantum variational imaginary time evolution,” Scientific Reports, vol. 11, no. 1, Oct. 2021. [Online]. Available: http://dx.doi.org/10.1038/s41598-021-00339-x

Uwagi

1. Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).

2. This work was Supported by the Grant DOB/002/RON/ID1/2018 by The National Centre for Research and Development.