Implementing Cryptography Pairings over Ordinary Pairing-Friendly Curves of Type $y^2 = x^5 +a \, x$

Abstract

In this paper, we describe an efficient implementation in Sage of the Tate pairing over ordinary hyperelliptic curves of type $y^2 = x^5 +a \, x$. First, we describe a method of construction of these curves according to Kawazoe and Takahashi [8]. Then, we describe an efficient formula for computing pairings on such curves over prime fields, and develop algorithms to compute Tate pairing. We provide a faster optimisation of the final exponentiation in particular for the embedding degree $k = 28$.

1 Introduction

In 1989, three years after the introduction of elliptic curves cryptography, Koblitz suggest to use hyper-elliptic curves as a generalization to higher genus curves [8]. He extended the idea of abelian points group on elliptic curves over finite field to the Jacobian of a hyperelliptic curves, since the Jacobian is a finite abelian group on which the arithmetic operations are applied.

The algebraic curves-based cryptography has divided the cryptographers community [11] into two teams. The first one which argues that the problems of factorization and discrete logarithm problem (DLP) over finite field have already been intensively studied; and that it would require more time before the community can really apprehend the nature of elliptic curves. The other team was ambitious, started working in it and proposed their first protocols.

The first protocols proposed are based on a mathematical tool called pairing, the oldest of them being the Weil pairing. This mathematical protocol has received a great attention by the researchers and is now among the majors topics in cryptography. In order to realize protocols based on pairings, it is essential to have Pairing-friendly-curves which have parameters such as p the large prime fields $\mathbb {F}_{p}$ and the embedding degree k. The embedding degree plays an important role in ensuring a certain desired level security. In this context, the security of the pairing-based cryptosystems depends on finding curves whose Jacobian order over the finite fields $\mathbb {F}_{p^{k}}$, is divisible by a larger prime number $\ell$ (a condition necessary for resisting attacks such as Pohling-Hellman attacks).

In this paper, we consider Kawazoe-Takahashi [8] genus two ordinary pairing-friendly curves of type $y^2 = x^5 +a \; x$ which are generated over a finite field $\mathbb {F}_{p^{k}}$ using a method introduced by Kachisa [7]. These curves are characterized by simple and fast complex multiplications. It is also possible to have curves with a known odd prime factor $\ell$ of the Jacobian order with different embedding degrees and offer a small $\rho _{-value} = 2 \; log (p) / log (\ell )$ between 2 and 3.

The paper is organized as follows. First, we recall some backgrounds on pairings over hyperelliptic curves, Jacobian group structure, and representation of divisors classes. We describe a method to construct ordinary pairing-friendly of Kawazoe and Takahashi curves with simple method proposed by Kachisa [7] to obtain curves with small $\rho _{-value}$. Then, we recall the Tate-Lichtenbaum pairing definition and present implementation techniques for pairings on hyperelliptic curves. We provide a new approach to the final exponentiation when the embedding degree is $k=28$. The critical computational task of evaluating a function at a divisor is also provided.

Finally, we give some implementation results in Sage using Intel Core i5-7300HQ CPU @ 2.50 GHz processor on several security levels. We conclude that for most applications there exits an efficient algorithm for computing pairings on hyperelliptic curves that is better that on ordinary elliptic curves from the point of view of efficiency and security.

2 Preliminaries

In this section, we briefly recall the definition of the hyperelliptic curves, pairings and the definition of the Tate-Lichtenbaum pairing.

2.1 Hyperelliptic Curves

A genus g hyperelliptic curves over a prime finite field $\mathbb {F}_{p}$ are non-singular curves of a general form:

$$\begin{aligned} \mathcal {H}: \;\quad \quad y^2 + h(x) \; y = f(x) \end{aligned}$$

(1)

with h, f $\in \mathbb {F}_{p}[x]$, $deg(f)=2\; g+1$, $deg(h) \le g$ and f(x) is monic. For any algebraic extension $\mathbb {K}$ of $\mathbb {F}_{p}$, there is a special point at infinity, which is denoted by $P_{\infty }$, and we can consider the set of K-rational points on $\mathcal {H}$:

