Abstract: Recent progress on pairing based cryptography was the use of extension of finite fields of the form

Fpk, and it was a lot secure and efficient when k≥12. In this paper, we will use the tower building technique

to study the case of k=36 to improve arithmetic operation. We will use a degree 2 or 3 twist to carry out most

operations in Fp2,Fp3,Fp4,Fp6,Fp9,Fp12 ,Fp18 and Fp36 , many paths will be found. Finally we will take the

optimal case to improve the computation in optimal ate pairing

Key-Words: Optimal ate pairing, Miller Algorithm, Embedding degree 36, Twist curve

Received: December 22, 2021. Revised: October 22, 2022. Accepted: November 29, 2022. Published: December 27, 2022.

After the discovering of pairing-based cryptography,

developers and researchers have been studying and

developing new techniques and methods for con-

structing more efficiently implementation of pairings

protocols and algorithms.The first pairing is intro-

duced by Weil Andre in 1948 called Weil pairing,

after that more pairing are appear like tate pairing,

ate pairing and a lot more. The benefit of Elliptic

curve cryptosystems which was discovered by Neal

Koblitz [1] and Victor Miller [2] is to reduce the key

sizes of the keys used in public key cryptography.

Some works are presented in [3] interested in signa-

ture numeric. The authors in [4] show that we can

use the final exponentiation in pairings as one of the

countermeasures against fault attacks. In [5],[6],[7],

[13] Nadia El and others show a study case of work-

ing with elliptic curve with embedding degree 5,9,15

and 27. Also in [9],[10],[11],[12] researchers show

the case of working with a curve with embedding de-

gree 18. In [8] they give a study of the security level

of optimal ate pairing.

In the present article, we seek to obtain efficient

ways to pairing computation for curves of embedding

degree 36. We will see how to improve arithmetic op-

eration in curves with embedding degree 36 by using

the tower building technique. We will give all the

cases studies that build these curves of embedding

degree 36, we will also studies the cases when using

a degree 2 or 3 twists, to handle most operations in

Fp2,Fp3,Fp4,Fp6,Fp9,Fp12 ,Fp18 and Fp36 . By mak-

ing use of this tower building technique, we can also

improve the arithmetic of Fp6,Fp12 ,Fp18 and Fp36 in

order to get better results. Finally we will compare

these cases to know which one is the optimal arith-

metic path on Fp2,Fp3,Fp4,Fp6,Fp9,Fp12 ,Fp18 and

Fp36 .

In this paper, we will investigate and examine what

will happen in case of optimal ate pairing with em-

bedding degree 36.

The paper is organized as follows: section 2, we re-

call some background on the main pairing properties

also ate pairing, and Miller Algorithm. Section 3,

presents our new techniques of tower building the el-

liptic curve of embedding degree 36. Section 4, will

present the results of our work with comparison be-

tween these methods. Finally, Section 5 concludes

this paper.

In everything that follows, Ewill represent an elliptic

curve with equation

y2=x3+ax +bfor a,b∈Fpwith pprime number.

The symbol aopt will denote the optimal ate pairing.

We shall use, without explicit mention, the following

• p: a prime number.

•q=pk: a power of a prime number.

•G1⊂(E(Fp)): additive group of cardinal

n∈N∗.

•G2⊂(E(Fpk)): additive group of cardinal

n∈N∗.

•G3⊂F∗

pk⊂µn: cyclic multiplicative group of

cardinal n∈N∗.

Tower Building Technique on Elliptic Curve with Embedding

Degree 36

1ISMAIL ASSOUJAA, 2SIHAM EZZOUAK, 3HAKIMA MOUANIS

Departement of Mathematics (LASMA laboratory)

University Sidi Mohammed Ben Abdellah

Fez city, MOROCCO

1. Introduction

2. Mathematical Background

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

325

Volume 21, 2022

•µn={u∈¯

Fp|un= 1}.

•P∞: the point at infinity of the elliptic curve.

•k: the embedding degree: the smallest integer

such that rdivides pk−1.

•fs,P : a rational function associated to the point

P and some integer s.

• m,s,i: multiplication, squaring, inversion in field

Fp.

•M2, S2, I2: multiplication, squaring, inversion

in field Fp2.

•M3, S3, I3: multiplication, squaring, inversion

in field Fp3.

•M4, S4, I4: multiplication, squaring, inversion

in field Fp4

•M6, S6, I6: multiplication, squaring, inversion

in field Fp6.

•M9, S9, I9: multiplication, squaring, inversion

in field Fp9.

