Tower building technique on elliptic curve with embedding degree 72

ISMAIL ASSOUJAA1, SIHAM EZZOUAK2AND HAKIMA MOUANIS3

Departement of Mathematics (LASMA laboratory)

University Sidi Mohammed Ben Abdellah

Fez city

MOROCCO

Abstract: Pairing based cryptography is one of the newest security solution that attract a lot of attention, because

we can work with efficient and faster pairing to make the security a lot practical, also the working with extension

finite field of the form Fpkis more useful and secure with k≥12 the implementation become more important. In

this paper, we will presents cases studies of improving pairing arithmetic calculation on curves with embedding

degree 72. We use the tower building technique, and study the case when using a degree 2 or 3 twist to carry out

most operations in Fp4,Fp6,Fp8,Fp9,Fp12 ,Fp18 ,Fp24 ,Fp36 and Fp72 .

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

Received: May 12, 2022. Revised: October 26, 2022. Accepted: November 28, 2022. Published: December 31, 2022.

After the discovering of pairing-based cryptography,

developers and researchers have been studding 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, af-

ter that more pairing are appear like tate pairing, ate

pairing and a lot more. The benefice of Elliptic curve

cryptosystems which was discovered by Neal Koblitz

[1] and Victor Miller [2] are to reduce the key sizes

of the keys utilize in public key cryptography. Some

works like presented in [3] interested in signature nu-

meric. The authors in [4] show that we can use the

final exponentiation in pairings as one of the coun-

termeasures against fault attacks. In [6],[7],[8], [15]

Nadia El and others show a study case of working

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

27. Also in [10],[11],[12],[13] and [14] researchers

show the case of working with curve with some em-

bedding degree. In [9] they give a study of security

level of optimal ate pairing, and other useful work

(see [5]) .

In the present article, we seek to obtain efficient ways

to pairing computation for curves of embedding de-

gree 72. We will see how to improve arithmetic op-

eration in curves with embedding degree 72 by us-

ing the tower building technique. We will give three

cases studies that show, when we use a degree 2

twists, we can handle most operations in Fp2and Fp4

or Fp6and Fp12 , and when we use a degree 3 twists,

we can handle most operations in Fp3and Fp6or Fp6

or Fp9and Fp18 instead. By making use of an tower

building technique, we also improve the arithmetic of

Fp9and Fp6in order to get better results. Finally we

will compare these cases to know which one is the

optimal arithmetic path on Fp2,Fp3,Fp4,Fp6,Fp8,

Fp9,Fp12 ,Fp18 ,Fp24 ,Fp36 and Fp72

In this paper, we will investigate and examine what

will happens in case of optimal ate pairing with em-

bedding degree 72.

The paper is organized as follow. Section 2 we re-

call some background on the main pairing propri-

eties also ate pairing, and Miller Algorithm. Section

3 presents our new techniques of tower building the

elliptic curve of embedding degree 72. Section 4 will

presents the optimal ate pairing used in our work. Fi-

nally, Section 5 we will calculate the operation cost

in this tower

elds for each possible case and concludes this pa-

per.

In everything that follows, Ewill represent an elliptic

curve with equation

y2=x3+ax +bfor b∈Fqwith qprime number.

The symbol aopt will denote the optimal ate pairing.

We shall use, without explicit mention, the following

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

n∈N∗.

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

n∈N∗.

•G3⊂F∗

qk⊂µn: cyclic multiplicative group of

cardinal n∈N∗.

1. Introduction

2. Mathematical Background

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

126

Volume 10, 2022

•µn={u∈¯

Fq|un= 1}.

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

•k: the embedding degree: the smallest integer

such that rdivides qk−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.

•M8, S8, I8: multiplication, squaring, inversion

in field Fp8.

•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 .

•M24, S24, I24: multiplication, squaring, inver-

sion in field Fp24 .

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

sion in field Fp36

•M72, S72, I72: multiplication, squaring, inver-

sion in field Fp72 .

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 ([20]).

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 ([20]).

2.1 Pairing definition and proprieties:

Definition 2.1. [18], 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) = Pand

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

127

Volume 10, 2022

ϕ(Q) = [p]Q.

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 [16]:

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 72:

As describe in ([9]-pp31), let k be a positive integer

with k < 1000 and 3|k. Let l=lcm(8, k), in our

case ok k= 72, we found that l= 72











q(x) = 1

8(2(xl

k+ 1)2+ (1 −xl

k)2(x5l

24 +xl

8−xl

24 )2)

8(2(x4+ 1)2+ (1 −x4)2(x15 +x9−x3)2).

r(x) = Φl(x) = Φ72(x) = x24 −x12 + 1.

t(x) = xl/k+ 1 = x4+ 1.

We can see that

q(x)+1−t(x) = (x24 −x12 + 1)(x14 −2x10 +

2x8+x6−4x4+ 2)/8

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 72

There is eight path possible to building this curve

E(Fp)→E(Fp2)→E(Fp4)→E(Fp8)→E(Fp24 )→E(Fp72 )

E(Fp)→E(Fp2)→E(Fp6)→E(Fp12 )→E(Fp24 )→E(Fp72 )

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

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

E(Fp)→E(Fp3)→E(Fp6)→E(Fp12 )→E(Fp24 )→E(Fp72 )

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

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

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

3. Tower Building Technique Elliptic

Curve with Embedding Degree 72

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

128

Volume 10, 2022

Exploring the first path

E(Fp)→E(Fp2)→E(Fp4)→E(Fp8)→E(Fp24 )→E(Fp72 )

The appropriate choices of irreducible polyno-

mial 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/2

Fp8=Fp4[t]/(t3−v),with ta non-square and t2= 21/4

Fp24 =Fp8[w]/(w3−t),with wa non-cube and w3= 21/8

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

Each rational point P5∈G2⊂E(Fp72 )has a spe-

cial vector representation with 72 elements in Fpfor

each x5and y5coordinates. The construction below

show that point P5∈E(Fp72 )and its cubic twisted

isomorphic rational point P4∈E(Fp24 ), which also

has a cubic twisted isomorphic rational point P′′′ ∈

E(Fp8), that lead to a three quadratic twisted isomor-

phic rational point P′′ ∈E(Fp4),P′∈E(Fp2)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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

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

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 72th twisted field Fp72 are:

M72 = (M24)Fp3= (M8)Fp3)Fp3= ((M4)Fp2)Fp3)Fp3

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

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

= ((9M2)Fp3)Fp3= ((27m)Fp3)Fp3= (27M3)Fp3

= (162m)Fp3= 162M3= 972m.

S72 = (S24)Fp3= (S8)Fp3)Fp3= ((S4)Fp2)Fp3)Fp3

= (((S2)Fp2)Fp2)Fp3)Fp3= (((2m)Fp2)Fp2)Fp3)Fp3

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

= ((6M2)Fp3)Fp3= ((18m)Fp3)Fp3= (18M3)Fp3

= (108m)Fp3= 108M3= 648m.

I72 = (I24)Fp3= (I8)Fp3)Fp3= ((I4)Fp2)Fp3)Fp3

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

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

= ((16M2+I2)Fp3)Fp3= ((52m+i)Fp3)Fp3

= (52M3+I3)Fp3= (321m+ 2s+i)Fp3

= 321M3+ 2S3+I3= 1935m+ 12s+i.

Exploring the second path

E(Fp)→E(Fp2)→E(Fp6)→E(Fp12 )→E(Fp24 )→E(Fp72 )

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),/ta non-square and t2= 21/6

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

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

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its cubic twisted iso-

morphic rational point P4∈E(Fp24 ), which also has

a quadratic twisted isomorphic rational point P′′′ ∈

E(Fp12 ), that lead to a more quadratic twisted iso-

morphic rational point P′′ ∈E(Fp6)and its cubic

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

129

Volume 10, 2022

twisted isomorphic rational point P′∈E(Fp2)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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

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, b)) with x′, y′∈Fp2

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

