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.
Funding Information
  • National Natural Science Foundation of China (12401696, 62272491, 62202475, 62002333)
  • Guangdong Provincial Key Laboratory of Information Security Technology (2023B1212060026)