Formulae for arithmetic on genus 2 hyperelliptic curves (Q1772238)

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 also considers (Section 7) the case of mixes of the three coordinate systems. For each operation (addition and doubling) and each coordinate system tables are given detailing the steps and the number of field operations (multiplications, squarings and inversions) involved.