of Pairings Using Elliptic Nets

(1)

Faster Explicit Formulae and Parallelization for Computation

of Pairings Using Elliptic Nets

Presented by

Hiroshi Onuki

A dissertation submitted in partial fulfillment of the requirements for the degree of

Doctor of Philosophy in Science

Department of Mathematics and Information Sciences Graduate School of Science and Engineering

Tokyo Metropolitan University

March 2017

(2)

(3)

Abstract

In this paper, we discuss computation of optimal pairings over some pairing- friendly curves and a symmetric pairing over supersingular elliptic curves via elliptic nets.

A standard algorithm for computing pairings is Miller’s algorithm, which inductively constructs a function that has a desired divisor. On the other hand, there is an alternative method for computing pairings. That is based on elliptic nets and proposed by Stange in 2007. Elliptic nets are defined by Stange as a generalization of elliptic divisibility sequences.

In many cases, the method based on elliptic nets is less efficient than Miller’s algorithm. However there are few researches for the method based on elliptic nets, while there are many studies to improve the efficiency of Miller’s algorithm. In particular, it is well-known that using twists of elliptic curves accelerates the calculation of some pairings in Miller s algorithm. We show that using twists of elliptic curves can be also applied to the method based on elliptic nets. We also give the necessary conditions that using twists of elliptic curves is effective.

Furthermore, we focused on the fact that the calculation of elliptic nets is suitable for the parallel computation. We constructed parallel algorithms for computing pairings based on elliptic nets and evaluate the eﬃciency of these algorithms.

We estimated the eﬃciency of our algorithms based on the number of multiplications on a field over which the pairing is defined. We also implemented our algorithms on some pairings. Our estimation and experimental results show that our methods are eﬀective theoretically and on a real machine.

i

(4)

(5)

Acknowledgements

The author would like to express my sincere gratitude to my supervisor Professor Shigenori Uchiyama for his enormous comments and invaluable support throughout my doctoral course. I also thank Dr. Naoki Kanayama and Dr. Tadanori Teruya for advising my research.

iii

(6)

(7)

List of Algorithms

1 Double and DoubleAdd [12] . . . 12

2 Double and DoubleAdd for Extended Block . . . 25

3 Multiplication in Fq² (cost : 3m+ ˜m) . . . . 32

4 Squaring in Fq² with D=−1∈/ F^∗q² (cost : 2m) . . . 32

5 Multiplication in Fq³ (cost : 6m+ 2 ˜m) . . . . 33

6 Squaring in Fq³ with −D∈F^∗q² (cost : 5m+ ˜m+ 2 ˜m^′) . . . . 33

vii

(10)

(11)

List of Tables

5.1 The limit number of processor . . . 26

5.2 Modified or extended . . . 26

5.3 Parallel algorithm for 4 processors (d= 2) . . . 27

5.5 Parallel algorithm for 16 processor (d= 2) . . . 27

5.11 Parallel algorithm for 14 processor (d= 4) . . . 28

6.1 Estimation of costs of multiplications . . . 33

6.2 Cost of Double . . . 35

6.3 Cost of DoubleAdd . . . 35

6.4 Cost of Double by parallel algorithms . . . 36

6.5 Cost of DoubleAdd by parallel algorithms . . . 36

7.1 Environment . . . 40

7.2 Experimental results . . . 41

ix

(12)

(13)

List of Figures

3.1 Block centred on i . . . 11 5.1 Extended block centred oni . . . 24

xi

(14)

(15)

Chapter 1 Introduction

For computing pairings on elliptic curves, Miller’s algorithm [7] has been widely used. But there is an alternative method for computing pairings.

That is based on elliptic nets and proposed by Stange [12] in 2007. Elliptic nets are defined by Stange as a generalization of elliptic divisibility sequences, which were studied by Ward [15]. Stange showed that the Tate pairing can be calculated by using an elliptic net. In 2011, Ogura et al. [8] gave formulae based on elliptic nets for computing some variants of the Tate pairing, including optimal pairings.

Both Miller’s algorithm and the method based on elliptic nets require O(log(m)) field operations for computing a pairing over an m-torsion sub- group, but in many cases, the coeﬃcient hiding behind the O notation of Miller’s algorithm is less than the method based on elliptic nets. Therefore Miller’s algorithm is faster than the method based on elliptic nets. But there are many studies to improve the eﬃciency of Miller’s algorithms, for example [1, 2, 5], on the other hand there are few studies on the method based on elliptic nets. So I thought that there is plenty of scope for improvement on the method based on elliptic nets and studied to improve this method.

For Miller’s algorithm, it is known that there is a method to improve the eﬃciency of calculating an optimal pairing by using a twist of an elliptic curve over which a pairing is defined. Leta:G₂×G₁ →µ_rbe an optimal paring on an elliptic curveE/Fq, whereG1, G2 are subgroups ofE[r] andµr is ther-th torsion subgroup of ¯Fq. To calculatea(Q, P) by using Miller’s algorithm, one needs to calculate a scalar multiplication of Q. This calculation is a main part of Miller’s algorithm. In the method using a twist, one calculate a scalar multiplication of Q^′, that is a point that corresponds to Q in the twits. If one can take a twist in which coordinates of Q^′ is in smaller field than that of Q, the scalar multiplication can be calculated more eﬃciently. Of course, one needs to adjust a gap betweenQand Q^′. But the cost of this adjustment