$$\begin{aligned} \mathcal {H}(K) := \lbrace (x, y) \in K \times K \; |\; y^2 + h(x) \; y - f(x) = 0 \rbrace \cup \lbrace \infty \rbrace . \end{aligned}$$

(2)

2.2 Pairings

The concept of a pairing was introduced in cryptography for the fitst time by Menezes et al. [11] to attack instances of the Discrete Logarithm Problem on elliptic curves and hyperelliptic curves. In 2000, pairing was used as bilinear application by Joux [6] to build cryptographic protocols.

Let $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ two additive abelian groups of prime order $\ell$, $\mathbb {G} _ {3}$ a multiplicative abelian group of order also $\ell$. A bilinear pairing on $(\mathbb {G}_{1},\; \mathbb {G}_{2},\; \mathbb {G}_{3} )$ is a map:

$$\begin{aligned} e : (\mathbb {G}_{1}, + )\; \times \; (\mathbb {G}_{2}, + )&\quad \longrightarrow \quad (\mathbb {G}_{3}, \times ) \end{aligned}$$

that satisfies the following requirements:

• 1. Bilinearity : $\forall D_{1}, D_{1}^{'} \in \mathbb {G}_{1}, \forall D_{2}, D_{2}^{'} \in \mathbb {G}_{2},$

  • i. $e(D_{1} + D_{1}^{'},D_{2})= e(D_{1},D_{2}) \; e(D_{1}^{'},D_{2}),$

  • ii. $e(D_{1},D_{2}+D_{2}^{'})= e(D_{1},D_{2}) \; e(D_{1},D_{2}^{'}),$

  • iii. $e(a \; D_{1}, D_{2}) = e(D_{1}, a\; D_{2}) = e(D_{1}, D_{2})^{a}, a \in \mathbb {N}^{*}.$

• 2. Non-degeneracy:

  • i. $\forall D_{1} \in \mathbb {G}_{1}-\{ 0 \},\; \exists D_{2} \in \mathbb {G}_{2} \; : \; e(D_{1},D_{2}) \; \ne \; 1,$

  • ii. $\forall D_{2} \in \mathbb {G}_{2}-\{ 0 \},\; \exists D_{1} \in \mathbb {G}_{1} \; : \; e(D_{1},D_{2}) \; \ne \; 1.$

• 3. Easily and efficiently calculable.

We recall here the definition of the Tate-Lichtenbaum pairing as it is stated in the literature, which is an explicit version described by Lichtenbaum.

Let $Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}})$ be the Jacobian group of the hyperelliptic curve $\mathcal {H}$ over $\mathbb {F}_{p^{k}}$, $\ell$ be a prime with $\ell \; | \; \sharp Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}})$ and let k be the smallest integer such that $\ell \; | \; (p^{k} - 1 )$, then k is called the embedding degree (dependent on $\ell$).

Definition 1

The Tate-Lichtenbaum pairing is a bilinear and non-degeneracy map defined by:

$$\begin{aligned} T_{\ell }:\quad&Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}})[\ell ] \times Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}}) / \ell \; Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}}) \quad \longrightarrow \quad \quad \mathbb {F}^{\times }_{p^{k}} / (\mathbb {F}^{\times }_{p^{k}})^{\ell }&\\&\quad \quad \quad \quad (D_{1},D_{2}) \quad \quad \longmapsto \quad T_{\ell }(D_{1},D_{2})=f_{\ell ,D_{1}} (D_{2})^{(p^{k} - 1)/\ell }. \end{aligned}$$

$f_{\ell ,D_{1}}$: the function given by the divisor $\ell \; D_{1}\; - \;\ell \; (\infty ) = div(f)$.

3 Pairing-Friendly Curves of Type $y^2 = x^5 +a \, x$

3.1 Curve Choice

