Due to its smaller key sizes, the hyperelliptic curve cryptosystem (HCC) has gained significant interest in contemporary cryptography, which typically relies on the discrete logarithm problem associated with hyperelliptic curves (HCDLP) of genus 2 or 3. Regrettably, Shor’s algorithm poses a potential risk to this widely applied cryptosystem. However, the precise quantum cost of HCDLP of genus 3 remains untapped due to the intricate nature of the divisor addition formulas. In this paper, we leverage Riemann–Roch theorem and the properties of symmetric polynomials to design reversible divisor addition in the Jacobian group of genus 3. Then, we analyze the quantum resources required to solve HCDLP over [Formula: see text]-bit prime fields, provide concrete estimates for classical 128-bit and 256-bit security levels, and compare them with those needed for ECDLP. The findings demonstrate that solving HCDLP demands more quantum resources than solving ECDLP at the same security level.
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.
Abstract It is well-established that Shor’s algorithm can solve the discrete logarithm problem (DLP) in polynomial time. The hyperelliptic curve DLP (HCDLP) of genus 2 has found widespread industrial applications and remains an active research domain. In this work, we develop a quantum algorithm for solving HCDLP over binary fields
F2n F 2 n by adapting Shor’s algorithmic framework. The core innovation lies in our divisor addition implementation, which combines the geometric interpretation of divisor operations with symmetric polynomial techniques. Using representative parameters (
n=163,283,571 n = 163 , 283 , 571 ), we quantify the required quantum resources from the perspective of minimal qubit count, minimal T-gate usage, and minimal quantum depth. Furthermore, we compare the quantum resources required for solving HCDLP over binary fields with those for solving HCDLP over general prime fields and demonstrate the vulnerability of HCDLP-based cryptosystems to quantum attacks. Our analysis reveals that: (1) solving HCDLP over binary fields requires fewer quantum gates and less quantum depth compared to solving it over general prime fields; (2) the maximum achievable quantum depth for HCDLP attacks falls below NIST’s minimum security threshold of
240 2 40 for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the
2157 2 157 resources needed for AES-128 attacks.
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only
3n+6⌊log2n⌋+O(1) logical qubits and
1056n3/log2n+O(n2) Toffoli gates, where
n is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively.
The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only
2n+6⌊log2n⌋+O(1) logical qubits and
229n2+O(nlog2n) Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo
pand order
q. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of
pand
qup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of order
q, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs of
pand
q, extrapolated the circuit sizes obtained, and compared them for
p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if
pis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of
pin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with
p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group with
p=1024bits.
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.
An algorithm of Ekerå and Gärtner, inspired by Regev’s factoring algorithm, computes discrete logarithms in multiplicative groups of prime fields. Asymptotically, it has the same qubit and gate complexity as Shor’s algorithm but splits the computation into d independent, parallel runs. The optimal value of this parameter is d∼n where n is the bit size of the cryptographic group. We propose an extension of this algorithm to hyperelliptic curves. For curves of genus g∼n, which are not used in cryptography, we prove unconditionally that the optimal number of parallel runs d∼n can still be achieved. For genus-two curves, we propose a heuristic algorithm. While its runtime speedup is difficult to quantify in general, we show that it can be expected to use up to d=8 parallel runs for specific curves relevant to cryptography, including GLV-friendly and pairing-friendly curves.