1 Introduction

Elliptic curves are offered for the use of cryptographic applications by Miller in 1985 [1] and then by Koblitz in 1987 [2]. Two years later, Koblitz [3] proposed that hyperelliptic curves of arbitrary genus can replace elliptic curves in cryptosystems. However, this claim was falsified by Gaudry [4], who showed that security is conversely proportional to the genus. Gaudry’s work led the cryptographic studies to be focused on the genus 1 and genus 2 cases specifically.

A genus 1 curve is an elliptic curve. The points on an elliptic curve can be made into an abelian group. In comparison, a hyperelliptic curve of genus \(\ge 2\) is not an algebraic group by itself; however, its Jacobian becomes an abelian group under the binary operation divisor addition. A landmarking algorithm for divisor addition was introduced by David G. Cantor in 1987 [5, §3, §4]. Cantor’s algorithm is deterministic and works for arbitrary genus hyperelliptic curves. The algorithm operates on Mumford’s coordinates [6], a polynomial representation of divisors, and, consequently, makes heavy use of polynomial arithmetic, which makes it relatively inefficient for cryptographic applications in its original form.

Cantor’s algorithm is improved by others [3, 7,8,9], and explicit formulas for hyperelliptic curves of particular genus are studied. Lange reports in her thesis [10] that Spallek [11] proposed explicit formulas for the most common addition on genus 2 curves, later optimized by Harley [12] for odd characteristic curves. Lange [10] advanced Harley’s approach to arbitrary characteristics. In her thesis [10] and her following work [13], Lange presented a complete divisor addition algorithm on genus 2 hyperelliptic curves in a semi-explicit manner. Speed-ups [14,15,16] followed Lange’s work. The complete inversion-free projective formulas are proposed in [17,18,19]. In 2011, Costello and Lauter [20] derived new formulas for Cantor’s composition step, which incorporates solving linear systems instead of polynomial arithmetic. In 2014, Hisil and Costello [21] extended the work in [20] by introducing Jacobian coordinates, reducing the operation counts significantly. A recent work by Hu et al. [22] further extends the work in [21] to the case of degenerate divisor addition. Apart from these developments, which are the main focus of this work, Gaudry [23] provided explicit formulas to perform pseudo-group operations on genus 2 Kummer surfaces which are currently the speed leader in curve-based cryptosystems; see the implementation in [24]. However, some cryptographic constructions enforce the use of prime order genus 2 Jacobians, which do not allow a Kummer parameterization.

This work aims to present complete, inversion-free, and explicit formulas for divisor addition on genus 2 hyperelliptic curves. We closely follow Lange’s thesis [10] and present an algorithm in affine coordinates. We dispose of all polynomial arithmetic by expressing the operations explicitly. As the main contribution of this paper, we propose the formulas in Jacobian coordinates by exploiting [21]. The formulas combine the works in [21] and [22] and handle the missing cases for the sake of a complete inversion-free algorithm.

The paper is organized as follows. We briefly cover the fundamental background in Sect. 2. In Sect. 3, we present the complete and explicit formulas in affine coordinates for divisor addition as an algorithm. We present the inversion-free formulas in Jacobian coordinates for the missing cases in the literature; see Sect. 4. The cost analysis is given in Sect. 5. We derive our conclusions in Sect. 6. For the convenience of the reader, we attach computer-aided verification scripts in the Appendix.

2 Preliminaries

This section recalls basic definitions in the theory of hyperelliptic curves. Throughout this section, we assume that K is a field with \(\mathrm {char(K)} \ne 2\).

2.1 Hyperelliptic curves

A hyperelliptic curve H of genus g over K is a non-singular curve with the equation

$$\begin{aligned} H(K): y^2 + h(x)y = f(x) \end{aligned}$$
(1)