We can give here explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobian proposed by Kawazoe and Takahishi [8], we show also such that curves are suitable to construct genus 2 pairing at the high security levels.

We consider p an odd prime number, $\mathbb {F}_{p}$ is a finite field of characteristic $p \ne 2$, so we can define equation of the curve $\mathcal {H}$ as $y^2 = f(x)$ where f(x) is a polynomial $\in \mathbb {F}_{p}[x]$ of degree 5. Let $Jac_{H}$ be the Jacobian variety of a hyperelliptic curve $\mathcal {H}$. We denote the group of rational points on $Jac_{H}$ over $\mathbb {F}_{p}$ by $Jac_{\mathcal {H}}(\mathbb {F}_{p})$.

To compute the Jacobian order, we need the characteristic polynomial of $p-$th power Frobenius endomorphism of $\mathcal {H}$. Then the order is given by

$$ \sharp \; Jac_{\mathcal {H}}(\mathbb {F}_{p}) = \chi _{p}(1) $$

It is very difficult to evaluate the characteristic polynomial of $p-$th power Frobenius endomorphism of $\mathcal {H}$ in 1 for hyperelliptic curves over height level bits fields, there are very few results on it, Gaudry and Harley [3] compute the group order over 80-bits fields but their algorithm needs very long running time. To solve this problem, there are a very special curves with complex multiplication, they are known by the existence of efficient algorithms called CM-methods to construct such curves. The best example of such ordinary pairing-friendly curves is curves of type $y^2 = x^5 + a \, x$ given by Kawazoe and Takahashi [8]. They proposed also a fast algorithm to compute the Jacobian group order over a prime finite field.

3.2 Counting Points

In [3] Gaudry presented a method to compute the Jacobian order modulo the characteristic p of the base field by using the Hasse-Witt matrix. Two main theorems in [10] and [16] quoted below:

Theorem 1

Let $y^2 = f (x)$ with $deg(f) = 2g + 1$ be the equation of a genus g hyperelliptic curve. Denote by $c_{i}$ the coefficient of $x^{i}$ in the polynomial $f(x)^{(p - 1)/2}$. Then the Hasse-Witt matrix is given by

$$ A = (c_{ip-j})_{1 \le i ,j \le g} .$$

The following theorem give the link between the characteristic polynomial of the Frobenius endomorphism and the Hasse-Witt matrix.

Theorem 2

Let $\mathcal {H}$ be a curve of genus g defined over a finite field $\mathbb {F}_{p^{k}}$. Let A be the Hasse-Witt matrix of $\mathcal {H}$, and let $A_{\phi } = A A^{(p)} ... A^{(p^{k-1})}$ . Let $\kappa (t)$ be the characteristic polynomial of the matrix $A_{\phi }$ and $\chi (t)$ the characteristic polynomial of the Frobenius endomorphism. Then

$$ \chi (t) \equiv (-1)^{g} \; t^{g} \; \kappa (t) (mod \; p). $$

This method is difficult in general when p is very large, but if we consider a special form of $f(x) = x^5 + a \, x \in \mathbb {F}_{p}[x]$ of degree 5 we can easily compute the Hasse-Witt matrix, $A= \left[ \begin{array}{cc} c_{p-1}&{}c_{p-2} \\ c_{2p-1}&{}c_{2p-2} \end{array}\right]$, the element $(c_{i})$ is coefficient of $x^{i}$ in polynomial $f(x)^{(p-1)/2}$. The characteristic polynomial of the Frobenius endomorphism of the genus 2 curve $y^2 = f (x)$ over $\mathbb {F}_{p}$ is

$$ \chi (t) = t^4 - s_{1}\,t^3 + s_{2} \, t^2 - s_{1} \, p \, t + p^2 ,\quad \quad \quad |s_{1}| \le 4 \sqrt{p},\quad |s_{2}| \le 6 \, p $$

The $s_{1}$ and $s_{2}$ are two integers (for more details see Theorem 3, [3]), they are given by

