# The Pairing Computation on Edwards Curves

Authors: Hongfeng Wu; Liangze Li; Fan Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We propose an elaborate geometry approach to explain the group law on twisted Edwards curves which are seen as the intersection of quadric surfaces in place. Using the geometric
interpretation of the group law, we obtain the Miller function for Tate pairing computation on twisted Edwards curves. Then we present the explicit formulae for pairing computation on twisted Edwards curves. Our formulae for the doubling step are a little faster than that proposed by Arène et al. Finally, to improve the efficiency of pairing computation, we present twists of degrees 4 and 6 on twisted Edwards curves.


---

## Body

## 1. Introduction

Pairing-based cryptography has been one of the most active areas in elliptic curve cryptography since 2000. Some details on this subject can be found in [1, 2]. How to compute pairings efficiently is a bottleneck for implementing pairing-based cryptography. The most efficient method of computing pairings is Miller’s algorithm [3]. Consequently, various improvements were presented in [4–8]. One way to improve the efficiency is to find other models of elliptic curves which can provide more efficient algorithms for pairing computation. Edwards curves were one of the popular models. Edwards curve was discovered by Edwards [9] and was applied in cryptography by Bernstein and Lange [10]. Then twisted Edwards curves which are the generalization of Edwards curves were introduced by Bernstein et al. in [11]. Bernstein and Lange also pointed out several advantages of applying the Edwards curves to cryptography. Pairing computation over Edwards curves was first considered in [12, 13]. In 2009, Arène et al. [4] gave the geometric interpretation of the group law and presented explicit formulae for computing the Tate pairing on twisted Edwards curves. Their formulae are faster than all previously proposed formulas for pairings computation on twisted Edwards curves. Their formulae are even competitive with all published formulae for pairing computation on Weierstrass curves. In particular, if a pairing-friendly curve used in a pairing-based protocol is isomorphic or isogenous to an Edwards curve, all the scalar multiplication appearing in the protocol can be computed efficiently [14].Any elliptic curve defined over a fieldK with characteristic different from 2 is birationally equivalent to an Edwards curve over some extension of K, that is, a curve given by x2+y2=1+dx2y2 with d∉{0,1}. In fact, the twisted Edwards curves can be seen as the intersection of two quadratic surfaces in space. That is to say, the twisted Edwards curves can be given by SWa,d:aX2+Y2-Z2-dW2=0, XY-ZW=0. For general elliptic curves given by intersection of two quadratic surfaces, the geometric interpretation of group law had been discussed by Merriman et al. in [15]. In this paper, we proposed a more detailed geometry approach to explain the group law for the case of twisted Edwards curves which are seen as the intersection of two quadratic surfaces. Using the geometric interpretation of the group law, we obtain the Miller function of Tate pairing computation on twisted Edwards curves. Then we present the explicit formulae for pairing computation on twisted Edwards curves. The doubling step of our formulae is a little faster than that in [4]. Finally, to reduce the cost of evaluating the Miller function on twisted Edwards curve, we employ quadratic, quartic, or sextic twists to the formulae of the Tate pairing computation. The high twists had been sufficiently studied by Costello et al. [16] on Weierstrass curves. As the result given by [17], one elliptic curve and its quartic/sextic twist can not have a rational twisted Edwards model at the same time, so we turn to Weierstrass curves for the high-degree twists of twisted Edwards curves. These twists enable us to reduce the cost of substituting to a half and a third, respectively, in j=1728 case and j=0 case.The remainder of the paper is organized as follows. In Section2, we provide some backgrounds and notations used in this paper. In Section 3, we give a geometry approach to explain the group law on twisted Edwards curves. In Section 4, we present pairing computation on twisted Edwards curves. In Section 5, we employ quartic and sextic twists to the formulae of the Tate pairing computation. In Section 6, we conclude our paper.


## 2. Preliminaries

### 2.1. Tate Pairing

Letp>3 be a prime, and let 𝔽q be a finite field with q=pn. E is an elliptic curve defined over 𝔽q with neutral element denoted by O. r is a prime such that r∣#E(𝔽q). Let k>1 denote the embedding degree with respect to r; that is, k is the smallest positive integer such that r∣qk-1. For any point P∈E(𝔽q)[r], there exists a rational function fP defined over 𝔽q such that div(fP)=r(P)-r(O), which is unique up to a nonzero scalar multiple. The group of rth roots of unity in 𝔽qk is denoted by μr. The reduced Tate pairing is then defined as follows:
(1)Tr:E(𝔽q)[r]×E(𝔽qk)⟶μr:(P,Q)⟼fP(Q)(qk-1)/r.
The rational function fP can be computed in polynomial time by using Miller’s algorithm [3]. Let r=(rl-1,…,r1,r0)2 be the binary representation of r, where rl-1=1. Let gP1,P2∈𝔽q(E) be the rational function satisfying div(gP1,P2)=(P1)+(P2)-(O)-(P1+P2), where P1+P2 denotes the sum of P1 and P2 on E and additions of the form (P1)+(P2) denote formal additions in the divisor group. Miller’s algorithm starts with T=P, and f=1 is written  as in Algorithm 1.Algorithm 1:Miller's algorithm.
Input:  r=∑i=0l-1ri2i, where ri∈{0,1}. P∈E(𝔽q),Q∈E(𝔽qk).
Output:  fr(qk-1)/r(Q)
(1)f←1,T←P
(2)for  i=l-2 down to 0 do do
(3)f←f2·gT,T(Q),T←2T
(4)if  ri=1 then then
(5)f←f·gT,P(Q),T←T+P
(6)end if
(7)end for
(8) returnf(qk-1)/r


### 2.2. Edwards Curves

Forchar(𝔽q)≠2, a twisted Edwards curve defined over 𝔽q is given by
(2)Ea,d:ax2+y2=1+dx2y2,
where a,d are distinct nonzero elements of 𝔽q. The projective closure of Ea,d in ℙ2 is
(3){(X:Y:Z)∈ℙ2:aX2Z2+Y2Z2=Z4+dX2Y2}.
This curve consists of the points (x,y) on the affine curve Ea,d, embedded as usual into ℙ2 by (x,y)↦(x:y:1), and extra points at infinity, that is, points when Z=0. There are exactly two such points, namely, Ω1=(1:0:0) and Ω2=(0:1:0). These points are singular.In fact, the twisted Edwards curve can be seen as the intersection of two quadric surfaces in space. That is, the twisted Edwards curve can be written as(4)SWa,d:aX2+Y2-Z2-dW2=0,XY-ZW=0.More generally, every elliptic curve defined over a fieldK with char(K)≠2 can be written in this normal form over an extension of K. Set O=(0:1:0:1) as the neutral element; the group law on (4) is given by
(5)-(X:Y:W:Z)=(-X:Y:-W:Z),(X1:Y1:W1:Z1)+(X2:Y2:W2:Z2)=(X3:Y3:W3:Z3),
where
(6)X3=(X1Y2+Y1X2)(Z1Z2-dW1W2),Y3=(Y1Y2-aX1X2)(Z1Z2+dW1W2),W3=(Y1Y2-aX1X2)(X1Y2+X2Y1),Z3=(Z1Z2-dW1W2)(Z1Z2+dW1W2).The pointO′=(0:-1:0:1) has order 2. Note that the above formula is unified; that is, it can be applied to both adding two distinct points and doubling a point. The fast arithmetic on twisted Edwards curves given by (4) can be found in [18, 19].We usem and s to denote the costs of multiplication and squaring in the base field 𝔽q, while M and S denote the costs of multiplication and squaring in the extension 𝔽qk.


