Quantum algorithm for solving discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves
- 22 August 2025
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Quantum Information
- Vol. 23 (06)
Abstract
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 [ ]-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.Keywords
Funding Information
- National Natural Science Foundation of China (12401696, 62272491, 62202475, 62002333)
- Guangdong Provincial Key Laboratory of Information Security Technology (2023B1212060026)
This publication has 19 references indexed in Scilit:
- Translating the Discrete Logarithm Problem on Jacobians of Genus 3 Hyperelliptic Curves with $(\ell ,\ell ,\ell )$-IsogeniesJournal of Cryptology, 2021
- On post-processing in the quantum algorithm for computing short discrete logarithmsDesigns, Codes and Cryptography, 2020
- Improved Quantum Circuits for Elliptic Curve Discrete Logarithms2020
- Quantum algorithm for solving hyperelliptic curve discrete logarithm problemQuantum Information Processing, 2020
- Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms2017
- Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers2017
- The effects of mixedness and entanglement on the properties of the entropic uncertainty in Heisenberg model with Dzyaloshinski–Moriya interactionQuantum Information Processing, 2016
- Elliptic and Hyperelliptic Curves: A Practical Security Analysis2014
- A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields1994
- Hyperelliptic cryptosystemsJournal of Cryptology, 1989