$$ s_{1} \equiv c_{p-1} + c_{2p-2} (mod \; p) \quad and \quad s_{2} \equiv c_{p-1} \; c_{2p-2} + c_{p-2} \; c_{2p-1} (mod \; p)$$

3.3 Pairing-Friendly Curves of the Cocks-Pinch Method

By using results in [Theorem 3, [3]] and Cocks-Pinch method for hyperelliptic curve $\mathcal {H}$ : $y^2 = x^5 + a \, x$. We can construct pairing-friendly curves of this type over a prime field $\mathbb {F}_{p}$, with parameters c and d integers such that: $p = c^2 + 2 \; d^2$, $\ell$ large prime factor of the Jacobian order over $\mathbb {F}_{p}$ and k embedding degree, satisfying the following conditions:

• 1. $p \equiv 1, \; 3 \; \;(mod \; 8),$

• 2. $\chi \equiv 0 \;\; (mod \; \ell ),$

• 3. $\phi _{k}(p) \equiv 0 \;\; (mod \; \ell ),$

• 4. $p = c^2 + 2 \; d^2, \quad with \quad c \equiv 1 \;\;(mod \; 4).$

We did the implementation in Sage of the algorithm presented by Kawazoe and Takahashi which is the analog of Cocks-Pinch method to obtain genus 2 ordinary hyperelliptic curves of the form $y^2 = x^5 + a \; x$. By using generalization of Kachisa [7] which he parametrized the parameters c, d, r and p as polynomials c(z), d(z), $\ell (z)$ and p(z) in a variable z. By using this approach, we can obtain curves with small $\rho -value = 2 \; log (p)/log (\ell )$.

4 Group Structure of Hyperelliptic Curve

4.1 General Group Element

The group structure of a hyperelliptic curve $\mathcal {H}$ over a finite field $\mathbb {F}_{q}$, $(q = p^k)$, p :  prime odd number $(p \ge 5)$ and k integer $(k \ge 1)$, recapitulates on the representation of his Jacobian. The following theorem show the unique representation of the Jacobian element.

Definition 2

A divisor D is a finite formal sum of points on the curve $\mathcal {H}$ such that:

$$\begin{aligned} D := \sum _{i=1}^{m}(P_{i}) \end{aligned}$$

(3)

We can also define the reduced divisor $D_{r}$ associated with D as follows:

Theorem 1

Let D an element on the Jacobian of the curve $\mathcal {H}$, the element D has a unique representation $D_{r}$ of the form:

$$\begin{aligned} D_{r} := \sum _{i=1}^{m}(P_{i}) - m(\infty ), \end{aligned}$$

(4)

such that:

• 1. $m \ne g$,

• 2. $P_{i}$ are affine points,

• 3. The involution $\imath$, satisfy: $\imath (P_{i})\ne \imath (P_{j})$, for all i, j such that $i \ne j$.

All elements on Jacobian form an abelian variety, Mumford [13] introduced a way of representing such that elements, it’s extremely useful for implementation.

Theorem 2

(Mumford representation). Let $\mathcal {H}$: $y^2 + h(x)\; y= f(x)$ a hyperelliptic curve of genus g define over a finite field $\mathbb {F}_{q}$, $q = p^k$ p: primer $(p \ge 5)$ and k integer $(k \ge 1)$. Let K an algebraic extension of $\mathbb {F}_{q}$, then any element D of the Jacobian of the curve $\mathcal {H}$, can be represented in a unique way by two polynomials $(u(x),v(x)) \in K[x]^{2}$ such that:

• 1. u is monic, with $deg(u(x)) \le g$,

• 2. $deg(v(x)) \le deg(u(x))$, and

• 3. u(x) divides $\{ v(x)^{2} + v(x) \; h(x) - f(x) \}$.

