.png){kind=icon}
.png){kind=icon}
Return
Quantum algorithm for solving binary hyperelliptic curve discrete logarithm problem
.png){kind=icon}
OA
AI
DOI：10.1186/s42400-025-00515-w.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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}$$ 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$$ ), 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}$$ for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the $$2^{157}$$ resources needed for AES-128 attacks.
Keywords:
Hyperelliptic Curves
Discrete Logarithm Problem
Shor’s Algorithm
Quantum Cryptanalysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
3.7
Papers:
574
Citations:
1.0K
View more organizations