(16)

2 CHAPTER 1. INTRODUCTION is often much less than a benefit from using the twist.

Our first achievement is an analogy of this method on the method based on elliptic nets. We showed that an elliptic net derived from a twist can be more eﬃciently calculated than that derived from the original curve, and that an optimal pairing can be calculated by using the elliptic net derive derived from a twist. In this paper, we will introduce this and other methods to improve the eﬃciency of the method based on elliptic nets. Our new method are as follows:

• The method using a twist (for optimal pairings)

• Modified elliptic nets (for optimal pairings and asymmetric parings over supersingular curves)

• Parallel computation for elliptic nets

• The extended block (for parallel computation)

The rest of this paper is organized as follows. In Chapter 2, we will give a brief overview of pairings and Miller’s algorithm. In Chapter 3, we will recall the definition of an elliptic net and introduce formulae for computing a pairing by using an elliptic net. In Chapter 4, we will describe the method using a twist and modified elliptic nets. In Chapter 5, we give parallel algorithm for computing an elliptic net. Our parallel algorithms are oriented toward pairing computation. We will also propose the extended block method for parallel computation. In Chapter 6, we will estimate the eﬃciency of our methods defined in Chapter 4 and 5. In Chapter 7, we will give an experimental results for some pairings. Finally, we conclude this paper in Chapter 8.

(17)

Chapter 2 Pairings

In this chapter, we recall definitions and basic properties of pairings over elliptic curves. We also give the definition and some properties of the Miller function, which was introduced by Miller [7] for calculating pairings.

Throughout this paper, we use the following notation.

O the point at infinity of an elliptic curve µ_n the set of n-th roots of unity

G[n] n-torsion subgroup of G

2.1 The Embedding Degree

In this paper, a pairing is a map from two additive groups to a multiplicative cyclic group G₁ ×G₂ → G_T. If G₁ = G₂, we call the pairing symmetric, otherwise asymmetric. In particular, we consider pairings over an elliptic curve defined over a finite field, which are maps from subgroups of torsion points on the elliptic curve to the subgroup of roots of unity in an extension of the field of definition. Therefore we need to find a extension field in which the torsion points can be defined. To do this, it is convenient to define the embedding degree.

Definition 2.1.1. Letqbe a prime power,r an integer prime toq. Then the smallest positive integer k that satisfies r |q^k−1 is called the embedding degree of r with respect to q.

In other words, the embedding degree is the smallest integer k such that Fq^k contains the set of r-th roots of unity µ_r.

The following two propositions state the relation between the embedding degree and a torsion subgroup of an elliptic curve defined over a finite field.

(18)

4 CHAPTER 2. PAIRINGS Proposition 2.1.2 ([11, Corollary III.8.1.1]). Let E be an elliptic curve defined over a field K and m∈N. Then

E[m]⊆E(K)⇒µ_m ⊆K.

Proposition 2.1.3 ([14, Proposition 5.5]). Let E be an elliptic curve define over a finite field Fq, r a prime which is prime to q and k the embedding degree of r with respect to q. If r|#E(Fq) and k >1 then k is the smallest integer such that E[r]⊆E(Fq^k).

2.2 The Tate Pairing

The following theorem claims the existence of the Tate pairing.

Theorem 2.2.1 ([14, Theorem 11.8]). Let E be an elliptic curve defined over a finite field Fq and n an integer such that n | q−1. Then there are non-degenerate bilinear pairings:

⟨· , ·⟩n:E(Fq)[n]×E(Fq)/nE(Fq)→F^∗q/F^∗qⁿ, τ_n :E(Fq)[n]×E(Fq)/nE(Fq)→µ_n, where for P ∈E(Fq)[n], Q∈E(Fq),

τ_n(P, QmodnE(Fq)) =⟨P, QmodnE(Fq)⟩ⁿ^q⁻ⁿ¹.

Definition 2.2.2. We call⟨·,·⟩n of Theorem 2.2.1 the Tate pairing andτ_n the reduced Tate pairing.

We denote⟨P, QmodnE(Fq)⟩nandτn(P, QmodnE(Fq)) by⟨P, Q⟩nand τ_n(P, Q) for short, respectively.

2.3 The Miller Function

The Miller function is a rational function on an elliptic curve which was defined by Miller [7] to calculate the Weil pairing. This function can be used to calculate the Tate pairing. And variants of the Tate pairing are defined by using this function.

First, for describing the definition of the Miller function, we recall the notation for divisors.

(19)

2.3. THE MILLER FUNCTION 5 Definition 2.3.1. Let E be an elliptic curve, D = ∑

Pn_P(P) a divisor on E and f a non-zero rational function onE. Then the degree of D is defined by deg(D) = ∑

P n_P. The support of D is defined by supp(D) = {P ∈ E | n_P ̸= 0}. The divisor of f is define by div(f) =∑

P ord_P(f)(P).

Furthermore, if supp(D)∩ supp(div(f)) = ∅, then we define f(D) =

∏f(P)ⁿ^P.

Proposition 2.3.2 ([11, Corolloary III.3.5]). Let E be an elliptic curve and D=∑

PnP(P)a divisor on E. Then there is a rational function on E such that div(f) = D if and only if deg(D) = 0 and ∑

P[n_P]P =O.

