Comparative Analysis of Calculations in Cryptographic Protocols Using a Combination of Different Bases of Finite Fields

Abstract

The chapter introduces a comparative analysis of the complexity of the Tate pairing operation on a supersingular elliptic curve and the complexity of the final exponentiation in the tripartite key agreement cryptographic protocol. The analysis takes into account a possibility of using different bases of finite fields in combination. Operations of multiplication and multiple squaring in the field $GF(2^{n} )$ and its 4-degree extension, of Tate pairing on supersingular elliptic curve and of final exponentiation are considered separately and in combination. We conclude that the best complexity bound for the pairing and the final exponentiation in the cryptographically significant field $GF(2^{191} )$ is provided by the combination of the polynomial basis of this field and 1-type optimal basis of the field expansion.

1 Introduction

The idea of combining bases to accelerate computations in finite fields was first introduced in [1] on the basis of the estimates of complexity of transformations of bases in the fields possessing the 2- or 3-type optimal normal basis (o.n.b.) [2]. In [3,4,5], a number of modifications of the multiplication in these bases have been proposed. In particular, in [5] multiplication algorithm in the so-called optimal polynomial basis of type 2 (in the terminology of [1] - almost polynomial basis (a.p.b)) using the multiplication operations in the ring GF(2)[X] is described and estimated. The product is converted into a.p.b. using a permutated o.n.b., i.e. by means of operations without reduction modulo an irreducible polynomial.

Recall that 1-type o.n.b. in the field $GF(2^{n} )$ occurs if p = n+1 is a prime number, and 2 is a primitive root mod p, 2-type o.n.b. or 3-type o.n.b. arise when p = 2n + 1 is a prime number, and the field characteristic 2 is a primitive root modulo p. If p≡3(mod 4), and 2 is a quadratic residue, we have 3-type o.n.b, otherwise 2-type o.n.b.

As used in this paper, the field $GF(2^{191} )$, has 3-type o.n.b. and its 4-th degree extension has 1-type o.n.b.. Availability o.n.b. allowing to speed up the operation of raising to a power equal to the power of the field characteristics, or the scalar multiplication of the elliptic curve point by the power of the field characteristics, as well as the operation of the square root extracting.

Polynomial basis p.b. of these fields has generators, which are the roots of the irreducible trinomials that simplifies the implementation of the operations of multiplication in these bases. Thus, there is reason to explore the possibility of sharing o.n.b. and p.b. in the implementation of the various stages of cryptographic protocols.

In this paper, we concretize the idea of using combinations of bases in relation to the implementation of the tripartite key agreement protocol [6] in arithmetic supersingular elliptic curve over a cryptographically significant field $GF(2^{191} )$: tacking into account security parameter k = 4 for supersingular elliptic curve over this field, security of discrete logarithm problem in group of elliptic curve points is equivalent to security of this problem in multiplicative group of order $2^{764} - 1$ [7]. Recall that this protocol is one round. System parameter is a point P of supersingular elliptic curve over the ground field $GF(2^{n} )$.

Each of the three participants A, B and C selects a private key a, b and c, computes and publishes the public key KA = aP, KB = bP and KC = cP. Then each of them receives the public keys of other participants, calculates an element e(bP,cP), e(aP, cP) or e(bP, aP) of the field $GF(2^{n \times 4} )$ performing the Tate pairing operation e with two points of an elliptic curve and then the operation of the final exponentiation (raising to a power equal to the quotient of the order of the group $GF(2^{n \times 4} )^{*}$ on the order of the elliptic curve). The final step is to calculate the shared secret key by exponentiation of the result to the power a, b and c respectively. The chapter provides upper bounds on the number of elementary operations in the pairing and the final exponentiation phases of the said cryptographic protocol. The rest part of chapter contains Sect. 2 were operation of multiplication and multi squaring in distinct bases of the field $GF(2^{191} )$ are considered, Sect. 3 that is devoted to these operations in 4-degree extension of this field comparing their complexity for distinct combinations of bases of basic field and its extension. In Sect. 4 we compare complexity of pairing and final exponentiation operations separately and totally for distinct combinations of bases. In conclusion the comparison results are summarized.