The cost of multiplication, squaring and inversion in

in the 72th twisted field Fp72 are:

M72 = (M24)Fp3= (M12)Fp2)Fp3= ((M6)Fp2)Fp2)Fp3

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

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

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

= (162m)Fp3= 162M3= 972m.

S72 = (S24)Fp3= (S12)Fp2)Fp3= ((S6)Fp2)Fp2)Fp3

= (((S2)Fp3)Fp2)Fp2)Fp3= (((2m)Fp3)Fp2)Fp2)Fp3

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

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

= (108m)Fp3= 108M3= 648m.

I72 = (I24)Fp3= (I12)Fp2)Fp3= ((I6)Fp2)Fp2)Fp3

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

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

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

= (107M2+I2)Fp3= (325m+i)Fp3

= 325M3+I3= 1959m+ 2s+i.

Exploring the third path

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

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 =Fp18 [w]/(w2−t),/wa non-square and w2= 21/18

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

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its quadratic twisted iso-

morphic rational point P4∈E(Fp36 ), which also has

a quadratic twisted isomorphic rational point P′′′ ∈

E(Fp18 ), that lead to a more cubic twisted isomorphic

rational point P′′ ∈E(Fp6)and its cubic twisted iso-

morphic rational point P′∈E(Fp2)and P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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, b)) with x′, y′∈Fp2

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

The cost of multiplication, squaring and inversion in

in the 72th twisted field Fp72 are:

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

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

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

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

= (324m)Fp2= 324M2= 972m.

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

= (((S2)Fp3)Fp3)Fp2)Fp2= (((2m)Fp3)Fp3)Fp2)Fp2

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

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

= (216m)Fp2= 216M2= 648m.

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

130

Volume 10, 2022

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

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

= (((4M3+I3)Fp3)Fp2)Fp2

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

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

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

= (207M2+ 12S2+I2)Fp2= (649m+i)Fp2

= 649M2+I2= 1951m+i.

Exploring the forth path

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

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),with wa non-cube and w3= 2 1

Fp72 =Fp36 [z]/(z2−w),/za non-square and z2= 21/36

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its quadratic twisted

isomorphic rational point P4∈E(Fp36 ), which also

has a cubic twisted isomorphic rational point P′′′ ∈

E(Fp12 ), that lead to a more quadratic twisted iso-

morphic rational point P′′ ∈E(Fp6)and its cubic

twisted isomorphic rational point P′∈E(Fp2)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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, b)) with x′, y′∈Fp2

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

The cost of multiplication, squaring and inversion in

in the 72th twisted field Fp72 are:

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

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

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

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

= (324m)Fp2= 324M2= 972m.

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

= (((S2)Fp3)Fp2)Fp3)Fp2= (((2m)Fp3)Fp2)Fp3)Fp2

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

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

= (216m)Fp2= 216M2= 648m.

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

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

= (((4M3+I3)Fp2)Fp3)Fp2

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

= ((33M2+ 2S2+I2)Fp3)Fp2

= ((107m+i)Fp3)Fp2= (107M3+I3)Fp2

= (651m+ 2s+i)Fp2= 651M2+ 2S2+I2

= 1961m+i.

Exploring the fifth path

E(Fp)→E(Fp3)→E(Fp6)→E(Fp12 )→E(Fp24 )→E(Fp72 )

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

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

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

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

131

Volume 10, 2022

Fp72 =Fp24 [z]/(z3−w),/wa non-cube and z3= 21/24

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its cubic twisted iso-

morphic rational point P4∈E(Fp24 ), which also has

a quadratic twisted isomorphic rational point P′′′ ∈

E(Fp12 ), that lead to a more quadratic twisted iso-

morphic rational point P′′ ∈E(Fp6)and its cubic

twisted isomorphic rational point P′∈E(Fp3)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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

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 72th twisted field Fp72 are:

M72 = (M24)Fp3= (M12)Fp2)Fp3= ((M6)Fp2)Fp2)Fp3

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

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

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

= (162m)Fp3= 162M3= 972m.