•M12, S12, I12: multiplication, squaring, inver-

sion in field Fp12 .

•M18, S18, I18: multiplication, squaring, inver-

sion in field Fp18 .

•M36, S36, I36: multiplication, squaring, inver-

sion in field Fp36 .

Arithmetic operation cost:

We already know that the cost of multiplication,

squaring and inversion in the quadratic field Fp2are:

M2= 3m,

S2= 2m,

I2= 4m+irespectively ([18]).

We already know that the cost of multiplication,

squaring and inversion in in the cubic twisted field

Fp3are:

M3= 6m,

S3= 5s,

I3= 9m+ 2s+irespectively ([18]).

2.1 Pairing definition and proprieties:

Definition 2.1. [16], Let (G1,+),(G2,+) and

(G3, .)three finite abelian groups of the same order

r. A pairing is a function:

e:G1×G2−→ G3

(P, Q)7→ e(P, Q)

with the following properties:

1- Bilinear: for all S, S1, S2∈G1and for all

T, T1, T2∈G2

e(S1+S2, T ) = e(S1, T )e(S2, T )

e(S, T1+T2) = e(S, T1)e(S, T2)

2- Non-degenerate: ∀P∈G1, there is a Q∈G2

such that e(P, Q)= 1 and ∀Q∈G2, there is a P∈

G1such that e(P, Q)= 1.

(*) if e(S, T ) = 1 for all T∈G2, then T=P∞.

2.2 Frobenius Map

For any element a∈Fpm, let us consider the follow-

ing map

πp:Fpm→Fpm

a7→ ap

Defined by:

πp(a) = (a1w+a2wp+a3wp2+... +amwpm−1)p

=a1wp+a2wp2+a3wp3+... +amwpm

=amw+a1wp+a2wp2+... +am−1wpm−1

Note that the order of F∗

pmis given by pm−1, that is,

wpm=wis satisfied.

The map πpis specially called the Frobenius map.

The Frobenius map for a rational point in E(Fq)is

given by:

For any rational point P= (x, y), Frobenius map ϕ

is given by

ϕ:E(Fq)→E(Fq)

P(x, y)7→ (xq, yq).

P∞7→ P∞.

Definition 2.2. (Ate pairing):

The Ate pairing is define by

G1=E[r]∩ker(ϕ−[1]) and G2=E[r]∩ker(ϕ−[p]),

where ϕdenotes the Frobenius map over E(Fp).

Let P∈G1, and Q∈G2satisfy: ϕ(P) = P

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

326

Volume 21, 2022

and ϕ(Q) = [p]Q, with [p]Q be the scalar mul-

tiplication for the rational point Q with scalar p

as: [p]Q=∑p−1

i=0 Q,0≤p<r, (if p=r then

[r]Q=P∞) .

We note the ate pairing with a(Q, P ), such that:

a:G2×G1−→ F∗

pk/(F∗

pk)r

(Q, P )7→ a(Q, P ) = ft−1,Q(P)pk−1

where ft−1,Q is the rational function associated to

the point Q and integer t−1, with tis the Frobenius

trace of E(Fp).ft−1,Q = (t−1)(Q)−([t−1]Q)−

(t−2)(P∞)

2.3 Pairing-friendly elliptic curves

We will use the definition of pairing-friendly curves

that is taken from [14]:

The construction of such curves depends on our being

able to find integers x, y satisfying an equation of the

form Dy2= 4q(x)−t(x)2

•q(x)and t(x)are polynomials

•The parameter Dis the Complex-multiplication

discriminant fixed positive integer

Elliptic Curves with Embedding Degree 36:

We can take:











q(x) = 1

28749 (x14 −4x13 + 7x12

+683x8−2510x7+ 4781x6

+117649x2−386569x+ 823543)

r(x) = x12 + 683x6+ 117649

t(x) = 1

259 (259 + 757x+ 2x7).

We can see that q(x) = 1

28749 (x12 + 683x6+

117649)(x2−4x+ 7) + 1

28749 (84027x+ 222x7) =

28749 (x12 + 683x6+ 117649)(x2−4x+ 7) +

259 (757x+ 2x7)

so q(x) + 1 −t(x) = 1

28749 (x12 + 683x6+

117649)(x2−4x+ 7) = 1

28749 r(x)(x2−4x+ 7)

hence r(x)really divides q(x) + 1 −t(x).

Twists of curves:

Let Ebe an elliptic curve of j-invariant 0, defined

over Fp. We have :

with a, b ∈Fp,j∈Fp3and basis element jis the

cubic non residue in Fp3,i∈Fp3and basis element

