The generalized method of solving ECDLP using quantum annealing

• Autorzy: Dzierzkowski Łukasz

Identyfikatory

DOI

10.24425/ijet.2025.153544

• Języki publikacji: EN

Abstrakty

EN

This paper presents a generalization of a method allowing the transformation of the Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. The original method requires that a given elliptic curve model has complete arithmetic. The new one has no such restriction, which is a breakthrough. Since the mentioned obstacle is no longer a problem, the latest version of the algorithm may be used for any elliptic curve model. As a result, one may use quantum annealing to solve ECDLP on any given model of elliptic curves.

Słowa kluczowe

EN

cryptology; cryptanalysis; elliptic curves; discrete logarithm; ECDLP; quantum annealing

• 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: 55--60
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Dzierzkowski Łukasz

• Military University of Technology

Bibliografia

• [1] S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.),” IEEE Transactions on information Theory, vol. 24, no. 1, pp. 106–110, 1978.
• [2] D. Shanks, “Five number-theoretic algorithms,” in Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), 1973, 1973.
• [3] D. Bernstein and T. Lange, “Two grumpy giants and a baby,” The Open Book Series, vol. 1, no. 1, pp. 87–111, 2013.
• [4] J. M. Pollard, “Monte Carlo methods for index computation (mod p),” Mathematics of computation, vol. 32, no. 143, pp. 918–924, 1978.
• [5] L. C. Washington, Elliptic curves: number theory and cryptography. Chapman and Hall/CRC, 2008.
• [6] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” 2017. [Online]. Available: https://arxiv.org/abs/1706.06752
• [7] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994, pp. 124–134.
• [8] M. Wroński, “Practical solving of discrete logarithm problem over prime fields using quantum annealing,” in International Conference on Computational Science. Springer, 2022, pp. 93–106.
• [9] 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.
• [10] E. Burek and M. Wroński, “Quantum Annealing and Algebraic Attack on Speck Cipher,” in International Conference on Computational Science. Springer, 2022, pp. 143–149.
• [11] 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,” Cryptology ePrint Archive, 2023.
• [12] 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, 2018.
• [13] 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, pp. 1–8, 2019.
• [14] O. Żołnierczyk and M. Wroński, “Searching B-Smooth Numbers Using Quantum Annealing: Applications to Factorization and Discrete Logarithm Problem,” in International Conference on Computational Science. Springer, 2023, pp. 3–17.
• [15] J. Ding, G. Spallitta, and R. Sebastiani, “Effective prime factorization via quantum annealing by modular locally-structured embedding,” Scientific Reports, vol. 14, no. 1, p. 3518, 2024.
• [16] M. Wroński, “Index calculus method for solving elliptic curve discrete logarithm problem using quantum annealing,” in International Conference on Computational Science. Springer, 2021, pp. 149–155.
• [17] 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.
• [18] 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.
• [19] D-Wave Advantage Leap. [Online]. Available: https://cloud.dwavesys.com/leap/
• [20] M. Wroński, “Faster point scalar multiplication on short Weierstrass elliptic curves over Fp using twisted Hessian curves over Fp2,” Journal of Telecommunications and Information Technology, no. 3, pp. 98–102, 2016.

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