For calculating pairings, we need a rational function whose divisor is n((P)−(O)), where P ∈E[n]. Miller [7] constructed such a function induc- tively by using the Miller functionf_m,P whose divisor ism(P)−([m]P)−(m− 1)O for m < n. Proposition 2.3.2 assures us that f_m,P exists. Furthermore f_m,P is unique up to multiplication by a non-zero constant. To resolve an ambiguity from multiplication by a nonzero constant, we define a normalized function in a certain sense.

Definition 2.3.3. Let E be an elliptic curve, P ∈ E and u_P a uniformizer at P. A non-zero function f on an elliptic curve is normalized in u_P if u⁻_P^ord^P^(f⁾f(P) = 1.

From now on, we assume all functions on an elliptic curve are normalized in a same uniformizer. For example, when the elliptic curve has Weierstrass form we may take uniformizer at O u_O=−y/x.

Now, we explain how to construct the Miller function.

Definition 2.3.4. Let E be an elliptic curve and P, Q ∈ E. L_P,Q is the function such that LP,Q = 0 is the equation of the line passing through P and Q or the equation of the tangent line to the curve if P =Q.

Definition 2.3.5. LetE be an elliptic curve and P, Q∈E, then define gP,Q:= L_P,Q

L_P_+Q,₋_(P_+Q) .

Lemma 2.3.6 ([7]).

div(L_P,Q) = (P) + (Q) + (−(P +Q))−3(O), (2.1) div(g_P,Q) = (P) + (Q)−(P +Q)−(O). (2.2)

(20)

6 CHAPTER 2. PAIRINGS Definition 2.3.7. Let E be an elliptic curve and P ∈ E. Define f_0,P = f_1,P = 1. Inductively, for n >0, define

f_n+1,P :=f_n,Pg_P,[n]P, (2.3)

f₋_n,P := 1

f_n,Pg_P,[₋_n]P. (2.4)

Lemma 2.3.8 ([7]).

div(f_n,P) = n(P) + ([n]P)−(n−1)(O), (2.5)

fm+n = fm,Pfn,Pg[m]P,[n]P, (2.6)

fmn = f_m,Pⁿ f_n,[m]P = f_n,P^m f_m,[m]P. (2.7) It is known that one can represent the Tate pairing by the Miller function.

Theorem 2.3.9 ([14, Proof of Theorem 11.8]). Let E be an elliptic curve defined over a finite field Fq, n an integer such that n|q−1 and π the q-th power Frobenius map on E. For P ∈E(Fq)[n], Q∈E(Fq)/nE(Fq), let D be a divisor of degree 0 such that sum(D) =Q and P, O ̸∈supp(D). Then

⟨P, Q⟩n = f_n,P(D) modF^∗_qⁿ, (2.8) τn(P, Q) = fn,P(D)^q−1ⁿ . (2.9) If the Miller function has its coeﬃcients in the field in which coeﬃcients of P and Q are, the Tate pairing can be represented more simply.

Proposition 2.3.10 ([11, Proposition XI.9.2]). In Theorem 2.3.9, assume that P ̸= Q and the Miller function f_n,P ∈ K(E), where K is a subfield of Fq which contains coeﬃcients of P and Q. Then

⟨P, Q⟩n=f_n,P(Q) modF^∗qⁿ. (2.10)

2.4 Optimal Pairings

Optimal pairings are variants of the Tate pairing and were proposed by Ver- cauteren [13]. These can be computed more eﬃciently than the Tate pairing.

In this subsection, let E be an elliptic curve over a finite field Fq, π the q-th power Frobenius map on E, r a prime that is prime to q and that divides #E(Fq), and k the embedding degree of r with respect to q. And we assume k ≥ 2. Then, from Proposition 2.1.3, E[r] ⊆ E(Fq^k) and it is well-known that as a linear map on E[r], eigenvalues of π are 1 and q. We defineG₁ =E[r]∩ker(π−[1]) andG₂ =E[r]∩ker(π−[q]).

Let f be the Miller function. And we assume these are normalized at O in a uniformizer which does not have zero or pole at points inG₁ except O.

(21)

2.5. SYMMETRIC PAIRINGS 7 Theorem 2.4.1 ([13]). λ=mr with r∤m and write λ =∑_l

i=0c_iqⁱ then

a_[c₀_,...,c_l_]:G₂×G₁ →µ_r, (Q, P)7→

( _l

∏

i=0

f_c_i_,Q(P)^qⁱ

l−1

∏

i=0

g_[s_i_]Q,[c_i_qⁱ_]Q(P) )^qk−1_r

with s_i =∑l

j=ic_jq^j, defines a bilinear pairing. Furthermore, if mkp^k⁻¹ ̸≡ q^k−1

r

∑l i=0

ic_iqⁱ⁻¹ modr.

then the pairing is non-degenerate.

Definition 2.4.2. The pairing in Theorem 2.4.1 is called optimal if it is non-degenerate and max_i{log₂c_i} ≤ ^log_φ(k)²^r+ log₂k, where φis Euler’s totient function.

Vercauteren constructed some examples of optimal pairings. For the de- tial, see [13].

2.5 Symmetric Pairings

In this section, we define a symmetric pairing over a supersingular elliptic curve.

At the beginning, we recall the definition and properties of a supersingular elliptic curve.

Definition 2.5.1. Let K be a field of characteristic p >0 and E an elliptic curve defined over K. We say that E is supersingular if

E[p^r] ={O} for all r ≥1.

Proposition 2.5.2([14, Proposition 4.31]).LetEbe an elliptic curve defined over a finite field K of characteristic p. Then E is supersingular if and only if #E(K)≡1 mod p.

Corollary 2.5.3 ([14, Corollary 4.32]). Let p ≥5 be an prime number and E an elliptic curve defined over Fp. Then Then E is supersingular if and only if #E(Fp) =p+ 1.

Let p ≥ 5 be a prime number, E a supersingular elliptic curve defined overFp and r a prime number such thatr |E(Fp). Since p≡ −1 modr, the

(22)

8 CHAPTER 2. PAIRINGS embedding degree ofr with respect topis 2. Therefore, from Theorem 2.2.1, there is the modified Tate pairing

τ_r :E(Fp²)[r]×E(Fp²)/rE(Fp²)→µ_r.

Now we construct a symmetric pairing from the above pairing. The j- invariant of E is 0 if p ≡2 mod 3 or 1728 if p≡ 3 mod 4 (see [11, Theorem V.4.1]). In the both cases, E has automorphisms which are not [±1]. We call these automorphisms distortion maps. The Weierstrass equation of E and its distortion maps can be written as follows.

• p≡2 mod 3

– j-invariant : 0

– Weierstrass equation : E :y² =x³+B, B ∈Fp

– Distortion maps : {±δ,±δ²}, δ: (x, y)7→(ωx, y) where ω∈Fp² is a primitive cube root of unity.

• p≡3 mod 4

– j-invariant : 1728

– Weierstrass equation : E :y² =x³+Ax, A∈Fp

– Distortion maps : {±δ}, δ: (x, y)7→(−x, iy) where i∈Fp² is a square root of −1.

Notice that distortion maps cannot be defined over Fp because ω /∈Fp if p≡2 mod 3 and i /∈Fp if p≡3 mod 4.

It is well-known that the following map defines a symmetric pairing over E(Fp)[r].

Fact 2.5.4. Let δ be a distortion map onE. Then the symmetric paring er

overE(Fp)[r] defined in the following is non-degenerate and bilinear:

e_r :E(Fp)[r]×E(Fp)[r]→µ_r, (P, Q)7→τ_r(P, δ(Q)).

(23)

Chapter 3 Elliptic Nets

Elliptic nets are generalization of elliptic divisibility sequences and were defined by Stange [12]. She proposed an alternative method for computing the Tate pairing based on them.

In this chapter, we give a brief review of pairing computation based on elliptic nets.

3.1 The Definition and Properties

In this section, we recall the definition of elliptic nets and their properties from [12].

Definition 3.1.1. Let A be a finitely generated free abelian group, R an integral domain. An elliptic net is a map W : A → R satisfying the following recurrence relation for p, q, r, s∈A:

W(p+q+s)W(p−q)W(r+s)W(r) +W(q+r+s)W(q−r)W(p+s)W(p)

+W(r+p+s)W(r−q)W(q+s)W(q) = 0. (3.1) Stange constructed an elliptic net associated to an elliptic curve E over K which is a subfield ofCor a finite field and P1, . . . , Pn which are points of E with P_i ̸=O for all iand P_i ̸=±P_j for alli̸=j. This elliptic net is a map Zⁿ→K(P₁, . . . , P_n), whereK(P₁, . . . , P_n) is the field generated by adjoining the coordinates of P1, . . . , Pn to K. For the details of the construction, see [12]. We denote an elliptic net associated to an elliptic curveE and its points P₁, . . . , P_n by W_P₁_,...,P_n_;E.

One important property of elliptic nets is their relation with division polynomials.

(24)

10 CHAPTER 3. ELLIPTIC NETS Proposition 3.1.2 ([12]). Let E be an elliptic curve over a subfield of C or a finite field and P₁, . . . , P_n∈E. Let ψ_m be the m-th division polynomial of E. Then

W_P₁_,...,P_n_;E(m,0, . . . ,0) =W_P₁_;E(m) = ψ_m(P₁). (3.2) In particular, forP = (x, y)∈E, [m]P = (x_m, y_m)is represented as follows:

x_m = xW_P_;E(m)²−W_P_;E(m+ 1)W_P_;E(m−1)

W_P_;E(m)² , (3.3)

y_m = WP;E(m+ 2)WP;E(m−1)²−WP;E(m−2)WP;E(m+ 1)²

4yW_P;E(m)³ .(3.4)

3.2 Pairings via Elliptic Nets

Stange showed that the Tate pairing can be represented by an elliptic net.

And Ogura et al. [8] proposed formulae for variants of the Tate pairing using an elliptic net. Here we introduce formulae for the Tate pairing and the pairing defined in Theorem 2.4.1.

Theorem 3.2.1 ([12]). Let E be an elliptic net defined over a finite field Fq and m a positive integer such that µ_m ⊆ Fq. For P ∈ E(Fq)[m] and Q∈E(Fq) with P ̸=±Q,

⟨P, P⟩m = W_P_;E(m+ 2)W_P_;E(1)

W_P_;E(m+ 1)W_P_;E(2) modF^∗q^m, (3.5)

⟨P, Q⟩m = W_P,Q;E(m+ 1,1)W_P,Q;E(1,0)

W_P,Q;E(m+ 1,0)W_P,Q;E(1,1) modF^∗q^m. (3.6) Theorem 3.2.2 ([8]). Let a_[c₀_,...,c_l_] be a bilinear pairing in Theorem 2.4.1.

Then

a_[c₀_,...,c_l_](Q, P) = ( _l

∏

i=0

(W_Q,P;E(c_i,1) W_Q,P;E(c_i,0)

)qⁱ∏l−1 i=0

g_[₋_s_i+1_]Q,[₋_c_i_qⁱ_]Q(P)⁻¹ )^qk_r⁻¹

.

Remark 3.2.3. From Proposition 3.1.2 and the fact that [c_iqⁱ]Q=πⁱ([c_i]Q), if blocks ofW_Q,P_;E centred onc_i fori= 1, . . . , lare given (a block of an ellptic net will be defined in the next section), g_[s_i_]Q,[c_i_qⁱ_]Q(P) in Theorem 3.2.2 can be computed by operations of Fq and the Frobenius map on Fq and the number of these operations does not depend onq or r, c_i.

(25)

3.3. CALCULATING ELLIPTIC NETS 11

3.3 Calculating Elliptic Nets

In the following, we state the method to compute an elliptic net W_P,Q;E proposed by Stange [12].

First we define a block of an elliptic net.

Definition 3.3.1. For an elliptic net W :Z² → R, a block of W centred on i is a set

{W(i−3,0), . . . , W(i+ 4,0), W(i−1,1), W(i,1), W(i+ 1,1)}. (See Figure 3.1.)

Figure 3.1: Block centred on i

The following proposition allows us to compute a block of an elliptic net inductively.

Proposition 3.3.2 ([12]). Let W : Z² → R be an elliptic net such that W(0,1) = W(1,0) = 1 and W(2,0), W(1,1), W(−1,1), W(2,−1) ∈ R^∗. Then

W(2i−1,0) =W(i+ 1,0)W(i−1,0)³

−W(i−2,0)W(i,0)³ , (3.7)

W(2i,0) = (W(i,0)W(i+ 2,0)W(i−1,0)²

−W(i,0)W(i−2,0)W(i+ 1,0)²)/W(2,0) , (3.8) W(2i−1,1) = (W(i+ 1,1)W(i−1,1)W(i−1,0)²

−W(i,0)W(i−2,0)W(i,1)²)/W(1,1), (3.9) W(2i,1) =W(i−1,1)W(i+ 1,1)W(i,0)²

−W(i−1,0)W(i+ 1,0)W(i,1)² , (3.10) W(2i+ 1,1) = (W(i−1,1)W(i+ 1,1)W(i+ 1,0)²

−W(i,0)W(i+ 2,0)W(i,1)²)/W(−1,1) , (3.11) W(2i+ 2,1) = (W(i+ 1,0)W(i+ 3,0)W(i,1)²

−W(i−1,1)W(i+ 1,1)W(i+ 2,0)²)/W(2,−1). (3.12)

(26)

12 CHAPTER 3. ELLIPTIC NETS Given a block centred oni, we can compute a block centred on 2ior 2i+1 by using this proposition. We call these algorithms Double and DoubleAdd respectively. For the detail of algorithms see Algorithm 1.

Algorithm 1Double and DoubleAdd [12]

Require: Block V centred at k of an elliptic net satisfying W(1,0) = W(0,1) = 1, values A = W(2,0)⁻¹, E = W(−1,1)⁻¹, F = W(2,−1)⁻¹, G=W(1,1)⁻¹ and booleanadd

Ensure: Block centred at 2k if add== 0 and centred at 2k+ 1 if add== 1

1: S₀ ←V[1,1]²

2: P₀ ←V[1,0]V[1,2]

3: for i= 0 to 5do

4: S[i]←V[0, i+ 1]²

5: P[i]←V[0, i]V[0, i+ 2]

6: end for

7: if add== 0 then

8: for i= 0 to 3 do

9: V[0,2i]←S[i]P[i+ 1]−S[i+ 1]P[i]

10: V[0,2i+ 1]←(S[i]P[i+ 2]−S[i+ 2]P[i])A

11: end for

12: V[1,0]←(P0S[1]−S0P[1])G

13: V[1,1]←P₀S[2]−S₀P[2]

14: V[1,2]←(P₀S[3]−S₀P[3])E

15: else

16: for i= 0 to 3 do

17: V[0,2i]←(S[i]P[i+ 2]−S[i+ 2]P[i])A

18: V[0,2i+ 1]←S[i+ 1]P[i+ 2]−S[i+ 2]P[i+ 1]

19: end for

20: V[1,0]←P₀S[2]−S₀P[2]

21: V[1,1]←(P0S[3]−S0P[3])E

22: V[1,2]←(S₀S[4]−P₀S[4])F

23: end if

24: return V

If characteristic of Fq is not 2 or 3 and E is given by a Weierstrass form y² =x³+Ax+B, then elements in a block of an elliptic netWP,Q;E centred on 1 and the constants in recurrences of Proposition 3.3.2 are as follows: (See

(27)

3.3. CALCULATING ELLIPTIC NETS 13 [12].)

W(0,0) = 0 , (3.13)

W(1,0) = 1 , (3.14)

W(2,0) = 2y₁ , (3.15)

W(3,0) = 3x⁴₁+ 6Ax²₁+ 12Bx1−A² , (3.16) W(4,0) = 4y₁(x⁶₁+ 5Ax⁴₁+ 20Bx³₁−5A²x²₁−4ABx₁−8B²−A³) ,

(3.17) W(5,0) =W(4,0)W(2,0)³ −W(1,0)W(3,0)³ , (3.18) W(−i,−j) =−W(i, j) for all i, j ∈Z, (3.19)

W(0,1) =W(1,1) = 1 , (3.20)

W(2,1) = 2x₁+x₂−

(y2−y1

x₂−x₁ )2

, (3.21)

W(−1,1) =x₁−x₂ , (3.22)

W(2,−1) = (y₂+y₁)²−(2x₁ +x₂)(x₁−x₂)² . (3.23)

(28)

(29)

Chapter 4 Our Improvement

In this chapter, we introduce two methods improving the computation of elliptic nets, which are proposed in [9] and [10]. The first is a method using a twist of an elliptic curve. This method is an analogy of a method using a twist for Miller’s algorithm (for the detail of a method for Miller’s algorithm, see [2, 5]). The second is a method that modify an elliptic net by multiplying a certain field element. This modification reduce the cost of DoubleAdd while that of Double is not changed.

4.1 Twists

In this section, we recall the definition of a twist of an elliptic curve and introduce the basic facts related to the twist which we need for our method improving the computation of an elliptic net.

Definition 4.1.1. Let E be an elliptic curve define over a field K. Atwist of E/K is an elliptic curve E^′/K that is isomorphic to E over ¯K. The set of twists ofE/K, modulo K-isomorphism, is denoted by Twist(E/K).

Definition 4.1.2. LetEbe an elliptic curve over a fieldK andE^′/K a twist ofE/K. Thedegree of a twistE^′is min{[L:K]|there is an isomorphism : E^′ →E defined over L}.

Twist(E/K) has a group structure (see [11, X.2]). The following proposition give the structure of Twist(E/K).

Proposition 4.1.3 ([11, Proposition X.5.4]). Let K be a field of character-

(30)

16 CHAPTER 4. OUR IMPROVEMENT istic not 2 or 3, E an elliptic curve over K, and let

n=







2 if j(E)̸= 0,1728 4 if j(E) = 1728 6 if j(E) = 0

Then Twist(E/K) is canonically isomorphic to K^∗/K^∗ⁿ. More precisely, choose a Weierstrass equation

E :y² =x³+Ax+B

for E/K, and let D ∈ K^∗. Then the elliptic curve E_D ∈ Twist(E/K) corresponding to DmodK^∗ⁿ has Weierstrass equation

(i) ED :y² =x³+D²Ax+D³B if j(E)̸= 0,1728,

(ii) E_D :y² =x³+DAx if j(E) = 1728 (so B = 0), (iii) E_D :y² =x³+DB if j(E) = 0 (so A = 0).

Let Fq be a finite field of characteristic not 2 or 3, E an elliptic curve over Fq, n the natural number that is defined in Proposition 4.1.3 and d = gcd(n, q−1). Then F^∗q/F^∗qⁿ is a cyclic group of order d. Let D ∈ F^∗q be a representative for a generator ofF^∗q/F^∗qⁿ and ξ a d-th root ofD. Proposition 4.1.3 says that if we choose a Weierstrass equation

E :y² =x³ +Ax+B, A, B ∈Fq

for E, a complete set of representatives for Twist(E/K) is given by Ei :y² =x³+A/ξ⁴ⁱx+B/ξ⁶ⁱ, i= 0, . . . , d−1.

Notice that for any n, A/ξ⁴ⁱ and B/ξ⁶ⁱ are in Fq because A = 0 in the case ξ⁴ ∈/ Fq and B = 0 in the case ξ⁶ ∈/ Fq. Therefore Ei is defined over Fq. An Fq^d-isomorphism ϕ_i : E_i → E is given by (x, y) 7→ (ξ²ⁱx, ξ³ⁱy). The degree of the twits E_i is [Fq(ξ²ⁱ, ξ³ⁱ) : Fq] = [Fq(ξⁱ) :Fq] = gcd(d, i). Hess et al. [5]

showed that the structure of E(Fq^d) can be expressed by twists Ei(Fq).

Theorem 4.1.4 ([5]). Let Fq be a finite field of characteristic not 2 or 3, E an ordinary elliptic curve over Fq admitting a twist of degree d, and (E_i, ϕ_i) fori= 0, . . . , d−1defined above. Assumegcd(#E(Fq), d) = 1, then the map

d−1

⊕

i=0

E_i(Fq)→E(Fq^d), (P_i)7→

d−1

∑

i=0

ϕ_i(P_i) is an isomorphism.

Remark 4.1.5. Theorem 4.1.4 is also true for not ordinary elliptic curves.

The assumption that E is ordinary is to use commutativity of End(E), but we need only the commutativity for an automorphism on E of order d and q-th power Frobenius map. This follows from d|q−1.

(31)

4.2. TWISTS FOR OPTIMAL PAIRINGS 17

4.2 Twists for Optimal Pairings

In this section, we consider computing optimal pairing on an elliptic curve defined over a finite field via an elliptic net associated to a twist of the elliptic curve. Throughout this section, Fq is a finite field with q elements of characteristic not 2 or 3, E is an elliptic curve defined over Fq, and π is the q-th power Frobenius map on E.

AssumeE has an optimal pairinga_[c₁_,...,c_l_]:G₁×G₂ →µ_r. From Theorem 3.2.2, we can compute the optimal pairing by computing blocks centred onc_i for i= 1, . . . , lof the elliptic net W_Q,P_;E. Therefore, we focus on computing the block centred on c_i.

First, we explain why we use a twist of a curve instead of an original curve. G1 = E[r]∩ker(π −[1]), so G1 ⊆ E(Fq). While from the fact that E[r] is generated by G₁ and G₂ and Proposition 4.1.3, G₂ ⊆ E(Fq^k) and k is the smallest integer satisfying this condition. Our aim is to calculate a block of WQ,P;E centred on ci. From Proposition 3.3.2 and the values of a block centred on 1 (see (3.13)–(3.23)), for any n ∈ Z, W_Q,P;E(n,0) does not depend on the coordinates ofP andW_Q,P_;E(n,1) depends on the coordinates of P and Q. Because P ∈ G1 and Q ∈ G2, all elements in the block of W_Q,P;E are in Fq^k. The cost of computing operations in a large field is more expensive than that of a smaller field. Therefore ifQhas its coordinates in a smaller field, the calculation of the elliptic net would be more eﬃcient. This is achieved by using a twist. We need the following theorem.

Theorem 4.2.1. Let r be a prime which is prime toq and dividing #E(Fq) and k the embedding degree of r with respect to q. Let n be defined in Proposition 4.1.3, d^′ = gcd(q−1, n), d = gcd(k, d^′) and e = k/d. Assume gcd(#E(Fq^e), d) = 1 and k ≥2.

Then E/Fq^e has the twist E^′ of degree d such that

• r|#E^′(Fq^e),

• ϕ(E^′(Fq^e)∩E^′[r]) = E[r]∩ker(π−[q]), where ϕ is the isomorphism : E^′ →E.

Furthermore E^′ is unique up to Fq^e-isomorphism.

Proof. As we stated in 2.4, E[r] = E[r] ∩ ker(π − [1]) ⊕ E[r]∩ ker(π − [q]). Proposition 4.1.3 shows E/Fq^e has a twist of degree d, therefore from Theorem 4.1.4,

E(Fq^k)∼=

d−1

⊕

i=0

E_i(Fq^e)

(32)

18 CHAPTER 4. OUR IMPROVEMENT whereE_i fori= 0, . . . , d−1 are twists of E/Fq^e defined in 4.1. Then there is a twist E_i s.t. ϕ_i(E(Fq^e)) contains a non-zero element ofE[r]∩ker(π−[q]).

We show that such a twist E_i satisfies the conditions of the theorem.

Since E[r]∩ker(π−[q]) is a cyclic group that has a prime order, it follows E[r]∩ker(π−[q]) ⊆ ϕ_i(E_i(Fq^e)). From Theorem 4.1.4, ϕ_i is an inclusion.

Therefore E_i(Fq^e) contains a subgroup of order r. This imply r |#E_i(Fq^e).

Next we showEiis a twist of degreed. Letd0be the degree of the twist. Then ϕ_i can be defined overFqêd⁰. SoE[r]∩ker(π−[q])⊆ϕ_i(E_i(Fqê))⊆E(Fqêd⁰)).

Since E[r]∩ker(π−[1]) = E(Fq)[r], E[r] ⊆ E(Fq^ed⁰)). From Proposition 2.1.2,µr ⊆Fq^ed⁰. This means ed0 divides the embedding degreek =ed. But d₀ ≤d sod₀ =d.