## 2.1. Tate Pairing

Letp>3 be a prime, and let 𝔽q be a finite field with q=pn. E is an elliptic curve defined over 𝔽q with neutral element denoted by O. r is a prime such that r∣#E(𝔽q). Let k>1 denote the embedding degree with respect to r; that is, k is the smallest positive integer such that r∣qk-1. For any point P∈E(𝔽q)[r], there exists a rational function fP defined over 𝔽q such that div(fP)=r(P)-r(O), which is unique up to a nonzero scalar multiple. The group of rth roots of unity in 𝔽qk is denoted by μr. The reduced Tate pairing is then defined as follows:
(1)Tr:E(𝔽q)[r]×E(𝔽qk)⟶μr:(P,Q)⟼fP(Q)(qk-1)/r.
The rational function fP can be computed in polynomial time by using Miller’s algorithm [3]. Let r=(rl-1,…,r1,r0)2 be the binary representation of r, where rl-1=1. Let gP1,P2∈𝔽q(E) be the rational function satisfying div(gP1,P2)=(P1)+(P2)-(O)-(P1+P2), where P1+P2 denotes the sum of P1 and P2 on E and additions of the form (P1)+(P2) denote formal additions in the divisor group. Miller’s algorithm starts with T=P, and f=1 is written  as in Algorithm 1.Algorithm 1:Miller's algorithm.
Input:  r=∑i=0l-1ri2i, where ri∈{0,1}. P∈E(𝔽q),Q∈E(𝔽qk).
Output:  fr(qk-1)/r(Q)
(1)f←1,T←P
(2)for  i=l-2 down to 0 do do
(3)f←f2·gT,T(Q),T←2T
(4)if  ri=1 then then
(5)f←f·gT,P(Q),T←T+P
(6)end if
(7)end for
(8) returnf(qk-1)/r


## 2.2. Edwards Curves

Forchar(𝔽q)≠2, a twisted Edwards curve defined over 𝔽q is given by
(2)Ea,d:ax2+y2=1+dx2y2,
where a,d are distinct nonzero elements of 𝔽q. The projective closure of Ea,d in ℙ2 is
(3){(X:Y:Z)∈ℙ2:aX2Z2+Y2Z2=Z4+dX2Y2}.
This curve consists of the points (x,y) on the affine curve Ea,d, embedded as usual into ℙ2 by (x,y)↦(x:y:1), and extra points at infinity, that is, points when Z=0. There are exactly two such points, namely, Ω1=(1:0:0) and Ω2=(0:1:0). These points are singular.In fact, the twisted Edwards curve can be seen as the intersection of two quadric surfaces in space. That is, the twisted Edwards curve can be written as(4)SWa,d:aX2+Y2-Z2-dW2=0,XY-ZW=0.More generally, every elliptic curve defined over a fieldK with char(K)≠2 can be written in this normal form over an extension of K. Set O=(0:1:0:1) as the neutral element; the group law on (4) is given by
(5)-(X:Y:W:Z)=(-X:Y:-W:Z),(X1:Y1:W1:Z1)+(X2:Y2:W2:Z2)=(X3:Y3:W3:Z3),
where
(6)X3=(X1Y2+Y1X2)(Z1Z2-dW1W2),Y3=(Y1Y2-aX1X2)(Z1Z2+dW1W2),W3=(Y1Y2-aX1X2)(X1Y2+X2Y1),Z3=(Z1Z2-dW1W2)(Z1Z2+dW1W2).The pointO′=(0:-1:0:1) has order 2. Note that the above formula is unified; that is, it can be applied to both adding two distinct points and doubling a point. The fast arithmetic on twisted Edwards curves given by (4) can be found in [18, 19].We usem and s to denote the costs of multiplication and squaring in the base field 𝔽q, while M and S denote the costs of multiplication and squaring in the extension 𝔽qk.


## 3. Geometric Interpretation of the Group Law on Twisted Edwards Curves

The aim of this section is to give the elaborate geometric interpretation of the group law on twisted Edwards curves which are seen as the intersection of two quadric surfaces in space. We consider projective planes which are given by homogeneous projective equationsΠ=0. In this paper, we still use the symbol Π to denote projective planes. In fact, any plane Π intersects SWa,d at exactly four points. Although these planes are not functions on SWa,d, their divisors can be well defined as
(7)div(Π)=∑R∈Π∩SWa,dnR(R),
where nR is the intersection multiplicity of Π and SWa,d at R. Then the quotient of two projective planes is a well-defined function which gives principal divisor. As we will see, this divisor leads to the geometric interpretation of the group law.When saying planeΠ passes three points P1,P2, and P3 (not necessary distinct), we means that Π exactly satisfies div(Π)≥(P1)+(P2)+(P3). In fact, by Riemann-Roch theorem or by explicit discussion on multiplicity, one can prove that there exists a unique plane which satisfies the above inequality. So we may denote this plane by ΠP1,P2,P3 from now on.


### 3.1. Group Law over the Twisted Edwards Curves

Abel-Jacobi theorem connects the group law with principal divisor. And we can get the lemma below.Lemma 1.
For twist Edwards curveSWa,d with neutral element O=(0:1:0:1), let O′=(0:-1:0:1). Then 4 points (not necessary distinct) P1, P2, P3, and P4 satisfy P1+P2+P3+P4=O′ if and only if there is a plane Π with div(Π)=(P1)+(P2)+(P3)+(P4).Proof.
Firstly, it is an easy calculation to get thatdiv(X-W)=3(O)+(O′).
Then the “if” part follows directly: ifdiv(Π)=(P1)+(P2)+(P3)+(P4), the principal divisor div(Π/(X-W))=(P1)+(P2)+(P3)+(P4)-3(O)-(O′) is translated into equation P1+P2+P3+P4=O′ by the Abel-Jacobi Theorem.
For the “only if” part, suppose thatP1+P2+P3+P4=O′. Consider the plane ΠP1,P2,P3; we can assume that div(ΠP1,P2,P3)=(P1)+(P2)+(P3)+(P4′), so it derives P1+P2+P3+P4′=O′ from the “if” part. Then we get P4=P4′; that is, div(ΠP1,P2,P3)=(P1)+(P2)+(P3)+(P4).By this lemma, we can easily construct planes to give the group law. The fourth intersection ofΠP1,O,O′ and the curve is -P1, that is, the negative point of P1. The fourth intersection of ΠP1,P2,O′ and the curve is -P1-P2, and its negative point gives P1+P2. Actually, this geometric interpretation is parallel with the tangent and chord law for the cubic plane curves.The neutral element we chose here is the same with that of [11], so we can claim that our explicit formulae for negative point, point addition, and point doubling are equivalent with which of [11].