jis the quadratic and cubic non residue in Fp3.

The figure below show all path possible for building

an elliptic curve with embedding degree 36

There is six path possible to building this curve

E(Fp)−→ E(Fp2)−→ E(Fp4)−→ E(Fp12 )−→ E(Fp36 )

E(Fp)−→ E(Fp2)−→ E(Fp6)−→ E(Fp12 )−→ E(Fp36 )

E(Fp)−→ E(Fp2)−→ E(Fp6)−→ E(Fp18 )−→ E(Fp36 )

E(Fp)−→ E(Fp3)−→ E(Fp6)−→ E(Fp12 )−→ E(Fp36 )

E(Fp)−→ E(Fp3)−→ E(Fp6)−→ E(Fp18 )−→ E(Fp36 )

E(Fp)−→ E(Fp3)−→ E(Fp9)−→ E(Fp18 )−→ E(Fp36 )

3. Tower Building Technique for

Elliptic Curve with Embedding Degree 36

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

327

Volume 21, 2022

Exploring the first path

E(Fp)−→E(Fp2)−→E(Fp4)−→E(Fp12 )−→E(Fp36 )

In everything that follow, we considers 3|(p−1)

and βis a quadratic and cubic non residue in Fp.

The appropriate choices of irreducible polynomial

defined by:

Fp2=Fp[u]/(u2−β),with βa non-square and u2= 2

Fp4=Fp2[v]/(v2−u),with va non-square and v2= 21

Fp12 =Fp4[t]/(t3−v),with ta non-cube and t3= 21

Fp36 =Fp12 [w]/(w3−t),with wa non-cube and w3= 2 1

Each point Pin E(Fp)can be written in E(Fp36 )

linked to the path choosed (see [9]-pp4). Each ra-

tional point P4∈G2⊂E(Fp36 )has a special vec-

tor representation with 36 elements in Fpfor each x4

and y4coordinates. The structure of the coefficients

of P4∈E(Fp36 )and its cubic twisted isomorphic

rational point P′′′ ∈E(Fp12 ), which also has a cubic

twisted isomorphic rational point P′′ ∈E(Fp4), that

lead to a quadratic twisted isomorphic rational point

P′∈E(Fp2), with other quadratic twisted isomor-

phic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) /x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′′ , y′′′ ∈Fp12

P′′(x′′ , y′′ ) = ((a, 0,0,0),(0,0,0, b)) with x′′ , y′′ ∈Fp4

P′(x′, y′) = ((a, 0),(0, b)) with x′, y′∈Fp2

P(x, y) = (a, b)with x, y ∈Fp

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M12)Fp3= (M4)Fp3)Fp3= ((M2)Fp2)Fp3)Fp3

= ((3m)Fp2)Fp3)Fp3= ((3M2)Fp3)Fp3

= ((9m)Fp3)Fp3= (9M3)Fp3= (54m)Fp3

= 54M3= 324m,

S36 = (S12)Fp3= (S4)Fp3)Fp3= ((S2)Fp2)Fp3)Fp3

= ((2m)Fp2)Fp3)Fp3= ((2M2)Fp3)Fp3

= ((6m)Fp3)Fp3= (6M3)Fp3= (36m)Fp3

= 36M3= 216m,

I36 = (I12)Fp3= (I4)Fp3)Fp3= ((I2)Fp2)Fp3)Fp3

= ((4m+i)Fp2)Fp3)Fp3= ((4M2+I2)Fp3)Fp3

= ((16m+i)Fp3)Fp3= (16M3+I3)Fp3

= (105m+ 2s+i)Fp3= 105M3+ 2S3+I3

= 639m+ 12s+i,

Exploring the second path

E(Fp)−→E(Fp2)−→E(Fp6)−→E(Fp12 )−→E(Fp36 )

The appropriate choices of irreducible polyno-

mial defined by:

Fp2=Fp[u]/(u2−β),with βa non-square and u2= 2

Fp6=Fp2[v]/(v3−u),with va non-cube and v3= 21/2

Fp12 =Fp6[t]/(t2−v),with ta non-square and t2= 21/6

Fp36 =Fp12 [w]/(w3−t),/wa non-cube and w3= 21/12

Each rational point P4∈G2⊂E(Fp36 )has a spe-

cial vector representation with 36 elements in Fpfor

each x4and y4coordinates. The structure of the

coefficients of P4∈E(Fp36 )and its cubic twisted

isomorphic rational point P′′′ ∈E(Fp12 ), which

also has a quadratic twisted isomorphic rational point