It remains to prove uniqueness. This immediately follows from injectivity of ⊕^di=0⁻¹Ei(Fq)→E(Fq^d).

LetE^′ be the twist in the above theorem and ϕthe isomorphismE^′ →E.

Then ϕ⁻¹(G₁)⊆ E^′(Fq^k) and ϕ⁻¹(G₂)⊆E^′(Fq^e). Therefore elements in the block of the elliptic net of E^′ which are depending only on ϕ⁻¹(Q) are in Fq^e, which is smaller thanFq^k if d≥2. For the relation between the original curve and the twist, see below.

original twist

E(Fq)⊇G1 ←→ ϕ⁻¹(G1)⊆E^′(Fq^k) E(Fq^k)⊇G₂ ←→ ϕ⁻¹(G₂)⊆E^′(Fq^e) W(i,0)∈Fq^k W(i,0)∈Fq^e

W(i,1)∈Fq^k W(i,1)∈Fq^k

From this, it follows that the cost of calculating the elliptic net of E^′ is less than that ofE. What we should do is to express the optimal pairing by using the elliptic net of E^′. We will do this in the next section. We will estimate the eﬃciency of using the twist in 6.2.

The remainder of this section, we summarize the condition that the above twist exists. Let r be a prime that is prime to q. We define integers (k, n, d^′, d, e) as follows:

k : the embedding degree ofr with respect toq, n =







2 if j(E)̸= 0,1728, 4 if j(E) = 1728, 6 if j(E) = 0, d^′ = gcd(q−1, n),

d = gcd(k, d^′), e = k/d.

(33)

4.3. ELLIPTIC NETS OF TWIST CURVES 19 Then we require the following conditions:

r|#E(Fq), (4.1)

k ≥2, (4.2)

d≥2, (4.3)

r ̸= 2 or 3. (4.4)

(4.1) and (4.2) are required for the existence of the pairing defined in Theorem 2.4.1 and that of the twist defined in Theorem 4.2.1. In addition, when (4.3) is satisfied, Fq^e is a proper subfield of Fq^k. Therefore, an elliptic net of E^′ can be computed more easily than that of E. (4.4) is need for computing an optimal pairing by using elliptic net of the twist. This is described in the next section.

4.3 Elliptic Nets of Twist Curves

Our goal in this section is to express the optimal pairing by using the twist defined in Theorem 4.2.1. Let E be an elliptic curve over a finite field Fq

of characteristic not 2 or 3, r a prime that is prime to q and (k, n, d^′, d, e) integers defined in 4.2. Assume E, r, k, n, d^′, d, e satisfy (4.1)–(4.4). Then there is a twist E^′ that satisfy the condition in Theorem 4.2.1. Let ϕ be an isomorphism : E^′ →E andξ a element inFq^k such thatϕ(x, y) = (ξ²x, ξ³y).