S72 = (S24)Fp3= (S12)Fp2)Fp3= ((S6)Fp2)Fp2)Fp3

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

= (((5S2)Fp2)Fp2)Fp3= (((10m)Fp2)Fp2)Fp3

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

= (90m)Fp3= 90M3= 540m.

I72 = (I24)Fp3= (I12)Fp2)Fp3= ((I6)Fp2)Fp2)Fp3

= (((I3)Fp2)Fp2)Fp2)Fp3

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

= (((9M2+ 2S2+I2)Fp2)Fp2)Fp3

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

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

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

= 331M3+I3= 1997m+ 2s+i.

Exploring the sixth path

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

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

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

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

Fp72 =Fp36 [z]/(z2−w),/za non-square and z2= 21/36

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its quadratic twisted

isomorphic rational point P4∈E(Fp36 ), which also

has a cubic twisted isomorphic rational point P′′′ ∈

E(Fp12 ), that lead to a more quadratic twisted iso-

morphic rational point P′′ ∈E(Fp6)and its cubic

twisted isomorphic rational point P′∈E(Fp3)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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 72th twisted field Fp72 are:

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

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

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

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

= (324m)Fp2= 324M2= 972m.

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

132

Volume 10, 2022

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

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

= (((5S2)Fp2)Fp3)Fp2= (((10m)Fp2)Fp3)Fp2

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

= (180m)Fp2= 180M2= 540m.

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

= (((I3)Fp2)Fp2)Fp3)Fp2

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

= (((9M2+ 2S2+I2)Fp2)Fp3)Fp2

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

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

= (109M3+I3)Fp2= (663m+ 2s+i)Fp2

= 663M2+ 2S2+I2= 1997m+i.

Exploring the seventh path

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

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

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

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

Fp72 =Fp36 [z]/(z2−w),/za non-square and z2= 21/36

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its quadratic twisted iso-

morphic rational point P4∈E(Fp36 ), which also has

a quadratic twisted isomorphic rational point P′′′ ∈

E(Fp18 ), that lead to a more cubic twisted isomorphic

rational point P′′ ∈E(Fp6)and its cubic twisted iso-

morphic rational point P′∈E(Fp3)and P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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 72th twisted field Fp72 are:

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

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

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

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

= (324m)Fp2= 324M2= 972m.

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

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

= (((5S2)Fp3)Fp2)Fp2= (((10m)Fp3)Fp2)Fp2

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

= (180m)Fp2= 180M2= 540m.

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

= (((I3)Fp2)Fp3)Fp2)Fp2

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

= (((9M2+ 2S2+I2)Fp3)Fp2)Fp2

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

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

= (219M2+ 2S2+I2)Fp2= (665m+i)Fp2

= 665M2+I2= 1999m+i.

Exploring the eighth path

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

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

133

Volume 10, 2022

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= 21/18

Fp72 =Fp36 [z]/(z2−w),/za non-square and z2= 21/36

Each rational point P5∈G2⊂E(Fp72 )has a special

vector representation with 72 elements in Fpfor each

x5and y5coordinates. The construction below show

that point P5∈E(Fp72 )and its quadratic twisted iso-

morphic rational point P4∈E(Fp36 ), which also has

a quadratic twisted isomorphic rational point P′′′ ∈

E(Fp18 ), that lead to a more quadratic twisted iso-

morphic rational point P′′ ∈E(Fp9)and its cubic

twisted isomorphic rational point P′∈E(Fp3)and

P∈E(Fp).

P5(x5, y5) = ((a, 0, ..., 0),(0, ..., 0, b)) /x5, y5∈Fp72

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′′ ∈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 72th twisted field Fp72 are:

M72 = (M36)Fp2= (M18)Fp2)Fp2= ((M9)Fp2)Fp2)Fp2

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

= (((6M3)Fp2)Fp2)Fp2= (((36m)Fp2)Fp2)Fp2

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

= (324m)Fp2= 324M2= 972m.

S72 = (S36)Fp2= (S18)Fp2)Fp2= ((S9)Fp2)Fp2)Fp2

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