P′′ ∈E(Fp6), that lead to a cubic twisted isomor-

phic rational point P′∈E(Fp2), with other quadratic

twisted isomorphic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) /x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′′ , y′′′ ∈Fp12

P′′(x′′ , y′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) with x′′ , y′′ ∈Fp6

P′(x′, y′) = ((a, 0),(0, b)) with x′, y′∈Fp2

P(x, y) = (a, b)with x, y ∈Fp

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

328

Volume 21, 2022

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M12)Fp3= (M6)Fp2)Fp3= ((M2)Fp3)Fp2)Fp3

= ((3m)Fp3)Fp2)Fp3= ((3M3)Fp2)Fp3

= ((18m)Fp2)Fp3= (18M2)Fp3= (54m)Fp3

= 54M3= 324m,

S36 = (S12)Fp3= (S6)Fp2)Fp3= ((S2)Fp3)Fp2)Fp3

= ((2m)Fp3)Fp2)Fp3= ((2M3)Fp2)Fp3

= ((12m)Fp2)Fp3= (12M2)Fp3= (36m)Fp3

= 36M3= 216m,

I36 = (I12)Fp3= (I6)Fp2)Fp3= ((I2)Fp3)Fp2)Fp3

= ((4m+i)Fp3)Fp2)Fp3

= ((4M3+I3)Fp2)Fp3= ((33m+ 2s+i)Fp2)Fp3

= (33M2+ 2S2+I2)Fp3= (107m+i)Fp3

= 107M3+I3= 651m+ 2s+i,

Exploring the third path

E(Fp)−→ E(Fp2)−→ E(Fp6)−→ E(Fp18 )−→ E(Fp36 )

The appropriate choices of irreducible polyno-

mial defined by:

Fp2=Fp[u]/(u2−β),with βa non-square and u2= 2

Fp6=Fp2[v]/(v3−u),with va non-cube and v3= 21/2

Fp18 =Fp6[t]/(t3−v),with ta non-cube and t3= 21/6

Fp36 =Fp12 [w]/(w2−t),/wa non-square and w2= 21/18

Each rational point P4∈G2⊂E(Fp36 )has a spe-

cial vector representation with 36 elements in Fpfor

each x4and y4coordinates. The structure of the co-

efficients of P4∈E(Fp36 )and its quadratic twisted

isomorphic rational point P′′′ ∈E(Fp18 ), which

also has a cubic twisted isomorphic rational point

P′′ ∈E(Fp6), that lead to a cubic twisted isomor-

phic rational point P′∈E(Fp2), with other quadratic

twisted isomorphic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) with x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′′ , y′′′ ∈Fp18

P′′(x′′ , y′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) with x′′ , y′′ ∈Fp6

P′(x′, y′) = ((a, 0),(0, b)) with x′, y′∈Fp2

P(x, y) = (a, b)with x, y ∈Fp

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M18)Fp2= (M6)Fp3)Fp2= ((M2)Fp3)Fp3)Fp2

= ((3m)Fp3)Fp3)Fp2= ((3M3)Fp3)Fp2

= ((18m)Fp3)Fp2= (18M3)Fp2= (108m)Fp2

= 108M2= 324m,

S36 = (S18)Fp2= (S6)Fp3)Fp2= ((S2)Fp3)Fp3)Fp2

= ((2m)Fp3)Fp3)Fp2= ((2M3)Fp3)Fp2

= ((12m)Fp3)Fp2= (12M3)Fp2= (72m)Fp2

= 72M2= 216m,

I36 = (I18)Fp2= (I6)Fp3)Fp2= ((I2)Fp3)Fp3)Fp2

= ((4m+i)Fp3)Fp3)Fp2

= ((4M3+I3)Fp3)Fp2= ((33m+ 2s+i)Fp3)Fp2

= (33M3+ 2S3+I3)Fp2= (215m+ 2s+i)Fp2

= 207M2+ 12S2+I2= 649m+i,

Exploring the forth path

E(Fp)−→ E(Fp3)−→ E(Fp6)−→ E(Fp12 )−→ E(Fp36 )

The appropriate choices of irreducible polyno-

mial defined by:

Fp3=Fp[u]/(u3−β),with βa non-cube and u3= 2

Fp6=Fp3[v]/(v2−u),with va non-square and v2= 21/3

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

329

Volume 21, 2022

Fp12 =Fp6[t]/(t2−v),with ta non-square and t2= 21/6

Fp36 =Fp12 [w]/(w3−t),/wa non-cube and w3= 21/12

Each rational point P4∈G2⊂E(Fp36 )has a spe-