## 3.1. Group Law over the Twisted Edwards Curves

Abel-Jacobi theorem connects the group law with principal divisor. And we can get the lemma below.Lemma 1.
For twist Edwards curveSWa,d with neutral element O=(0:1:0:1), let O′=(0:-1:0:1). Then 4 points (not necessary distinct) P1, P2, P3, and P4 satisfy P1+P2+P3+P4=O′ if and only if there is a plane Π with div(Π)=(P1)+(P2)+(P3)+(P4).Proof.
Firstly, it is an easy calculation to get thatdiv(X-W)=3(O)+(O′).
Then the “if” part follows directly: ifdiv(Π)=(P1)+(P2)+(P3)+(P4), the principal divisor div(Π/(X-W))=(P1)+(P2)+(P3)+(P4)-3(O)-(O′) is translated into equation P1+P2+P3+P4=O′ by the Abel-Jacobi Theorem.
For the “only if” part, suppose thatP1+P2+P3+P4=O′. Consider the plane ΠP1,P2,P3; we can assume that div(ΠP1,P2,P3)=(P1)+(P2)+(P3)+(P4′), so it derives P1+P2+P3+P4′=O′ from the “if” part. Then we get P4=P4′; that is, div(ΠP1,P2,P3)=(P1)+(P2)+(P3)+(P4).By this lemma, we can easily construct planes to give the group law. The fourth intersection ofΠP1,O,O′ and the curve is -P1, that is, the negative point of P1. The fourth intersection of ΠP1,P2,O′ and the curve is -P1-P2, and its negative point gives P1+P2. Actually, this geometric interpretation is parallel with the tangent and chord law for the cubic plane curves.The neutral element we chose here is the same with that of [11], so we can claim that our explicit formulae for negative point, point addition, and point doubling are equivalent with which of [11].


## 4. Miller Function overSWa,d

### 4.1. Construction of Miller Function

In this section we construct the Miller function overSWa,d. Let P1 and P2 be two points on SWa,d; by Lemma 1, we can get
(8)div(ΠP1,P2,O′)=(P1)+(P2)+(O′)+(-P1-P2),div(ΠP1+P2,O,O′)=(P1+P2)+(O)+(O′)+(-P1-P2).
Thus,
(9)div(ΠP1,P2,O′ΠP1+P2,O,O′)=(P1)+(P2)-(P1+P2)-(O).
So for addition steps, the Miller function gT,P over SWa,d can be given by setting P1=T, P2=P:
(10)gT,P=ΠT,P,O′ΠT+P,O,O′.
For doubling steps, we set P1=P2=T, and the Miller function gT,T over SWa,d is given as
(11)gT,T=ΠT,T,O′Π2T,O,O′.Then the remaining work is to compute the equation of these planes. The planes we use are of the formCXX+CY(Y+Z)+CWW=0, because they always pass through O′=(0:-1:0:1). Thus we only need to compute CX, CY, and CW. To get a unified description, we use P1, P2 for both addition and doubling steps and consider P1≠P2 and P1=P2, respectively, when necessary. Assume that P1=(X1:Y1:W1:Z1), P2=(X2:Y2:W2:Z2), and P3=P1+P2=(X3:Y3:W3:Z3).


### 4.2. Equation ofΠP1,P2,O′ with P1≠P2

In the case thatP1, P2, and O′ are pairwise distinct points on SWa,d, by solving linear equations, we get the coefficients of the plane ΠP1,P2,O′ as follows:
(12)CX=W2(Z1+Y1)-W1(Z2+Y2),CY=X2W1-X1W2,CW=X1(Y2+Z2)-X2(Z1+Y1).


### 4.3. Equation ofΠP1,P2,O′ with P1=P2

Suppose thatP1=P2≠O′. The tangent line to SWa,d at P1 is the intersection of the tangent planes to aX2+Y2-Z2-dW2=0 and XY-ZW=0 at P1. The tangent plane to aX2+Y2-Z2-dW2=0 at P1 is aX1X+Y1Y-Z1Z-dW1W=0. The tangent plane to XY-ZW=0 at P1 is Y1X+X1Y-W1Z-Z1W=0. Then ΠP1,P1,O′ is of the form:
(13)λ(aX1X+Y1Y-Z1Z-dW1W)+μ(Y1X+X1Y-W1Z-Z1W)=0.
Note that O′∈ΠP1,P1,O′; that is, λ(Y1+Z1)+μ(X1+W1)=0. One can verify that λ=-X1, μ=Z1 satisfy the equation. Hence, the equation of ΠP1,P1,O′ is
(14)-X1(aX1X+Y1Y-Z1Z-dW1W)+Z1(Y1X+X1Y-W1Z-Z1W)=0.Then we can get the coefficients ofΠP1,P1,O′ as follows:
(15)CX=Y1Z1-aX12,CY=X1Z1-X1Y1,CW=dX1W1-Z12.


### 4.4. Equation ofΠP3,O,O′

The planeΠP3,O,O′ can be regarded as a special case of ΠP1,P2,O′. For P3≠O, O′, we have
(16)CX=W3,CY=0,CW=-X3.
Thus, we have ΠP3,O,O′:W3X-X3W=0.


## 4.1. Construction of Miller Function

In this section we construct the Miller function overSWa,d. Let P1 and P2 be two points on SWa,d; by Lemma 1, we can get
(8)div(ΠP1,P2,O′)=(P1)+(P2)+(O′)+(-P1-P2),div(ΠP1+P2,O,O′)=(P1+P2)+(O)+(O′)+(-P1-P2).
Thus,
(9)div(ΠP1,P2,O′ΠP1+P2,O,O′)=(P1)+(P2)-(P1+P2)-(O).
So for addition steps, the Miller function gT,P over SWa,d can be given by setting P1=T, P2=P:
(10)gT,P=ΠT,P,O′ΠT+P,O,O′.
For doubling steps, we set P1=P2=T, and the Miller function gT,T over SWa,d is given as
(11)gT,T=ΠT,T,O′Π2T,O,O′.Then the remaining work is to compute the equation of these planes. The planes we use are of the formCXX+CY(Y+Z)+CWW=0, because they always pass through O′=(0:-1:0:1). Thus we only need to compute CX, CY, and CW. To get a unified description, we use P1, P2 for both addition and doubling steps and consider P1≠P2 and P1=P2, respectively, when necessary. Assume that P1=(X1:Y1:W1:Z1), P2=(X2:Y2:W2:Z2), and P3=P1+P2=(X3:Y3:W3:Z3).