As we saw before, we have two representations for a divisor D on the Jacobian, a natural representation $D = \sum _ {i = 1} ^ {m} (P_ {i}) - m (\infty )$ and a Mumford representation $D = (u (x), v (x))$. To do implementation, we must understand how to manipulate the two representations. For example to pass from the Mumford representation to the natural one, we compute the coordinates of the points $P_ {i} = (x_ {i}, v ( x_ {i}))$ with $x_ {i}$ the roots of the polynomial u(x) . In the case of genus 2 hyperelliptic curve $\mathcal {H}$, the Mumford representation of divisor of degree 0 whose effective part E is the sum of the points $P1 = (x_ {1}, y_ {1})$ and $P2 = (x_ {2}, y_ {2 }), \quad (E = P_ {1} \pm P_ {2})$ is obtained by multiplying and dividing by:

$$\begin{aligned} u(x) = x^2 - (x_{1}+x_{2})x+x_{1}x_{2} \quad and \quad v(x)= \frac{y_{1}-y_{2}}{x_{1}-x_{2}} (x-x_{1}) +y_{1}. \end{aligned}$$

(5)

The set of torsion points are the points whose order is finite, which is the case for all element on the Jacobian $Jac_{\mathcal {H}}$ over $\mathbb {F}_{q}$. The set of $\ell$-torsion points is defined as follows:

• 1. $[\ell ]D = \underbrace{D + D +...+ D}_{\ell \ \mathrm {terms}} \quad \quad if \quad \ell > 0$,

• 2. $[\ell ]D = -([-\ell ]D) \quad if \quad \ell < 0$,

• 3. $[0]D = (\infty )$.

By definition, we say that D is an $\ell$-torsion divisor if $[\ell ] D = (\infty )$. The subgroup of $\ell$-torsion divisors on the Jacobian of hyperelliptic curve $\mathcal {H}$ over a finite field $\mathbb {F}_{q}$ is denoted by $Jac_{\mathcal {H}}(\mathbb {F}_{q})[\ell ]$, with $q = p^k$, p: prime number $(p \ge 5 )$ and k integer $(k \ge 1)$.

4.2 Jacobian Subgroup Operations

To do pairing implementation, we need to perform operations on the Jacobian group $Jac_{\mathcal {H}}(\mathbb {F}_{p^k})[\ell ]$, Cantor [1] developed and showed efficient algorithms to manipulate elements of the Jacobian $Jac_{\mathcal {H}}[\ell ](\mathbb {F}_{p^k})$, by using the Mumford representation, assuming that $h(x) = 0$ and $p \ne 2$. These algorithms was later generalised by Koblitz [9] to remove these conditions.

We will show here the two algorithms implemented in Sage, the first one is to give a semi-reduced divisor D equivalent to $D_{s} \, \simeq \, D_{1} + D_{2}$ from two semi-reduced divisors $D_{1}$ and $D_{2}$ (represented by Algorithm 2), and the other algorithm is to reduce the divisor semi-reduced $D_{s}$ (given by Algorithm 2) to obtain a reduced divisor $D_{r}$ equivalent (represented by Algorithm 3).

5 Our Work

To compute pairing we need Miller algorithm [12] which makes it possible to calculate the function $f_{\ell ,D_{1}} (D_{2})$, this algorithm was applied for the elliptic case and quickly it has been generalised on hyperelliptic curves. We define the group law $\oplus$ on the Jacobian $Jac_{\mathcal {H}}(\mathbb {F}_{p^k})$, let $D_{1}$ and $D_{2}$ $\in$ $Jac_{\mathcal {H}}(\mathbb {F}_{p^k})$, there is a function $h \in \mathbb {F}_{p}(\mathcal {H})$ with its divisor:

$$ div(h_{D_{1} , D_{2}}) = D_{1} + D_{2} - (D_{1} \oplus D_{2}),$$

The main task involved in computing the evaluation $f_{\ell ,D_{1}}(D)$ in $D_{1}$, Miller has shown how to efficiently compute it, this function appearing in

$$ Div (f_ {\ell , D}) = \ell \; D - D_ {\ell }. $$

For $\ell = n + m$, n and m integers, we find:

$$ Div (f_ {\ell , D}) = Div (f_{n + m, D}) = f_{n, D}. \; f_{m, D}. \; h_{D_{n}, D_{m}}, $$

With h a function such that:

$$ div (h_{D_{n}, D_{m}}) = D_{n} + D_{m} - \rho (D_{n} + D_{m}), $$

$\rho (D_{n} + D_{m})$: the reduced divisor of $(D_{n} + D_{m}).$

This immediately leads to the following algorithm:

We can clearly see that the execution of the Miller algorithm requires the existence of an algorithm that allows the evaluation of the function $h \in \mathbb {F}_{q}(\mathcal {H})$, $q = p^k$ p: primer $(p \ge 5)$ and k integer $(k \ge 1)$. We called this algorithm “evaluatefunction()”, it’s the crucial step of Miller’s algorithm, it allows to calculate the value of the function in a point $D \in Jac_{\mathcal {H}} (\mathbb {F}_{q})$, such that D is a reduced divisor represented in Mumford representation. For this work, we will focus only on the evaluation of the function h in an effective divisor that we note $E = [ u_{E}(x), v_{E}(x) ]$. There are two different methods to compute h(E) (we use in general a norm computation and resultants).

The first method requires a polynomial factorisation of $u_{E}(x)$, it can be summarized by the following algorithm:

The above method is not the best because it didn’t take in consideration the fact that the result of the evaluation has to be in $\mathbb {F}_{q}$ Instead, one could partition the support into distinct Galois orbits as follows:

$$\{(x_{i}, y_{i}), (x_{i}^{q}, y_{i}^{q}),..., (x_{i}^{q^{g_{i}-1}}, y_{i}^{q^{g_{i}-1}}) \}$$

And the last step (6.) of the algorithm is simply reduced by calculating the norm $N_{\mathbb {F}_{q^{g_{i}}}/\mathbb {F}_{q}} (h(x_{i}, y_{i}))$.

The second method is faster than the first one, since it does not require any polynomial factorisation. It is based on the observation of $\tilde{h}(x) = h(x, v_{E}(x))$ which verified for all $x_{i}$ root of $u_{E}(x)$, $\tilde{h}(x_{i}) = h(x_{i}, v_{E}(x_{i}))$ so instead of calculating the product $h(E) = \prod _{i = 1}^{i = d} h(x_{i}, y_{i})$, the problem is reduced to the computation of $h(E) = \prod _{i = 1}^{i = d } \tilde{h}(x_{i})$, with $x_{i}$ the zeros of $u_{E}(x)$, but this corresponds exactly to the definition of the resultant of the two polynomials $u_{E} (x)$ and $\tilde{h} (x)$, and we can write:

$$ h(E) = Resultant( u_{E}(x), h(x, v_{E}(x)) ) $$

As we work on hyperelliptic curves of genus g, the polynomials degree $deg (u_{E}(x))$ of the Mumford representation of $E = [ u_{E}(x), v_{E}(x) ]$ is smaller than g, so we can write:

$$ h(E) = Resultant( u_{E}(x), \tilde{h}(x) \; mod \; u_{E}(x)) $$

We consider $\mathcal {H}$ a hyperelliptic curve of genus 2, defined over a finite field $\mathbb {F}_{q}$ by $y^2 + h_{x}y = f_{x}$, $(q = p^k)$, p :  prime odd number $(p \ge 5)$ and k integer $(k \ge 1)$, let $D,\; D_{1}\; and \; D_{2} \in Jac_{\mathcal {H}}(\mathbb {F}_{q})$, $D = E - d (\infty )$ , E effective divisor.

As $h_{D_{1}, D_{2}} = h(x,y)$ is a rational function $h(x,y) \in \mathbb {F}(\mathcal {H})$, we can write:

$$ h(x,y) = \frac{h_{1}(x,y)}{h_{2}(x,y)} $$

So,

$$ \tilde{h}(x) = h(x, v_{E}(x)) = \frac{h_{1}(x,v_{E}(x))}{h_{2}(x,v_{E}(x))} = \frac{\tilde{h_{1}}(x)}{\tilde{h_{2}}(x)}$$