cial vector representation with 36 elements in Fpfor

each x4and y4coordinates. The structure of the

coefficients of P4∈E(Fp36 )and its cubic twisted

isomorphic rational point P′′′ ∈E(Fp12 ), which

also has a quadratic twisted isomorphic rational point

P′′ ∈E(Fp6), that lead to a quadratic twisted iso-

morphic rational point P′∈E(Fp3), with other cu-

bic twisted isomorphic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) /x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′′ , y′′′ ∈Fp12

P′′(x′′ , y′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′ , y′′ ∈Fp6

P′(x′, y′) = ((a, 0,0),(0,0, b)) with x′, y′∈Fp3

P(x, y) = (a, b)with x, y ∈Fp

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M12)Fp3= (M6)Fp2)Fp3= ((M3)Fp2)Fp2)Fp3

= ((6m)Fp2)Fp2)Fp3= ((6M2)Fp2)Fp3

= ((18m)Fp2)Fp3= (18M2)Fp3= (54m)Fp3

= 54M3= 324m,

S36 = (S12)Fp3= (S6)Fp2)Fp3= ((S3)Fp2)Fp2)Fp3

= ((5s)Fp2)Fp2)Fp3= ((5S2)Fp2)Fp3

= ((10m)Fp2)Fp3= (10M2)Fp3= (30m)Fp3

= 30M3= 180m,

I36 = (I12)Fp3= (I6)Fp2)Fp3= ((I3)Fp2)Fp2)Fp3

= ((9m+ 2s+ +i)Fp2)Fp2)Fp3

= ((9M2+ 2S2+I2)Fp2)Fp3= ((35m+i)Fp2)Fp3

= (35M2+I2)Fp3= (109m+i)Fp3

= 109M3+I3= 663m+ 2s+i,

Exploring the fifth path

E(Fp)−→ E(Fp3)−→ E(Fp6)−→ E(Fp18 )−→ E(Fp36 )

The appropriate choices of irreducible polyno-

mial defined by:

Fp3=Fp[u]/(u3−β),with βa non-cube and u2= 2

Fp6=Fp3[v]/(v2−u),with va non-square and v3= 21/3

Fp18 =Fp6[t]/(t3−v),with ta non-cube and t3= 21/6

Fp36 =Fp18 [w]/(w2−t),/wa non-square and w2= 21/18

Each rational point P4∈G2⊂E(Fp36 )has a spe-

cial vector representation with 36 elements in Fpfor

each x4and y4coordinates. The structure of the co-

efficients of P4∈E(Fp36 )and its quadratic twisted

isomorphic rational point P′′′ ∈E(Fp18 ), which

also has a cubic twisted isomorphic rational point

P′′ ∈E(Fp6), that lead to a quadratic twisted iso-

morphic rational point P′∈E(Fp3), with other cu-

bic twisted isomorphic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) /x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′′ , y′′′ ∈Fp18

P′′(x′′ , y′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) /x′′ , y′′ ∈Fp6

P′(x′, y′) = ((a, 0,0),(0,0, b)) with x′, y′∈Fp3

P(x, y) = (a, b)with x, y ∈Fp

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M18)Fp2= (M6)Fp3)Fp2= ((M3)Fp2)Fp3)Fp2

= ((6m)Fp2)Fp3)Fp2= ((6M2)Fp3)Fp2

= ((18m)Fp3)Fp2= (18M3)Fp2= (108m)Fp2

= 54M3= 324m,

S36 = (S18)Fp2= (S6)Fp3)Fp2= ((S3)Fp2)Fp3)Fp2

= ((5s)Fp2)Fp3)Fp2= ((5S2)Fp3)Fp2

= ((10m)Fp3)Fp2= (10M3)Fp2= (60m)Fp2

= 60M2= 180m,

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

330

Volume 21, 2022

I36 = (I18)Fp2= (I6)Fp3)Fp2= ((I3)Fp2)Fp3)Fp2

= ((9m+ 2s+i)Fp2)Fp3)Fp2

= ((9M2+ 2S2+I2)Fp3)Fp2= ((35m+i)Fp3)Fp2

= (35M3+I3)Fp2= (219m+ 2s+i)Fp2

= 219M2+ 2S2+I2= 665m+i,

Exploring the sixth path

E(Fp)−→ E(Fp3)−→ E(Fp9)−→ E(Fp18 )−→ E(Fp36 )

The appropriate choices of irreducible polyno-

mial defined by:

Fp3=Fp[u]/(u3−β),with βa non-cube and u3= 2