## 4.2. Equation ofΠP1,P2,O′ with P1≠P2

In the case thatP1, P2, and O′ are pairwise distinct points on SWa,d, by solving linear equations, we get the coefficients of the plane ΠP1,P2,O′ as follows:
(12)CX=W2(Z1+Y1)-W1(Z2+Y2),CY=X2W1-X1W2,CW=X1(Y2+Z2)-X2(Z1+Y1).


## 4.3. Equation ofΠP1,P2,O′ with P1=P2

Suppose thatP1=P2≠O′. The tangent line to SWa,d at P1 is the intersection of the tangent planes to aX2+Y2-Z2-dW2=0 and XY-ZW=0 at P1. The tangent plane to aX2+Y2-Z2-dW2=0 at P1 is aX1X+Y1Y-Z1Z-dW1W=0. The tangent plane to XY-ZW=0 at P1 is Y1X+X1Y-W1Z-Z1W=0. Then ΠP1,P1,O′ is of the form:
(13)λ(aX1X+Y1Y-Z1Z-dW1W)+μ(Y1X+X1Y-W1Z-Z1W)=0.
Note that O′∈ΠP1,P1,O′; that is, λ(Y1+Z1)+μ(X1+W1)=0. One can verify that λ=-X1, μ=Z1 satisfy the equation. Hence, the equation of ΠP1,P1,O′ is
(14)-X1(aX1X+Y1Y-Z1Z-dW1W)+Z1(Y1X+X1Y-W1Z-Z1W)=0.Then we can get the coefficients ofΠP1,P1,O′ as follows:
(15)CX=Y1Z1-aX12,CY=X1Z1-X1Y1,CW=dX1W1-Z12.


## 4.4. Equation ofΠP3,O,O′

The planeΠP3,O,O′ can be regarded as a special case of ΠP1,P2,O′. For P3≠O, O′, we have
(16)CX=W3,CY=0,CW=-X3.
Thus, we have ΠP3,O,O′:W3X-X3W=0.


## 5. Pairing Computation

In this section, we analysis steps in Miller’s algorithm explicitly. For an addition step or doubling step, as is shown in Algorithm1, each addition or doubling step consists of three parts: computing the point T+P or 2T and the function gT,P or gT,T, evaluating gT,P or gT,P at Q, and then updating the variable f by f←f·gT,P(Q) or by f←f2·gT,T(Q).The updating part, as operation in𝔽qk, costs 1M for addition step and 1M+1S for doubling step. It is usually the main cost but with little room for optimization in one step. For the evaluating part, some standard methods such as denominator elimination and subfield simplification can be used, as we introduce below.We assume that embedding degreek is even. Let δ be a generator of 𝔽qk over 𝔽qk/2 with δ2∈𝔽qk/2. Suppose that Q′=(X0:Y0:W0:Z0)∈SWaδ-2,dδ-2(𝔽qk/2); we can see that Q=(X0:δY0:W0:δZ0)∈SWa,d(𝔽qk). If P3=P1+P2≠O, O′, for evaluation of gP1,P2(Q), we have
(17)gP1,P2(Q)=ΠP1,P2,O′(Q)ΠP3,O,O′(Q)=CXX0+CYδ(Y0+Z0)+CWW0W3X0-X3W0=CX(X0/(Y0+Z0))+CYδ+CW(W0/(Y0+Z0))(W3X0-X3W0)/(Y0+Z0)∈(CXθ+CYδ+CWη)𝔽qk/2*,
where θ=X0/(Y0+Z0) and η=W0/(Y0+Z0). Note that θ,η∈𝔽qk/2 and they are fixed during the whole computation, so they can be precomputed. The coefficients CX, CY, and CW are in 𝔽q; thus the evaluation at Q given the coefficients of the plane can be computed in km (multiplications by θ and η need (k/2)m each).The computation of the coordinates of points and the coefficients of planes, as a part of much variety, is discussed, respectively, for addition and doubling step as follows.


### 5.1. Addition Steps

LetP1=T and P2=P be distinct points with Z1Z2≠0. By variant of formulae of (6) and (12), the explicit formulas for computing P3=T+P and CX, CY, and CW are given as follows:
(18)A=X1·X2,B=Y1·Y2,C=Z1·W2,D=Z2·W1,E=W1·W2,F=(X1-Y1)·(X2+Y2)-A+B,G=B+aA,H=D-C,I=D+C,X3=I·F,Y3=G·H,Z3=F·G,W3=I·H,CX=(W1-Y1)·(W2+Y2)-E+B+H,CW=X2·Z1-X1·Z2-F,CY=(X1-W1)·(X2+W2)-A+E.
With these formulas, T+P and CX, CY, and CW can be computed in 14m+1mc, where 1mc is constant multiplication by a. For a mixed addition step, in which the base point P is chosen to have Z2=1, the costs reduce to 12m+1mc.Therefore, the total costs of an addition step are1M+km+14m+1mc, while a mixed addition step costs 1M+km+12m+1mc.


### 5.2. Doubling Steps

ForP1=P2=T, P3=2T. By the formulae of (6) and (15), our explicit formulas for computing P3=2T and CX, CY, CW are given as follows:
(19)A=X12,B=Y12,C=Z12,D=aA,E=B+D,F=2C-E,G=(X1+Y1)2-A-B,H=(Y1+Z1)2-B-C,X3=G·F,Y3=E·(B-D),Z3=E·F,W3=G·(B-D),2CX=H-2D,2CY=(X1+Z1)2-A-C-G,2CW=d((X1+W1)2-A)-C-E.By the above formulae,2T and CX, CY, and CW can be computed in 4m+7s+2mc, where 2mc are constant multiplications by a and d.So total costs of our formulae for a doubling step are1M+1S+km+4m+7s+2mc, while the total costs of the formulae for the doubling step proposed in [4] are 1M+1S+km+6m+5s+2mc, where 2mc are both constant multiplication by a.


## 5.1. Addition Steps

LetP1=T and P2=P be distinct points with Z1Z2≠0. By variant of formulae of (6) and (12), the explicit formulas for computing P3=T+P and CX, CY, and CW are given as follows:
(18)A=X1·X2,B=Y1·Y2,C=Z1·W2,D=Z2·W1,E=W1·W2,F=(X1-Y1)·(X2+Y2)-A+B,G=B+aA,H=D-C,I=D+C,X3=I·F,Y3=G·H,Z3=F·G,W3=I·H,CX=(W1-Y1)·(W2+Y2)-E+B+H,CW=X2·Z1-X1·Z2-F,CY=(X1-W1)·(X2+W2)-A+E.
With these formulas, T+P and CX, CY, and CW can be computed in 14m+1mc, where 1mc is constant multiplication by a. For a mixed addition step, in which the base point P is chosen to have Z2=1, the costs reduce to 12m+1mc.Therefore, the total costs of an addition step are1M+km+14m+1mc, while a mixed addition step costs 1M+km+12m+1mc.