First we show a relation between elliptic nets of E and E^′. Proposition 4.3.1. Let P^′, Q^′ ∈E^′ and i∈Z. Then

W_Q′,P^′;E^′(i,0) = ξⁱ²⁻¹W_ϕ(Q′),ϕ(P^′);E(i,0) , (4.5) WQ^′,P^′;E^′(i,1) = ξⁱ²⁻ⁱW_ϕ(Q′),ϕ(P^′);E(i,1) . (4.6) Proof. (3.13)–(3.17) shows that (4.5) holds for 0 ≤ i ≤ 4. For i ≥ 5, using (3.7) and (3.8), we can prove (4.5) by induction on i. Similarly, (3.20) – (3.22) shows that (4.6) holds for −1 ≤ i ≤ 2. (3.10), (3.11) and (4.5) for i ≥ 0 allows us to prove (4.6) by induction on i. Finally (3.19) proves the proposition for i <0.

This proposition allows us to replace fractions of the elliptic net of E in the formula in Theorem 3.2.2 by those of the elliptic net ofE^′ multiplied by a certain power ofξ. However we can replace those by a simpler form of the elliptic net of E^′ because of a so-called final exponentiation.

(34)

20 CHAPTER 4. OUR IMPROVEMENT Theorem 4.3.2. Let P^′, Q^′ ∈E^′ and i∈Z. Then

