Introduction

A cryptographic pairing is a non-degenerate bilinear map from certain pairs of points of elliptic curves to a multiplicative subgroup of appropriate order of finite fields. Whereas some research papers such as Boneh and Franklin’s identity-based encryption scheme [1], Lynn and Shacham’s short signature scheme [2] used pairings in a constructive manner to implement novel protocols, and Joux’s one round tripartite key exchange [3] used pairing to improve existing protocol which was in two rounds. There are several types of pairings such as the Weil pairing [4, 5], the Tate pairing [6], and its variants: the ate pairing [7], the R-ate pairing [8].

The original algorithm for computing pairings is due to Miller and is named the Miller algorithm. What the algorithm does is the efficient evaluation of a rational function associated with an r-torsion point of the elliptic curve.

Let \(E(F_{p})\) denote the set of rational points of an elliptic curve E over a finite field \(F_{p}\). Let r be the large prime divisor of \(\# E({\mathbb {F}}_{p})\) and c the integer, such that \(\# E({\mathbb {F}}_{p}) = c\cdot r\). For the Tate pairing for example, the group \({\mathbb {G}}_{1}\) is the subgroup \(E({\mathbb {F}}_{p})[r]\) of r-torsion points in \(E({\mathbb {F}}_{p})\), so that a point in \({\mathbb {G}}_{1}\) can be obtained by the scalar multiplication by c. The group \({\mathbb {G}}_{2}\) appears as the r-torsion subgroup of \({\tilde{E}}({\mathbb {F}}_{p^{k/d}})\), where \({\tilde{E}}\) is the degree-d twist of the elliptic curve E. Hashing can be done exactly as in the case of \({\mathbb {G}}_{1}\), but the cofactor c in this case is quite large making the scalar multiplication costly, and it is thus a major concern to make it as fast as possible.

Two methods are used for efficient hashing into \({\mathbb {G}}_{2}\): the Scott et al.’s method [9] and Fuentes et al.’s method [10]. Those methods have been applied to BN curves and BLS curves [11] and other curves [9]. This work continues the same line of research in which we consider hashing into \({\mathbb {G}}_{2}\) on the newly constructed pairing-friendly curves introduced by Scott and Guillevic [12]. For the case study with both methods, our results show that the Fuentes et al.’s method is at least twice faster than the Scott et al.’s method in terms of group operations. In addition, the computational cost of Hashing into \({\mathbb {G}}_{2}\) studied in this work is higher compared to the previous work done with BN curves, KSS curves, and BLS curves at comparable embedding degrees.

The rest of this paper is organised as follows: in the next section, we bring out some preliminary on elliptic curves and pairings useful for the understanding of this work. The following section describes and applies hashing into \({\mathbb {G}}_{2}\) with Scott et al. method to Aurifeuillean curves with embedding degree \(k\in \{6,9,15,18,27,54\} ,\) as well as hashing into \({\mathbb {G}}_{2}\) with Fuentes et al.’s method to the same elliptic curves, but not for \(k=15,\) since a certain condition was not satisfy. We also bring up a comparison between computational cost of hashing with Aurifeuillean curves and other pairing-friendly elliptic curves in this section. The last section concludes the work.

Preliminary on Elliptic Curves and Pairings

This section recalls some preliminaries on elliptic curves useful to understand the remainder of this work. We refer the reader to the book [4] for more details.

Elliptic Curves

Let \({\mathbb {F}}_{p}\) denote the finite field with p elements. \(\overline{{\mathbb {F}}}_{p}\) denotes its algebraic closure, \(\overline{{\mathbb {F}}}_{p}=\cup _{m\ge 1}^{} {\mathbb {F}}_{p^m}\). When the characteristic of \({\mathbb {F}}_p\) is different from 2 and 3 the Weierstrass elliptic curve is the set of points in \((x,y)\in \overline{{\mathbb {F}}}_{p}\times \overline{{\mathbb {F}}}_{p}\) satisfying the equation:

$$\begin{aligned} E: y^2= x^3 +ax+b, \end{aligned}$$
(1)

where \(a,b \in \overline{{\mathbb {F}}}_{p}\) together with an extra point at infinity \({\mathcal {O}}.\) If \(a,b \in {\mathbb {F}}_{p} ,\) then E is said to be defined over \({\mathbb {F}}_{p}\) and we denote this by \(E/{\mathbb {F}}_{p}.\) If E is defined over \({\mathbb {F}}_{p}\), then the set of \({\mathbb {F}}_{p}\)-rational points of E, denoted \(E({\mathbb {F}}_{p})\) is the set of points with coordinates in \({\mathbb {F}}_{p}\).

Group Law

Let E be the elliptic curve given by the Weierstrass Eq. (1). The addition rule is given below. For any point \(P_{1}\) and \(P_{2}\) of the curve where \(P_{i}(x_{i},y_{i})\) for \(i=1,2 .\)

  1. (i)

    \(P_{1}+{\mathcal {O}}={\mathcal {O}}+P_{1}=P_{1} .\)

  2. (ii)

    \(-{\mathcal {O}}={\mathcal {O}},\)

  3. (iii)

    Let \(P_{1}(x_{1},y_{1})\ne {\mathcal {O}},\) \(- P_{1}\) has as coordinates \(-P_{1}(x_{1},-y_{1})\) and \(P_{1}+(-P_{1})={\mathcal {O}}.\)

  4. (iv)

    \(P_{1}+P_{2}\) is of coordinates \((x_{3},y_{3})\) with

    $$\begin{aligned} x_{3}=\lambda ^2-x_{1}-x_{2} \quad y_{3}=\lambda (x_{1}-x_{3})-y_{1} \end{aligned}$$

    where

    $$\begin{aligned} \lambda = \left\{ \begin{array}{r c l} \dfrac{y_{1}-y_{2}}{x_{1}-x_{2}} ,\quad si \quad P_{1}\ne \pm P_{2}\\ \dfrac{3x_{1}^{2}+a}{2y_{1}} \quad si\quad P_{1}=P_{2}. \end{array} \right. \end{aligned}$$

Theorem 1

The set \((E({\mathbb {F}}_{p}),+)\) consisting of the elliptic curve given by the Weierstrass Eq. (1) together with addition defined above is an abelian group with identity element \({\mathcal {O}}.\)

The Frobenius endomorphism on the elliptic curve is defined by \(\pi : E(\overline{{\mathbb {F}}}_{p}) \longrightarrow E(\overline{{\mathbb {F}}}_{p}): (x,y) \longmapsto (x^p,y^p)\) and \({\mathcal {O}} \longmapsto {\mathcal {O}} .\) The following theorem gives a bound of the number of points of an elliptic curve.

Theorem 2

(Hasse) Let E the elliptic curve on finite field \({\mathbb {F}}_{q} ,\) with \(q=p^n\) then

$$\begin{aligned} \# E({\mathbb {F}}_{q})=q+1-t \quad with \quad |t|\le 2\sqrt{q}. \end{aligned}$$

Theorem 3

Let E the elliptic curve on finite field \({\mathbb {F}}_{q} ,\) then

$$\begin{aligned} \pi ^2-t\pi +q={\mathcal {O}}, \end{aligned}$$

where t is the unique integer equal to \(q+1-\# E({\mathbb {F}}_{q})\), called the trace of the Frobenius map on the elliptic curve.

There are two categories of elliptic curves: supersingular elliptic curves and ordinary elliptic curves. If \(t=0\) or \(\# E({\mathbb {F}}_{q})\equiv 1 \mod p,\) the curve is said to be supersingular otherwise it is an ordinary curve.

Definition 1

Let E and Ẽ be two elliptic curves defined over the finite field \({\mathbb {F}}_{q}\). then, Ẽ is called the twist of degree d of E if there exists an isomorphism \(\psi _{d}\) from Ẽ to E over \({\mathbb {F}}_{q^d}\) such that d is minimal.

r-Torsion Points

Definition 2

For \(P\in E(\overline{{\mathbb {F}}}_{p}), P\) is a r-torsion point if \([r]P={\mathcal {O}}.\)

The set of r-torsion points of \(E(\overline{{\mathbb {F}}}_{p})\) is denoted

$$\begin{aligned} E[r]= \left\{ P\in E(\overline{{\mathbb {F}}}_{p}): [r]P={\mathcal {O}}\right\} . \end{aligned}$$

Definition 3

Let r be a large prime number dividing \(\#E({{\mathbb {F}}_{q}}) ,\) the embedding degree of the elliptic curve E relatively to r is the least integer k, such that \(r/q^k-1\).

Remark 1

The embedding degree k is the minimal degree of extension field \({\mathbb {F}}_{q}\) such that \(E[r]\subset E({{\mathbb {F}}_{q^k}})\).

Pairings

Let \({\mathbb {G}}_{1}, {\mathbb {G}}_{2}\) and \({\mathbb {G}}_{3}\) be three groups of order r,  a pairing is non-degenerate bilinear map

$$\begin{aligned} e:{\mathbb {G}}_{1}\times {\mathbb {G}}_{2}\longrightarrow {\mathbb {G}}_{3}. \end{aligned}$$

Consequence

$$\begin{aligned} \forall j\in {\mathbb {N}},\quad e([j]P; Q) = e(P; Q)^j = e(P; [j]Q). \end{aligned}$$

On an elliptic curve E over \({\mathbb {F}}_{q}\), the following groups are defined:

  • \({\mathbb {G}}_{1}\) is the group \(E({\mathbb {F}}_{p})[r]\) of r-torsion points in \(E({\mathbb {F}}_{p}),\)

  • \({\mathbb {G}}_{2}\) is a group \({\tilde{E}}({\mathbb {F}}_{p^{k/d}})\) of r-torsion points, where \({\tilde{E}}\) is the degree d twist of E over a lower degree extension \({\mathbb {F}}_{p^{k/d}}.\)

  • \({\mathbb {G}}_{3}\) the group of rth roots of unity in \({\mathbb {F}}_{q^k}.\)

The Tate pairing is the map

$$\begin{aligned} e_{T}: {\mathbb {G}}_{1}\times {\mathbb {G}}_{2}\longrightarrow & {} {\mathbb {G}}_{3}\\ (P,Q)\longmapsto & {} (f_{r;P}(Q))^{\frac{p^k-1}{r}} \end{aligned}$$

where \(f_{r;P}\) is the Miller function, the rational function \(f_{r;P}\) verifying \(div( f_{r;R})=s(R)-([s]R)-(s-1){\mathcal {O}}\).

Order of Elliptic Curves and Its Twist

Consider an elliptic curve E defined over \({\mathbb {F}}_{p}\). The number of points of E is defined as \(\# E({\mathbb {F}}_{p})=p+1-t,\) where t is the trace of the p-power Frobenius of E, which obeys the Hasse bound \(t\leqslant 2\sqrt{p}.\) The trace \(t_{m}\) of the \(p^m\)-power Frobenius on E for an arbitrary m can be determined using the recursion:

$$\begin{aligned} t_{0}& = 2\\ t_{1}& = t\\ t_{i+1}& = t\cdot t_{i}-p\cdot t_{i-1} \end{aligned}$$

for all \(i\geqslant 1.\)

Therefore, the number of points of an elliptic curve E over \({\mathbb {F}}_{p^m}\) is defined as

$$\begin{aligned} \# E({\mathbb {F}}_{p^2})& = p^2+1-(t^2-2p), \quad \mathrm{for }\quad m=2 ,\\ \# E({\mathbb {F}}_{p^3})& = p^3+1-(t^3-3tp), \quad \mathrm{for} \quad m=3 ,\\ \# E({\mathbb {F}}_{p^m})& = p^m+1-t_{m}, \quad \mathrm{for} \quad m\geqslant 2 . \end{aligned}$$

If E admits a twist \({\tilde{E}}\) of degree d dividing k and \(q=p^{k/d},\) then for \(d=2 ,\)

$$\begin{aligned} \#{\tilde{E}}( {\mathbb {F}}_{q} ) = q+1+t . \end{aligned}$$

For \(d=3\)

$$\begin{aligned} \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1-(3f-t)/2, \quad \mathrm{or}\\ \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1-(-3f-t)/2, \end{aligned}$$

with \(t^2-4q=-3f^2\).

For \(d=4\)

$$\begin{aligned} \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1+f, \quad \mathrm{or}\\ \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1-f, \end{aligned}$$

with \(t^2-4q=-f^2\).

For \(d=6\)

$$\begin{aligned} \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1-(-3f+t)/2, \quad \mathrm{or}\\ \#{\tilde{E}}( {\mathbb {F}}_{q} )& = q+1-(3f+t)/2, \end{aligned}$$

with \(t^2-4q=-3f^2\) (see [9] for more explanation).

Addition Chain

Definition 4

(Basic definition) An addition chain for positive integer n is a sequence of positive integers \(\{e_{0}, e_{1}, e_{2},\ldots ,e_{s}\}\), such that

  1. (i)

    \(e_{0}=1, e_{1} =2\) and \(e_{s}=n\)

  2. (ii)

    for each i, \(1<i<s,\) there exist \(k,j<i\) such that \(e_{i}=e_{j}+e_{k}\)

A generalisation of the following definition take into consideration several integers.

Definition 5

(Generalisation) A generalisation of an addition chain of length l for a set of positive integers \(\{ n_{1}, n_{2},\ldots ,n_{s}\}\) is a sequence of positive integers \(\{e_{0}, e_{1}, e_{2},\ldots ,e_{l}\}\) which include \(\{ n_{1}, n_{2},\ldots ,n_{s}\}\), such that

  1. (i)

    \(e_{0}=1, e_{1} =2\) and \(e_{s}=n_{s}\)

  2. (ii)

    for each i, \(1<i<l,\) there exist \(k,j<i\) such that \(e_{i}=e_{j}+e_{k}\)

Such a chain defines a correct sequence of additions/substraction and doublings required for performing a scalar multiplication operation, [c]P;  with P an element of an arbitrary Abelian group.

By means of Olivos theorem [13], group operations with the addition chain of length l can be accomplished with \(l+s-1\) operations in the group including squaring and addition of element of the group. However, it has been shown that finding a minimal length addition sequence is an NP-hard problem.

Hashing into \({\mathbb {G}}_{2}\)

Real protocols such as Franklin’s identity-based encryption scheme require hashing of identities to \({\mathbb {G}}_{1}\) or \({\mathbb {G}}_{2}.\) The general approach to construct secure hash functions for hashing an identity to the group G of order r on an elliptic curve \(E({\mathbb {F}}_{p})\) consists to: first step to transform an arbitrary binary message (the identity) to an element x of \({\mathbb {F}}_{p} .\) Second step solves the quadratic curve equation on \({\mathbb {F}}_{p}\) to find a y coordinate (change x if y does not exist) and finally carry the point P of coordinate (x, y) to some elliptic curve subgroup \({\mathbb {G}}_{1}=E({\mathbb {F}}_{p})[r]\) or \({\mathbb {G}}_{2}={\tilde{E}}({\mathbb {F}}_{p^{k/d}})[r]\) by multiplying the point P by cofactor c,  where \(\#{\tilde{E}}( {\mathbb {F}}_{p} )=c.r.\)

When hashing to \({\mathbb {G}}_{1}\), the cofactor c and p / r have almost the same size and the hashing is considered to be easier than when hashing to \({\mathbb {G}}_{2}\) . In fact, in \({\mathbb {G}}_{2}\), the length of c increases and it is of the same size with \(p^{k/d}/r,\) so that the scalar multiplication becomes really costly. Therefore, it is of great interest to make hashing into \({\mathbb {G}}_{2}\) fast.

Hashing into \({\mathbb {G}}_{2}\) with Scott et al. Method

Let \(\phi : {\tilde{E}}\rightarrow E\) be the twist isomorphism from \({\tilde{E}}\) to E and \(\pi\) be the pth power Frobenius on E. Scott et al. realized that the endomorphism \(\psi =\phi ^{-1}\circ \pi \circ \phi\) can be used to quicken the computation of \(c\cdot P\) (this was noted in [14]).

The endomorphism \(\psi\) satisfies

$$\begin{aligned} \psi ^2(P)-[t]\psi (P)+[p]P={\mathcal {O}} . \end{aligned}$$
(2)

The idea of Scott is to first express c to the base p as

$$\begin{aligned} c=c_{0}+c_{1}p+c_{2}p^2+\cdots +c_{l}p^l \end{aligned}$$

and then use the identity \([p]P=[t]\psi (P)-\psi ^2(P) ,\) so

$$\begin{aligned}{}[c]P& = [c_{0}]P+[c_{1}p]P+[c_{2}p^2]P+\cdots +[c_{l}p^l]P ,\\& = [c_{0}]P+[c_{1}t]\psi (P)+[-c_{1}+c_{2}t^2]\psi ^2(P)+\cdots ,\\& = [g_{0}]P+[g_{1}]\psi (P)+[g_{2}]\psi ^2(P)+\cdots +[g_{2l}]\psi ^{2l}(P). \end{aligned}$$

where every \(g_{i}\) is a polynomial in x with degree smaller than the degree of p.

For a parameterized family of curves, the method requires first to pre-calculate the cardinality \({\tilde{n}}\in {\mathbb {Q}}[x]\) of \({\tilde{E}}({\mathbb {F}}_{q^{k/d}})\), where d is from the set of possible twist degrees \(\{1; 2; 3; 4; 6\}\), and is usually the maximum from this set that divides k. The application ends by the execution of the algorithm 2 in [9] which determine the coefficients of the polynomial [c(x)]P in \(\psi (P)\) where \(c(x) =\frac{{\tilde{n}}}{r(x)}\).

In what follows the Scott et al. hashing method is applied to Aurifeuillean curves [12] having embedding degree k equal to 6, 9, 15, 27 and 54.

Aurifeuillean Curves-6

The Aurifeuillean pairing-friendly curves-6 has an embedding degree of \(k = 6\). We consider the zero j-invariant curves having twist curves \({\tilde{E}}\) with degree \(d = 6\). This defines the group \({\mathbb {G}}_{2}\) as \({\mathbb {G}}_{2}= {\tilde{E}}({\mathbb {F}}_{p^{k/d}})(r)= {\tilde{E}}({\mathbb {F}}_{p})(r)\). The curve is parametrized by the polynomials:

$$\begin{aligned} p& = 9x^4+18x^3+18x^2+6x+1\\ r& = 3x^2+3x+1\\ t& = 3x^2+1,\\ \end{aligned}$$

The order of the group \({\tilde{E}}( {\mathbb {F}}_{p} )\) is c(x)r(x) ,  where c(x)

$$\begin{aligned} c(x)& = 3x^2+3x+3. \end{aligned}$$

for some rational point \(P\in {\tilde{E}}( {\mathbb {F}}_{p} ),\)

$$\begin{aligned}{}[c(x)]P& = [3x^2+3x+3]P. \end{aligned}$$

To evaluate the cost of the operations [c(x)]P,  we first calculate \([2]P+P=[3]P\) then \([x]([3]P)=[3x]P\) and \([x]([3x]P)=[3x^2]P .\) It is made of three point additions, one point doubling and two scalar multiplications by x.

Aurifeuillean Curves-9

The Aurifeuillean curves-9 family of elliptic curves has an embedding degree of \(k = 9,\) and an associated twist curve \({\tilde{E}}\) with degree \(d = 3\). This defines the group \({\mathbb {G}}_{2}\) as \({\mathbb {G}}_{2}= {\tilde{E}}({\mathbb {F}}_{p^{k/d}})(r)= {\tilde{E}}({\mathbb {F}}_{p^{3}})(r)\). The curve is parametrized by the polynomials:

$$\begin{aligned} p& = 81\,{x}^{8}+27\,{x}^{6}+27\,{x}^{5}-18\,{x}^{4}+9\,{x}^{3}+3\,{x}^{2}-3\,x+1\\ r& = 27x^6+9x^3+1\\ t& = -18x^4-3x+1 \end{aligned}$$

The cofactor of \(\#{\tilde{E}}({\mathbb {F}}_{p^{3}})\) relatively to r(x) yields,

$$\begin{aligned} c(x)& = 19683\,{x}^{18}+19683\,{x}^{16}+13122\,{x}^{15}-6561\,{x}^{14}\\&\quad +13122\, {x}^{13}-4374\,{x}^{12}-2187\,{x}^{11}\\&\quad +\,5103\,{x}^{10}-3402\,{x}^{9}+ 972\,{x}^{8}+729\,{x}^{7}-891\,{x}^{6}\\&\quad +486\,{x}^{5}-99\,{x}^{3}+45\,{x }^{2}-9\,x+1 . \end{aligned}$$

Applying Scott et al. method (algorithm 2 in [9]), the scalar multiplication [c(x)]P,  for some rational point \(P\in {\tilde{E}}( {\mathbb {F}}_{p^3} ),\) is reduced to

$$\begin{aligned} {[}c(x)]P& = \left[ -27\,{x}^{6}+81\,{x}^{5}-27\,{x}^{3}+6\,{x}^{2}+18\,{x}^{4}\right] P \\&\quad +\left[ -54\,{x}^{ 6}-9\,{x}^{3}+9\,{x}^{2}-27\,{x}^{4}-3\,x\right] \psi (P)\\&\quad +\,\left[ 1-54\,{x}^{6}-27\,{x}^{4}-9 \,{x}^{3}-3\,x\right] \psi ^2(P)\\&\quad +\,\left[ 36\,{x}^{4}-108\,{x}^{6}+6\,x-18\,{x}^{3}-2-6\,{x}^{2}\right] \psi ^3(P)\\&\quad+[-9\,{x}^{2}+1]\psi ^4(P). \end{aligned}$$

In addition, we put into factor the common coefficients:

$$\begin{aligned} {[}c(x)]P& = [108](\psi ^3([x^6]P))+[81]([x^5]P)\\&\quad +[54]\left( -\psi ([x^6P])-\psi ^2([x^6]P)\right) +[36](\psi ^3([x^4]P))\\&\quad + [27]\left( -[x^3]P-[x^6]P-\psi ([x^4]P)-\psi ^2([x^4]P)\right) \\&\quad +[18]([x^4]P-\psi ^3([x^3]P)) \\&\quad +\,[9]\left( -\psi ([x^3]P)+\psi ([x^2]P)-\psi ^2([x^3]P) -\psi ^4([x^2]P)\right) \\&\quad +[6]\left( [x^2]P+\psi ^3([x]P) \right) \\&\quad +\, [3]\left( -\psi ([x]P)-\psi ^2([x]P) \right) +[2](-\psi ^3(P))\\&\quad +[1]\left( \psi ^2(P)+\psi ^4(P)\right) \end{aligned}$$

There are 11 point additions inside the brackets. Then, extracting all the \(s=11\) coefficients below and constructing the addition chain:

$$\begin{aligned} \left\{ 1,\fbox {2},3,\fbox {6},9,\fbox {18},27,36,54,81,108 \right\} \end{aligned}$$

of length \(l=10 .\) The numbers in box are results of adding a number that comes before by itself. By Olivos theorem [13], the number of group operations is \(l+s-1=10+11-1=20\), which includes 3 point doubling (number of elements in box) and 17 extra point additions. To evaluate the rest of cost operations, we first calculate [x]P,  \([x^2]P=[x].([x]P),\) \([x^3]P=[x].([x^2]P),\) \([x^4]P=[x].([x^3]P),\) \([x^5]P=[x].([x^4]P),\) \([x^6]P=[x].([x^5]P).\) For \(i=1\) to 4 we evaluate \(\psi ^i(P),\) \(\psi ^i([x]P),\) \(\psi ^i([x^2]P),\) \(\psi ^i([x^3]P),\) \(\psi ^i([x^4]P),\) \(\psi ^i([x^5]P)\) and \(\psi ^i([x^6]P) .\) Just the values which appeared in the decomposition of [c(x)]P are needed.

In total, hashing to \({\mathbb {G}}_{2}\) in this family of curves has a cost of twenty eight point additions, three point doubling, six scalar multiplications by the parameter x and twenty \(\psi\) maps.

Aurifeuillean Curves-18

This family of curves has embedding degree \(k=18\) and is parameterised by the polynomials:

$$\begin{aligned} p& = 243\,{x}^{10}+1-162\,{x}^{8}+81\,{x}^{7}+27\,{x}^{6}-54\,{x}^{5}+9\,{x }^{4}+9\,{x}^{3}-3\,{x}^{2}.\\ r& = 27\,{x}^{6}+9\,{x}^{3}+1\\ t& = 3x^2+1 \end{aligned}$$

The zero j-invariant curves have twists of order 6. In this case, the group \({\mathbb {G}}_{2}\) is expressed as a subgroup of \({\tilde{E}}( {\mathbb {F}}_{p^3} ) .\) Then, c(x) is of degree 24. Applying Scott et al. method, [c(x)]P,  for \(P\in {\tilde{E}}( {\mathbb {F}}_{p^3} ),\) is reduced to

$$\begin{aligned} {[}c(x)]P& = \Bigg [2+81\,{x}^{8}-243\,{x}^{7}+81\,{x}^{5}\\&\quad -45\,{x}^{4}-18\,{x}^{3}+243\,{ x}^{9}+9\,{x}^{2}+27\,{x}^{6} \Bigg ]P\\&\quad +\,\Bigg [-27\,{x}^{6}+81\,{x}^{8}-9\,{x}^{4}+3\,{ x}^{2}\Bigg ] \psi (P)\\&\quad +\,\Bigg [81\,{x}^{8}+1-27\,{x}^{6}-3\,{x}^{2}\Bigg ]\psi ^2(P)\\&\quad +\,\Bigg [6\,{x}^{2}-54\,{x}^{6}+18 \,{x}^{4}-2\Bigg ] \psi ^3(P)\\&\quad +\,\Bigg [9\,{x}^{4}-6\,{x}^{2}+1\Bigg ]\psi ^4(P). \end{aligned}$$

The construction of addition chain yields, \(\{1,\fbox {2},3,\fbox {6},9,\fbox {18},27,45,\fbox {54},81, \underline{\fbox {162}},243 \}\) of length \(l=11 .\) The underline number is not among coefficients of the expression of [c(x)]P, but added to build addition chain. By Olivos theorem, the number of group operations is \(l+s-1=11+11-1=21\) plus 12 extra operations which from the number of additions of points of the same coefficient. The final cost is made by 5 point doublings, 28 point additions, 9 scalar multiplications by the parameter x, and 20 applications of \(\psi .\)

Aurifeuillean Curves-15

This family of curves has embedding degree \(k=15\) and is parametrized by the polynomials:

$$\begin{aligned} p& = 729\,{x}^{12}+243\,{x}^{10}+81\,{x}^{7}+54\,{x}^{6}+27\,{x}^{5}+3\,{x}^{2}+3\,x+1.\\ r& = 81\,{x}^{8}+81\,{x}^{7}+54\,{x}^{6}+27\,{x}^{5}+9\,{x}^{4}+9\,{x}^{3}+6\,{x}^{2}+3\,x+1\\ t& = 54\,{x}^{6}+3\,x+1 \end{aligned}$$

In this case, the group \({\mathbb {G}}_{2}\) is expressed as a subgroup of \({\tilde{E}}( {\mathbb {F}}_{p^5} ) .\) Then, c(x) is of degree 52. Applying Scott et al. method, [c(x)]P,  for \(P\in {\tilde{\mathbf{E }}}( {\mathbb {F}}_{p^5} ),\) is reduced to

$$\begin{aligned}{}[\lambda _{0}]P+\sum _{i=1}^{7}[\lambda _{i}]\psi ^i(P) \end{aligned}$$
(3)

where \(\lambda _{0},\lambda _{1},\lambda _{2},\lambda _{3},\lambda _{4},\lambda _{5},\lambda _{6}\) and \(\lambda _{7}\) are polynomials of \({\mathbb {Z}}[x]\) of degree less than or equal to 11. To ease the readability, these polynomials are fully reported in Appendix A. The scalar multiplication [c(x)]P can be calculated at the cost of 11 scalar multiplications by x and 83 applications of \(\psi .\)

Aurifeuillean Curves-27

The Aurifeuillean curves-27 has embedding degree \(k=27\) and twists of degree \(d=3\) The curve is giving by the following polynomial parametrization:

$$\begin{aligned} p& = 177147\,{x}^{22}+1+118098\,{x}^{20}+19683\,{x}^{18}+2187\,{x}^{13}\\&\quad + 1458\,{x}^{11}+243\,{x}^{9}+9\,{x}^{4}+3\,{x}^{2}\\ r& = 19683\,{x}^{18}+243\,{x}^{9}+1\\ t& = -3\,{x}^{2}+1 \end{aligned}$$

The group \({\mathbb {G}}_{2}\) is expressed as a subgroup of \({\tilde{E}}( {\mathbb {F}}_{p^9} ) .\) Then, c(x) is of degree 180. Applying Scott et al method, [c(x)]P,  for \(P\in {\tilde{E}}( {\mathbb {F}}_{p^9} ),\) is reduced to

$$\begin{aligned}{}[\lambda _{0}]P+\sum _{i=1}^{16}[\lambda _{i}]\psi ^i(P) \end{aligned}$$
(4)

where \(\lambda _{i},\) for \(i=0,1,\ldots ,16\) are polynomials of \({\mathbb {Z}}[x]\) of degree less than or equal to 21 (see Appendix B for their complete expressions). The multiplication [c(x)]P can be calculated at the cost of 21 scalar multiplications by x and 240 applications of \(\psi .\)

Aurifeuillean Curves-54

The Aurifeuillean curves-54 has embedding degree \(k=54\) and is parametrized by the polynomials:

$$\begin{aligned} p& = 59049\,{x}^{20}+59049\,{x}^{19}+19683\,{x}^{18}+1+729\,{x}^{11}+972\,{ x}^{10}+243\,{x}^{9}+3\,{x}^{2}+3\,x.\\ r& = 19683\,{x}^{18}+243\,{x}^{9}+1\\ t& = 243\,{x}^{10}+1,\\ \end{aligned}$$

The corresponding zero j-invariant curve has twist of degree \(d=6 ,\) and the group \({\mathbb {G}}_{2}\) is expressed as a subgroup of \({\tilde{E}}( {\mathbb {F}}_{p^9} ) ,\) then the cofactor is c(x) of degree 162. Applying Scott et al method, [c(x)]P,  for \(P\in {\tilde{\mathbf{E }}}( {\mathbb {F}}_{p^9} ),\) is reduced to

$$\begin{aligned}{}[\lambda _{0}]P+\sum _{i=1}^{10}[\lambda _{i}]\psi ^i(P), \end{aligned}$$
(5)

where \(\lambda _{0},\lambda _{1},\lambda _{2},\lambda _{3},\lambda _{4},\lambda _{5},\lambda _{6},\lambda _{7},\lambda _{8},\lambda _{9}\) and \(\lambda _{10}\) are polynomials of \({\mathbb {Z}}[x]\) of degree less than or equal to 19 (see Appendix C for their complete forms). The multiplication [c(x)]P can be calculated at the cost 19 scalar multiplications by x and 159 applications of \(\psi .\)

Comparison with Others Pairing-Friendly Elliptic Curves

Previous works [9, 11] on hashing into \({\mathbb {G}}_{2}\) using the Scott et al.’s method with BLS curves, MNT curves, KSS curves, and Freeman curves provided some computational costs that we confront to the results obtained in this work. We consider the notations A for point addition, D for point doubling, X for a scalar multiplication by the parameter x and \(\psi\) an application of the endomorphism \(\psi (.) .\) The endomorphism \(\psi\) can be efficiently calculated, whereas the multiplication by x,  is most costly, since x is large and the algorithm to compute large scalar multiplications require many point additions and doubling. The comparison is given in Table 1.

Table 1 Cost summary of hashing into \({\mathbb {G}}_{2}\) using the Scott et al.
Full size table

Hashing into \({\mathbb {G}}_{2}\) with Fuentes et al. Method

Fuentes et al. discovered that instead of multiplying the polynomial c(x) by the point P of elliptic curve as in the Scott et al. method, and it is sufficient to multiply P by \(c'\) a multiple of c, such that \(c'\) do not vanish modulo r.

Indeed, let f and \({\tilde{f}}\) be such that \(t^2-4p=Df^2\) and \({\tilde{t}}^2-4q=D{\tilde{f}}^2\), where D is the discriminant, \(n+t=p+1\) and \({\tilde{n}} + {\tilde{t}}=q+1\) where \(n=\# E({\mathbb {F}}_{p})\), \({\tilde{n}}=\# {\tilde{E}}({\mathbb {F}}_{q})\) and q a power of p. The Lemma 1 shows that \({\tilde{E}}({\mathbb {F}}_{q})\) is stable by \(\psi ,\) and the Lemma 2 illustrates the effect of \(\psi\) on the element of twisted curve \({\tilde{E}}({\mathbb {F}}_{q}) .\) (see [10] for evidence)

Lemma 1

If \(p\equiv 1 \mod d ,\) then \(\psi (Q) \in {\tilde{E}}({\mathbb {F}}_{q})\) for all \(Q\in {\tilde{E}}({\mathbb {F}}_{q}).\)

Lemma 2

If \(p\equiv 1 \mod d ,\) \(gcd({\tilde{f}},{\tilde{n}})=1\) and \({\tilde{E}}({\mathbb {F}}_{q})\) is a cyclic group, then \(\psi (Q)=aQ\) for all \(Q\in {\tilde{E}}({\mathbb {F}}_{q}),\) where a is

$$\begin{aligned} \frac{t}{2}+\frac{f({\tilde{t}}-2)}{2{\tilde{f}}} \quad or \quad \frac{t}{2}-\frac{f({\tilde{t}}-2)}{2{\tilde{f}}}. \end{aligned}$$
(6)

Theorem 4

[10] Suppose that \({\tilde{E}} ({\mathbb {F}}_{q})\) is cyclic and \(p\equiv 1 \mod d\).

Then, there exists a polynomial

$$\begin{aligned} h(z)=h_{0}+h_{1}z+\cdots +h_{\varphi (k)-1}z^{\varphi (k)-1} \end{aligned}$$

in \({\mathbb {Z}}[z]\) such that \([h(\psi )]Q\) is a multiple of [c]Q for all \(Q\in {\tilde{E}}({\mathbb {F}}_{q})\) and \(|h_{i}|^{\varphi (k)}\le \#{\tilde{E}}({\mathbb {F}}_{q})/r\) for all i.

Fuentes noticed that polynomials \(h\in {\mathbb {Z}}[z]\), such that \(h(a)\equiv 0 \mod c\) correspond to points in the integer lattice generated by the matrix:

$$\begin{aligned} M= \left( \begin{array}{c|c} c &{} 0 \\ \hline A &{} I_{\varphi (k)-1} \end{array}\right) \end{aligned}$$

where A is a column vector with ith entry \(-a^i\mod c ,\) \(i=1,2,\ldots ,\varphi (k)-1 .\)

The method begins as the Scott et al. method for obtaining \({\tilde{n}}\) the order of twisted curve \({\tilde{E}}\) and c(x) its cofactor relatively to r(x). We also find a(x) as defined in Lemma 2 and set the matrix M. Then used LLL algorithm [15] to reduce the coefficients of the matrix M. The linear combination of the rows of the reduced matrix obtained yields

$$\begin{aligned} h(z)=h_{0}(x)+h_{1}(x)z+h_{2}(x)z^2+\cdots \end{aligned}$$

and the final step of hashing into \({\mathbb {G}}_{2}\) with Fuentes et al. method is

$$\begin{aligned}{}[h(\psi )]P=[h_{0}(x)]P+[h_{1}(x)]\psi (P)+[h_{2}(x)]\psi (P)^2+\cdots \end{aligned}$$

The pre-computation is done using the software Maple and the LLL reduction is done using Magma V2.24-1 calculator

We applied Fuentes et al. hashing method to Aurifeuillean curves having embedding degree k equal to 6, 9, 18, 27 and 54. But we does not applied the method for \(k=15\), because the condition that the cyclotomic polynomial map to a (see Eq. 6) modulo the order of the twisted curve does not hold.

Aurifeuillean Curves-6

For the Aurifeuillean curves with \(k=6,\), the parameter a from Lemma2 is the following polynomial in x.

$$\begin{aligned} a(x)& = \frac{t}{2}+\frac{f({\tilde{t}}-2)}{2{\tilde{f}}} \mod {\tilde{n}}(x) \\& = 12x^2+6x^3+8x+3 \end{aligned}$$

We set

$$\begin{aligned} M= \left( \begin{array}{c|c} c(x) &{} 0 \\ -a(x) \mod c(x) &{} 1 \end{array}\right) . \end{aligned}$$

and the LLL reduction of M yields

$$\begin{aligned} LLL(M)=\left[ \begin{array}{cc} -{\frac{13}{4}}\,x+1/4&{}0\\ x+3/4&{}1/4\end{array} \right] . \end{aligned}$$

By multiplying the last row by 4 and setting \(h(z)=(4x+3)+z,\) \(h(a(x))=2(x+1)c(x) \mod {\tilde{n}}(x),\) with \(gcd(2x+2, r(x))=1.\) Hence, if \(P\in {E}( {\mathbb {F}}_{p(x)} ),\) then [h(a)]P is a multiple of [c]P and \([h(a)]P=[h(\psi )]P,\) so

$$\begin{aligned}{}[h(\psi )]P= [4x+3]P+\psi (P). \end{aligned}$$

\([3]P=[2]P+P,\) \([4x]P=[x]([2]([2]P)) ,\) then \([h(\psi )]P\) can be computed at the cost of 3 point additions, 2 point doubling, 1 scalar multiplication by the parameter x and 1 applications of \(\psi .\)

Aurifeuillean Curves-9

For the Aurifeuillean curves with \(k=9\), the parameter a is given by

$$\begin{aligned} a(x)& = -{\frac{2424212632}{217993987}}\,x+{\frac{5143304439}{217993987}}\,{ x}^{2}\\&\quad-\,{\frac{2610122718}{217993987}}\,{x}^{3}-{\frac{28189433622483 }{217993987}}\,{x}^{18}\\&\quad+\,{\frac{2506275703512}{217993987}}\,{x}^{16}-{ \frac{12796629413985}{217993987}}\,{x}^{15}\\&\quad+\,{\frac{1222024507191}{ 217993987}}\,{x}^{14} +{\frac{1016530951635}{217993987}}\,{x}^{13}\\&\quad-\,{ \frac{3969053944218}{217993987}}\,{x}^{12}+{\frac{1767566638755}{ 217993987}}\,{x}^{11}\\&\quad-{\frac{302386560777}{217993987}}\,{x}^{10}-{ \frac{838029510945}{217993987}}\,{x}^{9}\\&\quad+\,{\frac{547494386031}{ 217993987}}\,{x}^{8}-{\frac{185168432511}{217993987}}\,{x}^{7}\\&\quad-\,{ \frac{94951444725}{217993987}}\,{x}^{6}+{\frac{81127529640}{ 217993987}}\,{x}^{5}\\&\quad-\,{\frac{10251013101543}{217993987}}\,{x}^{22}-{ \frac{428418209700}{2986219}}\,{x}^{21}\\&\quad-\,{\frac{38370288560094}{ 217993987}}\,{x}^{20}-{\frac{5671787322267}{217993987}}\,{x}^{19}\\&\quad+\,{ \frac{359339840}{217993987}}-{\frac{11556879138387}{217993987}}\,{x} ^{17}\\&\quad-\,{\frac{34656702615}{217993987}}\,{x}^{4}-{\frac{27153033524343 }{217993987}}\,{x}^{23}. \end{aligned}$$

Setting

$$\begin{aligned} M= \left( \begin{array}{c|ccccc} c(x) &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ -a(x) \mod c(x) &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ -a(x)^2 \mod c(x) &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ -a(x)^3 \mod c(x) &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 \\ -a(x)^4 \mod c(x) &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \\ -a(x)^5 \mod c(x) &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \end{array}\right) \end{aligned}$$

and using LLL algorithm, we obtain the matrix with small coefficients:

$$\begin{aligned} \left[ \begin{array}{cccccc} -1/3\,{x}^{2}-1/3\,x&{}1/3\,x-1/9&{}-2/3\,{ x}^{2}+2/9&{}1/3\,{x}^{2}-1/3\,x&{}1/3\,x+1/9&{}{x}^{3}-1/3\,{x}^{2}+1/9\\ 1/3\,x-1/9&{}-2/3\,{x}^{2}+2/9&{}2/3\,{x}^{2}&{}1/3\,x+1 /9&{}{x}^{3}-1/3\,{x}^{2}+1/9&{}1/3\,{x}^{2}+1/3\,x\\ -2/ 3\,{x}^{2}+2/9&{}2/3\,{x}^{2}&{}2/9&{}{x}^{3}-1/3\,{x}^{2}+1/9&{}1/3\,{x}^{2}+ 1/3\,x&{}-1/3\,x+1/9\\ 2/3\,{x}^{2}&{}2/9&{}{x}^{3}+1/3\,{x }^{2}-1/9&{}1/3\,{x}^{2}+1/3\,x&{}-1/3\,x+1/9&{}2/3\,{x}^{2}-2/9 \\ 2/9&{}{x}^{3}+1/3\,{x}^{2}-1/9&{}-1/3\,{x}^{2}+1/3\,x&{} -1/3\,x+1/9&{}2/3\,{x}^{2}-2/9&{}-2/3\,{x}^{2}\\ {x}^{3}+ 1/3\,{x}^{2}-1/9&{}-1/3\,{x}^{2}+1/3\,x&{}-1/3\,x-1/9&{}2/3\,{x}^{2}-2/9&{}-2/ 3\,{x}^{2}&{}-2/9\end{array} \right] \end{aligned}$$

Taking the 6th row of the above matrix when multiplied by 9 we defined the polynomial:

$$\begin{aligned} h(z)& = 9\,{x}^{3}+3\,{x}^{2}-1+ \left( -3\,{x}^{2}+3\,x \right) z\\&\quad+ \left( -3 \,x-1 \right) {z}^{2}+ \left( 6\,{x}^{2}-2 \right) {z}^{3}-6\,{x}^{2}{ z}^{4}-2\,{z}^{5} . \end{aligned}$$

\(h(a(x))\equiv (9x^3+1)c(x) \mod \tilde{n}(x),\) with \(\gcd (r(x),9x^3+1)=1 .\) Hence if \(P\in {\tilde{E}}( {\mathbb {F}}_{p(x)^2} ),\) then [h(a)]P is a multiple of [c]P and \([h(a)]P=[h(\psi )]P.\)

$$\begin{aligned}{}[h(\psi )]P& = [9\,{x}^{3}+3\,{x}^{2}-1]P+ \left[ -3\,{x}^{2}+3\,x \right] \psi (P)\\&\quad+ \left[ -3 \,x-1 \right] {\psi (P)}^{2}+ \left[ 6\,{x}^{2}-2 \right] {\psi (P)}^{3}\\&\quad-\,[6\,{x}^{2}]{ \psi (P)}^{4}-[2]\,{\psi (P)}^{5}. \end{aligned}$$

That can be computed at the cost of 12 point additions,2 point doublings, 3 scalar multiplications by the parameter x and 11 applications of \(\psi\).

Aurifeuillean Curves-18

For Aurifeuillean curves with \(k=18,\) we follow the same process as above and obtain the polynomial:

$$\begin{aligned} h(z)& = -3\,{x}^{3}+x-1+ \left( 9\,{x}^{4}-3\,{x}^{2}+x \right) z+ \left( 3\,{ x}^{2}-1 \right) {z}^{2}\\&\quad+ \left( -3\,{x}^{3}+x+1 \right) {z}^{3}-2\,x{ z}^{4} \end{aligned}$$

with \(h(a(x))\equiv -3(9x^3+2)c(x) \mod \tilde{n}(x)\) and \(\gcd (r(x),-3(9x^3+2))=1 .\)

For every \(P\in {\tilde{E}}( {\mathbb {F}}_{p(x)^3} ) ,\)

$$\begin{aligned}{}[h(\psi )]P& = [-3\,{x}^{3}+x-1]P+ \left[ 9\,{x}^{4}-3\,{x}^{2}+x \right] \psi (P)\\&\quad+ \left[ 3\,{ x}^{2}-1 \right] {\psi (P)}^{2} \\&\quad+\,[-3\,{x}^{3}+x+1]{ \psi (P)}^{3}+[-2x]\,{\psi (P)}^{4}. \end{aligned}$$

That can be computed at the cost of 14 point additions, 2 point doublings, 4 scalar multiplications by the parameter x and 13 applications of \(\psi\).

Aurifeuillean Curves-27

For Aurifeuillean curves with \(k=27,\) the polynomial yields

$$\begin{aligned} h(z)& = 81x^9+27x^7+1+(-27x^7-9x^5)z\\&\quad+(9x^5+3x^3)z^2+(-3x^3-x)z^3\\&\quad+\,(-243x^{10}-81x^8-x)z^4+(81x^8+27x^6)z^5\\&\quad+(-27x^6-9x^4)z^6+(9x^4+3x^2)z^7\\&\quad+\,(-3x^2-1)z^8+(-81x^9-27x^7+1)z^9\\&\quad+(27x^7+9x^5)z^{10}+(-9x^5-3x^3)z^{11}\\&\quad+\,(3x^3+x)z^{12}+(-2x)z^{13} \end{aligned}$$

with \(h(a(x))\equiv 81x^9c(x) \mod \tilde{n}(x)\) and \(\gcd (r(x),81x^9)=1 .\) For every \(P\in {\tilde{E}}( {\mathbb {F}}_{p(x)^9} ),\)

$$\begin{aligned} {[}h(\psi )]P& = [81x^9+27x^7+1]P+ [ -27x^7-9x^5 ] \psi (P)\\&\quad+ [ 9x^5+3x^3 ] {\psi (P)}^{2} +[-3x^3-x]{ \psi (P)}^{3}\\&\quad+[-243x^10-81x^8-x]\,{\psi (P)}^{4}\\&\quad+[81x^8+27x^6]\,{\psi (P)}^{5}\\&\quad+\,[-27x^6-9x^4]\,{\psi (P)}^{6}+[9x^4+3x^2]\,{\psi (P)}^{7}\\&\quad+[-3x^2-1]\,{\psi (P)}^{8}\\&\quad+\,[-81x^9-27x^7+1]\,{\psi (P)}^{9}\\&\quad+[27x^7+9x^5]\,{\psi (P)}^{10}+[-9x^5-3x^3]\,{\psi (P)}^{11}\\&\quad+\,[3x^3+x]\,{\psi (P)}^{12}+[-2x]\,{\psi (P)}^{13}. \end{aligned}$$

That can be computed at the cost of 33 point additions, 5 point doublings, 10 scalar multiplications by the parameter x and 94 applications of \(\psi\).

Aurifeuillean Curves-54

For Aurifeuillean curves with \(k=54,\) we obtain the following polynomial:

$$\begin{aligned} h(z)& = 2x+1+(81x^9-1)z+(27x^7)z^2\\&\quad+(-27x^7-27x^6)z^3+(27x^6+18x^5)z^4\\&\quad+\,(-18x^5-9x^4)z^5+(9x^4+3x^3)z^6\\&\quad+(-3x^3)z^7+(-x)z^8+(-x)z^9\\&\quad+\,(81x^9+81x^8+1)z^{10}+(-81x^8-54x^7)z^{11}\\&\quad+(54x^7+27x^6)z^{12}+(-27x^6-9x^5)z^{13}\\&\quad+\,(9x^5)z^{14}+(3x^3)z^{15}\\&\quad+(-3x^3-3x^2)z^{16}+(3x^2+2x)z^{17} \end{aligned}$$

with \(h(a(x))\equiv 3x(81x^9+1)c(x) \mod \tilde{n}(x)\) and \(\gcd (r(x),3x(81x^9+1))=1.\) For every \(P\in {\tilde{E}}( {\mathbb {F}}_{p(x)^9} ),\)

$$\begin{aligned} {[}h(\psi )]P& = [2x+1]P+ \left[ 81x^9-1 \right] \psi (P)+ \left[ 27x^7 \right] {\psi (P)}^{2} \\&\quad+[-27x^7-27x^6]{ \psi (P)}^{3}+\,[27x^6+18x^5]\,{\psi (P)}^{4}\\&\quad+[-18x^5-9x^4]\,{\psi (P)}^{5}+[9x^4+3x^3]\,{\psi (P)}^{6}\\&\quad+\,[-3x^3]\,{\psi (P)}^{7}+[-x]\,{\psi (P)}^{8}+[-x]\,{\psi (P)}^{9}\\&\quad+[81x^9+81x^8+1]\,{\psi (P)}^{10}+\,[-81x^8-54x^7]\,{\psi (P)}^{11}\\&\quad+[54x^7+27x^6]\,{\psi (P)}^{12}+[-27x^6-9x^5]\,{\psi (P)}^{13}\\&\quad+\,[9x^5]\,{\psi (P)}^{14}+[3x^3]\,{\psi (P)}^{15}+[-3x^3-3x^2]\,{\psi (P)}^{16}\\&\quad+[3x^2+2x]\,{\psi (P)}^{17}. \end{aligned}$$

That can be computed at the cost of 33A point additions, 4 point doublings, 9 scalar multiplications by the parameter x and 126 applications of \(\psi\).

Comparison with Others Pairing Friendly Elliptic Curves

In Table 2, we recapitulate the computational costs of hashing into \({\mathbb {G}}_{2}\) using Fuentes et al. method with Aurifeuillean curves, KSS curves, Freeman curve and BN curves. As with Scott et al.’s method for \(k=18\) hashing with KSS curve is more efficient than with Aurifeuillean curve as far as group operations is concerned.

Table 2 Cost summary of hashing into \({\mathbb {G}}_{2}\) using the Fuentes et al.
Full size table

In Table 3, we carry out the computational costs of hashing into \({\mathbb {G}}_{2}\) using the Scott et al.’s and Fuentes et al.’s methods with Aurifeuillean curves with embedding degrees \(k=6,9,18,27\) and \(k=54 .\) We observe that for the two first cases, the Fuentes et al.’s method is twice as fast than the one of Scott et al. method. For \(k=18,27\) and 54, the Fuentes et al.’s method determines a 9/4, 21/10 and 19/8-fold improvement respectively. Previous works show that is it more efficient to hashing into \({\mathbb {G}}_{2}\) using the Fuentes et al.’s method with BLS, BN, and KSS curves. Our results on Aurifeuillean curve also confirm this assertion.

Table 3 Comparison between the computational cost of each hash map
Full size table

Conclusion

This work investigated on an efficient hashing into \({\mathbb {G}}_{2}\) to on the recent Scott–Guillevic Aurifeuillean curves. We applied the two existing hashing methods namely the Scott et al. and Fuentes et al. methods. Our results show that hashing on Auriffeuillean curves with embedding degree \(k=6,9, 18, 27\) and 54 is more costly than hashing on the well known BLS curves, KSS curves, or BN curves for comparable embedding degrees. Our results also confirm that hashing into \({\mathbb {G}}_{2}\) using the Fuentes et al.’s method is more efficient that using the Scott et al. method as reported in the previous work on the literature.