2 Bases and Operations in GF($2^{\varvec{n}}$)

Consider a sequence $\beta_{i} = \alpha^{i} + \alpha^{ - i} \in GF(2^{n} ),\,n = 191, i \in Z$. The set $\left\{ {1,\beta _{1} , \ldots ,\beta_{1}^{i} , \ldots ,\beta_{1}^{n - 1} } \right\}$ is called a polynomial base (p.b) of $GF(2^{n} )$, the set $\left\{ {\beta_{1} , \ldots ,\beta_{1}^{i} , \ldots ,\beta_{1}^{n} } \right\}\,(\left\{ {\beta_{1} , \ldots ,\beta_{1}^{i} , \ldots ,\beta_{1}^{2n} } \right\})$ forms an almost p.b (a.p.b) of $GF(2^{n} )$ (doubled a.p.b). The set $\left\{ {\xi_{1} , \ldots ,\xi_{i} , \ldots ,\xi_{n} } \right\} = \left\{ {\beta_{1}^{{2^{0} }} , \ldots ,\beta_{1}^{{2^{i - 1} }} , \ldots ,\beta_{1}^{{2^{n - 1} }} } \right\}$ is an optimal normal base (o.n.b) of $GF(2^{n} )$. The set $\left\{ {\beta_{1} , \ldots ,\beta_{i} , \ldots ,\beta_{n} } \right\}\,({\text{or}}\,\left\{ {\beta_{1} , \ldots ,\beta_{i} , \ldots ,\beta_{2n} } \right\})$, $\beta_{i} = \xi_{\pi \left( i \right)}$,$i = 1, \ldots n$, where π is a permutation

$$ \pi (i) = \left\{ {\begin{array}{*{20}c} {2^{i} \,\bmod \,p\,{\text{if}}\,2^{i} \,\bmod \,p \le n,} \\ {(p - 2^{i} )\,\bmod \,p\,{\text{if}}\, 2^{i} \,\bmod \,p > n,} \\ \end{array} } \right. $$

$p = 2n + 1$, is called a permuted o.n.b. (p.o.n.b) (or doubled p.o.n.b).

Let T $(T^{ - 1} )$ denote the operation of the conversion from a.p.b to p.o.n.b (from p.o.n.b to a.p.b). If $2^{k} < n < 2^{k + 1}$, then the conversion complexity (number of xor-operations) satisfies the recurrent inequality $L_{T} (n ) \le L_{T} \left( {n - 2^{k} } \right) + L_{T} \left( {2^{k} } \right) + n - 2^{k}$ with the initial value $L_{T} \,\left( 2\right) = 0$. This recurrence can be solved as $L_{T} \left( {2^{k} } \right) \le 2^{k - 1} \left( {k - 2} \right) + 1$ [5]. Note, that the weaker bound $L_{T} \left( {2^{k} } \right) \le 2^{k - 1} \left( k \right) + 1$ was derived in [1] due to the overestimated initial value $L_{T} ( 2) = 2$. From this inequality one can obtain estimations $L_{T} \,\left( { 1 9 1} \right) = 5 1 3$, $L_{T} \left( { 3 8 2} \right) = 1 2 2 7$. Trivially, the complexity of the operation D of the conversion from d.p.o.n.b to p.o.n.b. is n-1.

Following [5], we multiply elements of $GF(2^{n} )$ represented in a.p.b as elements of the ring GF(2)[X] getting the product in d.a.p.b. Denote this operation $\times_{R}$. Also following [5] we denote Bottom(a) and Top(a) the lower half of product and product after replacing of its lower half with zeros). We implement two multiplication operations in a.p.b:

${\mathbf{y}} \times_{apbP} {\mathbf{z}}$ with result in a.p.b,

${\mathbf{y}} \times_{apbN} {\mathbf{z}}$ with result in p.o.n.b,:

${\mathbf{y}} \times_{apbP} {\mathbf{z}} = Bottom({\mathbf{c}}) + T^{ - 1} \,(D(T(Top(c))))$,

${\mathbf{y}} \times_{apbN} {\mathbf{z}} = T(Bottom({\mathbf{c)}}) + D(T(Top(c)))$,

where ${\mathbf{c}} = {\mathbf{y}} \times_{R} {\mathbf{z}}$, «+» is n-bit xor.

It follows that complexity of each of these operations (number of logical operations) $L( \times_{apbP} ) = L( \times_{apbN} ) = M\left( n \right) + L_{T} \left( { 2n} \right) + 2n$ where M(n) is complexity of operation $\times_{R}$ (transformation D in this case is performed without “xor” - operations).

Implementing ${\mathbf{c}} = T({\mathbf{y}}) \times_{R} \,T({\mathbf{z}})$ instead of ${\mathbf{c}} = {\mathbf{y}} \times_{R} \varvec{z }$ we obtain also two multiplication operations in p.o.n.b:

${\mathbf{y}} \times_{ponbP} {\mathbf{z}}$ with result in a.p.b,

${\mathbf{y}} \times_{ponbN} {\mathbf{z}}$ with result in p.o.n.b.

Complexity of each of these operations $L( \times_{ponbP} ) = L( \times_{ponbN} ) = M(n) + 2*L_{T} \,(n) + L_{T} ( 2n) + n$.

Denote $\times_{pbN}$ multiplication in p.b. in the field $GF(2^{n} )$ with minimal polynomial P _onb(X) that root generates o.n.b. It can be performed converting operands to a.p.b., executing $\times_{apbP}$ and converting the product back to p.b. Mentioned converting’s are of complexity n. Hence complexity of multiplication $\times_{pbN}$ is $L( \times_{apbP} ) + 3n$.

P.b. is organized using the root of trinomial P _pb(X) instead P _onb(X). Let R(x) be the modulo trinomial reduction of complexity 2n. Then multiplication in p.b. of $GF(2^{n} )$ is denoted and described as ${\mathbf{y}} \times_{R} {\mathbf{z}} = R({\mathbf{x}} \times_{R} {\mathbf{y}})$. Its complexity is limited to M(n) + 2n. Squaring in p.b. is performed by an algorithm that directly take into account the reducing of the vector-result. Below we denote this operation $\varvec{z}_{pb}^{(1)} = \varvec{Z}^{2}$. Its complexity is limited to n, but symbolically synthesis for n = 191 gave the squaring program with only 99 xor’s.

Denote $\varvec{z}_{ponb}^{(j)} = \varvec{z}^{{2^{j} }}$ a raising to power $2^{j}$ operation implemented to element z in p.o.n.b. with result in a.p.b.:

for $i = \left( { 1,n} \right)$:

${\mathbf{b}}\left[ i \right] = {\mathbf{a}}[\uppi[\uppi^{ - 1} (i) - {\text{j}}]]$

${\mathbf{c}} = T({\mathbf{b}})$.

Its complexity equals 0, because logical operations absent.

Operation $\varvec{z}_{apb}^{{(\varvec{j})}} = T^{ - 1} (T(\varvec{z})^{{2^{j} }} )$ is implemented to element z in a.p.b. with result in a.p.b. Its complexity is 2L _T (n).

Operation $\varvec{z}_{apbN}^{{(\varvec{j})}} = T(\varvec{z})^{{2^{j} }}$ is implemented to element z in a.p.b. with result in p.o.n.b. Its complexity is L _T .

Operation $\varvec{z}_{pbN}^{{(\varvec{j})}} = T(\varvec{z})^{{2^{j} }}$ is implemented to element z in p.b. (for minimal polynomial $P_{\text{onb}} (X)$) with result in p.b. Its complexity is $2L_{T} (n) + n)$.

Denote $\varvec{z}_{pb}^{(j)} \varvec{ }$ a raising to power $2^{j}$ operation to element z in p. b. (for minimal polynomial $P_{\text{pb}} (X)$) with result in p.b.:

• c = z

• for $i = \left( { 1,j} \right)$:

  • $$ {\mathbf{c}} = {\mathbf{c}}_{pb}^{(1)} $$

Its complexity is bounded by nj (for n = 191 one can take estimate 99j).

In Table 1 there are represented the numbers of logical operations “xor” and “and” (denoted ⊕ and &) and the total numbers of these operations in rows {⊕, &} for multiplication and squaring in distinct bases of $GF(2^{191} )$. Here and below we assume implementation the fastest of the stated algorithms for multiplication in the ring $GF(2)[X]$ [8]. Here and below in tables there are represented data derived from estimates of the complexity of operations and confirmed by computer experiment. Column “$\Delta$ over the ring” contains numbers of operations without operations $X_{R}$ of multiplication in the ring.

Table 1. Comparison of Operations in $GF(2^{191} )$

3 Multiplication and Squaring in GF($2^{{191\varvec{ } \times 4}}$)

The field $GF((2^{191} )^{4} )$ contains a 1-type o.n.b. over the subfield $GF(2^{191} )$. Operations of addition, multiplication, and squaring in these bases can be implemented using operations in $GF(2^{191} )$ in p.b, a.p.b, or p.o.n.b of this basic field. It follows that there are 6 combinations of bases of basic field and its extension, and each of them can be chosen to implement operations of Tate pairing, final exponentiation, and operation of secret working key computing. Together with operations considered in the second section, algorithms of these operations use operations of multiplication in 4-degree extension of the field $GF(2^{n} )$ and operation of raising to power $2^{j}$.

Let ${\mathbf{a}}_{apb\_4nP}^{\left( j \right)}$ denote the operation of raising an element a to the power $2^{j}$ using operation $\varvec{z}_{apb}^{{(\varvec{j})}}$ of basic field and p.b. of its extension.

Let $\times_{apb\_4nP}$ be a multiplication using a.p.b. of basic field with multiplication $\times_{apb}$ and p.b. of its extension.

Analogous notation ${\mathbf{a}}_{apb\_4nN}^{\left( j \right)}$, ${\mathbf{a}}_{ponb\_4nN}^{\left( j \right)}$

${\mathbf{a}}_{ponb\_4nN}^{\left( j \right)}$ × _{apb_4nN} , × _{ponb_4nP} , × _{ponb_4nN} , × _{pb_4nP} , × _{pb_4nN} are used for operations in other combinations of field extension and basic field.

Denote +_4n an addition in field extension in any of its basis and any basis of basic field, its complexity equals 4n.

In can be shown that operations × _{apb_4nN} , × _{ponb_4nN} , × _{pb_4nN} can be implemented performing 9 multiplications an 22 additions in the field $GF(2^{n} )$.

So complexity of × _{apb_4nN} equals 4 $L( \times_{apbN} ) + 2 2n$. Complexity of operations × _{apb_4nP} , × _{ponb_4nP} , × _{pb_4nP} exceed these values of 6n accordingly numbers of n-bit additions for converting between o.n.b. and p.b. of field extension.

Complexity of multiple squaring is estimated analogously.

Numbers of logical operation for multiplication in distinct bases of the field $GF(2^{191} )$ and its extension are presented in Table 2.

Table 2. Comparison of Operations in $GF(2^{191 \times 4} )$

4 Tate Pairing and Final Exponentiation Operations

Let us consider four variants of Tate pairing computing with root extraction on supersingular elliptic curve $Y^{2} = X^{3} + X + {\mathbf{b}}$ [9].

• (a) A.p.b. of the field GF(2¹⁹¹), o.n.b of its extension.

