Formulae for arithmetic on genus 2 hyperelliptic curves
type: Item
instance of: scholarly article
title: Formulae for arithmetic on genus 2 hyperelliptic curves
zbMATH Open document ID: 1068.14065
author: Tanja Lange
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2005-04-15T00:00:00Z
review text: The use of hyperelliptic curves in cryptography was first proposed by \textit{N. Koblitz} [J. Cryptology 1, 139--150 (1989; Zbl 0674.94010)] as an alternative to elliptic curve cryptography. Instead of the group of rational points of an elliptic curve defined over a finite field, the divisor class group, or equivalently the ideal class group, of a hyperelliptic curve needs to be considered as base for the discrete logarithm problem (DLP). Cantor's algorithm [cf. \textit{D. G. Cantor}, Math. Comp. 48, 95--101 (1987; Zbl 0613.14022)], generalized to even characteristic by Koblitz [loc.cit.], allows to efficiently perform the arithmetic for this group. The present paper is concerned with the particular case of genus two hyperelliptic curves. It is worth noting that only hyperelliptic curves of genus two and three are cryptographically useful: for higher genus a subexponential algorithm exists for solving the DLP, algorithm first presented by \textit{L. Adleman, J. DeMarrais} and \textit{M.-D. Huang} [Algorithmic number theory, ANTS-I, 1994, Lect. Notes Comput. Sci. 877, 28--40 (1994; Zbl 0829.11068)]. The purpose of the paper is to give explicit formulae to perform in the case of genus two curves the group operations of addition and doubling (of ideal classes) in order, in the author's words, \`\` to achieve similar or even higher speed compared to elliptic curves'', The paper does a careful analysis of different cases and examines and compares three different coordinate systems: affine coordinates (Section 4) where each group operation needs one inversion, projective coordinates (Section 5) which avoid the costly inversions but need more multiplications and those that the author calls new coordinates (equivalent to Jacobian coordinates in the elliptic case) which also avoid inversions and such that doubling is faster. For this coordinate system the paper treats separately the cases of odd characteristic (Section 6) and of even characteristic (Appendix). The author als…
Mathematics Subject Classification ID: 14Q05
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14H45
zbMATH DE Number: 2157511
zbMATH Keywords: public key cryptography
zbMATH Keywords: discrete logarithm
zbMATH Keywords: fast arithmetic
zbMATH Keywords: explicit formulae
reviewed by: Juan Tena Ayuso
describes a project that uses: HECC
MaRDI profile type: Publication
full work available at URL: s00200-004-0154-8
OpenAlex ID: W2153226320
cites work: Countermeasures against Differential Power Analysis for Hyperelliptic Curve Cryptosystems
cites work: Q4783728
cites work: Computing in the Jacobian of a Hyperelliptic Curve
cites work: Q4249254
cites work: Algorithmic Number Theory
cites work: On efficient implementation of FPGA-based hyperelliptic curve cryptosystems
cites work: Q5706769
cites work: Q4474195
cites work: Q4676184
cites work: Hyperelliptic cryptosystems
cites work: Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
cites work: Q4530230
cites work: SCA Resistant Parallel Explicit Formula for Addition and Doubling of Divisors in the Jacobian of Hyperelliptic Curves of Genus 2
cites work: Selected Areas in Cryptography
cites work: Advances in Cryptology - ASIACRYPT 2003
cites work: Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura
cites work: Q4409128
cites work: Q4875903
cites work: Algebraic function fields and codes
DOI: 10.1007/S00200-004-0154-8
Recommended article: Q4847910
Recommended article: Q4664851
Recommended article: A general framework for subexponential discrete logarithm algorithms
Recommended article: Rethinking low genus hyperelliptic Jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formulæ
Recommended article: A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over \(\text{GF}(q)\)
Recommended article: Q3635542
Recommended article: Q3840199
Recommended article: Q4373642
Recommended article: Empirical optimization of divisor arithmetic on hyperelliptic curves over \(\mathbb{F}_{2^m}\)
Recommended article: Q3374896
description: scientific article; zbMATH DE number 2157511