Algorithm evaluation of the rational function $h = h_{D_{1}, D_{2}} (D)$ in E is given by:

6 Final Exponentiation

Tate pairing algorithm requires computation of final exponentiation after the Miller loop. The optimisation of this computation is to factor the term $(p^{k} - 1)/\ell$ combined with the p-th power Frobenius operations. So the final exponentiation can be written as

$$\begin{aligned} \dfrac{p^{k} - 1}{\ell } := \dfrac{\phi _{k}(p)}{\ell } \cdot \prod _{s|k, \; s < k} \phi _{s}(p) \end{aligned}$$

(6)

We note that this exponent is determined by fixed system parameters. This final exponent can be broken down into three components. Let $e = \dfrac{k}{2}$ then

$$\begin{aligned} \dfrac{p^{k} - 1}{\ell } := (p^{e} - 1) \cdot [\dfrac{(p^{e} + 1)}{\phi _{k}(p)} ]\cdot [\dfrac{\phi _{k}(p)}{\ell } ]\end{aligned}$$

(7)

For example for $k = 28$ the final exponent becomes

$$ \dfrac{p^{28} - 1}{\ell } = (p^{14} - 1) \cdot [\dfrac{(p^{14} + 1)}{\phi _{28}(p)} ]\cdot [\dfrac{\phi _{28}(p)}{\ell } ]$$

With $\phi _{28}(p) = p^{12} - p^{10} + p^8 - p^6 + p^4 - p^2 + 1$, so

$$ \dfrac{p^{28} - 1}{\ell } = (p^{14} - 1) \cdot (p^2 + 1) \cdot [\dfrac{(p^{12} - p^{10} + p^8 - p^6 + p^4 - p^2 + 1)}{\ell } ]$$

There are two parts of the exponentiation, the first one is an easy exponentiation to the power of $exp_{1} = (p^{14} - 1) \cdot (p^2 + 1)$ (because of the Frobenius), it also simplifies the rest of the final exponentiation because after raising to the power $(p^{14} - 1)$ the field element becomes “unitary”. The other part $exp_{2} = (p^{12} - p^{10} + p^8 - p^6 + p^4 - p^2 + 1)/ \ell$ is the very hard part of the final exponentiation can be calculated using a fast multi-exponentiation algorithm [5]. However, we can use the polynomial description of p(z) and $\ell (z)$ given by Kachisa in [7]. In this case the hard part of the final exponentiation is to the power of $(p^{12} - p^{10} + p^8 - p^6 + p^4 - p^2 + 1)/ \ell$. After substituting the polynomials for p(z) and $\ell (z)$, after it can be expressed to the base p.

7 Implementation Results

We have implemented the Tate pairing for the different level security on ordinary genus two curves in SageMath version 8.1. Our aim was not to provide an optimal ad-hoc implementation for any one of the curves or pairings, but rather to keep a sufficient level of security appropriate for a general purpose system, while still implementing algorithmic optimisations that apply in a broader context. All were performed on Intel Core i5-7300HQ CPU @ 2.50 GHz processor.

In the following, we will compute the execution time needed to calculate Tate’s pairing for different embedding degree and several levels of security. The following Table 1 shows the calculation time in milliseconds of all Tate’s large pairing computation steps on ordinary Kawazoe curves of type $y ^ 2 = x ^ 5 + a \; x$. So we compute the times: $t_{g}$, $t_{J}$, $t_{p}$, $t_{r}$, $t_{m}$ and $t_{e}$ such that: $t_{g}$: time generation of the curve equation, $t_{J}$: time computation of the Jacobian on $\mathbb {F}_{q}$, $t_{p}$: Construction time of Jacobian two points, $t_{r}$: reducing time of the two divisors, $t_{m}$: execution time of the Miller loop, $t_{e}$: time required for the final exponentiation.

