Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cybersecurity

Quantum algorithm for solving binary hyperelliptic curve discrete logarithm problem

Yan Huang, Du Zeng, Chao Chen, Zijian Zhou, Fangguo Zhang

Published Dec 17, 2025• 0 citations
Publisher

Abstract

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 $$\mathbb {F}_{2^n}$$ 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 $$2^{40}$$ 2 40 for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the $$2^{157}$$ 2 157 resources needed for AES-128 attacks.

DOI
10.1186/s42400-025-00515-w

Related papers

Quantum algorithm for solving discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves

Yan Huang, Fangguo Zhang, Zhaofeng Su +1 more

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.

International Journal of Quantum Information•Jul 30, 2025•1 citation

Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$

Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu +1 more

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$p$and order$q$. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of$p$and$q$up 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$p$and$q$, extrapolated the circuit sizes obtained, and compared them for$p = 2048$bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if$p$is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of$p$in 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 = 2048$bits under Shor's algorithm is almost equivalent to that of a safe-prime group with$p = 1024$bits.

arXiv:2503.23939•IEEE Transactions on Quantum Engineering•Jan 1, 2025•1 citation

Optimized quantum implementation of elliptic curve arithmetic over binary fields

Phillip Kaye

Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of $O(n^2)$, and a space-requirement of $O(n)$ qubits, where $n$ is the number of bits in the binary representation of $p$ (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).

arXiv:quant-ph/0407095•Quantum Information and Computation•Sep 1, 2005•27 citations

Regev’s Attack on Hyperelliptic Cryptosystems

Razvan Barbulescu, Gaetan Bisson

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.

Cryptography•Aug 28, 2026•0 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n)

Martin Rötteler, Rainer Steinwandt

Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for ${\mathbb F}_{2^n}$-multiplication in depth $\bigO(\log n)$ and for ${\mathbb F}_{2^n}$-inversion in depth $\bigO(\log^2 n)$.

Quantum Information and Computation•Jul 1, 2014•9 citations

Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation

Han Luo, Ziyi Yang, Ziruo Wang +2 more

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\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ 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\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ 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.

quant-pharXiv:2604.02311•Apr 3, 2026•0 citations
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\mathbb {F}_{2^n}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,571n = 163, 283, 571n=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 2402^{40}240 2 40 for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the 21572^{157}2157 2 157 resources needed for AES-128 attacks.
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.
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo ppp and Order qqq
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 modulopppand orderqqq. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs ofpppandqqqup 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 orderqqq, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs ofpppandqqq, extrapolated the circuit sizes obtained, and compared them forp=2048p = 2048p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same ifpppis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length ofpppin 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 withp=2048p = 2048p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group withp=1024p = 1024p=1024bits.
Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of O(n2)O(n^2)O(n2), and a space-requirement of O(n)O(n)O(n) qubits, where nnn is the number of bits in the binary representation of ppp (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).
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.
Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for F2n{\mathbb F}_{2^n}F2n​-multiplication in depth $\bigO(\log n)$ and for F2n{\mathbb F}_{2^n}F2n​-inversion in depth $\bigO(\log^2 n)$.
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⌊log⁡2n⌋+O(1)3n + 4\lfloor \log_2 n \rfloor + O(1)3n+4⌊log2​n⌋+O(1) logical qubits and 204n2log⁡2n+O(n2)204n^2\log_2 n + O(n^2)204n2log2​n+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⌊log⁡2n⌋+O(1)5n + 4\lfloor \log_2 n \rfloor + O(1)5n+4⌊log2​n⌋+O(1) qubits and O(n3)O(n^3)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.