Shor’s algorithm remains a cornerstone of quantum cryptanalysis, driving active research into reducing quantum resource overheads in both spatial and temporal dimensions. This work presents a dual-optimization framework targeting resource-efficient Shor-based quantum cryptanalysis on binary elliptic curves. Our approach conducts a comprehensive resource assessment across multiple abstraction levels—ranging from finite field arithmetic to elliptic curve group operations. At the low-level layer, we benchmark various quantum arithmetic constructor designs—including GCD-based, FLT-based, FLT-Basic or extended variants, in-place, and out-of-place execution models—analyzing Toffoli gate counts, qubit requirements, and circuit depths. At the group operation layer, we examine point addition and doubling circuits, employing complete iterations of Shor’s algorithm with elliptic curve point multiplication (ECPM) that require point addition (PA) only (with (2n+ 2) PA) and point doubling (PD) utilization (2nPD + 2 PA). We further simulate selected (2nPD + 2 PAoutplace) circuit designs, highlighting the advantages of optimized out-of-place PA circuits and integrated ECPM techniques from prior work. Additionally, we explore decompositions of multi-controlled gates to achieve a practical trade-off between qubit count and overall depth.
Shor’s algorithm remains a cornerstone of quantum cryptanalysis, driving active research into reducing quantum resource overheads in both spatial and temporal dimensions. This work presents a dual-optimization framework targeting resource-efficient Shor-based quantum cryptanalysis on binary elliptic curves. Our approach conducts a comprehensive resource assessment across multiple abstraction levels—ranging from finite field arithmetic to elliptic curve group operations. At the low-level layer, we benchmark various quantum arithmetic constructor designs—including GCD-based, FLT-based, FLT-Basic or extended variants, in-place, and out-of-place execution models—analyzing Toffoli gate counts, qubit requirements, and circuit depths. At the group operation layer, we examine point addition and doubling circuits, employing complete iterations of Shor’s algorithm with elliptic curve point multiplication (ECPM) that require point addition (PA) only (with (2n+ 2) PA) and point doubling (PD) utilization (2nPD + 2 PA). We further simulate selected (2nPD + 2 PAoutplace) circuit designs, highlighting the advantages of optimized out-of-place PA circuits and integrated ECPM techniques from prior work. Additionally, we explore decompositions of multi-controlled gates to achieve a practical trade-off between qubit count and overall depth.
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 (comprising2nPD +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 require2n3+2n(log3+1)+32n2logn+8n2+O(n(log3+1))Toffoli gates, approximately2n+7nlog6n+7qubits, and a circuit depth of approximately7+nlog39. 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.
This paper presents quantum cryptanalysis for binary elliptic curves from a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in the Qiskit quantum computer simulator. The proposed multiplier architecture, which improves the quantum Karatsuba multiplier from the previous study, reduces the depth and yields a lower number of CNOT gates that bound toO(nlog2(3))while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for the elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and giving new insights on quantum cryptanalysis for a depth-optimized implementation.
This paper improves upon the quantum circuits required for the Shor’s attack on binary elliptic curves. We present two types of quantum point addition, taking both qubit count and circuit depth into consideration.In summary, we propose an in-place point addition that improves upon the work of Banegas et al. from CHES’21, reducing the qubit count – depth product by more than 73% – 81% depending on the variant. Furthermore, we develop an out-of-place point addition by using additional qubits. This method achieves the lowest circuit depth and offers an improvement of over 92% in the qubit count – quantum depth product (for a single step).To the best of our knowledge, our work improves from all previous works (including the CHES’21 paper by Banegas et al., the IEEE Access’22 paper by Putranto et al., and the CT-RSA’23 paper by Taguchi and Takayasu) in terms of circuit depth and qubit count – depth product.Equipped with the implementations, we discuss the post-quantum security of the binary elliptic curve cryptography. Under the MAXDEPTH metric (proposed by the US government’s NIST), the quantum circuit with the highest depth in our work is 224, which is significantly lower than the MAXDEPTH limit of 240. For the gate count – full depth product, a metric for estimating quantum attack cost (proposed by NIST), the highest complexity in our work is 260 for the curve having degree 571 (which is comparable to AES-256 in terms of classical security), considerably below the post-quantum security level 1 threshold (of the order of 2156).
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses 3n+4⌊log2n⌋+O(1) logical qubits and 204n2log2n+O(n2) Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with 5n+4⌊log2n⌋+O(1) qubits and O(n3) Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys.
Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof.
In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.
The Shor's algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor's algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh-Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).