Paper 2026/106

New Quantum Circuits for ECDLP: Breaking Prime Elliptic Curve Cryptography

Abstract

This paper improves quantum circuits for realizing Shor's algorithm on elliptic curves. We present optimized quantum point addition circuits that focus on reducing circuit depth at the cost of using more qubits. Our implementation includes in-place and out-of-place point additions, considering both affine and projective coordinates, respectively. This significantly reduces the circuit depth and achieves about 58%-82% improvement in the qubit count $-$ \(T\)-depth product and 43%-87% improvement in the qubit count $-$ full depth product over previous works, including those of M. Roetteler et al. (Asiacrypt 2017) and T. Häner et al. (PQCrypto 2020). Based on these circuits, we construct Shor's algorithm and evaluate the post-quantum security of elliptic curve cryptography. Under the MAXDEPTH constraint proposed by NIST, which limits the maximum circuit depth to $2^{40}$, the maximum depth in our work is ${2^{28.9}}$ for the P-521 curve. For the total gate count and full depth product, a metric defined by NIST for evaluating quantum attack resistance, the maximum complexity for the same curve is ${2^{65.6}}$, far below the post-quantum security level~1 requirement of $2^{157}$. Beyond these logical analyses, we estimate the fault-tolerant costs (i.e., at the level of physical resources) for breaking elliptic curve cryptography. As one of our results, the P-224 curve (comparable to RSA-2048 in classical security) can be broken in 1.4 minutes using about 107 million physical qubits, or in 14.3 hours using about 670000 physical qubits.