Quantum algorithm for solving binary hyperelliptic curve discrete logarithm problem

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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:msub> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>163</mml:mn> <mml:mo>,</mml:mo> <mml:mn>283</mml:mn> <mml:mo>,</mml:mo> <mml:mn>571</mml:mn> </mml:mrow> </mml:math> ), 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>40</mml:mn> </mml:msup> </mml:math> for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the $$2^{157}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>157</mml:mn> </mml:msup> </mml:math> resources needed for AES-128 attacks.