## 5.2. Doubling Steps

ForP1=P2=T, P3=2T. By the formulae of (6) and (15), our explicit formulas for computing P3=2T and CX, CY, CW are given as follows:
(19)A=X12,B=Y12,C=Z12,D=aA,E=B+D,F=2C-E,G=(X1+Y1)2-A-B,H=(Y1+Z1)2-B-C,X3=G·F,Y3=E·(B-D),Z3=E·F,W3=G·(B-D),2CX=H-2D,2CY=(X1+Z1)2-A-C-G,2CW=d((X1+W1)2-A)-C-E.By the above formulae,2T and CX, CY, and CW can be computed in 4m+7s+2mc, where 2mc are constant multiplications by a and d.So total costs of our formulae for a doubling step are1M+1S+km+4m+7s+2mc, while the total costs of the formulae for the doubling step proposed in [4] are 1M+1S+km+6m+5s+2mc, where 2mc are both constant multiplication by a.


## 6. High-Degree Twists

Letd∣k, an elliptic curve E′ over 𝔽qk/d is called a twist of degree d of E/𝔽qk/d if there is an isomorphism ψ:E′→E defined over 𝔽qk, and this is the smallest extension of 𝔽qk/d over which ψ is defined. Depending on the j-invariant j(E) of E, there exist twists of degree at most 6, since char(𝔽q)>3. Pairing friendly curves with twists of degree higher than 2 arise from constructions with j-invariants j(E)=0 and j(E)=1728.


### 6.1. Edwards Curves withj=1728

For twisted Edwards curveEa,-a:ax2+y2=1-ax2y2, the j-invariant equals to 1728; hence, there exist twists of degree 4. The case a=1 is the “classical” Edwards curve x2+y2=1-x2y2 with complex multiplication D=-4 [20].Lemma 2.
Assume that4∣k, δ is a generator of 𝔽qk over 𝔽qk/4 and δ4∈𝔽qk/4, which implies δ2∈𝔽qk/2. Then the Weierstrass curve
(20)Wa:2av2=u3+1δ4u
is a twist of degree 4 over 𝔽qk/4 of Ea,-a. The isomorphism can be given as
(21)ψ:Wa⟶Ea,-a(u,v)⟼(x,y)=(uδv,δ2u-1δ2u+1).Proof.
Firstly, we prove thatψ is well defined; that is, ψ(u,v)∈Ea,-a. Note that
(22)1x2=δ2v2u2=a2δ2u(δ4u2+1).
We have
(23)1x2-a=a2δ2u(δ2u-1)2,1x2+a=a2δ2u(δ2u+1)2.
Then
(24)1-ax21+ax2=(δ2u-1δ2u+1)2=y2,thusax2+y2=1-ax2y2.
Moreover, it can be easily checked thatψ is invertible and satisfies ψ(O)=O; that is, ψ is an isomorphism. Besides, the minimal field that ψ can be defined over is 𝔽qk which has degree 4 over 𝔽qk/4. Hence, the twist degree is 4.ForQ′∈Wa(𝔽qk/4), we have (xQ,yQ)=ψ(Q′)∈Ea,-a(𝔽qk). Then its corresponding point Q∈SWa,-a(𝔽qk) can be given as (XQ:YQ:WQ:ZQ)=(xQ:yQ:xQyQ:1). One can check by substitution that
(25)XQ+WQYQ+ZQ=xQ=uδv,XQ-WQYQ+ZQ=xQ·1-yQ1+yQ=1δ3v.
For θ=u/(2v) and η=1/(2v), we have XQ/(YQ+ZQ)=θδ-1+ηδ-3 and WQ/(YQ+ZQ)=θδ-1-ηδ-3 with θ,η∈𝔽qk/4. Then for the evaluation of gP1,P2(Q) with P3=P1+P2≠O,O′, we get
(26)gP1,P2(Q)=ΠP1,P2,O′(Q)ΠP3,O,O′(Q)=CXXQ+CY(YQ+ZQ)+CWWQW3XQ-X3WQ=CX(θδ-1+ηδ-3)+CY+CW(θδ-1-ηδ-3)W3(θδ-1+ηδ-3)-X3(θδ-1-ηδ-3)=(CX-CW)η+(CX+CW)θδ2+CYδ3(W3+X3)η+(W3-X3)θδ2∈((CX-CW)η+(CX+CW)θδ2+CYδ3)𝔽qk/2*.So we can reducegP1,P2(Q) to (CX-CW)η+(CX+CW)θδ2+CYδ3. Moreover we may precompute θ and η since they are fixed during the whole computation. When CX,CY,CW∈𝔽q, and θ,η∈𝔽qk/4 are given, the evaluation at Q can be computed in (k/2)m, with (k/4)m each for multiplications by θ and η.The high twist not only reduces the cost of evaluatingg(Q) but also the cost of updating f, which is the main multiplication in Miller’s algorithm as a multiplication in 𝔽qk. Consider 𝔽qk as an 𝔽qk/4-vector space with bases 1, δ, δ2, and δ3. Then an arbitrary element α∈𝔽qk can be denoted as a0+a1δ+a2δ2+a3δ3 with ai∈𝔽qk/4, i=0,1,2,3. And the reduced value of g(Q) we have gotten above can be denoted as β=b0+b2δ2+b3δ3, where b3∈𝔽q and b0,b2∈𝔽qk/4. When using the Schoolbook method, multiplying α by β costs 4·(k/4)m for computing ai·b3, i=0,1,2,3 and costs 8(k/4)2m for ai·b0 and ai·b2. The total cost (k2/2+k)m equals to ((1/2)+(1/k))M, considering that a general multiplication in 𝔽qk costs M=k2m. Namely, the quartic twist may reduce the cost of the main multiplication in Miller’s algorithm to ((1/2)+(1/k))M.Therefore, theaddition step costs ((1/2)+(1/k))M+((k/2)+14)m+1mc, where 1mc is constant multiplication by a. For a mixed addition step, the costs reduce to ((1/2)+(1/k))M+((k/2)+12)m+1mc.Thedoubling step costs ((1/2)+(1/k))M+1S+((k/2)+4)m+7s+2mc, where 2mc are constant multiplications by a and d.


### 6.2. Edwards Curves withj=0