Algorithm $Pairing\_apb\_onb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{apb\_onb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{apb\_onb}$ (an element of the extension field with all coefficients being 0 s and 1 s of the field $GF( 2^{ 1 9 1} )$), ${\mathbf{b}} = 1_{apb}$ (identity element represented in a.p.b of $GF( 2^{n} )$).

• C = [1 _apb , 1 _apb , 1 _apb , 1 _apb ]

• t = t _{apb_onb}

• ${\textbf{s}}={\textbf{t}}_{apbP\_4nN}^{(1)}$

• for i = (1,n):

  • α = α _apbP ⁽¹⁾

  • β = α _apbP ⁽¹⁾

  • z = α+x

  • v = α× _apbP x

  • w = z + v+β+y+1 _apb

  • u = [z× _apbP t[0]), z× _apbP t[1]), z× _apbP t[2]), z× _apbP t[3]),),

  • v = z+1 _apb

  • r = [v× _apbP t _apb s [0], v× _apbP s[1], v× _apbP s[2], v× _apbP s[3]]

  • v = [w,w,w,w] + _4n u + _4n r

  • C = C × _{apbP_4nN} v

  • ${\textbf{x}}={\textbf{x}}_{apb}^{(n-1)}$

  • ${\textbf{y}}={\textbf{y}}_{apb}^{(n-1)}$

Complexity of this algorithm estimated accordingly numbers if multiplication, addition and squaring operations in them:

$$ {\text{L}}_{Pairing\_apb\_onb} (n) = 1 9 1( 2L({\mathbf{z}}_{apb}^{(1)} ) + 2 {\text{L(}}{\mathbf{z}}_{apb}^{(190)} )+ L( \times_{apbP} ) + L( \times_{apb\_4nN} ) + 1 5L( + )). $$

Remark that here and below multiplication with multiples t or s containing trivial elements are not taken into account in assessing complexity of pairing, L(+) is complexity of addition in $GF( 2^{191} )$.

• (b) P.o.n.b. of the field GF(2¹⁹¹), o.n.b of its extension.