where \(h(x), f(x) \in K[x]\), \(\textrm{deg}(h) \le g\), \(\textrm{deg}(f) = 2g + 1\), and f(x) is monic. We denote the point set of H as \(H({{\bar{K}}}) = \{ (x,y) \in {{\bar{K}}} \times {{\bar{K}}}: y^2 + h(x)y = f(x) \} \cup \{ {\mathcal {O}}\}\) where \({\mathcal {O}}\) is the single point at infinity. Let \(P = (x, y)\), the negative of P is given as \(-P = (x, -y - h(x))\). In the following sections, we will use the notation \(f'(x)\) and \(f''(x)\) for the derivatives \(\frac{d f(x)}{d x}\) and \(\frac{d^2 f(x)}{d x^2}\), respectively.

Under the assumption \(\textrm{char}(K) \ne 2\), H can be put in the simplified form \(y^2 = f(x)\). Additionally, under the assumption \(\textrm{char}(K) \ne 5\), a genus 2 hyperelliptic curve can be put in the form

$$\begin{aligned} y^2 = x^5+a_3 x^3+a_2 x^2+a_1 x+a_0. \end{aligned}$$

We use the letter H in the following sections to address such a curve. We note here that the formulas presented in this work apply to \(\textrm{char}(K) = 5\) provided that \(\Delta _H \ne 0\), where \(\Delta \) is the discriminant of f(x).

2.2 Divisors

A divisor D on H is a formal sum

$$\begin{aligned} D = \sum _{P \in H({{\bar{K}}})} n_P (P) \end{aligned}$$

where only a finite number of \(n_P \in {\mathbb {Z}}\) are nonzero. The identity is called the zero divisor, denoted 0, with \(\forall P,\, n_P = 0\). The support of D is the set \(\textrm{supp}(D) = \{ P \in H(\mathbb {{{\bar{K}}}}): n_P \ne 0 \}\) and the degree of D is given by \(\textrm{deg}(D) = \sum _{P \in H({{\bar{K}}})} n_P\). The order of D at a point \(P \in H(\mathbb {{{\bar{K}}}})\) is the coefficient \(n_P\). A divisor of a function f is given by \((f) = \sum _{P \in H({{\bar{K}}})} \textrm{ord}_f(P)\) where \(\textrm{ord}_f(P)\) is the multiplicity of f on P.

A semi-reduced divisor has the form \(D = \sum n_P (P) - (\sum n_P) ({\mathcal {O}})\) where \(n_P \ge 0\) and \(-P \not \in \textrm{supp}(D)\) if \(P \in \textrm{supp}(D)\) unless \(P = -P\) with \(n_P = 1\). The inverse of a semi-reduced divisor is formulated as \(-D = \sum n_P (-P) - (\sum n_P) ({\mathcal {O}})\). A reduced divisor is a semi-reduced divisor with \(\sum n_P \le g\).

Throughout this paper we will refer to divisors with one and two points in their support (other than \({\mathcal {O}}\)) as; degenerate and non-degenerate divisors, respectively.

On H, the set of all divisors, denoted \(\textrm{Div}_{{{\bar{K}}}}(H)\); degree zero divisors, namely \(\textrm{Div}_{{{\bar{K}}}}^0(H)\); the principal divisors (divisors of a function), denoted \(\textrm{Prin}_{{{\bar{K}}}}(H)\) form a group. Moreover, the groups mentioned satisfy

$$\begin{aligned} \textrm{Prin}_{{{\bar{K}}}}(H) \subseteq \textrm{Div}_{{{\bar{K}}}}^0(H) \subseteq \textrm{Div}_{{{\bar{K}}}}(H). \end{aligned}$$

The quotient group \(\textrm{Div}_{{{\bar{K}}}}^0(H) / \textrm{Prin}_{\bar{K}}(H)\) is called the divisor class group, which is isomorphic to the Jacobian, denoted by J(H). Two divisors \(D_1, D_2 \in J(H)\) are equivalent, denoted \(D_1 \sim D_2\), if \(D_1 - D_2 \in \textrm{Prin}_{{{\bar{K}}}}(H)\). An important observation about the Jacobian is that each coset of it has a unique reduced divisor. Moreover, let \(D_1, D_2 \in J(H)\) be reduced divisors; then there exists a reduced divisor D such that \(D \sim D_1 + D_2\).

A reduced divisor \(D \in J(H)\) can be represented using the Mumford representation [6] with two polynomials as \(D = [u(x), v(x)]\) where the following assumptions hold

  1. (i)

    u is monic,

  2. (ii)

    \(\textrm{deg}(v) < \textrm{deg}(u) \le 2,\)

  3. (iii)

    \(u \mid v^2-f.\)

Mumford representation of a degenerate divisor \(D = (P_1) - ({\mathcal {O}})\) where \(P_1 = (x_1,y_1) \in H(K)\) has the form \(D = [x-x_1, y_1]\). Notice that the point in the support of a degenerate divisor is defined to be in H(K). For a non-degenerate divisor \(D = (P_1) + (P_2) - 2({\mathcal {O}})\) where \(P_1 = (x_1,y_1) \in H({{\bar{K}}})\) and \(P_2 = (x_2,y_2) \in H({{\bar{K}}})\), we will use the notation \(D = [x^2+q x + r, s x+t]\) with \(q, r, s, t \in K\). Here, assuming \(x_1 \ne x_2\),

$$\begin{aligned} q= & {} -x_1-x_2,\nonumber \\ r= & {} x_1 x_2, \nonumber \\ s= & {} \frac{y_1-y_2}{x_1-x_2}, \nonumber \\ t= & {} \frac{x_1 y_2-x_2 y_1}{x_1-x_2}, \end{aligned}$$
(2)

and otherwise

$$\begin{aligned} q= & {} -2 x_1, \nonumber \\ r= & {} x_1^2, \nonumber \\ s= & {} \frac{5 x_1^4+3 a_3 x_1^2+2 a_2 x_1+a_1}{2 y_1}, \nonumber \\ t= & {} \frac{-3 x_1^5-a_3 x_1^3+a_1 x_1+2 a_0}{2 y_1}. \end{aligned}$$
(3)

We note that \(y_1 = 0\) is not possible by definition of a reduced divisor whose support cannot contain opposite points. Finally, the identity is represented by the divisor [1, 0].

2.3 Cantor’s algorithm

In 1987, Cantor introduced an algorithm [5, §3, §4] to compute divisor addition on hyperelliptic curves, analogous to class group arithmetic, which is generalized and presented later by [3, 25]. Cantor’s algorithm uses polynomial arithmetic and works for all hyperelliptic curves of arbitrary genus. There are two stages of the algorithm; composition stage (Algorithm 1 lines 1–5) computes the semi-reduced divisor that is equal to the addition of the inputs; reduction stage (Algorithm 1 lines 6–12) computes the related unique reduced divisor. For further information, we refer the reader to the appendix of [26].

Algorithm 1
figure a

Cantor’s Algorithm [3, 5, 25]

Full size image

We use this algorithm to verify the correctness of the explicit formulas presented in Sect. 3. Since the computations involving these verifications are tedious, we prefer to carry them out succinctly with the help of computer algebra rather than pages-long algebraic investigation. We now present the complete and explicit group law in Sect. 3.

3 Explicit formulas for divisor addition

We start with basic facts which are referenced in the body of our algorithm.

Lemma 1

Let \(D_1\) and \(D_2\) be degenerate divisors such that \(D_1 \ne -D_2\). Then, \(D_1 + D_2\) is non-degenerate.

Proof

This is simply Mumford’s composition. \(\square \)

Lemma 2

Let \(D_1\) be a degenerate and \(D_2\) be a non-degenerate divisor. Then, \(D_1 + D_2\) cannot be the zero divisor.

Proof

Let \(D_1 = [x-x_1, y_1]\) and \(D_2 = [x^2+q_2 x+r_2, s_2 x+t_2]\) as in the definition of the lemma. \(-D_1 = [x-x_1, -y_1]\) is degenerate by construction. Assume that \(D_1 + D_2 = 0\). So, \(D_2 = -D_1\). However, \(D_2\) is non-degenerate, contradiction. Thus, the addition of a degenerate divisor with a non-degenerate divisor cannot give the zero divisor. \(\square \)

Lemma 3

There exists no degenerate divisor \(D \in J(H)\) such that \(3D = 0\).

Proof

Let D be a divisor in J(H) such that \(3D = 0\). Assume that \(D = (P) - ({\mathcal {O}})\) is degenerate. So, \(2D = (-P) - ({\mathcal {O}})\). Nevertheless, by Lemma 1, 2D must be non-degenerate while \((-P) - ({\mathcal {O}})\) is clearly degenerate. This is a contradiction by Lemma 2. Therefore, D must be non-degenerate. \(\square \)

In the remainder of this section, we define two input divisors \(D_1\), \(D_2\), and an output divisor \(D_3 = D_1 + D_2\), and examine the complete formulas for \(D_3\). We set divisor \(D_3 = (P_5) - ({\mathcal {O}}) = [x-x_5, y_5]\) if \(D_3\) is degenerate and \(D_3 = (P_5) + (P_6) - 2({\mathcal {O}}) = [x^2+q_3 x+r_3, s_3 x+t_3]\) if non-degenerate.

3.1 Trivial inputs

Here, we investigate the output when at least one of the input divisors is the identity, namely the zero divisor. The cases are trivial, i.e., if one input divisor is 0 then the output is the other input divisor (which is also true when both inputs are 0).

3.2 Degenerate/degenerate inputs

Let \(D_1 = (P_1) - ({\mathcal {O}}) = [x-x_1,y_1]\) and \(D_2 = (P_3) - ({\mathcal {O}}) = [x-x_3,y_3]\). Now, we investigate whether \(D_1\) and \(D_2\) are joint by examining the points at their support: \(P_1 = (x_1, y_1)\) and \(P_3 = (x_3, y_3)\) in H(K).

  • \(\underline{\text {Case}\ x_1 = x_3}\): The input divisors are joint with \(P_1 = \pm P_3\).

    • \(\underline{\text {Case}\ y_1 = -y_3}\): We have \(P_1 = -P_3\). Thus, \(D_1 = -D_2\) and \(D_3 = 0\).

    • \(\underline{\text {Case}\ y_1 = y_3}\): We have \(P_1 = P_3\). Therefore, \(D_1 = D_2\) and \(D_3 = 2D_1 = 2(P_1) - 2({\mathcal {O}}) = [x^2+q_3 x+r_3,\ s_3 x+t_3]\) is non-degenerate and can be computed with Mumford’s composition (3). [Script 2] in the Appendix verifies the correctness of this formula.

  • \(\underline{\text {Case}\ x_1 \ne x_3}\): The input divisors are disjoint, and \(D_3 = [x^2+q_3 x+r_3,\ s_3 x+t_3]\) can be computed with Mumford’s composition (2). [Script 3] in the Appendix verifies the correctness of this formula.

Since the conditions above exhaust all possible cases, a degenerate output is not possible, as stated in Lemma 1. Note that the case where \(x_1 = x_3\) and \(y_1 = y_3 = 0\) (special point doubling) is handled by “\(\underline{\text {Case}\ y_1 = -y_3}\)”.

3.3 Degenerate/non-degenerate inputs

We continue with the addition of a non-degenerate and a degenerate divisor. We assume that the inputs are swapped, if necessary, in order to have \(D_1\) and \(D_2\), degenerate and non-degenerate, respectively. Let \(D_1 = (P_1) - ({\mathcal {O}}) = [x-x_1,y_1]\) and \(D_2 = (P_3) + (P_4) - 2({\mathcal {O}}) = [u_2(x), v_2(x)] = [x^2+q_2 x+r_2,\ s_2 x+t_2]\) be divisors in J(H) where \(P_1 = (x_1, y_1) \in \) \(H(K) - \{{\mathcal {O}}\}\).

  • \(\underline{\text {Case}\ u_2(x_1) = 0}\): Since \(x_1 \in K\) is a root of the polynomial \(u_2(x)\), we deduce that \(u_2(x)\) must have the roots \(x_3, x_4 \in K\) satisfying \((x_3-x_1) (x_4-x_1) = 0\), though we do not know \(x_3\) and \(x_4\) explicitly. Without loss of generality, we assume \(x_3 = x_1\). Now, we compute, \(y_3 = v_2(x_1)\), \(x_4 = -q_2-x_3\), and \(y_4 = v_2(x_4)\). Clearly, \(x_1, y_1, x_3, y_3, x_4, y_4 \in K\). Before we proceed to investigate the following subcases, we note that \(P_3 = (x_3, y_3)\) and \(P_4 = (x_4, y_4)\) are in \(H(K) - \{{\mathcal {O}}\}\).

    • \(\underline{\text {Case}\ y_1 = -y_3}\): We have \(P_1 = -P_3\). The points \(P_1\) and \(P_3\) cancel out each other which results in the degenerate output \(D_3 = (P_4) - ({\mathcal {O}}) = [x-x_4, y_4]\).

    • \(\underline{\text {Case}\ y_1 = y_3}\): Here \(P_1 = P_3\) and we continue with investigating the rare case \(P_1 = P_3 = P_4\).

      1. *

        \(\underline{\text {Case}\ x_1 = x_4}\): We have \(P_1 = \pm P_4\). Now, \(P_1 = -P_4\) is not possible, because otherwise \(D_2 = (P_1) + (-P_1) - 2({\mathcal {O}})\) would be non-reduced. Thus, \(P_1 = P_3 = P_4\) which leads us to the formula \(D_3 = 3(P_1) - 3({\mathcal {O}}) = 3D_1\) in [22, §3.2] with

        $$\begin{aligned} \begin{aligned} q_3 =&\, 3 x_1-A^2, \\ r_3 =&\, a_3-2 A B+3 x_1 (q_3-x_1), \\ s_3 =&\, A q_3-B, \\ t_3 =&\, A r_3-C \end{aligned} \end{aligned}$$
        (4)

        where

        $$\begin{aligned} \begin{aligned} A&=\, \frac{2 y_1^2 f''(x_1)-f'(x_1)^2}{8 y_1^3}, \\ B&=\, \frac{f'(x_1)}{2 y_1}-2 A x_1, \\ C&=\, y_1-A x_1^2-B x_1. \end{aligned} \end{aligned}$$

        Note that \(D_1 = (P_1) - ({\mathcal {O}})\) cannot have order threeFootnote 1. Note also that the denominators of \(q_3\), \(r_3\), \(s_3\), and \(t_3\) are all powers of \(y_1\). Here, \(y_1 \ne 0\) because the case \(y_1 = 0\) is handled in “\(\underline{\text {Case}\ y_1 = -y_3}\)”. Therefore, the denominators never vanish. [Script 4] in the Appendix verifies the correctness of this formula.

      2. *

        \(\underline{\text {Case}\ x_1 \ne x_4}\): Now, \(P_4\) is disjoint with other points in both supports. So, the addition consists of the doubling of \(D_1 = (P_1) - ({\mathcal {O}})\) and the accumulation of \((P_4) - ({\mathcal {O}})\) on \(2D_1\). In this case, we compute divisor \(2(P_1) - 2({\mathcal {O}}) = [x^2+q x + r, s x+t]\) as in Eq. (3). Note that the denominator \(y_1\) in Eq. (3) does not vanish since the case \(y_1 = 0\) is again handled in “\(\underline{\text {Case}\ y_1 = -y_3}\)”. Now, \(D_3 = 2(P_1) + (P_4) - 3({\mathcal {O}})\) can be computed with the generic formula in [22, §3.1] as follows,

        $$\begin{aligned} \begin{aligned} q_3 =&\, x_4-q-A^2, \\ r_3 =&\, a_3+q^2-r-A (B+s) \\&+x_4 q_3, \\ s_3 =&\, A q_3-B, \\ t_3 =&\, A r_3-C \end{aligned} \end{aligned}$$
        (5)

        where

        $$\begin{aligned} \begin{aligned} A&=\, \frac{y_4-s x_4-t}{x_4^2+q x_4+r}, \\ B&=\, s+q A, \\ C&=\, t+r A. \end{aligned} \end{aligned}$$

        Notice that the denominator of A vanishes only when \(P_4\) is in the support of divisor \(2(P_1) - 2({\mathcal {O}})\), which is in contradiction with the assumption \(x_1 \ne x_4\). [Script 5] in the Appendix verifies the correctness of this formula.

  • \(\underline{\text {Case}\ u_2(x_1) \ne 0}\): In this case, we have disjoint divisors, and the generic addition formula in [22, §3.1] applies directly. We have

    $$\begin{aligned} \begin{aligned} q_3 =&\, x_1-q_2-A^2, \\ r_3 =&\, a_3+q_2^2-r_2-A (B+s_2)+x_1 q_3, \\ s_3 =&\, A q_3-B, \\ t_3 =&\, A r_3-C \end{aligned} \end{aligned}$$
    (6)

    where

    $$\begin{aligned} \begin{aligned} A&=\, \frac{y_1-s_2 x_1-t_2}{x_1^2+q_2 x_1+r_2}, \\ B&=\,s_2+q_2 A, \\ C&=\, t_2+r_2 A. \end{aligned} \end{aligned}$$

    Note that \(x_1^2+q_2 x_1+r_2 = u_2(x_1) \ne 0\). [Script 6] in the Appendix verifies the correctness of this formula.

Finally, we remark that the addition of a non-degenerate divisor with a degenerate divisor cannot give the zero divisor by Lemma 2.

3.4 Non-degenerate/non-degenerate inputs

In this section, we examine the last and most common addition, where both inputs are non-degenerate. Let \(D_1 = (P_1) + (P_2) - 2({\mathcal {O}}) = [u_1(x), v_1(x)] = [x^2+q_1 x+r_1, s_1 x+t_1]\), and \(D_2 = (P_3) + (P_4) - 2({\mathcal {O}}) = [u_2(x), v_2(x)] = [x^2+q_2 x+r_2, s_2 x+t_2]\).

  • \(\underline{\text {Case}\ u_1 = u_2}\): This implies that \(\{x_1, x_2\} = \{x_3, x_4\}\), though we do not know \(x_i\) and \(y_i\) explicitly. We continue by investigating \(v_1\) and \(v_2\).

    • \(\underline{\text {Case}\ v_1 = -v_2}\): We have either \(v_1(x_1) = -v_2(x_3)\) and \(v_1(x_2) = -v_2(x_4)\) or \(v_1(x_1) = -v_2(x_4)\) and \(v_1(x_2) = -v_2(x_3)\) which implies that \(\{y_1, y_2\} = \{-y_3, -y_4\}\). Thus, \(D_1 = -D_2\) and \(D_3 = 0\).

    • \(\underline{\text {Case}\ v_1 = v_2}\): Similarly, we have either \(v_1(x_1) = v_2(x_3)\) and \(v_1(x_2) = v_2(x_4)\) or \(v_1(x_1) = v_2(x_4)\) and \(v_1(x_2) = v_2(x_3)\) which implies that \(\{y_1, y_2\} = \{y_3, y_4\}\). Also, note that \(y_1 \ne 0\) or \(y_2 \ne 0\) because otherwise \(\{y_1,y_2\} = \{-y_3,-y_4\}\), which is covered in “\(\underline{\text {Case}\ v_1 = -v_2}\)”. Thus, \(D_1 = D_2\) and the doubling operation \(D_3 = 2D_1\) is present. We define the common subexpressions A, B, and C for doubling as in [21, §5].

      $$\begin{aligned} \begin{aligned} A =&\, \left( (q_1^2-4 r_1+a_3) q_1-a_2+s_1^2\right) (q_1 s_1-t_1) \\&\, +(3 q_1^2-2 r_1+a_3) r_1 s_1, \\ B =&\, 2 (q_1 s_1-t_1) t_1-2 r_1 s_1^2, \\ C =&\, \left( (q_1^2-4 r_1+a_3) q_1-a_2+s_1^2\right) s_1 \\ =&\, +(3 q_1^2-2 r_1+a_3) t_1. \end{aligned} \end{aligned}$$
      (7)

      The doubling formula in [21, §5] is not defined for two cases; when the output is degenerate and when the denominator B vanishes. The approach in [10, §3.1, §3.4] properly handles each case leaving a minor use of polynomial arithmetic. Our little contribution here is to eliminate the polynomial arithmetic and carry out the computation solely with field arithmetic. Therefore, we need to pinpoint algebraically the case where the output is degenerate or non-degenerate. These cases are given as follows.

      1. *

        \(\underline{\text {Case}\ B = 0}\): B is equal to \(-2 y_1 y_2\) which corresponds to the \(\textrm{resultant}(h+2 v_1, u_1)\) calculated in [10, §3.1]. Now, \(B=0\) induces at least one of the points in the support being a special point which gives the identity when doubled. We assume \(y_2 = 0\) without loss of generality and compute \(x_2\) by explicitly calculating \(\text {gcd}(u_1,v_1)=x-x_1\) as in [10, §3.1]. We have \(x_2=-t_1/s_1\), \(x_1=-q_1-x_2\) and \(y_1=v_1(x_1)\). Finally, \(D_3 = 2(P_1)-2({\mathcal {O}})\) can be computed with the composition formula (3).

      2. *

        \(\underline{\text {Case}\ B \ne 0}\): Here, the points in the support are not special points, but a degenerate output is possible. The line “\(s = k/(h + 2 v) \bmod u\)” of Section 3.4 of [10] is subject to accidental cancellation, which may lead to a degenerate output that is again handled implicitly. An explicit approach is to detect the degenerate output beforehand and to generate new formulas free of polynomial arithmetic. For this purpose, we investigate the common subexpression C.

      3. *

        \(\underline{\text {Case}\ C = 0}\): As stated in [22, §3.3], \(C = 0\) implies a degenerate output since the coefficient of the degree 3 term in the intersection parabola \(y = d x^3+a x^2+b x+c\) is equal to \(-C/B\) [22]. The corrected version of the formula in [22, §3.3] is as followsFootnote 2

        $$\begin{aligned} \begin{aligned} x_5 =&\, 2 q_1+\frac{A^2}{B^2}, \\ y_5 =&\, x_5 (q_1+x_5)\frac{A}{B}- x_5 s_1+r_1 \frac{A}{B}-t_1. \end{aligned} \end{aligned}$$
        (8)

        [Script 7] in the Appendix verifies the correctness of this formula.

      4. *

        \(\underline{\text {Case}\ C \ne 0}\): In this case, the doubling formula in [21, §5] applies for the non-degenerate output \(D_3\) [10, 20].

        $$\begin{aligned} \begin{aligned} q_3 =&\, 2 \frac{A}{C}-\frac{B^2}{C^2}, \\ r_3 =&\, \frac{A^2}{C^2}+2 q_1 \frac{B^2}{C^2}-2 s_1 \frac{B}{C}, \\ s_3 =&\, (r_1-r_3) \frac{C}{B}-q_3 (q_1-q_3) \frac{C}{B} \\&\, +(q_1-q_3) \frac{A}{B}-s_1, \\ t_3 =&\, (r_1-r_3) \frac{A}{B}-r_3 (q_1-q_3) \frac{C}{B}-t_1. \end{aligned} \end{aligned}$$
        (9)

        [Script 8] in the Appendix verifies the correctness of this formula.

    • \(\underline{\text {Case}\ v_1 \ne \pm v_2}\): Since \(\{x_1, x_2\} = \{x_3, x_4\}\) and \(P_i = (x_i, y_i)\) are points on the curve, we have \(\{y_1, y_2\} = \{\pm y_3, \pm y_4\}\). This gives us four configurations

      1. (i)

        \(\{y_1, y_2\} = \{y_3, y_4\}\),

      2. (ii)

        \(\{y_1, y_2\} = \{-y_3, y_4\}\),

      3. (iii)

        \(\{y_1, y_2\} = \{y_3, -y_4\}\), and

      4. (iv)

        \(\{y_1, y_2\} = \{-y_3, -y_4\}\).

      Notice that (i) implies \(v_1 = v_2\) and (iv) implies \(v_1 = -v_2\). Thus, either (ii) or (iii) holds in this case but not (i) and (iv). Without loss of generality, we may assume \(P_2 = -P_4\) and so \(D_3 = 2(P_1) - 2({\mathcal {O}})\). We compute \(x_1 = (t_1-t_2)/(s_2-s_1)\) and \(y_1 = v_1(x_1)\) as in [10, §3.1]. The doubling of \(P_1\) can be done with the formula (3).

  • \(\underline{\text {Case}\ u_1 \ne u_2}\): Here, the supports of \(D_1\) and \(D_2\) are not identical. Thus, we continue with the addition formulas. We define the common subexpressions A, B, and C as in [21, §5].

    $$\begin{aligned} \begin{aligned} A =&\, (t_1-t_2) (q_2 (q_1-q_2) \\&\, -(r_1-r_2))-r_2 (q_1-q_2) (s_1-s_2), \\ B =&\, (r_1-r_2) (q_2 (q_1-q_2) \\&\, -(r_1-r_2))-r_2 (q_1-q_2)^2, \\ C =&\, (q_1-q_2) (t_1-t_2)-(r_1-r_2) (s_1-s_2). \end{aligned} \end{aligned}$$
    (10)

    As before, we try to detect the cases where the addition formula in [21, §5] is not defined. For that purpose, we investigate the common subexpressions B and C. The reason that we concentrate on B is illuminated when we write B in terms of \(x_1\), \(x_2\), \(x_3\), and \(x_4\) which is given as follows,

    $$\begin{aligned} B = -(x_2-x_4) (x_2-x_3) (x_1-x_4) (x_1-x_3). \end{aligned}$$

    The value \(-B\) corresponds to the \(\textrm{resultant}(u_1,u_2)\) in [10, §3.1] and becomes zero when \(\{P_1, P_2\} \cap \{ \pm P_3, \pm P_4 \} \ne \emptyset \).

    • \(\underline{\text {Case}\ B = 0}\): The supports of the input divisors are joint. Without loss of generality we may assume \(x_1=x_3\) and calculate \(x_1 = -(r_1-r_2)/(q_1-q_2)\),  \(y_1 = v_1(x_1)\),  \(x_3 = x_1\),  \(y_3 = v_2(x_3)\),  \(x_2 = -q_1-x_1\),  \(y_2 = v_1(x_2)\),  \(x_4 = -q_2-x_3\),  and \(y_4 = v_2(x_4)\) as in [10, §3.1].

      1. *

        \(\underline{\text {Case}\ y_1 = -y_3}\): Here, \(P_1 = (x_1, y_1)\) and \(P_3 = (x_1, -y_1)\) are negatives of each other. So, \(D_3 = (P_2) + (P_4) - 2({\mathcal {O}})\) can be calculated with (2).

      2. *

        \(\underline{\text {Case}\ y_1 = y_3}\): In this case, \(P_1 = (x_1, y_1)\) can be doubled with (3) and \(P_2 = (x_2, y_2)\) and \(P_4 = (x_4, y_4)\) can be added one by one using the procedure in Sect. 3.3.

    • \(\underline{\text {Case}\ B \ne 0}\): Here the supports of the divisors are disjoint. We continue with the investigation of degenerate output. An accidental cancellation occurs in the addition formulas [10, §3.2] when the output is degenerate, just as in doubling. In [22, §3.3], it is stated that \(C=0\) implies a degenerate output since the coefficient \(d = -C/B = 0\) of the intersection parabola \(y = d x^3+a x^2+b x+c\) annihilates the degree 3 term.

      1. *

        \(\underline{\text {Case}\ C = 0}\): The corrected version of the formula in [22, §3.3] is as followsFootnote 3

        $$\begin{aligned} \begin{aligned} x_5 =&\, (q_1+q_2)+\frac{A^2}{B^2}, \\ y_5 =&\, x_5 (q_1+x_5)\frac{A}{B}- x_5 s_1+r_1 \frac{A}{B}-t_1. \end{aligned} \end{aligned}$$
        (11)

        [Script 9] in the Appendix verifies the correctness of this formula.

      2. *

        \(\underline{\text {Case}\ C \ne 0}\): The addition formula in [21, §5] applies. Furthermore, this is the most frequent case in most cryptographic applications. We reproduce the formulas here to keep the text self-contained.

        $$\begin{aligned} \begin{aligned} q_3 =&\, (q_1-q_2)+2\frac{A}{C}-\frac{B^2}{C^2}, \\ r_3 =&\, (q_1-q_2) \frac{A}{C}+\frac{A^2}{C^2}+(q_1+q_2) \frac{B^2}{C^2} \\&-(s_1+s_2) \frac{B}{C}, \end{aligned}\nonumber \\ \begin{aligned} s_3 =&\, (r_1-r_3) \frac{C}{B}-q_3 (q_1-q_3) \frac{C}{B} \\&+(q_1-q_3) \frac{A}{B}-s_1, \\ t_3 =&\, (r_1-r_3) \frac{A}{B}-r_3 (q_1-q_3) \frac{C}{B}-t_1. \\ \end{aligned} \end{aligned}$$
        (12)

        [Script 10] in the Appendix verifies the correctness of this formula.

4 Jacobian coordinates

The first inversion-free projective formulas for divisor addition on genus 2 hyperelliptic curves are proposed by Lange in [17] where an affine divisor \((q_1,r_1,s_1,t_1)\) is represented as \((Q_1,R_1,S_1,T_1,Z_1)\) satisfying \((\lambda Q_1 :\lambda R_1 :\lambda S_1 :\lambda T_1 : \lambda Z_1) = (q_1 :r_1 :s_1 :t_1 :1)\) and \(\lambda \ne 0\). Lange improved the operation counts by adopting a new weighting where \((q_1,r_1,s_1,t_1)\) is represented as \((Q_1,R_1,S_1,T_1,Z_1,W_1)\) satisfying \((\lambda ^2 Q_1 :\lambda ^2 R_1 :\lambda ^3 \mu S_1 :\lambda ^3 \mu T_1 :\lambda Z_1 :\mu W_1) = (q_1 :r_1 :s_1 :t_1 :1 :1)\) and \(\lambda , \mu \ne 0\) in [19].

Hisil and Costello introduced Jacobian coordinates for hyperelliptic curves of genus 2 in [21]. Their work transfers the weights of x and y coordinates of H across Mumford coordinates and provides a weighted projective representation of divisors. Let \((q_1,r_1,s_1,t_1)\) represent an affine non-degenerate divisor \([x^2+q_1 x+r_1, s_1 x+t_1] \in J(H)\). Such divisor \((q_1,r_1,s_1,t_1)\) is represented as \((Q_1,R_1,S_1,T_1,Z_1,W_1)\) satisfying \((\lambda ^2 Q_1 :\lambda ^4 R_1 :\lambda ^3 \mu S_1 : \lambda ^5 \mu T_1 :\lambda Z_1 :\mu W_1) = (q_1 :r_1 :s_1 :t_1 :1 :1)\) and \(\lambda , \mu \ne 0\). We refer to [21] for further details.

In this work, we represent degenerate divisors following the same construction. Let \((x_1,y_1)\) represent an affine degenerate divisor \([x-x_1, y_1] \in J(H)\). By adapting the weights above to x, y coordinates, we represent \((x_1,y_1)\) as \((X_1,Y_1,Z_1,W_1)\) satisfying \((\lambda ^2 X_1 :\lambda ^5 \mu Y_1 :\lambda Z :\mu W) = (x_1 :y_1 :1 :1)\) and \(\lambda , \mu \ne 0\).

The inversion-free formulas in weighted Jacobian coordinates are given only for the most common addition and doubling (corresponding to Eqs. (9) and (12) resp.) in [21], and only for the cases that contain degenerate divisors in [22]. Moreover, the degenerate divisors in [22] are considered to be in affine coordinates.

By following the same order as in Sect. 3, we present inversion-free formulas with all divisors in weighted Jacobian coordinates for the sake of a complete inversion-free divisor addition algorithm. We omit the cases that are already given in [21, 22] by referring the reader to the mentioned papers. Finally, a complete and inversion-free divisor addition algorithm is given in https://github.com/ozbayelif/jac-on-jac in Magma [27]. The code is optimized to reduce operation counts by eliminating the common subexpressions in the formulas. Throughout this section, we will represent the output divisor as \(D_3 = (P_5) + (P_6) - 2({\mathcal {O}}) = (Q_3, R_3, S_3, T_3, Z_3, W_3)\) if non-degenerate and as \(D_3 = (P_5) - ({\mathcal {O}}) = (X_5, Y_5, Z_5, W_5)\) if degenerate.

4.1 Degenerate/degenerate inputs

Let the input divisors be represented as \(D_1 {=} (X_1, Y_1, Z_1, W_1)\) and \(D_2 = (X_2, Y_2, Z_2, W_2)\). The inversion-free formulas of the two cases \(D_1 = D_2\) and \(D_1 \ne D_2\) are given in [22, §4.4]; however, the input divisors are considered to be in affine coordinates.

The formula for the case \(D_1 = D_2\) given below corresponds to Eq. (3).

$$\begin{aligned} \begin{aligned} {Q}_{3}&= - 2 {X}_{1} \\ {R}_{3}&= {X}_{1}^{2} \\ {S}_{3}&= \left( {a}_{1} {Z}_{1}^{8} + 2 {a}_{2} {X}_{1} {Z}_{1}^{6} + 3 {a}_{3} {X}_{1}^{2} {Z}_{1}^{4} + 5 {X}_{1}^{4} \right) {W}_{1} \\ {T}_{3}&= \left( 2 {a}_{0} {Z}_{1}^{10} + {a}_{1} {X}_{1} {Z}_{1}^{8} - {a}_{3} {X}_{1}^{3} {Z}_{1}^{4} - 3 {X}_{1}^{5} \right) {W}_{1} \\ {Z}_{3}&= {Z}_{1} \\ {W}_{3}&= 2 {Y}_{1} \end{aligned} \end{aligned}$$
(13)

The inversion-free version of Eq. (2) for \(D_1 \ne D_2\) is as follows.

$$\begin{aligned} \begin{aligned} {Q}_{3}&= - {X}_{1} {Z}_{2}^{2} - {X}_{2} {Z}_{1}^{2} \\ {R}_{3}&= {X}_{1} {Z}_{2}^{2} {X}_{2} {Z}_{1}^{2} \\ {S}_{3}&= {Y}_{1} {Z}_{2}^{5} {W}_{2} - {Y}_{2} {Z}_{1}^{5} {W}_{1} \\ {T}_{3}&= \left( {X}_{1} {Y}_{2} {Z}_{1}^{3} {W}_{1} - {X}_{2} {Y}_{1} {Z}_{2}^{3} {W}_{2} \right) {Z}_{1}^{2} {Z}_{2}^{2} \\ {Z}_{3}&= {Z}_{1} {Z}_{2} \\ {W}_{3}&= \left( {X}_{1} {Z}_{2}^{2} - {X}_{2} {Z}_{1}^{2} \right) {W}_{1} {W}_{2} \end{aligned} \end{aligned}$$
(14)

4.2 Degenerate/non-degenerate inputs

Let the input divisors be represented as \(D_1 = (P_1) - ({\mathcal {O}}) = (X_1, Y_1, Z_1, W_1)\) and \(D_2 = (P_3) - (P_4) - 2({\mathcal {O}}) = (Q_2, R_2, S_2, T_2, Z_2, W_2)\). As investigated in Sect. 3.3, there exist 4 cases that can occur.

The case where \(P_1 = - P_3\) gives the degenerate output \(D_3 = (P_4) - ({\mathcal {O}})\) whose coordinates can be recovered, as described in “Case \(u_2(x_1) = 0\)”, with the following formula.

$$\begin{aligned} \begin{aligned} {X}_{3}&= {X}_{1} \\ {Y}_{3}&= {S}_{2} {Z}_{1}^{3} {X}_{3} {Z}_{2}^{2} + {T}_{2} {Z}_{1}^{5} \\ {Z}_{3}&= {Z}_{1} \\ {W}_{3}&= {W}_{2} {Z}_{2}^{5} \end{aligned} \quad \begin{aligned} {X}_{4}&= - {Q}_{2} {Z}_{1}^{2} - {X}_{3} {Z}_{2}^{2} \\ {Y}_{4}&= {S}_{2} {Z}_{1}^{3} {X}_{4} + {T}_{2} {Z}_{1}^{5} \\ {Z}_{4}&= {Z}_{1} {Z}_{2} \\ {W}_{4}&= {W}_{2} \end{aligned} \end{aligned}$$
(15)

The inversion-free tripling formula in [22], for \(P_1 = P_3 = P_4\), leaves the point \(P_1\) to be tripled in affine coordinates. Here, the fully weighted formula is given, which corresponds to Eq. (4).

$$\begin{aligned}{} & {} \begin{aligned} {F'}&= \left( {a}_{1} {Z}_{1}^{8} + 2 {a}_{2} {X}_{1} {Z}_{1}^{6} + 3 {a}_{3} {X}_{1}^{2} {Z}_{1}^{4} + 5 {X}_{1}^{4} \right) {W}_{1} \\ {F''}&= 2 \left( {a}_{2} {Z}_{1}^{6} + 3 {a}_{3} {X}_{1} {Z}_{1}^{4} + 10 {X}_{1}^{3} \right) \\ K&= 8 {Y}_{1}^{3} \\ A&= \left( 2 {F''} {Y}_{1}^{2} - {F'}^{2} \right) {W}_{1} \\ B&= 2 {F'} {Y}_{1}^{2} - A {X}_{1} \\ C&= {Y}_{1} K - \left( A {X}_{1} + 2 B \right) {X}_{1} {W}_{1} \\ {Z}_{3}&= K {Z}_{1} \\ {Q}_{3}&= 3 {X}_{1} K^{2} - A^{2} \\ {R}_{3}&= {a}_{3} {Z}_{3}^{4} - \left( 4 A B - 3 {X}_{1} \left( {Q}_{3} - {X}_{1} K^{2} \right) \right) K^{2} \end{aligned}\nonumber \\{} & {} \begin{aligned} {S}_{3}&= A {Q}_{3} {W}_{1} - 2 B K^{2} {W}_{1} \\ {T}_{3}&= A {R}_{3} {W}_{1} - C K^{4} \\ {W}_{3}&= {W}_{1} \end{aligned} \end{aligned}$$
(16)

The following case is where \(P_1 = P_3 \ne P_4\). Let \(2 D_1 = (Q, R, S, T, Z, W)\) be computed with Eq. (13). Then, \(2 D_1\) and \((P_4) - ({\mathcal {O}})\) can be added, as in Eq. (5), with the below formula.

$$\begin{aligned} \begin{aligned} K&= \left( Q Z^{2} {X}_{4} {Z}_{4}^{2} + {X}_{4}^{2} Z^{4} + R {Z}_{4}^{4} \right) {W}_{4} \\ A&= {Y}_{4} Z^{5} W - \left( S {Z}_{4}^{3} {X}_{4} Z^{2} + T {Z}_{4}^{5} \right) {W}_{4} \\ B&= S K {Z}_{4} + A Q \\ C&= T K {Z}_{4} + A R \\ L&= K {Z}_{4} W \\ M&= K Z W \\ {Q}_{3}&= {X}_{4} M^{2} - Q L^{2} - A^{2} \\ {R}_{3}&= \left( {a}_{3} Z^{4} + Q^{2} - R \right) L^{4} - A \left( B + K S {Z}_{4} \right) L^{2} \\&\quad + {Q}_{3} {X}_{4} M^{2} \\ {S}_{3}&= A {Q}_{3} - B L^{2} \\ {T}_{3}&= A {R}_{3} - C L^{4} \\ {Z}_{3}&= K Z {Z}_{4} W \\ {W}_{3}&= 1 \end{aligned} \end{aligned}$$
(17)

The last case corresponds to Eq. (6), where the supports are disjoint. The formula in [22] leaves \(P_1\) in affine coordinates. The fully-weighted formula is given below.

$$\begin{aligned} \begin{aligned} K&= \left( {Q}_{2} {Z}_{2}^{2} {X}_{1} {Z}_{1}^{2} + {X}_{1}^{2} {Z}_{2}^{4} + {R}_{2} {Z}_{1}^{4} \right) {W}_{1} \\ A&= {Y}_{1} {Z}_{2}^{5} {W}_{2} - \left( {S}_{2} {Z}_{1}^{3} {X}_{1} {Z}_{2}^{2} + {T}_{2} {Z}_{1}^{5} \right) {W}_{1} \\ B&= {S}_{2} K {Z}_{1} + A {Q}_{2} \\ C&= {T}_{2} K {Z}_{1} + A {R}_{2} \\ L&= K {Z}_{1} {W}_{2} \\ M&= K {Z}_{2} {W}_{2} \\ {Q}_{3}&= {X}_{1} M^{2} - {Q}_{2} L^{2} - A^{2} \\ {R}_{3}&= \left( {a}_{3} {Z}_{2}^{4} + {Q}_{2}^{2} - {R}_{2} \right) L^{4} \\&\quad - A \left( B + K {S}_{2} {Z}_{1} \right) L^{2} + {Q}_{3} {X}_{1} M^{2} \\ {S}_{3}&= A {Q}_{3} - B L^{2} \\ {T}_{3}&= A {R}_{3} - C L^{4} \\ {Z}_{3}&= K {Z}_{1} {Z}_{2} {W}_{2} \\ {W}_{3}&= 1 \end{aligned} \end{aligned}$$
(18)

4.3 Non-degenerate/non-degenerate inputs

Let the input divisors be \(D_1 = (P_1) + (P_2) - 2({\mathcal {O}}) = (Q_1, R_1, S_1, T_1, Z_1, W_1)\) and \(D_2 = (P_3) + (P_4) - 2({\mathcal {O}}) = (Q_2, R_2, S_2, T_2, Z_2, W_2)\).

We omit the cases where the output is degenerate and refer the reader to [22, §4.3]. Likewise, we refer to [21] for the common subexpressions in Jacobian coordinates and the formulas for the common cases. Throughout this section, we use the notation \(P_i = (X_{P_i}, Y_{P_i}, Z_{P_i}, W_{P_i})\) for the points in the supports to avoid confusion between the Z, W coordinates of points and divisors.

We continue with doubling where \(u_1 = u_2\) and \(v_1 = v_2\). The case \(B=0\) does not involve a degenerate divisor, yet it is a rare case where the common addition formulas do not work. Hence, the case is missing in the literature. When \(B = 0\), the result \(D_3 = 2(P_1) - 2({\mathcal {O}})\) can be calculated by making the coordinates of \(P_1\) explicit as below and doubling it with Eq. (13).

$$\begin{aligned} \begin{aligned} {X}_{P_2}&= - {T}_{1} \\ {X}_{P_1}&= - \left( {Q}_{1} {S}_{1} - {T}_{1} \right) {S}_{1} \\ {Y}_{P_1}&= \left( {S}_{1} {T}_{1} + {X}_{P_1} \right) {S}_{1}^{4} \\ {Z}_{P_1}&= {S}_{1} {Z}_{1} \\ {W}_{P_1}&= {W}_{1} \end{aligned} \end{aligned}$$
(19)

The addition in the case \(u_1 = u_2,\ v_1 \ne \pm v_2\) gives \(D_3 = 2(P_1) - 2({\mathcal {O}})\). The coordinates of \(P_1\) can be computed with the following formula and can be doubled with Eq. (13).

$$\begin{aligned} \begin{aligned} K&= {S}_{1} {Z}_{2}^{3} {W}_{2} - {S}_{2} {Z}_{1}^{3} {W}_{1} \\ {X}_{P_1}&= \left( {T}_{2} {Z}_{1}^{5} {W}_{1} - {T}_{1} {Z}_{2}^{5} {W}_{2} \right) K \\ {Y}_{P_1}&= \left( {S}_{1} {X}_{P_1} + {T}_{1} {Z}_{2}^{2} K^{2} \right) K^{3} {Z}_{2}^{3} \\ {Z}_{P_1}&= K {Z}_{1} {Z}_{2} \\ {W}_{P_1}&= {W}_{1} \end{aligned} \end{aligned}$$
(20)

Now we investigate addition where \(u_1 \ne u_2\). We focus on the case \(B = 0\) which indicates that the input divisors share exactly one common point in their supports. The coordinates of the points in the supports can be calculated as below.

$$\begin{aligned} \begin{aligned} K&= {Q}_{1} {Z}_{2}^{2} - {Q}_{2} {Z}_{1}^{2} \\ {X}_{P_1}&= \left( {R}_{2} {Z}_{1}^{4} - {R}_{1} {Z}_{2}^{4} \right) K \\ {Y}_{P_1}&= \left( {S}_{1} {X}_{P_1} + {T}_{1} K^{2} {Z}_{2}^{2} \right) K^{3} {Z}_{2}^{3} \\ {Z}_{P_1}&= {Z}_{1} {Z}_{2} K \\ {W}_{P_1}&= {W}_{1} \\ {X}_{P_2}&= {X}_{P_1} \\ {Y}_{P_2}&= \left( {S}_{2} {X}_{P_2} + {T}_{2} K^{2} {Z}_{1}^{2} \right) K^{3} {Z}_{1}^{3} \\ {Z}_{P_2}&= {Z}_{P_1} \\ {W}_{P_2}&= {W}_{2} \\ {X}_{P_3}&= - {Q}_{1} K^{2} {Z}_{2}^{2} - {X}_{P_1} \\ {Y}_{P_3}&= \left( {S}_{1} {X}_{P_3} + {T}_{1} K^{2} {Z}_{2}^{2} \right) K^{3} {Z}_{2}^{3} \\ {Z}_{P_3}&= {Z}_{P_1} \\ {W}_{P_3}&= {W}_{1} \\ {X}_{P_4}&= - {Q}_{2} K^{2} {Z}_{1}^{2} - {X}_{P_2} \\ {Y}_{P_4}&= \left( {S}_{2} {X}_{P_4} + {T}_{2} K^{2} {Z}_{1}^{2} \right) K^{3} {Z}_{1}^{3} \\ {Z}_{P_4}&= {Z}_{P_1} \\ {W}_{P_4}&= {W}_{2} \end{aligned} \end{aligned}$$
(21)

In the case where \(Y_{P_1} = - Y_{P_3}\), the result is \(D_3 = (P_2) + (P_4) - 2({\mathcal {O}})\) and can be calculated with Eq. (14).

If \(Y_{P_1} = Y_{P_3}\), the result can be calculated by doubling \(P_1\) with Eq. (13) and adding \(P_2\) and \(P_3\) with Eq. (14).

5 Cost analysis

The divisor addition on genus 2 hyperelliptic curves is intricate, with plenty of different cases. Although rare cases have a low chance of occurrence, handling them in cryptographic applications is vital. While some of the rare cases are quite costly to handle, some others are not.

In Fig. 1; we illustrate all the cases of divisor addition on genus 2 hyperelliptic curves; we present the operation counts and point out the gaps in the literature, which are filled with this work. The dashed edges represent the missing cases in the literature that are proposed with fully-weighted formulas in Jacobian coordinates here. We refer to; degenerate/degenerate addition as \(1+1\), degenerate/non-degenerate addition as \(1+2\), and non-degenerate/non-degenerate addition as \(2+2\). The letter ‘M’ stands for the number of field multiplications; ‘S’ for field squarings; and ‘D’ for addition or multiplication with constants, respectively. Each edge represents a condition to be checked before determining the present case, with respect to the algorithm in Sect. 3. The operation counts given below the edges denote the cost of checking the condition. In some cases, the operations required for determining the case to be handled also provide common subexpressions, which are shared with the addition formulas in that context. Each leaf of the tree corresponds to a case in Sect. 3. The operation counts of each case are given in the leaves.

The case where \(u_1 \ne u_2\), \(B = 0\), and \(P_1 = P_3\) leads to 8 different cases enumerated with ‘*’ in front. In that case, \(D_1 = (P_1) + (P_2) - 2({\mathcal {O}})\) and \(D_2 = (P_1) + (P_4) - 2({\mathcal {O}})\). Adding \(D_1\) and \(D_2\) requires doubling \(P_1\) and adding \(P_2\) and \(P_4\) to the result. Here, 2 cases may occur while the addition of \(P_2\): either \(P_1 = P_2\) or \(P_1 \ne P_2\) (\(P_1 = -P_2\) is not possible since \(D_1\) would not be reduced otherwise). When \(P_1 = P_2\), the addition of \(2(P_1) - 2({\mathcal {O}})\) and \((P_2) - ({\mathcal {O}})\) corresponds to the tripling in Eq. (4). If \(P_1 \ne P_2\), the addition can be done with Eq. (6). Let \((P_5) + (P_6) - 2({\mathcal {O}})\) be the result for both cases. The result may or may not contain a point in its support joint with \((P_4) - ({\mathcal {O}})\). That leads to 4 cases for both:

  • *1 and *5: \(-P_4 = P_5\) (output \(P_6\)),

  • \(P_4 = P_5\)

    • *2 and *6: \(P_5 = P_6\) (Eq. (4)),

    • *3 and *7: \(P_5 \ne P_6\) (Eq. (5)),

  • *4 and *8: \(\pm P_4 \ne P_5\) (Eq. (6)).

We note that \(P_5\) and \(P_6\) can be interchanged without loss of generality.

Fig. 1
figure 1

Divisor addition cases

Full size image
figure b
figure c

The operations needed for the detection of the cases are also taken into account in contrast to the previous works, which present the operation counts for specific cases. This may lead to differences with the operation counts given in the literature. However, exceptional outputs may be produced when assumptions on the inputs are made without checking if the conditions are met. Thus, it is sensible to include the cost of case detection to demonstrate the performance of our complete algorithm.

6 Conclusion

This paper introduced explicit and inversion-free formulas for the complete group law of genus 2 hyperelliptic curves. The formulas are derived from Cantor’s algorithm and presented case by case in regard to whether the divisors are degenerate or non-degenerate. This work can be seen as a completion of the works started in [21] and [22] on Jacobian coordinates.

Any cryptographic application which enforces using a prime order genus 2 Jacobian is amenable to introducing exceptional situations, such as the addition of two divisors with joint support. Our formulas provide an efficient fallback that eliminates the need for polynomial arithmetic required by Cantor’s algorithm. Although the formulas we present consist of rare cases, a cryptographic application based on an operation such as digital signature verification is expected to handle all cases properly. In such a scenario, our complete algorithm can be used to prevent active attacks based on faulty inputs which target to trigger an exceptional output.