Fp9=Fp3[v]/(v3−u),with va non-cube and v3= 21/3

Fp18 =Fp9[t]/(t2−v),with ta non-square and t2= 21/9

Fp36 =Fp18 [w]/(w2−t),/wa non-square and w2= 2 1

Each rational point P4∈G2⊂E(Fp36 )has a spe-

cial vector representation with 36 elements in Fpfor

each x4and y4coordinates. The structure of the co-

efficients of P4∈E(Fp36 )and its quadratic twisted

isomorphic rational point P′′′ ∈E(Fp18 ), which

also has a quadratic twisted isomorphic rational point

P′′ ∈E(Fp9), that lead to a cubic twisted isomorphic

rational point P′∈E(Fp3), with other cubic twisted

isomorphic rational point P∈E(Fp).

P4(x4, y4) = ((a, 0, ..., 0),(0, ..., 0, b)) with x4, y4∈Fp36

P′′′(x′′′ , y′′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) with x′′′ , y′′′ ∈Fp18

P′′(x′′ , y′′ ) = ((a, 0, ..., 0),(0, ..., 0, b)) with x′′ , y′′ ∈Fp9

P′(x′, y′) = ((a, 0,0),(0,0, b)) with x′, y′∈Fp3

P(x, y) = (a, b)with x, y ∈Fp

The cost of multiplication, squaring and inversion in

in the 36th twisted field Fp36 are:

M36 = (M18)Fp2= (M9)Fp2)Fp2= ((M3)Fp3)Fp2)Fp2

= ((6m)Fp3)Fp2)Fp2= ((6M3)Fp2)Fp2

= ((36m)Fp2)Fp2= (36M2)Fp2= (108m)Fp2

= 108M2= 324m,

S36 = (S18)Fp2= (S9)Fp2)Fp2= ((S3)Fp3)Fp2)Fp2

= ((5s)Fp3)Fp2)Fp2= ((5S3)Fp2)Fp2

= ((25s)Fp2)Fp2= (25S2)Fp2= (50m)Fp2

= 50M2= 150m,

I36 = (I18)Fp2= (I9)Fp2)Fp2= ((I3)Fp3)Fp2)Fp2

= ((9m+ 2s+i)Fp3)Fp2)Fp2

= ((9M3+ 2S3+I3)Fp2)Fp2

= ((63m+ 12s+i)Fp2)Fp2

= (63M2+ 12S2+I2)Fp2= (217m+i)Fp2

= 217M2+I2= 655m+i,

Let Ebe an elliptic curve defined over Fpwith p > 3

according to the following short Weierstrass equa-

tion: E:y2=x3+ax +b.

Definition 4.1. (Optimal ate pairing on elliptic

curves with embedding degree 36):

The Optimal ate pairing on elliptic curves with em-

bedding degree 36 is define for P∈G1, and Q∈G2.

We note it aopt, such that:

aopt :G2×G1−→ G3

(Q, P )7→ aopt(Q, P ) = fx,Q(P)p36 −1

For optimal ate pairing with embedding degree 36

we have:

(Q, P )7→ (fx,Q.f p

3,Q.lx[Q],[3p]Q(P)) p36 −1

with lA,B denotes the line through points A and B,

4. Main Theorem

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

331

Volume 21, 2022

Algorithm 1 Optimal ate pairing with embedding de-

gree 36

Input: P∈G1, Q ∈G′

Output: aopt(Q, P )

1: f←1,T←Q

2: for i=llog2(l)−1downto 0 do

3: f←f2.lT,T (P), T ←[2]T

4: if li= 1 then

5: f←f.lT,Q(P), T ←T+Q

6: end

7: end

8: f1←fp

9: f←f.f1

10: Q1←x[Q],Q2←[3p]Q

11: f←f.lQ1,Q2(P)

12: f←fp36−1

13: return f

The cost of line 3 is 3Mk+ 2Sk+Ik

The cost of line 5 is 3Mk+Sk+Ik

Lemma 4.1. .

In miller algorithm we have that the final exponen-

tiation is p36−1

r. The efficient computation of final

exponentiation take a lot of attention. Because this

exponentiation can be divide into two parts as fol-

low:

p36 −1