The twisted Edwards curveax2+y2=1+dx2y2 has j-invariant ja,d=16(a2+14ad+d2)3/ad(a-d)4; hence, ja,d=0 if and only if a=(-7±43)d. Note that 3 is a square in finite field 𝔽q if and only if q≡±1(mod12). Now we assume that q≡±1(mod12) and a, d satisfy the relation a=(-7±43)d. Then Edwards curve Ea,d:ax2+y2=1+dx2y2 has j-invariant equal to 0; hence, there exist twists of degree 6. The case a=1 is the Edwards curve x2+y2=1-(7+43)x2y2 with complex multiplication D=-3 [20].We denote thatM=2(a+d)/(a-d) and N=4/(a-d) when given a,d.Lemma 3.
Assume that6∣k, δ is a generator of 𝔽qk over 𝔽qk/6 with δ6∈𝔽qk/6, which implies δ2∈𝔽qk/2 and δ3∈𝔽qk/3. Then the Weierstrass elliptic curve
(27)WMN:v2=u3-M3N327δ6
is a twist of degree 6 over 𝔽qk/6 of Ea,d. The isomorphism can be given as
(28)ψ:Wa⟶Ea,d,(u,v)⟼(x,y)=(Nδ(3u-MNδ2)3v,3u-MNδ2-3Nδ23u-MNδ2+3Nδ2).Proof.
Firstly, we check thatψ is well defined; that is, ψ(u,v)∈Ea,d. We denote that u′=u-(MNδ2)/3, then
(29)v2=u3-M3N3δ627=u′(u′2+MNδ2u′+M2N2δ43),x=Nδu′v,y=u′-Nδ2u′+Nδ2.
Note that
(30)1x2=v2N2δ2u′2=1N2δ2u′(u′2+MNδ2u′+M2N2δ43).
Since M-Na=-2, M-Nd=2, and M2=3, we have
(31)1x2-a=1N2δ2u′(u′-Nδ2)2,1x2-d=1N2δ2u′(u′+Nδ2)2.
Thus
(32)1-ax21-dx2=(u′-Nδ2u′+Nδ2)2=y2,thatis,ax2+y2=1+dx2y2.
Moreover, it can be easily checked thatψ is invertible and satisfies ψ(O)=O; that is, ψ is an isomorphism. Besides, the minimal field that ψ can be defined over is 𝔽qk which has degree 6 over 𝔽qk/6. Hence, the twist degree is 6.ForQ′∈WMN(𝔽qk/6), we have (xQ,yQ)=ψ(Q′)∈Ea,d(𝔽qk). Then its corresponding point Q∈SWa,d(𝔽qk) can be given as (XQ:YQ:WQ:ZQ)=(xQ:yQ:xQyQ:1). One can check by substitution that
(33)XQ+WQYQ+ZQ=xQ=Nuvδ-MN23vδ3,XQ-WQYQ+ZQ=xQ·1-yQ1+yQ=N2vδ3.
For θ=(Nu/2v)δ6 and η=(N2/6v)δ6, we have
(34)XQYQ+ZQ=θδ-5+(3-M)ηδ-3,WQYQ+ZQ=θδ-5-(3+M)ηδ-3
with θ,η∈𝔽qk/6. Then for the evaluation of gP1,P2(Q) with P3=P1+P2≠O, O′, we get
(35)gP1,P2(Q)=ΠP1,P2,O′(Q)ΠP3,O,O′(Q)=CXXQ+CY(YQ+ZQ)+CWWQW3XQ-X3WQ=CX(XQ/(YQ+ZQ))+CY+CW(WQ/(YQ+ZQ))W3(XQ/(YQ+ZQ))-X3(WQ/(YQ+ZQ))=((θδ-5-(3+M)ηδ-3)CX(θδ-5+(3-M)ηδ-3)+CY+CW(θδ-5-(3+M)ηδ-3))×((θδ-5-(3+M)ηδ-3)W3(θδ-5+(3-M)ηδ-3)-X3(θδ-5-(3+M)ηδ-3))-1=(ηδ2+CYδ5+(3(CX-CW)(CX+CW)θ+(3(CX-CW)-M(CX+CW))ηδ2+CYδ5+(3(CX-CW))×(+(3(W3+X3)-M(W3-X3))ηδ2(W3-X3)θ+(3(W3+X3)-M(W3-X3))ηδ2)-1∈(+(3(CX-CW)-M(CX+CW))ηδ2(CX+CW)θ+(3(CX-CW)-M(CX+CW))ηδ2+CYδ5+(3(CX-CW)-M(CX+CW))ηδ2)𝔽qk/2*.So we can reducegP1,P2(Q) to the representative in the last line. Moreover we may precompute θ and η since they are fixed during the whole computation. When CX,CY,CW∈𝔽q, and θ, η∈𝔽qk/6 are given, the evaluation at Q can be computed in (k/3)m+mc, with (k/6)m each for multiplications by θ and η and a constant multiplication by M=2(a+d)/(a-d).Similarly with thej=1728 case, consider 𝔽qk as an 𝔽qk/6-vector space with bases 1,δ,δ2,…,δ5. Then an arbitrary element α∈𝔽qk can be denoted as a0+a1δ+a2δ2+⋯+a5δ5 with ai∈𝔽qk/6, i=0,1,…,5. And the reduced g(Q) we have gotten above can be denoted as β=b0+b2δ2+b5δ5, where b5∈𝔽q and b0,b2∈𝔽qk/6. When using the Schoolbook method, multiplying α by β costs 6·(k/6)m for computing ai·b5, i=0,1,2,3 and costs 12(k/6)2m for ai·b0 and ai·b2. The total cost ((k2/3)+k)m equals to ((1/3)+(1/k))M, considering that a general multiplication in 𝔽qk costs M=k2m. Namely, the sextic twist may reduce the cost of the main multiplication in Miller’s algorithm to ((1/3)+(1/k))M.Therefore, theaddition step costs ((1/3)+(1/k))M+((k/3)+14)m+2mc, where 2mc are multiplications by a and 2(a+d)/(a-d). For a mixed addition step, the costs reduce to ((1/3)+(1/k))M+((k/3)+12)m+2mc.Thedoubling step costs ((1/3)+(1/k))M+1S+((k/3)+4)m+7s+3mc, where 3mc are multiplications by a, d, and 2(a+d)/(a-d).Table1 shows the concrete comparison for doubling step (DBL), mixed addition step (mADD), and addition step (ADD).Table 1
DBL
mADD
ADD
Arène et al. [4]
1
M
+
1
S
+
k
m
+
6
m
+
5
s
+
2
m
c
1
M
+
k
m
+
12
m
+
1
m
c
1
M
+
k
m
+
14
m
+
1
m
c
This paperj≠0,1728
1
M
+
1
S
+
k
m
+
4
m
+
7
s
+
2
m
c
1
M
+
k
m
+
12
m
+
1
m
c
1
M
+
k
m
+
14
m
+
1
m
c
This paperj=1728
(
1
/
2
+
1
/
k
)
M
+
1
S
+
(
k
/
2
)
m
+
4
m
+
7
s
+
2
m
c
(
1
/
2
+
1
/
k
)
M
+
(
k
/
2
)
m
+
12
m
+
1
m
c
(
1
/
2
+
1
/
k
)
M
+
(
k
/
2
)
m
+
14
m
+
1
m
c
This paperj=0
(
1
/
3
+
1
/
k
)
M
+
1
S
+
(
k
/
3
)
m
+
4
m
+
7
s
+
3
m
c
(
1
/
3
+
1
/
k
)
M
+
(
k
/
3
)
m
+
12
m
+
2
m
c
(
1
/
3
+
1
/
k
)
M
+
(
k
/
3
)
m
+
14
m
+
2
m
c


## 6.1. Edwards Curves withj=1728

For twisted Edwards curveEa,-a:ax2+y2=1-ax2y2, the j-invariant equals to 1728; hence, there exist twists of degree 4. The case a=1 is the “classical” Edwards curve x2+y2=1-x2y2 with complex multiplication D=-4 [20].Lemma 2.
Assume that4∣k, δ is a generator of 𝔽qk over 𝔽qk/4 and δ4∈𝔽qk/4, which implies δ2∈𝔽qk/2. Then the Weierstrass curve
(20)Wa:2av2=u3+1δ4u
is a twist of degree 4 over 𝔽qk/4 of Ea,-a. The isomorphism can be given as
(21)ψ:Wa⟶Ea,-a(u,v)⟼(x,y)=(uδv,δ2u-1δ2u+1).Proof.
Firstly, we prove thatψ is well defined; that is, ψ(u,v)∈Ea,-a. Note that
(22)1x2=δ2v2u2=a2δ2u(δ4u2+1).
We have
(23)1x2-a=a2δ2u(δ2u-1)2,1x2+a=a2δ2u(δ2u+1)2.
Then
(24)1-ax21+ax2=(δ2u-1δ2u+1)2=y2,thusax2+y2=1-ax2y2.
Moreover, it can be easily checked thatψ is invertible and satisfies ψ(O)=O; that is, ψ is an isomorphism. Besides, the minimal field that ψ can be defined over is 𝔽qk which has degree 4 over 𝔽qk/4. Hence, the twist degree is 4.ForQ′∈Wa(𝔽qk/4), we have (xQ,yQ)=ψ(Q′)∈Ea,-a(𝔽qk). Then its corresponding point Q∈SWa,-a(𝔽qk) can be given as (XQ:YQ:WQ:ZQ)=(xQ:yQ:xQyQ:1). One can check by substitution that
(25)XQ+WQYQ+ZQ=xQ=uδv,XQ-WQYQ+ZQ=xQ·1-yQ1+yQ=1δ3v.
For θ=u/(2v) and η=1/(2v), we have XQ/(YQ+ZQ)=θδ-1+ηδ-3 and WQ/(YQ+ZQ)=θδ-1-ηδ-3 with θ,η∈𝔽qk/4. Then for the evaluation of gP1,P2(Q) with P3=P1+P2≠O,O′, we get
(26)gP1,P2(Q)=ΠP1,P2,O′(Q)ΠP3,O,O′(Q)=CXXQ+CY(YQ+ZQ)+CWWQW3XQ-X3WQ=CX(θδ-1+ηδ-3)+CY+CW(θδ-1-ηδ-3)W3(θδ-1+ηδ-3)-X3(θδ-1-ηδ-3)=(CX-CW)η+(CX+CW)θδ2+CYδ3(W3+X3)η+(W3-X3)θδ2∈((CX-CW)η+(CX+CW)θδ2+CYδ3)𝔽qk/2*.So we can reducegP1,P2(Q) to (CX-CW)η+(CX+CW)θδ2+CYδ3. Moreover we may precompute θ and η since they are fixed during the whole computation. When CX,CY,CW∈𝔽q, and θ,η∈𝔽qk/4 are given, the evaluation at Q can be computed in (k/2)m, with (k/4)m each for multiplications by θ and η.The high twist not only reduces the cost of evaluatingg(Q) but also the cost of updating f, which is the main multiplication in Miller’s algorithm as a multiplication in 𝔽qk. Consider 𝔽qk as an 𝔽qk/4-vector space with bases 1, δ, δ2, and δ3. Then an arbitrary element α∈𝔽qk can be denoted as a0+a1δ+a2δ2+a3δ3 with ai∈𝔽qk/4, i=0,1,2,3. And the reduced value of g(Q) we have gotten above can be denoted as β=b0+b2δ2+b3δ3, where b3∈𝔽q and b0,b2∈𝔽qk/4. When using the Schoolbook method, multiplying α by β costs 4·(k/4)m for computing ai·b3, i=0,1,2,3 and costs 8(k/4)2m for ai·b0 and ai·b2. The total cost (k2/2+k)m equals to ((1/2)+(1/k))M, considering that a general multiplication in 𝔽qk costs M=k2m. Namely, the quartic twist may reduce the cost of the main multiplication in Miller’s algorithm to ((1/2)+(1/k))M.Therefore, theaddition step costs ((1/2)+(1/k))M+((k/2)+14)m+1mc, where 1mc is constant multiplication by a. For a mixed addition step, the costs reduce to ((1/2)+(1/k))M+((k/2)+12)m+1mc.Thedoubling step costs ((1/2)+(1/k))M+1S+((k/2)+4)m+7s+2mc, where 2mc are constant multiplications by a and d.


## 6.2. Edwards Curves withj=0

The twisted Edwards curveax2+y2=1+dx2y2 has j-invariant ja,d=16(a2+14ad+d2)3/ad(a-d)4; hence, ja,d=0 if and only if a=(-7±43)d. Note that 3 is a square in finite field 𝔽q if and only if q≡±1(mod12). Now we assume that q≡±1(mod12) and a, d satisfy the relation a=(-7±43)d. Then Edwards curve Ea,d:ax2+y2=1+dx2y2 has j-invariant equal to 0; hence, there exist twists of degree 6. The case a=1 is the Edwards curve x2+y2=1-(7+43)x2y2 with complex multiplication D=-3 [20].We denote thatM=2(a+d)/(a-d) and N=4/(a-d) when given a,d.Lemma 3.
Assume that6∣k, δ is a generator of 𝔽qk over 𝔽qk/6 with δ6∈𝔽qk/6, which implies δ2∈𝔽qk/2 and δ3∈𝔽qk/3. Then the Weierstrass elliptic curve
(27)WMN:v2=u3-M3N327δ6
is a twist of degree 6 over 𝔽qk/6 of Ea,d. The isomorphism can be given as
(28)ψ:Wa⟶Ea,d,(u,v)⟼(x,y)=(Nδ(3u-MNδ2)3v,3u-MNδ2-3Nδ23u-MNδ2+3Nδ2).Proof.
Firstly, we check thatψ is well defined; that is, ψ(u,v)∈Ea,d. We denote that u′=u-(MNδ2)/3, then
(29)v2=u3-M3N3δ627=u′(u′2+MNδ2u′+M2N2δ43),x=Nδu′v,y=u′-Nδ2u′+Nδ2.
Note that
(30)1x2=v2N2δ2u′2=1N2δ2u′(u′2+MNδ2u′+M2N2δ43).
Since M-Na=-2, M-Nd=2, and M2=3, we have
(31)1x2-a=1N2δ2u′(u′-Nδ2)2,1x2-d=1N2δ2u′(u′+Nδ2)2.
Thus
(32)1-ax21-dx2=(u′-Nδ2u′+Nδ2)2=y2,thatis,ax2+y2=1+dx2y2.
Moreover, it can be easily checked thatψ is invertible and satisfies ψ(O)=O; that is, ψ is an isomorphism. Besides, the minimal field that ψ can be defined over is 𝔽qk which has degree 6 over 𝔽qk/6. Hence, the twist degree is 6.ForQ′∈WMN(𝔽qk/6), we have (xQ,yQ)=ψ(Q′)∈Ea,d(𝔽qk). Then its corresponding point Q∈SWa,d(𝔽qk) can be given as (XQ:YQ:WQ:ZQ)=(xQ:yQ:xQyQ:1). One can check by substitution that
(33)XQ+WQYQ+ZQ=xQ=Nuvδ-MN23vδ3,XQ-WQYQ+ZQ=xQ·1-yQ1+yQ=N2vδ3.
For θ=(Nu/2v)δ6 and η=(N2/6v)δ6, we have
(34)XQYQ+ZQ=θδ-5+(3-M)ηδ-3,WQYQ+ZQ=θδ-5-(3+M)ηδ-3
with θ,η∈𝔽qk/6. Then for the evaluation of gP1,P2(Q) with P3=P1+P2≠O, O′, we get
(35)gP1,P2(Q)=ΠP1,P2,O′(Q)ΠP3,O,O′(Q)=CXXQ+CY(YQ+ZQ)+CWWQW3XQ-X3WQ=CX(XQ/(YQ+ZQ))+CY+CW(WQ/(YQ+ZQ))W3(XQ/(YQ+ZQ))-X3(WQ/(YQ+ZQ))=((θδ-5-(3+M)ηδ-3)CX(θδ-5+(3-M)ηδ-3)+CY+CW(θδ-5-(3+M)ηδ-3))×((θδ-5-(3+M)ηδ-3)W3(θδ-5+(3-M)ηδ-3)-X3(θδ-5-(3+M)ηδ-3))-1=(ηδ2+CYδ5+(3(CX-CW)(CX+CW)θ+(3(CX-CW)-M(CX+CW))ηδ2+CYδ5+(3(CX-CW))×(+(3(W3+X3)-M(W3-X3))ηδ2(W3-X3)θ+(3(W3+X3)-M(W3-X3))ηδ2)-1∈(+(3(CX-CW)-M(CX+CW))ηδ2(CX+CW)θ+(3(CX-CW)-M(CX+CW))ηδ2+CYδ5+(3(CX-CW)-M(CX+CW))ηδ2)𝔽qk/2*.So we can reducegP1,P2(Q) to the representative in the last line. Moreover we may precompute θ and η since they are fixed during the whole computation. When CX,CY,CW∈𝔽q, and θ, η∈𝔽qk/6 are given, the evaluation at Q can be computed in (k/3)m+mc, with (k/6)m each for multiplications by θ and η and a constant multiplication by M=2(a+d)/(a-d).Similarly with thej=1728 case, consider 𝔽qk as an 𝔽qk/6-vector space with bases 1,δ,δ2,…,δ5. Then an arbitrary element α∈𝔽qk can be denoted as a0+a1δ+a2δ2+⋯+a5δ5 with ai∈𝔽qk/6, i=0,1,…,5. And the reduced g(Q) we have gotten above can be denoted as β=b0+b2δ2+b5δ5, where b5∈𝔽q and b0,b2∈𝔽qk/6. When using the Schoolbook method, multiplying α by β costs 6·(k/6)m for computing ai·b5, i=0,1,2,3 and costs 12(k/6)2m for ai·b0 and ai·b2. The total cost ((k2/3)+k)m equals to ((1/3)+(1/k))M, considering that a general multiplication in 𝔽qk costs M=k2m. Namely, the sextic twist may reduce the cost of the main multiplication in Miller’s algorithm to ((1/3)+(1/k))M.Therefore, theaddition step costs ((1/3)+(1/k))M+((k/3)+14)m+2mc, where 2mc are multiplications by a and 2(a+d)/(a-d). For a mixed addition step, the costs reduce to ((1/3)+(1/k))M+((k/3)+12)m+2mc.Thedoubling step costs ((1/3)+(1/k))M+1S+((k/3)+4)m+7s+3mc, where 3mc are multiplications by a, d, and 2(a+d)/(a-d).Table1 shows the concrete comparison for doubling step (DBL), mixed addition step (mADD), and addition step (ADD).Table 1
DBL
mADD
ADD
Arène et al. [4]
1
M
+
1
S
+
k
m
+
6
m
+
5
s
+
2
m
c
1
M
+
k
m
+
12
m
+
1
m
c
1
M
+
k
m
+
14
m
+
1
m
c
This paperj≠0,1728
1
M
+
1
S
+
k
m
+
4
m
+
7
s
+
2
m
c
1
M
+
k
m
+
12
m
+
1
m
c
1
M
+
k
m
+
14
m
+
1
m
c
This paperj=1728
(
1
/
2
+
1
/
k
)
M
+
1
S
+
(
k
/
2
)
m
+
4
m
+
7
s
+
2
m
c
(
1
/
2
+
1
/
k
)
M
+
(
k
/
2
)
m
+
12
m
+
1
m
c
(
1
/
2
+
1
/
k
)
M
+
(
k
/
2
)
m
+
14
m
+
1
m
c
This paperj=0
(
1
/
3
+
1
/
k
)
M
+
1
S
+
(
k
/
3
)
m
+
4
m
+
7
s
+
3
m
c
(
1
/
3
+
1
/
k
)
M
+
(
k
/
3
)
m
+
12
m
+
2
m
c
(
1
/
3
+
1
/
k
)
M
+
(
k
/
3
)
m
+
14
m
+
2
m
c


## 7. Conclusion

In this paper, we propose an elaborate geometry approach to explain the group law on Edwards curves which are seen as the intersection of two quadric surfaces in space. Using the geometric interpretation of the group law, we obtain the Miller function of Tate pairing computation on twisted Edwards curves. Then we present the explicit formulae for pairing computation on twisted Edwards curves. The doubling step of our formulae is a little faster than that in [4]. Finally, to improve the efficiency, we present quartic and sextic twists on twisted Edwards curves. By using high twists, the costs of substituting in j=1728 case and j=0 case can be reduced to a half and a third, respectively. Above all, it is interesting to consider more efficient formulae for pairing computation on twist Edwards curves.



---

*Source: 136767-2013-11-07.xml*