Transformation of the discrete logarithm problem over F2n to the QUBO problem using normal bases

• Autorzy: Wroński Michał , Leśniak Mateusz

Identyfikatory

DOI

10.24425/ijet.2025.153543

• Języki publikacji: EN

Abstrakty

EN

Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately 3n2 logical variables for the binary field F2n . In our estimations, we assume the existence of an optimal normal base in the given fields. Such a QUBO instance can then be solved using quantum annealing.

Słowa kluczowe

EN

Discrete Logarithm Problem; Quantum Annealing; Binary Fields

• 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: 47--53
• Opis fizyczny: Bibliogr., 19 poz., rys., tab.

Twórcy

autor

Wroński Michał

• Department of Cryptology, NASK – National Research Institute

autor

Leśniak Mateusz

• Department of Cryptology, NASK – National Research Institute

Bibliografia

• [1] 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. [Online]. Available: https://doi.org/10.1109/SFCS.1994.365700
• [2] O. Regev, “An efficient quantum factoring algorithm,” 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2308.06572
• [3] S. Ragavan and V. Vaikuntanathan, “Space-efficient and noise-robust quantum factoring,” in Advances in Cryptology – CRYPTO 2024, L. Reyzin and D. Stebila, Eds. Cham: Springer Nature Switzerland, 2024, pp. 107–140. [Online]. Available: https://doi.org/10.1007/978-3-031-68391-6_4
• [4] M. Ekerå and J. Gärtner, “Extending Regev’s factoring algorithm to compute discrete logarithms,” in Post-Quantum Cryptography, M.-J. Saarinen and D. Smith-Tone, Eds. Cham: Springer Nature Switzerland, 2024, pp. 211–242. [Online]. Available: https://doi.org/10.1007/978-3-031-62746-0_10
• [5] M. Wroński, “Practical solving of discrete logarithm problem over prime fields using quantum annealing,” in Computational Science – ICCS 2022. Cham: Springer International Publishing, 2022, pp. 93–106. [Online]. Available: https://doi.org/10.1007/978-3-031-08760-8_8
• [6] M. Wroński, E. Burek, Ł. Dzierzkowski, and O. Żołnierczyk, “Transformation of elliptic curve discrete logarithm problem to qubo using direct method in quantum annealing applications,” Journal of Telecommunications and Information Technology, no. 1, pp. 75–82, 2024. [Online]. Available: https://doi.org/10.26636/jtit.2024.1.1463
• [7] 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, p. 17667, Dec 2018. [Online]. Available: https://doi.org/10.1038/s41598-018-36058-z
• [8] M. Wroński, “Index calculus method for solving elliptic curve discrete logarithm problem using quantum annealing,” in Computational Science – ICCS 2021, M. Paszynski, D. Kranzlmüller, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sloot, Eds. Cham: Springer International Publishing, 2021, pp. 149–155. [Online]. Available: https://doi.org/10.1007/978-3-030-77980-1_12
• [9] 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, J. Mikyška, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. Sloot, Eds. Cham: Springer Nature Switzerland, 2023, pp. 3–17. [Online]. Available: https://doi.org/10.1007/978-3-031-36030-5 1
• [10] M. Wroński and Ł. 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, pp. 0541–0564, 2024. [Online]. Available: https://doi.org/10.26421/QIC24.7-8-1
• [11] E. Burek, M. Wroński, K. Mańk, and M. Misztal, “Algebraic attacks on block ciphers using quantum annealing,” IEEE Transactions on Emerging Topics in Computing, vol. 10, no. 2, pp. 678–689, 2022. [Online]. Available: https://doi.org/10.1109/TETC.2022.3143152
• [12] E. Burek and M. Wroński, “Quantum annealing and algebraic attack on speck cipher,” in Computational Science – ICCS 2022, D. Groen, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sloot, Eds. Cham: Springer International Publishing, 2022, pp. 143–149. [Online]. Available: https://doi.org/10.1007/978-3-031-08760-8_12
• [13] M. Wronski, E. Burek, and M. Lesniak, “ (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, no. 01, pp. 1–14, Oct. 5555. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/TETC.2024.3474856
• [14] 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. 94, no. 4, p. 30–37, Oct. 2023. [Online]. Available: https://jtit.pl/jtit/article/view/1340
• [15] M. Leśniak, E. Burek, and M. Wroński, “Unsafe mechanisms of bluetooth, e0 stream cipher cryptanalysis with quantum annealing,” in Computational Science – ICCS 2024, L. Franco, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sloot, Eds. Cham: Springer Nature Switzerland, 2024, pp. 389–404. [Online]. Available: https://doi.org/10.1007/978-3-031-63778-0_28
• [16] G. Morse, T. Kozsik, O. Mencer, and P. Rakyta, “A compact qubo encoding of computational logic formulae demonstrated on cryptography constructions,” 2024. [Online]. Available: https://arxiv.org/abs/2409.07501
• [17] R. C. Mullin and A. Mahalanobis, Dickson bases and finite fields. Faculty of Mathematics, University of Waterloo, 2005.
• [18] A. Amin and T. F. Al-Somani, “Hardware implementations of gf (2ˆ m) arithmetic using normal basis,” Journal of Applied Sciences, vol. 6, no. 6, pp. 1362–1372, 2006. [Online]. Available: https://doi.org/10.3923/jas.2006.1362.1372
• [19] Y. AONO, S. LIU, T. TANAKA, S. UNO, R. V. METER, N. SHINOHARA, and R. NOJIMA, “The present and future of discrete logarithm problems on noisy quantum computers,” IEEE Transactions on Quantum Engineering, vol. 3, pp. 1–21, 2022. [Online]. Available: https://doi.org/10.1109/TQE.2022.3183385

Uwagi

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).