r= (p36 −1

ϕk(p)).(ϕk(p)

We can take A=p36 −1

ϕk(p)and d=ϕk(p)

r, so that

fp18−1

r= (fA)d.

The goal of this final exponentiation is to raise the

function f∈Fpkin the miller loop result, to the

p36−1

r-th power. As we see above, this can be broken

into two part, p36 −1

r= (p36−1

ϕk(p)).(ϕk(p)

r). Computing

fA=f

p36−1

ϕk(p)is considered easy, consting only a few

multiplication and inversion, and inexpensive p-th

powering in Fpk. But the calculation of the power

d=ϕk(p)

ris a more hard to do.

We can see that: p36 −1=(p18 −1)(p18 + 1) or

p36 −1 = (p12 −1)(p24 +p12 + 1)

Curve Final exponentiation Easy part Hard part

KSS-36 p36−1

rp12 −1p24+p12 +1

KSS-36 p36−1

rp18 −1p18+1

The exponentiation fp36−1

rcan be computed us-

ing the following multiplication-powering-inversion

chain:

•f→fp→((fp)p)p=fp3→((fp3)p3)p3

=fp9→(fp9)p9=fp18

f→fp18

f=fp18−1

f→fp18 .f =fp18+1

f→fp18−1.f p18 +1 =fp36 −1→fp36 −1

The cost to calculate fp36−1

ris

6(p−1)Mk+ 2Ik+ 2Mk

•or f→fp→((fp)p)p=fp3→(fp3)p3

=fp6→(fp6)p6=fp12

f→(fp12 )p12 →fp24

f→fp12

f=fp12−1

f→fp24 .fp12 .f =fp24+p12 +1

f→fp12−1.f p24 +p12 +1 =fp36 −1→fp36 −1

The cost to calculate fp36−1

ris

6(p−1)Mk+ 2Ik+ 3Mk

So with working with the first case is a slight bet-

ter than second case, so the cost of miller algorithm

in this case is

2(6MK+3Sk+2Ik)+6(p−1)Mk+6Mk+Sk+3Ik

Comparison

Here we shall give cost of operations (Multiplication,

squaring and inversion) of the tower field that we use

in every path possible

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

332

Volume 21, 2022

Table 1: Cost of operations in first path

Field O Cost

Fp4:M49m

S46m

I416m+i

Fp12 :M12 54m

S12 36m

I12 105m+2s+i

Fp36 :M36 324m

S36 216m

I36 639m+12s+i

Table 2: Cost of operations in second path

Field O Cost

Fp6:M618m

S612m

I633m+2s+i

Fp12 :M12 54m

S12 36m

I12 107m+i

Fp36 :M36 324m

S36 216m

I36 651m+2s+i

Table 3: Cost of operations in third path

Field O Cost

Fp6:M618m

S612m

I633m+2s+i

Fp18 :M18 108m

S18 72m

I18 207m+12s+i

Fp36 :M36 324m

S36 216m

I36 649m+i

Table 4: Cost of operations in fourth path

Field O Cost

Fp6:M618m

S610m

I635m+i

Fp12 :M12 54m

S12 30m

I12 109m+i

Fp36 :M36 324m

S36 180m

I36 663m+2s+i

Table 5: Cost of operations in fifth path

Field O Cost

Fp6:M618m

S610m

I635m+i

Fp18 :M18 108m

S18 60m

I18 219m+2s+i

Fp36 :M36 324m

S36 180m

I36 665m+i

Table 6: Cost of operations in sixth path

Field O Cost

Fp9:M936m

S925s

I973m+12s+i

Fp18 :M18 108m

S18 50m

I18 217m+i

Fp36 :M36 324m

S36 150m

I36 655m+i

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

333

Volume 21, 2022

In the tables above give the overall cost of opera-

tions in each the tower fields.

We found that the cost of multiplication is the same

for any path chosen, however the cost of squaring and

inversion change on the path, so we can see that the

minimal cost for squaring is 150m (path 6) and in-

version is 639m+12s+i (path 1), so to find the better

path we shall calculate the cost of miller algorithm

taking S= 0.8Mand I= 40Min path 1 and 6, we

have:

On path 1: (1964,6l+1944p+2308,8)m.

On path 6: (1892l+1944p+2235).

So we found that the optimal path to do this calcu-

lation is when we chose the sixth path, so the best

path for tower building the elliptic curve of embed-

ding degree 36 is:

Fp−→ Fp3−→ Fp9−→ Fp18 −→ Fp36

In this paper, we give some methods for tower build-

ing of extension of finite field of embedding degree

36. We show that there is three efficients construc-

tions of these extensions of degree 36. We show that

by using a degree 2 or 3 twist we handle to perform

most of the operations in Fpor Fp9or in Fpor Fp6.

By using this tower building technique, we also im-

prove the arithmetic of Fp6and Fp9in order to get

better results of calculate the cost of their multiplica-

tion, squaring and inversion, and found the optimal

path for tower building this field with the minimal

cost.

References:

[1] Victor S. Miller. Use of elliptic curves in cryp-

tography. Crypto 1985, LNCS 218, pp. 417-

426, 1985.

[2] Neal Koblitz. Elliptic curve cryptosystems.

Mathematics of Computation, Vol. 48, No. 177,

pp. 203-209, 1987.

[3] R.L. Rivest, A. Shamir, and L.M. Adleman. A

method for obtaining digital signatures and pub-

lickey cryptosystems. Commun. ACM, Vol. 21,

No. 2, pp. 120-126, 1978.

[4] Whelan, C., Scott, M.: The Importance of the

Final Exponentiation in Pairings When Consid-

ering Fault Attacks. In: Takagi, T., Okamoto,

T., Okamoto, E., Okamoto, T. (eds.) Pairing

2007. LNCS, vol. 4575, pp. 225-246. Springer,

Heidelberg (2007).

[5] Nadia El Mrabet, Nicolas Guillermin, and So-

rina Ionica. A study of pairing computation for

curves with embedding degree 15. DBLP vol-

ume 2009.

[6] Nadia El Mrabet and Marc Joye. GUIDE TO

PAIRING-BASED CRYPTOGRAPHY. Chap-

man and Hall/CRC CRYPTOGRAPHY AND

NETWORK SECURITY, 2018.

[7] Emmanuel Fouotsa, Nadia El Mrabet and Am-

inatou Pecha. Optimal Ate Pairing on Ellip-

tic Curves with Embedding Degree 9; 15 and

27. journal of Groups, Complexity, Cryptology,

Volume 12, issue 1 (April 17, 2020) gcc:6285

[8] Narcisse Bang Mbiang, Diego De Freitas

Aranha, Emmanuel Fouotsa. Computing the

optimal ate pairing over elliptic curves with em-

bedding degrees 54 and 48 at the 256-bit secu-

rity level. Int. J. Applied Cryptography, Vol. 4,

No. 1, 2020.

[9] Md. Al-Amin Khandaker, Taehwan Park, Ya-

suyuki Nogami, and Howon Kim, Member, KI-

ICE. A Comparative Study of Twist Property

in KSS Curves of Embedding Degree 16 and

18 from the Implementation Perspective. J. lnf.

Commun. Converg. Eng. 15(2): 97-103, Jun.

2017.

[10] Md. Al-Amin Khandaker, Yasuyuki NOGAMI.

Isomorphic Mapping for Ate-based Pairing

over KSS Curve of Embedding Degree 18.

10.1109/CANDAR.2016.0113 November

2016.

[11] Rahat Afreen, S.C. Mehrotra. A REVIEW ON

ELLIPTIC CURVE CRYPTOGRAPHY FOR

EMBEDDED SYSTEMS. International Jour-

nal of Computer Science & Information Tech-

nology (IJCSIT), Vol 3, No 3, June 2011.

[12] Md. Al-Amin Khandaker, Yasuyuki NOGAMI.

A Consideration of Towering Scheme for Ef-

ficient Arithmetic Operation over Extension

Field of Degree 18. 19th International Confer-

ence on Computer and Information Technol-

ogy, December 18-20, 2016, North South Uni-

versity, Dhaka, Bangladesh.

5. Conclusion

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

334

Volume 21, 2022

[13] Nadia El Mrabet, Aurore Guillevic, and Sorina

Ionica. Efficient Multiplication in Finite Field

Extensions of Degree 5. DBLP 10.1007/978-3-

642-21969-6-12 June 2011.

[14] Michael Scott, Aurore Guillevic. A New Fam-

ily of Pairing-Friendly elliptic curves. May 21,

2018.

[15] Michael Scott, On the Efficient Implementa-

tion of Pairing-Based Protocols, in cryptogra-

phy and coding, pp. 296-308, Springer, 2011.

[16] Joseph H. Silverman, The Arithmetic of Elliptic

Curves, Second Edition, 2000.

[17] Ezekiel J. Kachisa, Edward F. Schaefer, and

Michael Scott. Constructing Brezing-Weng

pairing-friendly elliptic curves using elements

in the cyclotomic field. In Galbraith and Pater-

son [29], pages 126-135.

[18] Augusto Jun Devegili1, Colm Eigeartaigh,

Michael Scott, and Ricardo Dahab, Multiplica-

tion and Squaring on Pairing-Friendly Fields,

2006.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the Creative

Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en_US

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2022.21.39

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2224-2872

335

Volume 21, 2022