In
[
18], Gallant, Lambert and Vanstone give a method to speed up scalar multiplications [
w]
P in
\(E({\mathbb {F}}_q)[r]\). This method is based on the knowledge of a non-trivial multiple of the point
P, that is obtained from an efficiently computable endomorphism
\(\omega : E \rightarrow E\) such that
\(\omega (P)\) is a multiple of
P. Building on this idea, Galbraith and Scott
[
17] reduced the computational cost of multiplying by the cofactor
c introducing a suitable group endomorphism
\(\psi :{\tilde{E}} \rightarrow {\tilde{E}}\). Such an endomorphism is defined as
\(\psi =\phi ^{-1} \circ \pi \circ \phi\), where
\(\pi\) is the
q-power Frobenius on
E and
\(\phi\) is an isomorphism from the twist curve
\({\tilde{E}}\) to
E. The endomorphism
\(\psi\) satisfies
$$\begin{aligned} \psi ^2(P)-[t]\psi (P)+[q]P=\infty \end{aligned}$$
(1)
for all
\(P \in {\tilde{E}}({\mathbb {F}}_{q^{k/d}})\). In the above relation
t is the trace of Frobenius
\(q+1-\#E({\mathbb {F}}_q)\). Galbraith and Scott proposed to first express the cofactor
c to the base
q as
$$\begin{aligned} c=c_0+c_1q+\cdots +c_{\ell }q^{\ell } \end{aligned}$$
(2)
and then use (
1) to simplify the multiplication
cP as
$$\begin{aligned}{}[g_0]P+[g_1]\psi (P)+\cdots +[g_{2\ell }]\psi ^{2\ell }(P) \end{aligned}$$
(3)
where
\(\mid g_i \mid < q\) for every
i.
2.1 Scott et al. method
The above approach was further developed by Scott et al. in
[
33], where it is applied to several families of pairing-friendly curves. In particular, the curves taken into account in
[
33] are: the MNT curves for the case
\(k=6\), the BN curves with
\(k=12\), the Freeman curves with
\(k=10\) and the KSS curves for the cases
\(k=8\) and
\(k=18\). It is important to highlight that all these families are composed by curves defined over a prime field
\({\mathbb {F}}_p\), with
p, the order
r and the trace
t expressed as polynomials having rational coefficients. Consequently, also the cofactor
c can be described as a polynomial in
\({\mathbb {Q}}[x]\). Thanks to such a parameterisation, Scott et al. speed up the cofactor multiplication [
c]
P reducing it to the evaluation of a polynomial of the powers
\(\psi ^{i}(P)\), with coefficients that are polynomials in
x. Such coefficients are obtained by means of polynomial modular arithmetic. In particular, due to Euclidean Division, all these coefficients have degrees smaller than
deg(
p(
x)) (for the same reason, numerical coefficients
\(g_i\) are bounded by
q).
2.2 Fuentes et al. method
Fuentes et al.
[
16] improved Scott et al. method observing that, in order to obtain a non-zero multiple of
\(P \in {\tilde{E}}({\mathbb {F}}_{q}^{k/d})\) having order
r, it is sufficient to multiply
P by
\(c'\), a multiple of
c such that
\(c' \not \equiv 0 \pmod {r}\). In particular they proved the following result (see
[
16], page 11):
The first condition about h(z) gives a tool for computing a multiple of [c]P as the sum of some scalar multiplications. These multiplications are computationally light since their scalar factors are bounded thanks to the second condition satisfied by h(z).
The proof of Thereom
1 is by construction and, exploiting the
LLL algorithm of Lenstra, Lenstra and Lovasz
[
25], it leads to a procedure to explicitly compute
h(
z). For the sake of easy reference we briefly sketch the proof’s steps.
With \({\tilde{n}}\) we denote the cardinality \(\#{\tilde{E}}({\mathbb {F}}_{q^{k/d}})=q^{k/d}+1-{\tilde{t}}\), with \({\tilde{f}}\) the integer such that \({\tilde{t}}^2-4q^{k/d}=D{\tilde{f}}^2\) (where D is square-free) and, analougously, with f the integer for which \(t^2-4q=Df^2\) holds.
First of all it is observed that, for every point
\(P \in {\tilde{E}}({\mathbb {F}}_{q^{k/d}})\), it holds
\(\psi (P)=[a]P\) with:
$$\begin{aligned} a= \frac{t}{2} \pm \frac{f({\tilde{t}}-2)}{2{\tilde{f}}} \end{aligned}$$
(5)
and therefore
\(h(\psi )P=[h(a)]P\). Then, the relation
$$\begin{aligned} (\psi _{\mid {\tilde{E}}({\mathbb {F}}_{q^{k/d}})})^k=id_{{\tilde{E}}({\mathbb {F}}_{q^{k/d}})} \end{aligned}$$
is obtained. Hence
\(\varPhi _k(a)\equiv 0 \pmod {{\tilde{n}}}\), where
\(\varPhi _k\) is the
k-th cyclotomic polynomial (which has degree equal to
\(\varphi (k)\)). This allows to restrict the search of
h(
z) into the set of all polynomials of
\({\mathbb {Z}}[z]\) having degree less than
\(\varphi (k)\). Denoting with
a the column vector with
i-entry
\(-a^i\), if we consider the vectors of the integer lattice generated by the matrix
$$\begin{aligned} M=\left[ \ \begin{array}{c|c} c &{} {\mathbf {0}} \\ \hline {\mathbf {a}} &{} I_{\varphi (k)-1} \end{array}\ \right] \end{aligned}$$
as coefficients of 1,
z,
\(z^2\),
\(\ldots\),
\(z^{\varphi (k)-1}\) respectively, we obtain polynomials
\(h(z) \in {\mathbb {Z}}[z]\) such that
\(h(a) \equiv 0 \pmod {c}\). Finally, it is observed that the considered lattice and the convex set generated by all vectors of the form
\((\pm \mid c \mid ^{1/\varphi (k)},\ldots ,\pm \mid c \mid ^{1/\varphi (k)})\) have non-empty intersection. A lattice element lying in this intersection could be obtained using the
LLL algorithm
[
25]; such an element determines the coefficients of a polynomial
\(h(z) \in {\mathbb {Z}}[z]\) with the desired properties.
In
[
16], such a polynomial is obtained for the BN curves with
\(k=12\), the Freeman curves with
\(k=10\), the KSS curves for the cases
\(k=8\) and
\(k=18\). As already observed, these families are composed by curves defined over a prime field
\({\mathbb {F}}_p\), with
p, the order
r and the trace
t expressed as polynomials having rational coefficients. Consequently, also the cofactor
c and the scalar
a can be described as a polynomials in
\({\mathbb {Q}}[x]\).
The matrix
M obtained considering the parameterised forms of
c and
a is
$$\begin{aligned} M=\left[ \ \begin{array}{c|c} c(x) &{} {\mathbf {0}} \\ \hline {\mathbf {a}}(x) &{} I_{\varphi (k)-1} \end{array}\ \right] , \end{aligned}$$
where
a(x) is the column vector with
i-entry
\(-a^i(x) \pmod {c(x)}\), and it generates a lattice in
\({\mathbb {Q}}[x]^{\varphi (k)}\). Exploiting the algorithm in
[
30], the matrix
M could be transformed into a new matrix
\(M'\) having as rows the elements of a reduced basis for the lattice. Considering the polynomials composing a row of
\(M'\) as coefficients of 1,
z,
\(z^2\),
\(\ldots\),
\(z^{\varphi (k)-1}\) respectively, Fuentes et al. were able to obtain a polynomial
\(h(z)=\sum _{i} h_i(x)z^i \in {\mathbb {Z}}[x][z]\) satisfying the following two conditions:
(CI)
\(h(a(x)) \equiv s(x)c(x) \pmod {{\tilde{n}}(x)}\), with \(gcd(s(x),r(x))=1\), for some \(s(x) \in {\mathbb {Q}}[x]\);
(CII)
\(deg(h_i(x)) \le deg(c(x))/\varphi (k)\), where \(\varphi\) is the Euler’s totient function.
The first condition assures that
\([a(x_0)]P\) is a non-zero multiple of
\([c(x_0)]P\) for every value
\(x_0 \in {\mathbb {Z}}\) of the parameter
x, and that such a multiple can be computed as the sum of some scalar multiplications. These multiplications are computationally light thanks to the second condition in which scalar factors are bounded.
Consequently, for each of the curves in the above pairing-friendly families, Fuentes et al. compute a formula for hashing into \({\mathbb {G}}_2\) that is valid for every curve in the family itself. In particular, the cofactor multiplication [c(x)]P is reduced to the evaluation of a polynomial of the powers \(\psi ^i(P)\), with coefficients that are polynomials in x. Comparing their computational results with those of Scott et al. method for the same families, Fuentes et al. provided evidence that their method is faster for all the considered curves.
2.3 BLS curves
Families of pairing-friendly curves vary significantly, hence it is not possible to a priori determine if one of the two above hashing methods is more efficient than the other for a given family. BLS curves are recently gaining increasing interest
[
3,
27]. Thus it is of great concern to determine also for these curves which is, among Scott et al. and Fuentes et al. methods, the more efficient one. In
[
12, Sec. 8.5], Scott et al. method is explicitly applied to BLS curves having
\(k \in \{12,24\}\), and authors state that in these cases the most efficient method for hashing into
\({\mathbb {G}}_2\) is the one proposed by Scott et al.
In this paper we deduce the formulas derived from the application of both methods to BLS curves having
\(k=\{12,24,30\}\), and we provide evidences that, on the contrary, the most efficient method is the one of Fuentes et al. Furthermore, we apply Scott et al. method also to BLS curves with
\(k \in \{42,48\}\). On the other hand, the computations necessary, within Fuentes et al. method, to obtain the polynomial
h(
z) for BLS curves having
\(k=42,48\) were infeasible for the computational power at our disposal. Nevertheless, in Sect.
5 we propose two polynomials
\({\mathfrak {h}}(z)\), for the cases
\(k=42\) and
\(k=48\), that fully satisfies and
almost fully satisfies conditions (CI), (CII), respectively. In particular, in both cases
\({\mathfrak {h}}(a(x))\) is congruent to a multiple of
c(
x) modulo
\({\tilde{n}}(x)\), i.e.
\({\mathfrak {h}}(\psi )P\) is a multiple of [
c(
x)]
P for all
\(P \in {\tilde{E}}({\mathbb {F}}_{q^{k/d}})\). Furthermore, for
\(k=48\) the proposed polynomial satisfies the relation
\(deg({\mathfrak {h}}_i(x)) \le deg(c(x))/\varphi (k)\) for every
i, while for
\(k=42\) this condition holds for every
\({\mathfrak {h}}_i(x)\) except
\({\mathfrak {h}}_0(x)\), that has degree equal to
\(\left\lfloor {deg(c(x))/\varphi (k)}\right\rfloor +1\).
We conclude this section briefly recalling BLS curves’ parameters. Barreto, Lynn and Scott
[
6], and Brezing and Weng
[
10] proposed a polynomial parameterisation for complete families of pairing-friendly curves having prime fields
\({\mathbb {F}}_p\) as basefields, fixed embedding degrees, and short Weierstrass equations of the form
\(y^{2} = x^{3} + b\).
In the following, we consider only those BLS curves with embedding degree
\(k \equiv 0 \pmod 6\), and such that
\(18 \not \mid k\). This choice is due to efficiency reasons, since each of such curves admits a twist having the highest possible degree
\(d=6\)
[
20], allowing to consider
\({\mathbb {G}}_2\) as a subgroup of
\({\tilde{E}}({\mathbb {F}}_{p^{k/6}})\). In this case BLS curves are parameterised by the following polynomials
[
14]:
$$\begin{aligned} p(x)= & {} \frac{1}{3} (x-1)^{2}(x^{k/3}-x^{k/6} +1)+x\\ r(x)= & {} \varPhi _{k}(x)\\ t(x) =& x +1, \end{aligned}$$
where
\(\varPhi _{k}\) is the cyclotomic polynomial of order
k.