(W_ϕ(Q′),ϕ(P^′);E(i,1) W_ϕ(Q′),ϕ(P^′);E(i,0)

)^qk⁻¹

r

=W_Q′,P^′;E^′(i,1)^qk^r⁻¹. (4.7) Proof. From Proposition 4.3.1,

(W_ϕ(Q′),ϕ(P^′);E(i,1) W_ϕ(Q′),ϕ(P^′);E(i,0)

)^qk−1_r

= (

ξⁱ⁻¹W_Q′,P^′;E^′(i,1) W_Q′,P^′;E^′(i,0)

)^qk_r⁻¹

. (4.8)

Since q^k−1 = (qê(d⁻¹⁾+· · ·+ 1)(qê−1) and r ∤qê−1,qê−1 divides ^q^k_r⁻¹. From d|q−1,qê(d⁻¹⁾+· · ·+ 1≡0 modd. Sincer ̸= 2 or 3, and d= 2, 3, 4 or 6,d divides (qê(d⁻¹⁾+· · ·+ 1)/r. Therefore (qê−1)d| ^q^k_r⁻¹. From this and the fact W_Q′,P^′;E^′(i,0) and ξ^d ∈ Fqê, it follows that W_Q′,P^′;E^′(i,0)^qk^r⁻¹ = 1 and ξ^qk−1^r = 1. This completes the proof of the theorem.

Remark 4.3.3. Theorem 4.3.2 allow us to replace W_Q,P;E(c_i,1) W_Q,P;E(c_i,0) In Theorem 3.2.2 by W_ϕ−1(Q),ϕ⁻¹(P);E^′(c_i,1). Furthermore we can compute g_[₋_s_i+1_]Q,[₋_c_i_qⁱ_]Q(P) from blocks of W_ϕ−1(Q),ϕ⁻¹(P);E^′ centred on c_i by using Proposition 4.3.1.

4.4 Modified Elliptic Nets

In this section, we define a modified elliptic net for promoting the eﬃciency of computation of Double and DoubleAdd.

Definition 4.4.1. Let W : Z² → R be an elliptic net satisfying W(0,1) = W(1,0) = 1, W(−1,1) ∈ R^∗. Then we define a modified elliptic net W˜ of W as follows:

W˜(s, t) = W(−1,1)^stW(s, t). (4.9) Proposition 4.4.2. A modified elliptic net is an elliptic net.

Proof. It follows from substituting (4.9) into (3.1).

Let E be an elliptic curve and P = (x1, y1), Q = (x2, y2) ∈ E and both are not O, P ̸= ±Q, and 2P −Q ̸= O. In the computation of Double or DoubleAdd, this modification changes W(−1,1) from (x₁−x₂) to 1 and W(1,1) from 1 to (x1−x2). After this modification, the cost of computing Double for a modified elliptic net is the same as that for an original elliptic