Algorithm $Pairing\_ponb\_onb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{ponb\_onb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{ponb\_onb}$ when ${\mathbf{b}} = 1_{ponb}$ (that is, the identity element represented in p.o.n.b. of $GF( 2^{n} )$) differs from just considered only in the type used in operations in the notation of which “apb” is replaced by “ponb”, $1_{apb}$ is replaced by $1_{ponb}$.

Hence complexity of this pairing operation is represented by formula

$$ L_{Pairing\_ponb\_onb} (n) = 1 9 1( 2L({\mathbf{z}}_{ponb}^{(1)} ) + 2L{\mathbf{z}}_{ponb}^{(190)} + L( \times_{ponbP} ) + L( \times_{ponb\_4nN} ) + 1 5L( + )). $$

• (c) A.p.b. of the field $GF( 2^{ 1 9 1} )$, and p.b. of its extension.

Algorithm $Pairing\_apb\_pb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{apb\_pb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{apb\_pb}$ when ${\mathbf{b}} = 1_{apb}$.

• C = [1 _apb , 0 _apb , 0 _apb , 0 _apb ]

• t = t _apbpb

• s = t _{apbpbapbP_4nPb} ⁽¹⁾

• for i = (1,n):

  • α = α _apbP ⁽¹⁾

  • β = β _apbP ⁽¹⁾

  • z = α+x

  • v = α× _apbP x

  • w = z + v +β + y + 1 _apb

  • u = [z× _apbP t[0], z× _apbP t[1], z× _apbP t[2], z× _apbP t[3]]

  • v = z+1 _apb

  • r = [v× _apbP s[0],v× _apbP s[1],v× _apbP s[2], v× _apbP s[3]]

  • v = [w, 0 _apb , 0 _apb , 0 _apb ] + _4n u + _4n r

  • C = C× _{apbP_4nPb} v

  • ${\textbf{x}}={\textbf{x}}_{apbP}^{(n-1)}$

  • ${\textbf{y}}={\textbf{y}}_{apbP}^{(n-1)}$

Its complexity is the following:

$$ \begin{aligned}L_{Pairing\_apb\_pb} (n) &= 1 9 1( 2L({\mathbf{z}}_{apb}^{(1)} ) + 2L({\mathbf{z}}_{apb}^{(190)} ) \\ & + L( \times_{apbP} ) + {\text{L}}( \times_{apb\_4nP} ) + 1 1 {\text{L(}} + )).\end{aligned} $$

• (d) P.o.n.b. of the field $GF( 2^{ 1 9 1} )$, p.b. of its extension.

Algorithm $Pairing\_ponb\_pb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{ponb\_pb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{ponb\_pb}$ when ${\mathbf{b}} = 1_{ponb\_pb}$ can be obtained from the considered algorithm $Pairing\_apb\_pb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{apb\_pb} ,{\mathbf{b}})$ via substitution of indices of operations, pairing parameter, and the field identity element. Its complexity is estimated by formula

$$ \begin{array}{*{20}c} {{\text{L}}_{Pairing\_ponb\_pb} (n) = 1 9 1( 2L({\mathbf{z}}_{ponb}^{(1)} ) + 2L({\mathbf{z}}_{aonb}^{(190)} )} \\ { + L( \times_{ponbP} ) + L( \times_{ponb\_4nP} ) + 1 1L( + )).} \\ \end{array} $$

Now consider two variants of Tate pairing computing without root extraction on supersingular elliptic curve $Y^{2} = X^{3} + X + {\mathbf{b}}$ [9].

• (a) P.b. of the field $GF( 2^{ 1 9 1} )$, o.n.b. of its extension.

Algorithm $Pairing\_pb\_onb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{pb\_onb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{pb\_onb}$ when ${\mathbf{b}} = 1_{pb}.$

• C = [1 _pb , 1 _pb , 1 _pb , 1 _pb ]

• t = t _pbonb

• s = t _{pb_4nN} ⁽¹⁾

• ${\textbf{u}}={\textbf{x}}^{(1)}_{pb}$

• v = u

• ${\textbf{y}}={\textbf{y}}^{(1)}_{pb}$

• for i = (1,n):

  • ${\varvec{\upalpha}}={\varvec{\upalpha}}^{(4)}_{pb}$

  • ${\varvec{\upbeta}}={\varvec{\upbeta}}^{(4)}_{pb}$

  • w = α×_bp(v + 1_pb) + u+y + b+((n-1)/2)_pb

  • v = α+v

  • r = v+1 _pb

  • a = [w + v× _pb t [0] + r× _pb s[1], w + v× _pb t _pb [2] + r× _pb s[3],

  • w + v× _pb s [0] + r× _pb s[1], w + v× _pb s[2] + r× _pb s[3]]

  • ${\textbf{C}}={\textbf{C}}^{(1)}_{pb_4nN}{\times}_{pb_4nN}{\textbf{a}}$

  • u = u + v+1 _pb

  • v = v + 1 _pb

Its complexity is estimated as follows:

$$ \begin{aligned} L_{Pairing\_pb\_onb} (n) & = 1 9 1( 2L({\mathbf{z}}_{pb}^{(1)} ) + 2 {\text{L}}({\mathbf{z}}_{pb}^{(4)} ) + 2L({\mathbf{z}}_{aonb}^{(190)} ) \\ & + L( \times_{pb} ) + 2 {\text{L}}( \times_{{{\text{pb}}\_4nN}} ) + {\text{L}}\left( {{\mathbf{a}}_{ab\_4nN}^{( 1)} } \right) \, + {\text{ 16L(}} + )). \\ \end{aligned} $$

• (b) P.b. of the field $GF( 2^{ 1 9 1} )$, p.b. of its extension.

Algorithm $Pairing\_pb\_pb({\varvec{\upalpha}},{\varvec{\upbeta}},{\mathbf{x}},{\mathbf{y}},{\mathbf{t}}_{pb\_pb} ,{\mathbf{b}})$ for pairing of points $P = ({\varvec{\upalpha}},{\varvec{\upbeta}})$, $Q = \left( {{\mathbf{x}},{\mathbf{y}}} \right)$ using pairing parameter ${\mathbf{t}}_{pb}$ when ${\mathbf{b}} = 1_{pb}$ differs from just considered in four rows:

• C = [1 _pb , 0 _pb , 0 _pb , 0 _pb ]

• t = t _{pb_pb}

• ${\textbf{s}}={\textbf{t}}_{pb\_4nP}^{(1)}$

• ${{\textbf{C}}={{\textbf{C}}^{(1)}_{pb\_4np}}{\times}_{pb\_4nP}}$

Its complexity is represented by formula

$$ \begin{aligned} {\text{L}}_{Pairing\_pb\_onb} (n) & = 1 9 1( 2L(z_{pb}^{(1)} ) + 2L(z_{pb}^{(4)} ) + { 2}L(z_{aonb}^{(190)} ) \\ & + L( \times_{pb} ) + 2 L( \times_{{{\text{pb}}\_4nP}} ) + L\left( {{\mathbf{a}}_{ab\_4nP}^{( 1)} } \right) \, + { 16}L( + )). \\ \end{aligned} $$

Table 3 presents data on the number of logical operations executed considered pairing algorithms on supersingular elliptic curve $Y^{2} = X^{3} + X + 1$ over GF(2¹⁹¹) (1 corresponds to 29910607 “xor”, or 10875600 “and” or 43094757 of both these operations). In the tables below we also provide better bounds (given in parentheses) obtained via conversion to a basis with faster implementation of the corresponding operation.

Table 3. Comparison of complexity of pairing algorithms

For the considered supersingular elliptic curve over the field $GF(2^{191} )$, the final exponent is

$$ \begin{array}{*{20}l} {d = 30 9 1 6 300 1 8 4 1 3 80 6 6 7 5 7 5 6 2 8 1 5 1 2 8 2 3 6 3 3 5 8 9 1 9 70 4 1 6 6 9 5 4 9 6 8 7 9 2 9 6 7 1 60 2 40 8 9 5 9} \hfill \\ { 8 40 1 2 9 3 7 8 5 7 9 5 9 4 40 2 9 3 7 5 2 7 60 1 2 9 9 3 4 9 3 2 2 2 2 6 6 6 9 4 9 4 90 7 7 8 7 7 9 8 4 9 8 7 3 5 9 1 80 7 9 30 1} \hfill \\ { 8 7 8 4 4 3 6 80 8 6 1 3 9 4 9 30 3 3 7 7 5 3 9 7 4 9 2 8 1 5 2 9 8 5 5.} \hfill \\ \end{array} $$

Taking into account that in binary expansion of this number the units take the places 0–95, 97–190, 192–381, 478, and 573 one can represent this exponent as

$$ \begin{aligned} d & = (((2^{95} + 1)2^{286} + \left( {2^{190} - 1 } \right))2^{95} + \left( {2^{94} - 1 } \right))2^{97} + \left( {2^{96} - 1 } \right) \\ & = \left( {\left( {a_{0} 2^{286} + a_{1} } \right)2^{95} + a_{2} } \right)2^{97} + a_{3} . \\ \end{aligned} $$

As a corollary, final exponentiation algorithm corresponds to the formula

${\mathbf{x}}^{d} = ((({\mathbf{y}}_{0} )^{{2^{286} }} {\mathbf{y}}_{1} )^{{2^{95} }} {\mathbf{y}}_{2} )^{{2^{97} }} {\mathbf{y}}_{3}$, where ${\mathbf{y}}_{0} = {\mathbf{x}}^{{a_{0} }} = {\mathbf{x}}^{95} {\mathbf{x}}$ and the remaining elements ${\mathbf{y}}_{1} = {\mathbf{x}}^{{a_{1} }} , {\mathbf{y}}_{2} = {\mathbf{x}}^{{a_{2} }} , {\mathbf{y}}_{3} = {\mathbf{x}}^{{a_{3} }}$, can be computed by the additive chain 1,2,4,8,10,14,20,40,80,94,96,160,180,190 of lengths 13.

This allows obtaining the following program of final exponentiation using a.p.b. of basic field and p.o.n.b. of its extension.

x = a;	${{\textbf{v}}={\textbf{x}}_{apbP\_4N}^{(1)}};$	z 1 = v× apbN_4N x;	z = v× apbN_4N z 1;
${{v}={z_1}_{ponbP\_4N}^{(2)}};$	${{\textbf{v}}={\textbf{z}}_{ponbP\_4N}^{(4)}};$	z = y× apbN_4N z;	${{\textbf{v}_{2}}={\textbf{x}}_{apbP\_4N}^{(2)}};$
v = z× apbP_4nN v	z 2 = v× apbP_4nN z 1;	${{\textbf{v}}={\textbf{x}}_{apbP\_4N}^{(4)}};$	z = v× apbP_4nN z 2;
${{\textbf{v}_{10}}={\textbf{x}}_{apbP\_4N}^{(10)}};$	z 3 = z 2× apbP_4nN z 2;	z 4 = z 2 × apbN_4nN z 2;	${{\textbf{v}_{3}}={\textbf{x}}_{apbP\_4N}^{(20)}};$
z = v 3 × apbP_4nN z 3;	z 5 = v × apbN_4nN z 4;	${{\textbf{x}}{{x}}_{apbP\_4N}^{(40)}};$	z = v × apbP_4nN z 5;
z 6 = z 5 × apbP_4nN z;	${{\textbf{v}_{10}}={\textbf{x}}_{apbP\_4N}^{(14)}};$	z = v× apbP_4nN z;	y 2 = v 1× apbP_4nN z;
z = v 2× apbP_4nN y 2;	y 3 = z 1× apbP_4nN z;	${{\textbf{v}}={\textbf{x}}_{apbP\_4N}^{(80)}};$	z = z 6 ×v;
z = v 6 × apbP_4nN z;	z = v 3 × apbP_4nN z;	z = v 3× apbP_4nN z;	z = v 3× apbP_4nN z 4 ;
z = v 10 × apbP_4nN z;	y 1 = z 2× apbP_4nN z;	${{\textbf{z}}={\textbf{x}}_{ponbP\_4N}^{(95)}};$	y 0 = z× apbP_4nN x;
${{\textbf{z}}={\textbf{y}_{0}}_{ponbP\_4N}^{(286)}};$	z = z× apbN_4nN y 1;	${{\textbf{z}}={\textit{z}}_{ponbP\_4N}^{(95)}};$	z = z × apbP_4nN y 2;
${{\textbf{z}}={\textbf{z}}_{apbP\_4N}^{(97)}};$	z = z× apbP_4nN y 3;	c = z.

Programs for other combination of fields bases differ only by operation notation. These programs contain 17 multiplication and 14 multi squaring’s in the field $GF(2^{191 \times 4} )$. It is easy to write formula of complexity of these operations and compute their values that are given in Table 4 (1 corresponds to 3421756 logical operations “xor” and “and”). In each case 374 additions, 153 multiplications and 2644 squaring’s in $GF(2^{191} )$ are executed.

Table 4. Final exponentiation, n = 191

In three partite key agreement protocol, final exponentiation is performed after pairing operation. In Table 5 there are represented total numbers of logical operations for implementations of this composition in distinct combinations of bases (1 corresponds to 44310956 logical operations “xor” and “and”).

Table 5. Comparison of composition of pairing and final exponentiation, n = 191

5 Conclusion

In this chapter, implementation of algebraic operations in finite fields possessing 2-type or 3- type optimal normal basis and in its 4-degree extension has been comparatively considered taking into account possibility of using distinct combination of bases. Comparative data were also obtained on the complexity of the implementation of pairing and final exponentiation operations in a three-partite key agreement protocol. Based on these data, we can conclude that although for final exponentiation the best is combination of almost polynomial basic of the base field and optimal normal basis of its extension, pairing and final exponentiation are performed faster in polynomial basis of $GF(2^{191} )$ and optimal normal basis of its extension. At the same time, it can be noted that the differences in the complexity of implementation with the use of different combinations of bases are not so significant. The advantage of a polynomial basis of the base field is a consequence of the peculiarities of the pairing algorithm without root extraction.