Transformation of Elliptic Curve Discrete Logarithm Problem to QUBO Using Direct Method in Quantum Annealing Applications
DOI:
https://doi.org/10.26636/jtit.2024.1.1463Keywords:
cryptanalysis, D-Wave, elliptic curve discrete logarithm problem, quantum annealingAbstract
This paper investigates how to reduce the elliptic curve discrete logarithm problem over prime fields to the quadratic unconstrained binary optimization (QUBO) problem in order to obtain as few logical qubits as possible. In the best case scenario, if n is the bitlength of a characteristic of prime field Fp, approximately 3n³ logical qubits are required for such a reduction in the Edwards curve case. We present a practical attack on an elliptic curve discrete logarithm problem over the 3-bit prime field F7 for an elliptic curve with the subgroup of order 8. We solved this problem using the D-Wave Advantage QPU. To the best of the authors' knowledge, no one has made, so far, a practical attack on the elliptic curve discrete logarithm over a prime field using the direct quantum method.
Downloads
References
P.W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," in: Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, USA, 1994.
View in Google Scholar
M. Ekerå, "Revisiting Shor’s Quantum Algorithm for Computing General Discrete Logarithms", arXiv:1905.09084, 2019.
View in Google Scholar
M. Ekerå and J. Håstad, "Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers", International Workshop on Post-Quantum Cryptography, Utrecht, The Netherlands, pp. 347-363, 2017.
View in Google Scholar
C. Gidney and M. Ekerå, "How to Factor 2048 Bit RSA Integers in 8 Hours Using 20 million Noisy Qubits", Quantum, vol. 5, art. no. 433, 2021.
View in Google Scholar
G. Banegas, D.J. Bernstein, I. Van Hoof, and T. Lange, "Concrete Quantum Cryptanalysis of Binary Elliptic Curves", IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2021, no. 1, pp. 451-472, 2021.
View in Google Scholar
M. Roetteler, M. Naehrig, K.M. Svore, and K. Lauter. "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms", International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017.
View in Google Scholar
S.D. Galbraith and P. Gaudry, "Recent Progress on the Elliptic Curve Discrete Logarithm Problem", Designs, Codes and Cryptography, vol. 78, pp. 51-72, 2016.
View in Google Scholar
S. Jiang, K.A. Britt, A.J. McCaskey, T.S. Humble, and S. Kais, "Quantum Annealing for Prime Factorization", Scientific Reports, vol. 8, art. no. 17667, 2018.
View in Google Scholar
M. Wroński, "Practical Solving of Discrete Logarithm Problem over Prime Fields Using Quantum Annealing", Computational Science - ICCS 2022, pp. 93-106, 2022.
View in Google Scholar
The Quantum Computing Company D-WAVE, Getting Started with the D-wave System. User Manual, 2020 (https://docs.dwavesys.com/docs/latest/doc_getting_started.html).
View in Google Scholar
M. Wroński, "Index Calculus Method for Solving Elliptic Curve Discrete Logarithm Problem Using Quantum Annealing", International Conference on Computational Science, Kraków, Poland, pp. 149-55, 2021.
View in Google Scholar
S. Mukherjee and B.K. Chakrabarti, "Multivariable Optimization: Quantum Annealing and Computation", The European Physical Journal Special Topics, vol. 224, pp. 17-24, 2015.
View in Google Scholar
J. Renes, C. Costello, and L. Batina, "Complete Addition Formulas for Prime Order Elliptic Curves", Advances in Cryptology - EUROCRYPT 2016, pp. 403-428, 2016.
View in Google Scholar
D.J. Bernstein and T. Lange, "Faster Addition and Doubling on Elliptic Curves," International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2007.
View in Google Scholar
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.
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Michał Wroński, Elżbieta Burek, Łukasz Dzierzkowski, Olgierd Żołnierczyk
This work is licensed under a Creative Commons Attribution 4.0 International License.
