A Highly Efficient ECPM Quantum Circuit for Binary Elliptic Curve Cryptanalysis

Abstract

This paper provides a detailed analysis and estimation of the quantum resources required for depth-optimized elliptic curve point multiplication (ECPM), with a focus on qubits, Toffoli gates, CNOT gates, and circuit depth. The proposed ECPM quantum circuit, which is tailored for binary elliptic curve cryptanalysis using Shor’s algorithm, incorporates improved arithmetic operations into optimized point addition (PA) and point doubling (PD) processes. The quantum resources required for single-step and full-step ECPM implementations (comprising $2n$ PD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require ( $2n+2$ )PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require $2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})$ Toffoli gates, approximately $2n + 7n\log _{6} n + 7$ qubits, and a circuit depth of approximately $7+n\log _{3}{9}$ . Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.

Keywords

• Elliptic curve
• ECPM
• quantum cryptanalysis
• shor