= (((5S3)Fp2)Fp2)Fp2= (((25s)Fp2)Fp2)Fp2

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

= (150m)Fp2= 150M2= 450m.

I72 = (I36)Fp2= (I18)Fp2)Fp2= ((I9)Fp2)Fp2)Fp2

= (((I3)Fp3)Fp2)Fp2)Fp2

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

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

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

= ((63M2+ 12S2+I2)Fp2)Fp2

= ((217m+i)Fp2)Fp2

= (217M2+I2)Fp2= (655m+i)Fp2

= 655M2+I2= 1969m+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 72):

The Optimal ate pairing on elliptic curves with em-

bedding degree 72 is define for P∈G1and Q∈G2.

We note it aopt, such that:

aopt :G2×G1−→ G3

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

For optimal ate pairing with embedding degree 72

([21]-pp30), we have:

(Q, P )7→ (fx,Q.fp

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

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

4. Optimal Ate Pairing on Elliptic

Curve with Embedding Degree 72

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

134

Volume 10, 2022

Algorithm 1 Optimal ate pairing with embedding de-

gree 72

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←fp72−1

13: return f

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

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

Proposition 4.1. .

In miller algorithm we have that the final exponen-

tiation is p72 −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: p72−1

r= (p72 −1

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

Remark 4.1. We can take A=p72−1

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

so that fp72−1

r= (fA)d.

The goal of this final exponentiation is to raise

the function f∈Fpkin the miller loop result, to the

p72−1

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

into two part, p72−1

r= (p72 −1

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

r). Computing

fA=f

p72−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: p72 −1=(p36 −1)(p36 + 1) or

p72 −1 = (p24 −1)(p48 +p24 + 1)

Curve Final exponentiation Easy part Hard part

KSS-72 p72−1

rp24 −1p48+p24 +1

KSS-72 p72−1

rp36 −1p36+1

The exponentiation fp72−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 = (fp18 )p18 =fp36

f→fp36

f=fp36−1

f→fp36 .f =fp36+1

f→fp36−1.f p36+1 =fp72 −1→fp72−1

The cost to calculate fp72−1

ris

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

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

=fp6→(fp6)p6=fp12 = (fp12 )p12 =fp24

f→(fp24 )p24 →fp48

f→fp24

f=fp24−1

f→fp48 .fp24 .f =fp48 +p24+1

f→fp24−1.f p48+p24 +1 =fp72−1→fp72 −1

The cost for computing fp72−1

ris

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

So with working with the first case is a slight better

than second case, so the cost of miller algorithm in

this case is

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

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

135

Volume 10, 2022

Table 1: Cost of operations in first path

Field O Cost

Fp4:M49m

S46m

I416m+i

Fp8:M827m

S818m

I852m+i

Fp24 :M24 162m

S24 108m

I24 321m+2s+i

Fp72 :M72 972m

S72 648m

I72 1935m+12s+i

Table 2: Cost of operations in second path

Field O Cost

Fp6:M618m

S62m

I633m+2s+i

Fp12 :M12 54m

S12 12m

I12 107m+i

Fp24 :M24 162m

S24 36m

I24 325m+2s+i

Fp72 :M72 972m

S72 648m

I72 1943m+2s+i

Table 3: Cost of operations in third path

Field O Cost

Fp6:M618m

S612m

I633m+2s+i

Fp18 :M18 108m

S18 36m

I18 207m+12s+i

Fp36 :M36 324m

S36 108m

I36 649m+i

Fp72 :M72 972m

S72 648m

I72 1951m+i

Table 4: Cost of operations in forth path

Field O Cost

Fp6:M618m

S612m

I633m+2s+i

Fp12 :M12 54m

S12 36m

I12 107m+i

Fp36 :M36 324m

S36 216m

I36 661m++2si

Fp72 :M72 972m

S72 648m

I72 1961m+i

Table 5: Cost of operations in fifth path

Field O Cost

Fp6:M618m

S610m

I635m+i

Fp12 :M12 54m

S12 30m

I12 109m+i

Fp24 :M24 162m

S24 90m

I24 331m+i

Fp72 :M72 972m

S72 540m

I72 1997m+2s+i

Table 6: Cost of operations in sixth 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

Fp72 :M72 972m

S72 540m

I72 1997m+i

Table 7: Cost of operations in seventh 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

Fp72 :M72 972m

S72 540m

I72 1999m+i

Table 8: Cost of operations in eighth path

Field O Cost

Fp9:M936m

S925s

I963m+12s+i

Fp18 :M18 108m

S18 50m

I18 217m+i

Fp36 :M36 324m

S36 150m

I36 655m+i

Fp72 :M72 972m

S72 450m

I72 1969m+i

5. Comparison

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

136

Volume 10, 2022

In the tables above, we give the overall cost of

operations in each the tower fields. We found that

the cost of multiplication is the same whatever the

path, however the cost of squaring and inversion

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

cost for squaring is 450m (path 8) and inversion is

1935m+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 3, we have:

On path 1:

2(6M72 +3S72 + 2I72) +7(p−1)M72 + 6M72 +

S72 + 3I72 = (5872.6l+ 6804p+ 5629,8)m.

On path 8:

2(6M72 + 3S72 + 2I72) + 7(p−1)M72 + 6M72 +

S72 + 3I72 = (5600l+ 6804p+ 5505)m.

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

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

path for tower building the elliptic curve of embed-

ding degree 72 is:

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

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

ing of extension of finite field of embedding degree

72. We show that there are two efficients construc-

tions of these extensions of degree 72. We show that

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

most of the operations in Fp4,Fp6,Fp8,Fp9,Fp12 ,

Fp18 ,Fp24 ,Fp36 and Fp72 . By using this tower build-

ing technique, we also improve the arithmetic of Fp72

in order to speed up miller algorithm by reducing the

cost of multiplication, 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] ISMAIL ASSOUJAA, SIHAM EZZOUAK,

HAKIMA MOUANIS. Compression Point

in Field of Characteristic 3. Springer, I4CS

2022, CCIS 1747, pp. 104–111, 2022.

https://doi.org/10.1007/978-3-031-23201-5_7.

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

rina Ionica. A study of pairing computation for

curves with embedding degree 15. DBLP vol-

ume 2009.

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

PAIRING-BASED CRYPTOGRAPHY. Chap-

man and Hall/CRC CRYPTOGRAPHY AND

NETWORK SECURITY, 2018.

[8] 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

[9] 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.

[10] 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.

[11] 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.

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

ELLIPTIC CURVE CRYPTOGRAPHY FOR

6. Conclusion

WSEAS TRANSACTIONS on COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

137

Volume 10, 2022

EMBEDDED SYSTEMS. International Jour-

nal of Computer Science & Information Tech-

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

[13] 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.

[14] ISMAIL ASSOUJAA, SIHAM EZZOUAK,

HAKIMA MOUANIS. Tower Building

Technique on Elliptic Curve with Em-

bedding Degree 36. WSEAS TRANS-

ACTIONS ON COMPUTERS. DOI:

10.37394/23205.2022.21.39.

[15] 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.

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

ily of Pairing-Friendly elliptic curves. May 21,

2018.

[17] Michael Scott, On the Efficient Implementa-

tion of Pairing-Based Protocols, in cryptogra-

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

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

Curves, Second Edition, 2000.

[19] 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.

[20] Augusto Jun Devegili1, Colm Eigeartaigh,

Michael Scott, and Ricardo Dahab, Multiplica-

tion and Squaring on Pairing-Friendly Fields,

2006.

[21] Razvan Barbulescu, Sylvain Duquesne, Updat-

ing Key Size Estimations for Pairings, J Cryp-

tol. 2019.

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 COMPUTER RESEARCH

DOI: 10.37394/232018.2022.10.17

Ismail Assoujaa, Siham Ezzouak, Hakima Mouanis

E-ISSN: 2415-1521

138

Volume 10, 2022