For $t_ {g}$, $t_ {J}$ and $t_ {p}$, we will directly give the time needed by predefined algorithms in Sage to generate the desirable curves, compute Jacobian and to construct two points on the Jacobian $Jac_{\mathcal {H}}(\mathbb {F}_{p})$ over prime finite field. On the other hand, the times $t_ {r}$ and $t_ {m}$ are the conclusion of the implementation of the different executable algorithms proposed by Galbraith [2], Granger et al. [4] and others.

To vary the embedding degree, we will always work on genus two Kawazoe and Takahashi curves of type $y ^ 2 = x ^ 5 + a \; x$ generated by Kachisa [7], these parameters are chosen in order to have the desirable ordinary pairing-friendly curves.

Table 1. Execution times in milliseconds (ms) to compute Tate’s pairing.

For cryptography applications, the discrete logarithm problems in $Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}})$ and in the multiplicative group $\mathbb {F}_{p^{k}}$ must both be computationally infeasible. For Jacobian varieties of hyperelliptic curves of genus 2 the best known discrete logarithm problem (DLP) algorithm is the parallelized rho-Pollard algorithm in [14] and [15], which has running time $O(\sqrt{\ell })$ where $\ell$ is the size of the largest prime-order subgroup of $Jac_{\mathcal {H}}(\mathbb {F}_{p^{k}})$. In the following Table 2, we will give the security level for genus two curves according to the size of the curve parameters $(k, p, \ell )$ and the $\rho -value = \dfrac{g \; log (p)}{log (\ell )}$.

Table 2. Embedding degrees for hyperelliptic curves of genus $g = 2$ required to obtain commonly desired levels of security.

Now, we calculate the execution time in Sage needed to compute Tate pairing for different security levels (128, 192 and 256 bits), the following Table 3 lists the execution time of Miller loop and final exponentiation required to compute pairing in milliseconds (ms).

Table 3. Execution times in milliseconds (ms) required to compute Tate’s pairing for different security levels.

8 Conclusions

In this work, we discuss an implementation of pairings over pairing-friendly hyperelliptic curves. In particular, we focus on Kawazoe-Takahashi genus 2 curves of the form $y^2 = x^5 + a \; x$. We provide the necessary background to have sufficient understanding of pairings on hyperelliptic curves, discuss the algorithm to sample curves of the desired type, and describe the group structure of these curves. We then continue and present details of the Miller algorithm that are involved in the efficient evaluation of the pairing.

First, we present the analogue of the Cocks-Pinch method to obtain ordinary Kawazoe-Takahashi pairing-friendly curves using approach of Kachisa to have curves with a small $\rho -value$, we have implemented this method in Sage, the ordinary Jacobian order over $\mathbb {F}_{p}$, $\mathbb {F}_{p^{k}}$ and the various curve parameters are calculated.

Second, we gave several techniques for pairing computation more precisely for Tate pairing case, operations on Jacobian subgroup, Miller loop and we have provided explicit formulae for the evaluation of the function $f_{D_{1}, D_{2}}(E)$ in effective divisor required by the Miller algorithm. We then continue and give a performance method for final exponentiation in order to speed up the pairing, generally applicable and which is calculated in two parts, an easy part given a unitary field element and a hard part using polynomial description of curve parameters.

Finally, we gave the implementation results in Sage for different levels of security according to the embedding degree of the curve. Our studies indicates that pairing on hyperelliptic curves is computable and we can have pairing applications efficient and competitive to the pairing on elliptic curves in performance and security level.

As the main contribution here is the evaluation of the rational function h in the point on the Jacobian of the curve over prime field, that appears in the evaluation of $f_{\ell ,D_{1})}(D)$ in algorithm of Miller. We present one method, that is based on the factorization of polynomials, and a faster one, that instead of factorization of polynomials is based on the resultant of polynomials The includes some interesting ideas to improve the evaluation of pairings on hyperelliptic curves. We also gave a fast method to calculate the final exponentiation by using the parametrization of the curve parameters p and l.