e(P + P , Q) = e(P, Q)e(P , Q) and e(P, Q + Q ) = e(P, Q)e(P, Q ).

Non-degeneracy:

• For all P ∈ G1 , with P = 0, there is some Q ∈ G2 such that

e(P, Q) = 1.

• For all Q ∈ G2 , with Q = 0, there is some P ∈ G1 such that

e(P, Q) = 1.

The two examples of pairings which we will consider are the Weil and

Tate pairings on elliptic curves over ¬nite ¬elds. First we give some easy

consequences of bilinearity.

Lemma IX.1. Let e be a bilinear pairing as above. Let P ∈ G1 and Q ∈ G2 .

Then

1. e(P, 0) = e(0, Q) = 1.

2. e(’P, Q) = e(P, Q)’1 = e(P, ’Q).

3. e([j]P, Q) = e(P, Q)j = e(P, [j]Q) for all j ∈ Z.

183

184 IX. PAIRINGS

Proof. Property 1 follows from e(P, Q) = e(P + 0, Q) = e(P, Q)e(0, Q)

and similar formulae for Q. Property 2 follows from 1 = e(0, Q) = e(P +

(’P ), Q) = e(P, Q)e(’P, Q). Property 3 is then immediate.

IX.2. Divisors and Weil Reciprocity

We recall the language of divisors from algebraic geometry. General ref-

erences are Silverman [307] and Washington [343]. This section may be

omitted on ¬rst reading.

Let C be a curve over a perfect ¬eld K (the two important cases for our

purposes are when C is an elliptic curve or is the projective line). We denote

by C(K) the set of all points on the curve de¬ned over the algebraic closure

of the ¬eld K. A divisor on C is a formal sum D = P ∈C(K) nP (P ), where

nP ∈ Z and all but ¬nitely many nP are zero. The divisor with all nP = 0

is denoted 0. The set of divisors on C is denoted DivK (C) and has a natural

group structure of addition. The support of a divisor D is the set of all points

P such that nP = 0. The degree of a divisor D is deg(D) = P nP . For

σ ∈ Gal(K/K) we de¬ne Dσ = P nP (σ(P )). A divisor is de¬ned over K if

D = Dσ for all σ ∈ Gal(K/K).

If f is a non-zero function on C, then ordP (f ) counts the multiplicity of f

at P , see [307, Section II.1]. Note that ordP (f ) is positive when f (P ) = 0 and

is negative if f has a pole at P . The divisor of a non-zero function f , written

(f ), is the divisor P ∈C(K) ordP (f )(P ). It follows that (f g) = (f ) + (g) and

(f /g) = (f ) ’ (g). A principal divisor on C is a divisor which is equal to (f )

for some function f . An important theorem of algebraic geometry states that

deg((f )) = 0 (see Remark II.3.7 of [307] or Theorem VII.7.9 of [226]).

A function f is de¬ned over K if it can be written with all coe¬cients

lying in the ¬eld K. If f is a non-zero function de¬ned over K, then the

divisor (f ) is de¬ned over K.

—

If f ∈ K is a constant, then (f ) = 0. Conversely, if (f ) = 0, then f must

be a constant. Hence, if (f ) = (g), then (g/f ) = 0 and so g is a constant

multiple of f . In other words, the divisor (f ) determines the function f up

to a non-zero scalar multiple.

Two divisors D and D are said to be equivalent (written D ∼ D) if

D = D+(f ) for some function f . If D1 ∼ D1 and D2 ∼ D2 , then (D1 +D2 ) ∼

(D1 +D2 ). The divisor class group of a curve is the set of all divisors of degree

zero up to equivalence with group structure inherited from DivK (C).

The group law on an elliptic curve can be expressed in terms of divisors.

Let P1 and P2 be two points on E(K). Suppose the line between the two

points P1 and P2 (take the tangent line if P1 = P2 ) has equation l(x, y) = 0.

This line hits the elliptic curve E at some other point S = (xS , yS ). The

linear polynomial l(x, y) may be interpreted as a function mapping elliptic

curve points to K. The function l(x, y) has divisor (l) = (P1 ) + (P2 ) +

IX.3. DEFINITION OF THE TATE PAIRING 185

(S) ’ 3(O). The vertical line v(x) = (x ’ xS ) passes through the points S

and P3 = P1 + P2 by de¬nition. Interpreting v(x) as a function on E gives

(v) = (S) + (P3 ) ’ 2(O). Hence the equation P3 = P1 + P2 is the same as

the divisor equality (P3 ) ’ (O) = (P1 ) ’ (O) + (P2 ) ’ (O) ’ (l/v) and the

mapping of P to the divisor class of (P ) ’ (O) is a group homomorphism.

The above ideas are summarized in the following result, which relates

equivalence of divisors on an elliptic curve E with point addition on E.

Theorem IX.2. Let E be an elliptic curve over a ¬eld K. Let

D= nP (P )

P

be a degree zero divisor on E. Then D ∼ 0 (i.e., there is a function f such

that D = (f )) if and only if P [nP ]P = O on E.

Let f be a function and let D = P nP (P ) be a divisor of degree zero

such that the support of D is disjoint to the support of (f ). De¬ne

f (P )nP .

f (D) =

P

—

Note that if g = cf for some constant c ∈ K , then g(D) = f (D) when D

has degree zero. Hence, in this case the quantity f (D) depends only on the

divisors (f ) and D. If f and D are both de¬ned over K, then f (D) ∈ K.

The following remarkable result is used to prove various properties of the

Weil and Tate pairings. It is proved in the appendix to this chapter.

Theorem IX.3 (Weil reciprocity). Let f and g be non-zero functions on a

curve C over K. Suppose that the support of (f ) and the support of (g) are

disjoint. Then f ((g)) = g((f )).

IX.3. De¬nition of the Tate Pairing

We now introduce the most important pairing in elliptic curve cryptogra-

phy. The Tate pairing was introduced by Tate as a rather general pairing on

abelian varieties over local ¬elds. Lichtenbaum [224] gave an interpretation

in the case of Jacobians of curves over local ¬elds which permits explicit com-

putation. Frey and R¨ck [126, 125] considered the Tate pairing over ¬nite

u

¬elds and thus introduced the Tate pairing to the cryptographic community.

For more background details about the Tate pairing see Frey [127].

Let E be an elliptic curve over a ¬eld K0 . Let n be a positive integer

which is coprime to the characteristic of the ¬eld K0 . The set of nth roots of

—

unity is de¬ned to be µn = {u ∈ K0 : un = 1}. De¬ne the ¬eld K = K0 (µn )

to be the extension of K0 generated by the nth roots of unity. De¬ne

E(K)[n] = {P ∈ E(K) : [n]P = O}

186 IX. PAIRINGS

and

nE(K) = {[n]P : P ∈ E(K)}.

Then E(K)[n] is a group of exponent n. Further, nE(K) is a subgroup of

E(K) and the quotient group E(K)/nE(K) is a group of exponent n. One

may think of E(K)/nE(K) as the set of equivalence classes of points in E(K)

under the equivalence relation P1 ≡ P2 if and only if (P1 ’ P2 ) ∈ nE(K).

De¬ne

(K — )n = {un : u ∈ K — }.

Then (K — )n is a subgroup of K — and the quotient group K — /(K — )n is a group

of exponent n. The groups K — /(K — )n and µn are isomorphic.

The groups E(K)[n] and E(K)/nE(K) have the same number of elements,

but it is not necessarily the case that the points of E(K)[n] may be used as

representatives for the classes in E(K)/nE(K). For example, let p and r be

primes such that r4 divides (p ’ 1). There is an elliptic curve E over Fp with

p ’ 1 points which has r4 points of order r2 de¬ned over Fp . In this case

E[r] ⊆ rE(Fp ). Another example is given below.

Example: The elliptic curve E : y 2 = x3 + x ’ 3 over K0 = F11 has 6

points. Let n = 3 and write ζ3 for a root of t2 + t + 1 over F11 . Then K =

K0 (µn ) = F11 (ζ3 ) = F112 . One can compute that #E(K) = 22 33 . A basis for

E(K)[3] is {(9, 3), (10, 3 + 6ζ3 )}. The point R = (3 + 6ζ3 , 1 + 7ζ3 ) ∈ E(K)

has order 9 and satis¬es [3]R = (10, 3 + 6ζ3 ). Hence (10, 3 + 6ζ3 ) ∈ 3E(K)

and so E(K)[3] does not represent E(K)/3E(K). A basis for E(K)/3E(K)

is {(9, 3), (3 + 6ζ3 , 1 + 7ζ3 )}.

However, in many cases of relevance for cryptography one can represent

E(K)/nE(K) using the points of E(K)[n]; see Theorem IX.22.

We are now in a position to de¬ne the Tate pairing. Let P ∈ E(K)[n]

and let Q ∈ E(K). We think of Q as representing an equivalence class in

E(K)/nE(K). Since [n]P = O, it follows that there is a function f such that

(f ) = n(P ) ’ n(O). Let D be any degree zero divisor equivalent to (Q) ’ (O)

such that D is de¬ned over K and the support of D is disjoint from the

support of (f ). In most cases such a divisor can easily be constructed by

choosing an arbitrary point S ∈ E(K) and de¬ning D = (Q + S) ’ (S). Since

f and D are de¬ned over K, the value f (D) is an element of K. Since the

supports of (f ) and D are disjoint, we have f (D) = 0, and so f (D) ∈ K — .

The Tate pairing of P and Q is de¬ned to be

P, Q = f (D)

n

interpreted as an element of K — /(K — )n .

We emphasize that values of the Tate pairing are equivalence classes. The

reader is warned that we will use the symbol = to denote equivalence under

this relation.

IX.4. PROPERTIES OF THE TATE PAIRING 187

Example: Consider the elliptic curve

E : y 2 = x(x2 + 2x + 2)

over F3 such that E(F3 ) = {O, (0, 0)}. Let n = 2, P = (0, 0) and note that

µ2 = {1, 2} ⊆ F3 . Now suppose we are to compute P, P 2 .

The function x has divisor (x) = 2(P ) ’ 2(O). We now must ¬nd a

divisor D which is equivalent to (P ) ’ (O) but which has support disjoint

from {O, P }. Since there are only two points in E(F3 ) we cannot in this case

choose D = (P + S) ’ (S) for some S ∈ E(F3 ).

Write F32 = F3 (i), where i2 = ’1, and consider points on E over F32 .

The divisor D = ((1 + i, 1 + i)) + ((1 ’ i, 1 ’ i)) ’ ((1, i)) ’ ((1, ’i)) is

de¬ned over F3 as a divisor. Note that (1, i) + (1, ’i) = O in E(F32 ) and that

(1 + i, 1 + i) + (1 ’ i, 1 ’ i) is a point in E(F3 ) which is not O, and so it is P .

Hence, by Theorem IX.2 we have D ∼ (P ) ’ (O).

Finally,

(1 + i)(1 ’ i)

P, P 2 = x(D) = = 2.

(1)(1)

IX.4. Properties of the Tate Pairing

The Tate pairing is not a well de¬ned element of K — as it depends on

the choice of D and also on the choice of representative Q of the class in

E(K)/nE(K). This is why we must consider values of the Tate pairing to be

equivalence classes in K — /(K — )n . The following two lemmas show that the

Tate pairing is well de¬ned as an element of K — /(K — )n .

Lemma IX.4. Let f be a function such that (f ) = n(P ) ’ n(O) and let D ∼

D be degree zero divisors such that the supports of D and D are disjoint to

the support of (f ). Suppose that f , D and D are all de¬ned over K. Then

f (D )/f (D) ∈ (K — )n .

Proof. Write D = D + (g). Then the support of (g) is disjoint to the

support of (f ) and

f (D ) = f (D + (g)) = f (D)f ((g)).

Weil reciprocity implies that

f ((g)) = g((f )) = g(n(P ) ’ n(O)) = (g(P )/g(O))n ∈ (K — )n .

Lemma IX.5. Let P ∈ E(K)[n] and Q, R ∈ E(K). Let f be a function

such that (f ) = n(P ) ’ n(O). Let D and D be divisors de¬ned over K

with support disjoint to the support of (f ) such that D ∼ (Q) ’ (O) and

D ∼ (Q + [n]R) ’ (O). Then f (D )/f (D) ∈ (K — )n .

188 IX. PAIRINGS

Proof. By Theorem IX.2, we have D ∼ D + n(R) ’ n(O). By Lemma IX.4

we have f (D ) = f (D + n(R) ’ n(O)) up to nth powers. Finally,

f (D + n(R) ’ n(O)) = f (D)f ((R) ’ (O))n

and the result follows.

Note that the Tate pairing depends closely on the ¬elds under considera-

tion. If L is an extension of K, then an element ζ ∈ K — may satisfy ζ ∈ (K — )n

but ζ ∈ (L— )n . Similarly, a point Q ∈ E(K) may satisfy Q ∈ nE(K) but

Q ∈ nE(L).

In some situations we consider a di¬erent function f to de¬ne the pairing.

Lemma IX.6. Up to nth powers the pairing can be de¬ned using a function

g such that (g) = n(P + R) ’ n(R) for an arbitrary point R ∈ E(K).

Proof. Let f be such that (f ) = n(P ) ’ n(O) and suppose R ∈ E(K).

Let h be the function corresponding to the addition of P and R. In other

words, (h) = (P + R) ’ (R) ’ (P ) + (O). De¬ning g = f hn gives (g) =

(f ) + n(h) = n(P + R) ’ n(R). Let D be any divisor with support disjoint

from the supports of (f ) and (g). Then g(D) = f (D)h(D)n is equal to f (D)

up to nth powers.

We now list the key properties of the Tate pairing (recall that = and =

often refer to equivalence modulo nth powers).

Theorem IX.7. Let E be an elliptic curve over K0 and let n be coprime to

the characteristic of K0 . Let K = K0 (µn ). The Tate pairing satis¬es:

1. (Bilinearity) For all P, P1 , P2 ∈ E(K)[n] and Q, Q1 , Q2 ∈ E(K)/nE(K),

P 1 + P2 , Q = P1 , Q P2 , Q

n n n

and

P, Q1 + Q2 n = P, Q1 n P, Q2 n .

2. (Non-degeneracy) Suppose K is a ¬nite ¬eld.1 For all P ∈ E(K)[n],

P = O, there is some Q ∈ E(K)/nE(K) such that P, Q n = 1.

Similarly, for all Q ∈ E(K)/nE(K) with Q ∈ nE(K) there is some

P ∈ E(K)[n] such that P, Q n = 1.

3. (Galois invariance) If σ ∈ Gal(K/K0 ), then σ(P ), σ(Q) n = σ( P, Q n ).

Proof. We prove bilinearity with two cases:

Case 1: Let P1 + P2 = P3 and let g be the function such that (P3 ) ’ (O) =

(P1 )’(O)+(P2 )’(O)+(g). If (f1 ) = n(P1 )’n(O) and (f2 ) = n(P2 )’n(O),

then (f1 f2 g n ) = n(P3 ) ’ n(O). Let D ∼ (Q) ’ (O) have support disjoint to

{P1 , P2 , P3 , O} (it can be shown that such a divisor always exists). Then

= f1 f2 g n (D) = f1 (D)f2 (D)g(D)n

P1 + P2 , Q = P3 , Q

n n

in K — /(K — )n .

which is equal to P1 , Q P2 , Q

n n

1

Non-degeneracy is also proved in some other cases, for example, p-adic ¬elds.

IX.5. THE TATE PAIRING OVER FINITE FIELDS 189

Case 2: Suppose Q1 + Q2 = Q3 . If D1 ∼ (Q1 ) ’ (O) and D2 ∼ (Q2 ) ’ (O),

then D1 + D2 ∼ (Q3 ) ’ (O) and so

P, Q1 + Q2 = f (D1 + D2 ) = f (D1 )f (D2 ) = P, Q1 P, Q2

n n n

in K — /(K — )n .

Proofs of non-degeneracy can be found in Frey-R¨ck [126]and Hess [167].

u

For the Galois-invariance, de¬ne f σ to be the function obtained by ap-

plying σ to all the coe¬cients of f . Then σ(f (P )) = f σ (σ(P )). If (f ) =

n(P ) ’ n(O), then (f σ ) = n(σ(P )) ’ n(O) and σ(P ), σ(Q) n = f σ (σ(D)) =

σ(f (D)) = σ( P, Q n ).

IX.5. The Tate Pairing over Finite Fields

Suppose that K0 = Fq is a ¬nite ¬eld. Let E be an elliptic curve de¬ned

over K0 and let n be an integer coprime to q which divides #E(K0 ). The

¬eld K = K0 (µn ) is some ¬nite extension Fqk . The number k is called the

embedding degree or security multiplier and it is simply the smallest positive

integer such that n divides (q k ’ 1). We stress that the number k is, strictly

speaking, a function k(q, n) of q and n; however, the context is usually clear

and so we will simply write k. Since k is the order of q modulo n it follows

that k divides φEul (n) (Euler phi-function). Hence, if n is prime, then k

divides (n ’ 1).

For a random ¬eld Fq and a random elliptic curve E, if we let n be a

large divisor of #E(Fq ), then the embedding degree k is usually very large

(almost the same number of bits as n) and so computation in the ¬eld Fqk

has exponential complexity (in terms of the input size q).

Since E is de¬ned over Fq , if P and Q are de¬ned over a proper sub¬eld

of Fqk , then P, Q n is also de¬ned over the same proper sub¬eld of Fqk . Now

suppose that n is a prime, in which case our convention is to call it r. Since

Fqk is the smallest ¬eld containing both µr and Fq it follows that, for every

intermediate ¬eld Fq ⊆ L ‚ Fqk with L = Fqk , we have L ⊆ (F—k )r . These

q

observations lead to the following trivial but important result, which tells us

when the value of the Tate pairing can be trivial.

Lemma IX.8. Let E be an elliptic curve over Fq and let r be a prime. Suppose

the embedding degree for E and r is k > 1. Let L be a proper sub¬eld of Fqk

which contains Fq . If P, Q ∈ E(L), then P, Q r ∈ (F—k )r .

q

When K0 = Fq and K = Fqk , a value of the Tate pairing is an equiva-

lence class in F—k /(F—k )n and for practical purposes we would like a unique

q q

representative of this class. The natural way to proceed is to raise this value

to the power (q k ’ 1)/n. This kills o¬ all nth powers leaving an exact nth

root of unity in Fqk . Hence for the remainder of this chapter we consider the

190 IX. PAIRINGS

bilinear pairing

k

e(P, Q) = P, Q n ’1)/n

(q

which maps into the group µn ‚ F—k rather than the group F—k /(F—k )n .

q q q

We now give some compatibility results for the Tate pairing.

Theorem IX.9. Let E be an elliptic curve over Fq . Let n|#E(Fq ) and sup-

pose the embedding degree corresponding to q and n is k. Let N = hn be a

multiple of n which divides q k ’ 1.

1. Let P ∈ E(Fq ) have order n and let Q ∈ E(Fqk ). Then

(q k ’1)/N (q k ’1)/n

P, Q = P, Q .

n

N

2. Let P ∈ E(Fqk )[N ] and let Q ∈ E(Fqk ). Then P, Q = [h]P, Q up

N n

to nth powers.2 Another way to say this is that

(q k ’1)/n k

= [h]P, Q n ’1)/n .

(q

P, Q N

ˆ

3. Let φ : E ’ E be an isogeny and let φ be the dual isogeny. Then, up

to nth powers,

ˆ

φ(P ), Q n = P, φ(Q) n .

4. Let φ : E ’ E be an isogeny. Then, up to nth powers,

deg(φ)

φ(P ), φ(Q) = P, Q .

n n

Proof.

1. Write N = hn. Let D be a degree zero divisor equivalent to (Q) ’ (O).

Suppose g is a function over Fq such that (g) = n(P ) ’ n(O). Then

(g h ) = N (P ) ’ N (O) and so

(q k ’1)/N k ’1)/N k ’1)/n (q k ’1)/n

= g h (D)(q = g(D)(q

P, Q = P, Q .

n

N

2. By part 1

(q k ’1)/N h(q k ’1)/N

(q k ’1)/n

[h]P, Q = [h]P, Q = P, Q .

n N N

3. (This proof uses notation de¬ned in the appendix to this chapter).

The point φ(P ) has order dividing n. Suppose (f ) = n(P ) ’ n(O) and

D ∼ (Q)’(O). Then (φ— f ) = φ— ((f )) = n(φ(P ))’n(O). By Theorem

III.6.1(b) of [307], φ— D ∼ (φ(Q)) ’ (O). Hence, by Lemma IX.26,

ˆ

φ(P ), Q = (φ— f )(D)

n

= f (φ— D)

ˆ

= P, φ(Q) n .

4. By part 3

ˆ

φ(P ), φ(Q) = P, φφ(Q) = P, [deg(φ)]Q n .

n n

2

Since P, Q N is de¬ned up to N th powers and [h]P, Q is de¬ned up to nth powers

n

we can compare their values only up to nth powers.

IX.6. THE WEIL PAIRING 191

IX.6. The Weil Pairing

Let E be an elliptic curve de¬ned over K0 and let n be an integer coprime

to the characteristic of K0 . De¬ne K = K0 (E[n]) to be the ¬eld extension of

K0 generated by the coordinates of all the points in E(K) of order divisible

by n. The Weil pairing is a map

en : E[n] — E[n] ’ µn ⊆ K — .

For more information about the Weil pairing see Section III.8 of [307] or

Section III.5 of [ECC]. There are two equivalent de¬nitions of the Weil

pairing (for the proof of equivalence see [63] or [173]). The de¬nition we give

is the one which is closer to the de¬nition of the Tate pairing.

Let P, Q ∈ E[n] and let D, D be degree zero divisors such that the support

of D and D are disjoint and such that D ∼ (P ) ’ (O) and D ∼ (Q) ’ (O).

By Theorem IX.2, there are functions f and g such that (f ) = nD and

(g) = nD . The Weil pairing is de¬ned to be

en (P, Q) = f (D )/g(D).

The Weil pairing takes values in µn ⊆ K — . The following result gives

some properties of the Weil pairing.

Theorem IX.10. The Weil pairing satis¬es the following properties.

1. (Bilinearity) For all P, P , Q, Q ∈ E[n],

en (P + P , Q) = en (P, Q)en (P , Q)

and

en (P, Q + Q ) = en (P, Q)en (P, Q ).

2. (Alternating) en (P, P ) = 1 and so en (P, Q) = en (Q, P )’1 .

3. (Non-degeneracy) If en (P, Q) = 1 for all Q ∈ E[n], then P = O.

4. (Galois invariance) For all σ ∈ Gal(K/K)

en (σ(P ), σ(Q)) = σ(en (P, Q)).

5. (Compatibility) If P ∈ E[nm] and Q ∈ E[n], then

enm (P, Q) = en ([m]P, Q).

ˆ

6. If φ : E ’ E is an isogeny with dual φ, then

ˆ

en (φ(P ), Q) = en (P, φ(Q)).

Proof. All properties except non-degeneracy can be proved using Weil reci-

procity and other techniques as used for the Tate pairing. For details see

Propositions 8.1 and 8.2 of Silverman [307] (also see Hess [167]).

The following corollary is easily deduced and is of fundamental impor-

tance.

192 IX. PAIRINGS

Corollary IX.11. Let E be an elliptic curve over a ¬eld k and let r be a

prime. Let P, Q ∈ E(k)[r] such that P = O. Then Q lies in the subgroup

generated by P if and only if er (P, Q) = 1.

Note the similarity between the de¬nition of the Weil pairing and the Tate

pairing. In the Weil pairing, the term f (D ) is equivalent modulo nth powers

to P, Q n while the term g(D) is equivalent modulo nth powers to Q, P n .

Hence we can write

P, Q n

en (P, Q) = up to nth powers. (IX.1)

Q, P n

Note that this equation is only useful in the case where µn ⊆ (K — )n .

One di¬erence between the Weil pairing and the Tate pairing is that the

Tate pairing requires working over K0 (µn ) while the Weil pairing requires the

potentially much larger ¬eld K0 (E[n]). The following theorem of Balasubra-

manian and Koblitz shows that, in the cases most relevant for cryptography,

these two ¬elds are actually the same.

Theorem IX.12. (Balasubramanian and Koblitz [12]) Let E be an elliptic

curve over Fq and let r be a prime dividing #E(Fq ). Suppose that r does not

divide (q ’ 1) and that gcd(r, q) = 1. Then E[r] ‚ E(Fqk ) if and only if r

divides (q k ’ 1).

The Weil pairing can be generalized from E[n] = ker([n]) to ker(φ) where φ

is any isogeny. In a certain case, Garefalakis [140] shows that the generalized

Weil pairing is essentially equivalent to the Tate pairing.

IX.7. Non-degeneracy, Self-pairings and Distortion Maps

(q k ’1)/n

We now restrict to the case where K = Fqk and e(P, Q) = P, Q .

n

IX.7.1. Non-Degeneracy. Non-degeneracy means that, for all points P ∈

E(Fqk )[n], except P = O, there is some Q ∈ E(Fqk ) such that e(P, Q) = 1.

The question we consider more closely is, for which points Q do we have

e(P, Q) = 1?

For the remainder of this subsection we restrict ourselves to the case where

n is a prime, and we call it r. Then E(Fqk )[r], E(Fqk )/rE(Fqk ) and µr ‚ F—kq

may all be considered as vector spaces over Fr . De¬ne

d = dimFr (E(Fqk )[r]) = dimFr (E(Fqk )/rE(Fqk )) ∈ {1, 2}.

Choose a basis {Pi } for E(Fqk )[r] over Fr and a basis {Qi } for E/rE. Then

the pairing can be represented as a d — d matrix M over Fr . For any P =

i ai Pi ∈ E[r] and any Q = j bj Qj ∈ E(Fq k ) we have

e(P, Q) = (ai )t M (bj ).

If det(M ) = 0, then there is a vector v such that vM = 0 and this contradicts

non-degeneracy. Hence det(M ) = 0.

IX.7. NON-DEGENERACY, SELF-PAIRINGS AND DISTORTION MAPS 193

By ¬xing P we may consider the pairing as an Fr -linear map from the

quotient group E(Fqk )/rE(Fqk ) to µr . The rank-nullity theorem implies that

for every such point there is a (d ’ 1)-dimensional subspace of points Q such

that e(P, Q) = 1. Similarly, ¬xing Q gives an Fr -linear map from E(Fqk )[r]

to µr and an analogous result follows.

We consider the two cases in turn. If E(Fqk )[r] has dimension one as an

Fr -vector space, then so does E(Fqk )/rE(Fqk ) and so for all P ∈ E(Fqk )[r],

with P = O, and all Q ∈ E(Fqk ), with Q ∈ rE(Fqk ) we have e(P, Q) = 1.

If E(Fqk )[r] has dimension two, then for every point P ∈ E(Fqk )[r], P = O

there is a basis {Q, R} for E(Fqk )/rE(Fqk ) such that e(P, Q) = g = 1 and

e(P, R) = 1. It follows that e(P, [a]Q + [b]R) = g a = 1 for all a coprime to r.

IX.7.2. Self-Pairings. The alternating property of the Weil pairing is that

the pairing of any point P with itself is always 1. We now consider the

possibilities for a “self-pairing” in the case of the Tate pairing.

The ¬rst issue is that E(Fqk )[n] and E(Fqk )/nE(Fqk ) are di¬erent groups.

If P ∈ E(Fqk )[n] © nE(Fqk ), then e(P, P ) = 1. Theorem IX.22 shows that

many relevant cases for cryptography have E[n] © nE(Fqk ) = {O}. Similarly,

if P ∈ E(Fq ) has prime order r and if k > 1, then by Lemma IX.8 e(P, P ) = 1

and so the pairing is trivial. We have established the following fact.

Lemma IX.13. Let E be an elliptic curve over Fq , let r be a prime dividing

#E(Fq ) and let P ∈ E(Fq ) be a point of order r. Let k be the embedding

degree corresponding to q and r. Then e(P, P ) = 1 if k > 1 or if P ∈ rE(Fq ).

In the case k = 1 there are several possibilities. Suppose E is an elliptic

curve over Fq and r is a prime number such that r|#E(Fq ) and r|(q ’ 1) (and

so k = 1). Let P = O be a point of order r. If r #E(Fq ) (if p is a prime

and k is an integer, then the symbol pk m means that pk divides m and pk+1

does not divide m), then there is a unique subgroup of order r in E(Fq ) and

the non-degeneracy of the Tate pairing implies that e(P, P ) = 1.

If there are r2 points of order r in E(Fq ), then it is possible that e(P, P ) =

1. For example, the curve y 2 = x3 + 11 over F31 has group structure (Z/5Z)2

and the points P = (2, 9) and Q = (3, 10) form a basis for the points of

order 5. One can compute that e(P, P ) = 16, e(Q, Q) = 8, e(P, Q) = 2 and

e(Q, P ) = 8. It follows that

2 +4ab+3b2

e([a]P + [b]Q, [a]P + [b]Q) = 24a

and hence e(R, R) = 1 for all points R ∈ E[5] except R = O.

An example of the opposite situation is given by E : y 2 = x3 + 4 over

F997 (this example was provided by Kim Nguyen). The points P = (0, 2) and

Q = (747, 776) generate the 9 points of order 3 in E(F997 ). One can compute

that e(P, P ) = 1, e(Q, Q) = 1 and e(P, Q) = e(Q, P )’1 = 304. Hence we have

e(R, R) = 1 for all R ∈ E[3].

194 IX. PAIRINGS

IX.7.3. Distortion Maps. The typical case in cryptographic applications

is P ∈ E(Fq ) and k > 1. It is very useful to be able to consider “self-pairings”

in this case. A valuable technique introduced by Verheul [335], which applies

to both the Tate and Weil pairings, is to use a non-rational endomorphism.

Lemma IX.14. Let P ∈ E(Fq ) have prime order r and suppose k > 1. Sup-

pose that E(Fqk ) has no points of order r2 . Let φ be an endomorphism of E.

If φ(P ) ∈ E(Fq ), then e(P, φ(P )) = 1.

Proof. Since φ is an endomorphism it follows that the order of φ(P ) is r

or 1. The latter case does not occur since φ(P ) ∈ E(Fq ). Hence {P, φ(P )}

is a basis for the r-torsion on E. Since there is no r2 -torsion it follows that

φ(P ) ∈ rE(Fqk ). Finally, since e(P, P ) = 1 it follows that e(P, φ(P )) = 1.

A non-rational endomorphism which maps a point from E(Fq ) to E(Fqk )

as in the lemma is called a distortion map. For a given supersingular curve

(see De¬nition IX.18) there is at least one nice choice (indeed, Theorem 5

of [336] proves that distortion maps always exist). In Section IX.13 we give

examples of convenient distortion maps for supersingular curves. However,

the following result from [335] implies that distortion maps do not exist for

ordinary (i.e., non-supersingular; see Section IX.10) curves.

Theorem IX.15. Let E be an elliptic curve over Fq which has a distortion

map. Then E is supersingular.

Proof. Suppose φ is an endomorphism which maps some point P ∈ E(Fq )

to a point φ(P ) ∈ E(Fq ). Let • be the q-power Frobenius map, which is an

endomorphism of E. Then •(P ) = P and •(φ(P )) = φ(P ) and so φ —¦ • =

• —¦ φ in End(E). Hence, End(E) is non-commutative and E is supersingular

according to De¬nition IX.18.

IX.7.4. The Trace Map. An alternative to using a non-rational endomor-

phism (which works for all elliptic curves) is the following. Let P = (x, y) ∈

E(Fqk ) and de¬ne the trace map

k’1

i i

(xq , y q )

Tr(P ) = σ(P ) =

i=0

σ∈Gal(Fqk /Fq )

where the sum is elliptic curve point addition. The trace map is a group homo-

morphism and Tr(P ) ∈ E(Fq ). Under conditions like those of Lemma IX.14

it follows that if P ∈ E(Fqk ) has prime order r, P ∈ E(Fq ) and Tr(P ) = O,

then e(Tr(P ), P ) = 1. We stress that the trace map transforms points which

are de¬ned over a large ¬eld into points de¬ned over a small ¬eld, whereas

distortion maps go the other way around. For further details see Boneh, Lynn

and Shacham [42].

The trace map enables mapping into a speci¬c cyclic subgroup of E(Fqk )

of order r (called the trace zero subgroup T ) as follows. If P is a randomly

IX.7. NON-DEGENERACY, SELF-PAIRINGS AND DISTORTION MAPS 195

chosen element of E(Fqk ) of order r, then P = [k]P ’ Tr(P ) is easily seen to

satisfy Tr(P ) = O. Furthermore, if P ∈ E(Fq ) and if r is coprime to k, then

P = O. This idea is used in [42]. A more e¬cient way to map into the trace

zero subgroup using twists is given in [18]. The following degeneracy result

was shown to me by Dan Boneh.

Lemma IX.16. Let E be an elliptic curve over Fq . Let r be a prime such that

r divides #E(Fq ) and such that the subgroup of r elements has embedding

degree k > 1. Assume that r does not divide either k or (q ’ 1). Let Tr be the

trace map with respect to Fqk /Fq as above and • the q-power Frobenius. Let

T = {P ∈ E(Fqk )[r] : Tr(P ) = O}.

Then T = {P ∈ E(Fqk )[r] : •(P ) = [q]P } and for all P, Q ∈ T we have

e(P, Q) = 1.

Proof. If P ∈ E(Fq )[r], then Tr(P ) = [k]P . Hence T © E(Fq )[r] = {O}.

On the other hand, it is easy to see that T is a subgroup of E(Fqk )[r]. Hence

#T = r and T is cyclic.

Let • be the q-power Frobenius map, which acts on both Fqk and on

E(Fqk ). It is known that • has eigenvalues 1 and q on E(Fqk ). Let {P1 , P2 }

be a basis for E(Fqk )[r] such that •(P1 ) = P1 and •(P2 ) = [q]P2 . Then

Tr(P2 ) = [1 + q + · · · + q k’1 ]P2 = [(q k ’ 1)/(q ’ 1)]P2 = O and it follows that

P2 is the generator of T .

To complete the proof it su¬ces to prove that e(P2 , P2 ) = 1 and we do

this by showing e(P2 , P2 ) ∈ Fq . Consider

2

e(P2 , P2 )q = •(e(P2 , P2 )) = e(•(P2 ), •(P2 )) = e([q]P2 , [q]P2 ) = e(P2 , P2 )q .

Acting by •’1 gives e(P2 , P2 ) = e(P2 , P2 )q , which implies e(P2 , P2 ) ∈ Fq .

IX.7.5. Symmetry. Another issue for the Tate pairing is to consider the

relationship between P, Q n and Q, P n , for points P, Q ∈ E(K)[n]. Up to

nth powers we have

P, Q = Q, P n en (P, Q).

n

Since the Weil pairing is non-degenerate, we often have P, Q n = Q, P n up

to nth powers.

However, if distortion or trace maps are being used, then the pairing is

usually restricted to a single cyclic subgroup. In this case Q = [m]P for some

m and so

e(Q, φ(P )) = e([m]P, φ(P )) = e(P, [m]φ(P )) = e(P, φ(Q)).

In other words, the pairing is symmetric when restricted to a cyclic subgroup.

196 IX. PAIRINGS

IX.8. Computing the Tate Pairing Using Miller™s Algorithm

Victor Miller [249] gave an algorithm to compute the Weil pairing in

polynomial time and this approach can also be used to compute the Tate

pairing. The main issue is how to construct a function f such that (f ) =

n(P ) ’ n(O). Miller™s idea is to use the double-and-add method to construct

such a function in stages.

Write fi for a function such that (fi ) = i(P ) ’ ([i]P ) ’ (i ’ 1)(O). Such a

function is uniquely de¬ned up to a constant multiple. The function we aim

to compute is fn .

Lemma IX.17. The functions fi can be chosen to satisfy the following condi-

tions.

1. f1 = 1.

2. Let l and v be the straight lines used in the computation of [i]P +[j]P =

[i + j]P . Then

l

fi+j = fi fj .

v

Proof. The fact that we can take f1 = 1 is clear. In the general case we

have

(l/v) = ([i]P ) + ([j]P ) ’ ([i + j]P ) ’ (O)

and so

(fi fj l/v) = i(P ) ’ ([i]P ) ’ (i ’ 1)(O) + j(P ) ’ ([j]P ) ’ (j ’ 1)(O) + (l/v)

= (i + j)(P ) ’ ([i + j]P ) ’ (i + j ’ 1)(O).

This proves the result.

These formulae are most simply used in the cases j = 1 (addition) and j =

i (doubling). Miller™s algorithm uses an addition chain for [n]P to compute

fn . Since we are interested in the value fn (D) we evaluate all intermediate

quantities at the divisor D = (Q + S) ’ (S).3

Algorithm IX.1: Miller™s Algorithm

INPUT: P, Q ∈ E(K) where P has order n.

OUTPUT: P, Q n .

1. Choose a suitable point S ∈ E(K).

2. Q ← Q + S.

3. T ← P .

4. m ← log2 (n) ’ 1, f ← 1.

5. While m ≥ 0 do:

Calculate lines l and v for doubling T .

6.

T ← [2]T .

7.

3

The generalization of Miller™s algorithm to other divisors D is straightforward.

¨

IX.9. THE MOV/FREY“RUCK ATTACK ON THE ECDLP 197

f ← f 2 l(Q )v(S) .

8. v(Q )l(S)

If the mth bit of n is one, then:

9.

Calculate lines l and v for addition of T and P .

10.

T ←T + P.

11.

f ← f l(Q )v(S) .

12. v(Q )l(S)

m ← m ’ 1.

13.

14. Return f .

Note that line 12 of the algorithm is simpli¬ed to l = (x ’ xP ) and v = 1

in the ¬nal iteration since T = ’P in that case.

Clearly there are log2 (n) iterations of the main loop of Miller™s algorithm

and so the doubling operation is executed log2 (n) times. The number of times

the addition operation (lines 10 to 12) is executed is equal to one less than

the Hamming weight of n. Hence Miller™s algorithm runs in polynomial time.

One way to choose a suitable point S is to choose a random point in

E(K). When n is large the algorithm can easily be made deterministic by

taking S = [i]P , where the binary expansion of i is not a segment of the

binary expansion of n (or by taking S = Q if P ∈ E(Fq ) and Q ∈ E(Fq )).

A variation of the algorithm outputs an explicit expression for the function

f as a straight-line program (i.e., as a product of powers of small polynomials

which requires polynomial storage space if it is kept in factored form).

Example: Let E : y 2 = x3 +1 over F101 . Then #E(F101 ) = 101+1 = 2·3·17.

For n = 17 we have k = 2. Write F1012 = F101 (θ), where θ2 = ’2. Let

P = (87, 61) (which has order 17) and let Q = (48, θ) (which has order 102).

Set D = ([2]Q) ’ (Q). We compute the following values:

i fi (D) i fi (D)

11 8 46 + 18θ

2 52 + 56θ 16 22 + 43θ

4 53 + 3θ 17 74 + 62θ

Hence P, Q 17 = 74 + 62θ. Raising to the power (1012 ’ 1)/17 = 600

gives the value 93 + 25θ ∈ µ17 .

IX.9. The MOV/Frey“R¨ck Attack on the ECDLP

u

An important application of pairings in elliptic curve cryptography is to

transform an instance of the elliptic curve discrete logarithm problem into an

instance of a ¬nite ¬eld discrete logarithm problem. The motivation for this

approach is that there are index-calculus algorithms for the discrete logarithm

problem in ¬nite ¬elds which run in subexponential time. An approach using

the Weil pairing was given by Menezes, Okamoto and Vanstone [239] while

an approach using the Tate pairing was given by Frey and R¨ck [126].

u

Let P ∈ E(Fq ) be of prime order r, coprime to q, and let Q be some

multiple of P . The MOV/Frey“R¨ck attack is as follows:

u

198 IX. PAIRINGS

Algorithm IX.2: MOV/Frey“R¨ck Attack

u

P, Q ∈ E(Fq ), of prime order r, such that Q = [»]P

INPUT:

for some unknown value ».

OUTPUT: Discrete logarithm » of Q to the base P .

1. Construct the field Fqk such that r divides (q k ’ 1).

2. Find4 a point S ∈ E(Fqk ) such that e(P, S) = 1.

3. ζ1 ← e(P, S).

4. ζ2 ← e(Q, S).

5. Find » such that ζ1 = ζ2 in F—k using an index-calculus

»

q

method (perform linear algebra modulo r).

6. Return ».

The ¬rst steps of this attack require negligible computational resources,

but solving the discrete logarithm problem in the ¬nite ¬eld Fqk is non-trivial;

the complexity of solving discrete logarithms in F—k is subexponential in q k .

q

Hence the attack has exponential complexity in terms of k and this strategy

is only e¬ective when k is “small”.

An important contribution of Menezes, Okamoto and Vanstone was the

observation that supersingular curves always have small values of k; see Corol-

lary IX.21. There are also non-supersingular curves which are vulnerable to

this attack. For example, for every prime power q = pa (p > 2) there are

elliptic curves E over Fq with q ’ 1 points and the reduction in this case

requires no extension of the ground ¬eld.

IX.10. Supersingular Elliptic Curves

We ¬rst give the de¬nition of supersingularity (see Silverman [307]).

Definition IX.18. Let E be an elliptic curve over a ¬eld Fq , where q is

a power of p. Then E is supersingular if one of the following equivalent

conditions holds:

1. #E(Fq ) ≡ 1 (mod p) (equivalently, #E(Fq ) = q + 1 ’ t where p|t).

2. E has no points of order p over Fq .

3. The endomorphism ring of E over Fq is non-commutative (more pre-

cisely, is an order in a quaternion algebra).

If E is not supersingular, then it is called ordinary.

Every supersingular elliptic curve in characteristic p has j(E) ∈ Fp2 and

so is isomorphic over Fp to a curve de¬ned over Fp2 . But, in general, there are

twists de¬ned over Fpn which are not isomorphic over Fpn to curves de¬ned

over Fp2 .

4

This step is trivial in practice; a random point satis¬es the condition with overwhelm-

ing probability.

IX.10. SUPERSINGULAR ELLIPTIC CURVES 199

We will now classify the embedding degrees for supersingular elliptic

curves. First we need a result of Waterhouse.

Theorem IX.19. (Waterhouse [344]) Let p be a prime and let a ∈ N. De¬ne

T = {pa + 1 ’ #E(Fpa ) : E an elliptic curve over Fpa }.

√

Then T equals the set of all t ∈ Z with |t| ¤ 2 pa which satisfy one of the

following conditions:

1. gcd(t, p) = 1.

If a is even, then t = ±2pa/2 .

2.

If a is even and p ≡ 1 (mod 3), then t = ±pa/2 .

3.

If a is odd and p = 2, 3, then t = ±p(a+1)/2 .

4.

If (a is odd) or (a is even and p ≡ 1 (mod 4)), then t = 0.

5.

The curves corresponding to condition 1 are ordinary while the others are

supersingular.

Theorem IX.20. The following table lists all possibilities for embedding de-

gree and group structure for supersingular elliptic curves over Fq .

k q #E(Fq ) Group structure of E(Fqk )

√ √

q±2 q+1 (Z/( q ± 1)Z)2

p2b

1

(Z/(q + 1)Z)2

2 (5) q+1

√

(Z/(q 3/2 ’ 1)Z)2

3 (3) q+ q+1

√

q ’ √q + 1 (Z/(q 3/2 + 1)Z)2

3 (3)

q ± √2q + 1

22b+1 (Z/(q 2 + 1)Z)2

4

q ± 3q + 1

32b+1 (Z/(q 3 + 1)Z)2

6

In the above table the numbers (3) and (5) in the q column correspond to cases

3 and 5 of Theorem IX.19 (in case 3, q is a square). In the ¬rst k = 3 case

the MOV/Frey“R¨ck attack maps the discrete logarithm into the ¬nite ¬eld

u

Fq3/2 rather than Fq3 .

Proof. The proof follows from Theorem IX.19 and [320]. Let q = pa . Since

E is supersingular, the number of points on E over Fq is given by q + 1 ’ t,

where t satis¬es one of the conditions 2 to 5.

The characteristic polynomial of the q-power Frobenius map • on E over

Fq is given by P (T ) = T 2 ’ tT + q. If we factor P (T ) = (T ’ ±)(T ’ ±) over

C, then the characteristic polynomial of the q k -power Frobenius map on E is

(T ’ ±k )(T ’ ±k ) and #E(Fqk ) = q k + 1 ’ ±k ’ ±k . Proposition 2 of [320]

shows that if the characteristic polynomial of the q k -power Frobenius map is

(T ’±k )2 , where ±k ∈ Z, then the group structure of E(Fqk ) is (Z/|1’±k |Z)2 .

√

• Case t = ±2 q:

In this case q is a square and the characteristic polynomial of Frobenius

√ √ √ √

is P (T ) = T 2 ±2 qT +q = (T ± q)2 . Since ( q +1)( q ’1) = (q ’1)

the embedding degree is k = 1.

200 IX. PAIRINGS

√

• Case t = ± q:

√

In this case q is a square and #E(Fq ) = (q ± q + 1). We have (q ±

√ √

q + 1)( q “ 1) = q 3/2 “ 1 and (q 3/2 ’ 1)(q 3/2 + 1) = (q 3 ’ 1) and so

√

k = 3. In the case of t = + q we really have #E(Fq ) divides (q 3/2 ’ 1)

and so “k = 3/2”. The characteristic polynomial of the Frobenius map

over Fq3 is P (T ) = (T ± q 3/2 )2 .

• Case t = ±p(a+1)/2 :

In the case p = 2 we have #E(Fq ) = (2a ± 2(a+1)/2 + 1). The char-

acteristic polynomial of Frobenius is T 2 ± 2(a+1)/2 T + 2a and its roots

are

“1 ± i

√

±, ± = 2a/2 .

2

We compute that ±4 = ±4 = ’22a and so the characteristic polynomial

of Frobenius on E over Fq4 is (T + q 2 )2 . Hence [1 + q 2 ]P = O for all

P ∈ √ q4 ) and so E(Fq4 ) has group structure (Z/(q 2 + 1)Z)2 . Since

E(F √

(q + 2q + 1)(q ’ 2q + 1) = (q 2 + 1) divides (q 4 ’ 1) we deduce that

k = 4. √

In the case p = 3 we have #E(Fq ) = (q ± 3q + 1). The character-

istic polynomial of Frobenius has roots

√

“ 3±i

±, ± = 3a/2 .

2

One sees that ±6 = ±6 = ’33a and so the characteristic polynomial of

√

Frobenius on E over Fq6 is (T + q 3 )2 . Since (q + 1)(q + 3q + 1)(q ’

√

3q + 1) = (q + 1)(q 2 ’ q + 1) = (q 3 + 1) the result follows.

• Case t = 0:

In this case #E(Fq ) = (q + 1) and n divides (q ’ 1)(q + 1) = (q 2 ’ 1)

and so k = 2. The characteristic polynomial of Frobenius over Fp2 is

P (T ) = (T + q)2 .

Corollary IX.21. (Menezes, Okamoto and Vanstone [239]) Supersingular

elliptic curves have k ¤ 6.

The table in Theorem IX.20 shows us that when E is supersingular and

#E(Fq ) has a large prime divisor r then there are no di¬culties when com-

paring the groups E(Fqk )[r] and E(Fqk )/rE(Fqk ).

Theorem IX.22. Let E be a supersingular elliptic curve over Fq with em-

√

bedding degree k and let r be a prime dividing #E(Fq ) with r > 4 q. Then

r2 #E(Fqk ) and E(Fqk )[r] © rE(Fqk ) = {O}.

√

Proof. If r > 4 q, then r #E(Fq ). Furthermore, #E(Fq ) is the unique

integer in the Hasse interval which is divisible by r. Since the group orders

IX.11. APPLICATIONS AND COMPUTATIONAL PROBLEMS FROM PAIRINGS 201

speci¬ed in Theorem IX.20 are all products of integers in the Hasse interval,

it follows that r2 #E(Fqk ) and that the full r-torsion is de¬ned over Fqk .

In traditional cryptographic applications (i.e., where pairings are not used)

one usually avoids supersingular curves. This is easily achieved. For example,

in characteristic two, none of the elliptic curves y 2 + xy = x3 + ax2 + b are

supersingular. Criteria for detecting/avoiding supersingular curves of higher

genus are given in [130].

IX.11. Applications and Computational Problems from Pairings

In this section we consider some computational problems related to pair-

ings. Applications to cryptography will be discussed in Chapter X.

IX.11.1. Deducing Group Structure. The Weil pairing can be used to

determine the group structure of an elliptic curve. The key fact is Corol-

lary IX.11, which gives a test for whether Q ∈ P . Given N = #E(Fq ),

if N has no square factors, then the group structure of E(Fq ) is isomorphic

to Z/N Z. If r2 divides N , then there could be a point of order r2 or two

independent points of order r. The Weil pairing shows that one can only

have two independent points when r divides (q ’ 1).

Given the factorization of gcd(q ’ 1, #E(Fq )) the group structure can be

determined in random polynomial time using the following algorithm due to

Miller [249]. For a rigorous analysis see Kohel and Shparlinski [209].

Algorithm IX.3: Miller™s Algorithm for Group Structure

E/Fq with #E(Fq ) = N0 N1 where gcd(N1 , q ’ 1) = 1 and

INPUT:

all primes dividing N0 divide q ’ 1.

OUTPUT: Integers r and s such that E(Fq ) ∼ (Z/rZ) — (Z/sZ)

=

as a group.

r ← 1, s ← 1.

1.

While (rs = N0 ) do:

2.

Choose random points P , Q ∈ E(Fq ).

3.

P ← [N1 ]P , Q ← [N1 ]Q .

4.

Find the exact orders m and n of P and Q.

5.

r ← lcm(m, n).

6.

± ← er (P, Q).

7.

Let s be the exact order of ± in µr ⊆ F— .

8. q

Return s and rN1 .

9.

202 IX. PAIRINGS

IX.11.2. Separating DH and DDH. An important computational prob-

lem in cryptography is the elliptic curve decision Di¬e“Hellman problem (see

[34]). Let E be an elliptic curve over a ¬eld K and let r be a prime.

Decision Di¬e“Hellman problem (ECDDH):5 Given points P1 , P2 , P3

and P4 in E(K)[r] such that P2 = [»]P1 for some », determine whether

P4 = [»]P3 .

In certain cases this problem can be solved using pairings as follows. If

e(P1 , P3 ) = 1, it is enough to test whether

e(P1 , P4 ) = e(P2 , P3 ).

Joux and Nguyen [186] have constructed elliptic curves (both supersingu-

lar and ordinary) such that the decision Di¬e“Hellman probleman be solved

in polynomial time using a pairing, but the (computational) Di¬e“Hellman

problem is provably as hard as solving the discrete logarithm problem. This

suggests that ECDDH really is an easier problem than ECCDH.

IX.11.3. Bilinear Di¬e“Hellman Problem. Many of the new applica-

tions of pairings in cryptography depend for their security on the di¬culty of

the following problem which was ¬rst stated by Boneh and Franklin [39].

Bilinear Di¬e“Hellman problem (BDH): Given P , Q, P1 = [a]P and

P2 = [b]P such that e(P, Q) = 1, compute

e([ab]P, Q).

(This is often written in the special case Q = ψ([c]P ), where ψ is a distortion

map.)

Lemma IX.23. The BDH problem is no harder than either the elliptic curve

Di¬e-Hellman problem (ECDHP) or the ¬nite ¬eld Di¬e-Hellman problem.

Proof. Given a DH oracle on E we run it on input (P, P1 , P2 ) to obtain

[ab]P and then compute the value e([ab]P, Q).

Given a DH oracle for the ¬nite ¬eld we compute h1 = e(P, Q), h2 =

e(P1 , Q) = ha and h3 = e(P2 , Q) = hb and run the oracle on input (h1 , h2 , h3 ).

1 1

The result is hab = e([ab]P, Q).

1

One can also de¬ne a decision problem (see Joux [184]).

Decision Bilinear Di¬e“Hellman problem (DBDH) : Given P , Q such

that e(P, Q) = 1, and given P1 = [a]P , P2 = [b]P and g test whether

?

g = e([ab]P, Q).

The methods of Lemma IX.23 show that the DBDH problem is not harder

than the decision Di¬e“Hellman problem in the ¬nite ¬eld.

5

Our statement of DDH is very general; the authors of [42] call this co-DDH.

IX.12. PARAMETER SIZES AND IMPLEMENTATION CONSIDERATIONS 203

There are many other computational problems relating to pairings (see

Joux [184]). One interesting result is the following.

Theorem IX.24. (Verheul [335]) Let G and H be cyclic groups of prime

order r. Let e : G — G ’ H be a non-degenerate pairing where H ‚ F—k is the

q

image subgroup. If there is an e¬ciently computable group homomorphism

from H to G, then the Di¬e“Hellman problem in G and H can be e¬ciently

solved.

Proof. (Sketch) Denote by φ : H ’ G the homomorphism. Let P, P2 =

[a]P, P3 = [b]P be the input Di¬e“Hellman problem and de¬ne e(P, P ) = h.

If φ(h) = P , then the problem is trivial: [ab]P = φ(e(P2 , P3 )).

Hence de¬ne c to be such that φ(h) = [c]P . Verheul gives a variation on

the double-and-add method which computes Q = [c’2 ]P as follows. Since

c’2 ≡ cr’3 (mod r), we want to compute [cr’3 ]P . Given [cn ]P one can

compute φ(e(P, [cn ]P )) = [cn+1 ]P and φ(e([cn ]P, [cn ]P )) = [c2n+1 ]P .

One then computes [ab]P = φ(e(φ(e([c’2 ]P, P2 )), P3 )).

IX.12. Parameter Sizes and Implementation Considerations

The hardness of the BDH depends on the hardness of the DH problems

both on the elliptic curve E(Fq ) and in the ¬nite ¬eld Fqk . For most cryp-

tographic applications based on pairings we therefore need to be working in

a subgroup of E(Fq ) of su¬ciently large prime order r and we need to be

working with a su¬ciently large ¬nite ¬eld. For current minimum levels of

security we require r > 2160 and q k > 21024 .

The e¬ciency depends on the particular scheme, but in general smaller

values for q means that arithmetic on the elliptic curve E(Fq ) is faster and

transmission of elliptic curve points in E(Fq ) requires less bandwidth. Hence

we tend to want to keep q as small as possible and to gain our security from

larger values for k. A popular choice is to work with points in E(Fq ), where

q ≈ 2170 , and to have a curve with embedding degree k = 6 so that q k ≈ 21024 .

The two main issues for implementing cryptographic applications are

1. How to ¬nd suitable elliptic curves.

2. How to compute e(P, Q) quickly.

We deal with these issues in the next two sections.

In the future, key sizes will have to grow to stay ahead of the increased

computational power available to adversaries. There is an asymmetry with

the BDH problem which is worth mentioning. On the elliptic curve side, to

double the time taken to attack the system one adds an extra two bits to the

size of the prime r. On the ¬nite ¬eld side, one has to add more than 2 bits

to double the security. For example, if elliptic curve key sizes increased by

50% to 240 bits then the ¬nite ¬eld key sizes would at least double to 2048

bits. This issue means that embedding degrees of size larger than 6 may be

useful in the future (see Subsection IX.15.2).

204 IX. PAIRINGS

IX.13. Suitable Supersingular Elliptic Curves

Supersingular curves are suitable for pairing-based cryptosystems since it

is possible to have k = 2, 3, 4 and 6. Table IX.1 contains the most popular

supersingular elliptic curves available for various ¬elds.

Table IX.1. Popular Supersingular Elliptic Curves

k Elliptic curve data

2 E : y 2 = x3 + a over Fp , where p ≡ 2 (mod 3)

#E(Fp ) = p + 1

Distortion map (x, y) ’ (ζ3 x, y), where ζ3 = 1.

3

2 y 2 = x3 + x over Fp , where p ≡ 3 (mod 4)

#E(Fp ) = p + 1.

Distortion map (x, y) ’ (’x, iy), where i2 = ’1.

3 E : y 2 = x3 + a over Fp2 , where

p ≡ 5 (mod 6) and a ∈ Fp2 , a ∈ Fp is a square which is not a cube.

#E(Fp2 ) = p2 ’ p + 1.

Distortion map (x, y) ’ (xp /(γa(p’2)/3 ), y p /a(p’1)/2 ),

where γ ∈ Fp6 satis¬es γ 3 = a.

4 Ei : y 2 + y = x3 + x + ai over F2 , where a1 = 0 and a2 = 1.

#Ei (F2l ) = 2l ± 2(l+1)/2 + 1 (l odd)

Distortion map (x, y) ’ (u2 x + s2 , y + u2 sx + s), where u ∈ F22

and s ∈ F24 satisfy u2 + u + 1 = 0 and s2 + (u + 1)s + 1 = 0.

6 Ei : y 2 = x3 ’ x + ai over F3 , where a1 = 1 and a2 = ’1.

#Ei (F3l ) = 3l ± 3(l+1)/2 + 1 (l odd).

Distortion map (x, y) ’’ (± ’ x, iy), where i ∈ F32 and ± ∈ F33

satisfy i2 = ’1 and ±3 ’ ± ’ ai = 0.

In the cases k = 2, 3 we have chosen complex multiplication (CM) curves

with discriminant D = ’3 and D = ’4. One can use other CM discriminants

to get k = 2, 3 (for instance, Examples 5 and 6 of [138] in characteristic p

when ( ’7 ) = ’1 or ( ’2 ) = ’1). As we have seen, embedding degree 6 is the

p p

largest which can be achieved using supersingular elliptic curves. We discuss

methods to obtain larger values of k in Section IX.15.

Note that in the characteristic 2 example the distortion map acts as a

cube root of ’1 while the characteristic 3 example acts as a square root of

’1. It follows that in both cases the elliptic curve has an endomorphism ring

isomorphic to an order in a quaternion algebra which contains Z[i] or Z[ζ3 ]

as a subring.

One problem with the examples in characteristics 2 and 3 is that there are

only a small number of curves and ¬elds to choose from. Hence, there is an

element of luck in the search for a suitable large prime factor and our choice

of parameters is not very ¬‚exible. No such problems arise when working over

Fp . Two nice examples in characteristic three are over F3163 . We ¬nd that

IX.14. EFFICIENT COMPUTATION OF THE TATE PAIRING 205

#E1 (F3163 ) is 7 times a 256-bit prime and that #E2 (F3163 ) is equal to a 259-bit

prime (see [130] for details).

Another consideration for the case of a small characteristic is Copper-

smith™s algorithm [86] for discrete logarithms in ¬nite ¬elds. This algorithm

was originally described in the case of characteristic two but it can be general-

ized to other ¬elds of small characteristic. It is more e¬cient than the general

methods for taking discrete logarithms in ¬nite ¬elds. So one is obliged to

work with larger ¬elds to get equivalent security to the case of Fp .

IX.14. E¬cient Computation of the Tate Pairing

We turn to the issue of e¬cient computation of the Tate pairing. We

consider the case where E is an elliptic curve over Fq with k > 1 (typically

(q k ’1)/n

with P ∈ E(Fq ) and Q ∈

k = 4 or 6) and we are computing P, Q n

E(Fqk ).

The ¬eld Fqk is much larger than the ¬eld Fq . Hence we perform as many

operations in E(Fq ) as possible. The best approach is to represent Fqk as an

extension of Fq with a convenient basis.

The most important implementation techniques are the following. We

refer to Galbraith, Harrison and Soldera [133] and Barreto, Kim, Lynn and

Scott [16, 18] for further details.

1. If possible, work in a small subgroup (n ≈ 2160 ) of E(Fq ) and/or choose

n to have low Hamming weight (in signed binary representation or

signed ternary representation as appropriate).

2. Work over the small ¬eld Fq wherever possible. In particular, the func-

tion f with divisor (f ) = n(P ) ’ n(O) is de¬ned over Fq and so the

lines l and v in Miller™s algorithm are all de¬ned over Fq . Furthermore,

choose the auxiliary point S in Miller™s algorithm to lie in E(Fq ). This

signi¬cantly reduces the number of computations (though see point 6

below, where S is omitted entirely when k > 1).

3. Implement arithmetic in Fq and Fqk as e¬ciently as possible. This is

particularly relevant in characteristic three.

4. Avoid divisions in Fqk . This is done by replacing the variable f in

Miller™s algorithm by f1 /f2 . Hence, for example, line 8 of Miller™s

algorithm becomes

2 2

f1 = f1 l(Q )v(S), f2 = f2 v(Q )l(S).

A single division is performed at the end of the algorithm.

5. Perform ¬nal exponentiation e¬ciently. In particular, take advantage

of the linearity of the qth power Frobenius map for exponents of special

form. Sometimes several of these exponentiations can be performed in

?

one. For example, to test whether e(P, Q) = e(R, S), one can test

k ?

whether ( P, Q n / R, S n )(q ’1)/n = 1.

206 IX. PAIRINGS

6. If k > 1 and n is prime, then n does not divide (q’1) and so all elements

of F— map to 1 when raised to the power (q k ’ 1)/n. Hence we can

q

ignore all terms in Miller™s algorithm which give rise to an element of

F— . For example, since l, v and S are de¬ned over Fq , we need not

q

compute l(S) and v(S) at all. Line 8 of Miller™s algorithm becomes

2 2

f1 = f1 l(Q ), f2 = f2 v(Q ).

Indeed, we may now take Q = Q (see Theorem 1 of Barreto et al. [18]).

7. If we are using non-rational endomorphisms of a suitable form, then all

denominators in Miller™s algorithm can be removed (see Barreto et al.

[16, 18]).

Two techniques which are often used to speed-up point exponentiation for

elliptic curves are window methods (see [ECC, Section IV.2.3]) and projective

coordinates ([ECC, Section IV.1]). We now argue that these methods are

not useful in the case of the Tate pairing.

Firstly, when n has low Hamming weight (which is a common case) there

is no advantage from using window methods. Now suppose n is arbitrary and

suppose we use windows of length w. We precompute a table of points [d]P

(where ’2w’1 < d ¤ 2w’1 ) and corresponding function values fd,1 /fd,2 which

record the value at the divisor D of the function fd . The key observation is

that, when performing an addition of [d]P rather than P , line 12 of Miller™s

algorithm changes from

f1 = f1 l(Q ), f2 = f2 v(Q ) to f1 = f1 fd,1 l(Q ), f2 = f2 fd,2 v(Q ).

Hence, as well as the signi¬cant initial cost of setting up the table for the

window method, there is an increase from two to four Fqk -multiplications in

each addition stage. If we compute the division during the precomputation

(i.e., fd,2 = 1), then we still require three Fqk -multiplications at the expense of

greater cost during the precomputation. One can therefore show that window

methods do not provide a speedup in this setting.

If group orders without low Hamming weight are used, then the methods

of Eisentr¨ger, Lauter and Montgomery [114] for performing [2]P + Q in one

a

step give a signi¬cant e¬ciency improvement.

There is no need to use projective coordinates for the points in E(Fqk ) as

we have already bundled all the Fqk divisions to a single division at the end.

One can use projective coordinates for the operations in E(Fq ). The perfor-

mance analysis depends on the relative costs of inversion and multiplication

in Fq . This idea was examined by Izu and Takagi [180], but their analysis is

misleading. Using projective coordinates does not reduce the number of Fqk

operations and experiments show that a¬ne coordinates are faster.

In equation (IX.1) we saw that the Weil pairing can be computed by

essentially two Tate pairing computations. Hence one might expect that the

Tate pairing is about twice as fast as the Weil pairing (except for the extra

IX.14. EFFICIENT COMPUTATION OF THE TATE PAIRING 207

exponentiation, which is required for the Tate pairing). In fact, since we

usually have P ∈ E(Fq ) and Q ∈ E(Fqk ), the cost of computing Q, P n

is considerably higher than the cost of computing P, Q n . Hence the Tate

pairing is more than twice as fast as the Weil pairing.

IX.14.1. Doubling in Characteristic Two. Let E : y 2 + y = x3 + x + a

be a supersingular curve in characteristic 2 with embedding degree k = 4. As

is well known, doubling of points on E can be performed without divisions.

Let P = (x1 , y1 ). Then the tangent line to E at P has slope » = (x2 + 1)

1

and has equation l : y = »(x ’ x1 ) + y1 . The third point of intersection has

x-coordinate x2 = »2 = x4 + 1. The vertical line has equation x ’ x2 = 0

1

and [2](x1 , y1 ) = (x2 , y2 ), where y2 = 1 + »(x2 + x1 ) + y1 . Hence the point

(x2 , y2 ) and the equations of the lines l and v can be computed from (x1 , y1 )

by two applications of the squaring map (easy in characteristic two), one

multiplication and some additions.

The equation [2](x1 , y1 ) = (x4 + 1, y1 + x4 ) (if a ∈ F2 ) shows a connection

4

1 1

between doubling and the action of Frobenius squared. The characteristic

polynomial of Frobenius in this example is T 2 ± 2T + 2. Since

(T 2 + 2T + 2)(T 2 ’ 2T + 2) = (T 4 + 4)

we have [4] = ’•4 , where • is the 2-power Frobenius. This gives the formula

[4](x1 , y1 ) = (x16 , y1 + 1)

16

1

which is clearly a consequence of our doubling formula.

IX.14.2. Tripling in Characteristic Three. Suppose P = (x1 , y1 ) is a

point on

E : y 2 = x3 + a4 x + a6

over F3m . The tangent to E at P has slope »2 = 1/y1 and

[2]P = (x2 , y2 ) = (»2 + x1 , ’»3 ’ y1 ).

2 2

The line between (x1 , y1 ) and [2](x1 , y1 ) has slope »3 = y1 ’ »2 . Putting this

3

together, if a4 , a6 ∈ F3 , then

[3](x1 , y1 ) = (x9 + a6 (1 ’ a4 ), ’y1 ).

9

1

So tripling is division-free, although one division is required6 to compute the

equations of the lines l and v. Note that there is a connection between tripling

and Frobenius squared.

Since tripling is so e¬cient it makes sense to utilize a base three Miller

algorithm in characteristic three. Furthermore, as the next subsection shows,

one can use group orders with low Hamming weight in base three which makes

the base three Miller™s algorithm very e¬cient.

6

This division can usually be avoided by homogenising, since it contributes an element

of Fq which is removed during the ¬nal exponentiation.

208 IX. PAIRINGS

The fact that tripling is easy on certain curves in characteristic three was

¬rst noticed by Duursma [110] (Lemma 3.1). Let P = (a, b) be a point on

y 2 = x3 ’ x + d. Then the function h = b3 y ’ (ap ’ x + d)(p+1)/2 satis¬es

(h) = 3(x, y) ’ 3(O) + (’3P ) ’ (O).

This has been used by Duursma and Lee [112] to obtain a faster implemen-

tation of the Tate pairing in characteristic three.

IX.14.3. Low Hamming Weight Example. Often we are not able to

choose the order of P to be a prime of low Hamming weight. For example,

#E1 (F3163 ) = N = 3163 ’ 382 + 1 = 7r

where r is a prime. The prime r does not have low Hamming weight in base

(3163 ’1)/r (3163 ’1)/N

three. So instead of computing P, Q r we compute P, Q N .

By part 1 of Theorem IX.9 the pairing value is the same in both cases.

Note that the exponentiation is to the power

((3163 )6 ’ 1)/N = (3163·4 + 3163·3 ’ 3163 ’ 1)(3163 + 382 + 1)

which also has low Hamming weight. Moreover, this exponentiation can be

computed using repeated applications of the Frobenius map, which is very

e¬cient.

IX.15. Using Ordinary Curves

As mentioned in Section IX.12, it would be useful to have families of

curves with increasing k.

With supersingular elliptic curves the upper limit is k = 6. Rubin and

Silverberg [306] have shown how to obtain values of k larger than 6 from a

combination of supersingular elliptic curves and Weil descent. Their methods

are quite practical, and they give a signi¬cant improvement to the BLS short

signature scheme (see Section 5.1 of [306] for details). However, the possibil-

ities for k are somewhat limited by e¬ciency considerations. Another avenue

is to use higher genus supersingular curves (see Galbraith [130] and Rubin

and Silverberg [306] for details). However, there are severe limitations in the

higher genus case too.

Instead we turn to ordinary (i.e., non-supersingular) elliptic curves. There

are two problems with ordinary curves in this context.

• As we have seen, there are no distortion maps in this case. Nevertheless,

many of the cryptosystems can be easily modi¬ed to handle this issue.

• Results of Balasubramanian and Koblitz [12] show that such curves are

extremely rare. More precisely, if k is ¬xed, then the expected number

of pairs (q, E), where q is a prime power in the range M/2 ¤ q ¤ M

and E is an Fq -isogeny class of elliptic curves over Fq such that E(Fq )

has a large subgroup with embedding degree k, is O(M 1/2+ ). Hence

we cannot expect to ¬nd them by choosing curves at random.

IX.15. USING ORDINARY CURVES 209

For the remainder of this section we discuss some special methods for

constructing ordinary elliptic curves with convenient embedding degrees. All

these algorithms are based on the CM method; see [ECC, Chapter VIII]. We

begin by showing that degree 3, 4 and 6 can be recovered in the ordinary case,

and then later show how to ¬nd curves with k > 6.

IX.15.1. The MNT Criteria. The ¬rst e¬orts in this direction were ob-

tained by by Miyaji, Nakabayashi and Takano [251] (MNT). They showed

how to obtain the values k = 3, 4, 6 with ordinary elliptic curves.

Theorem IX.25. ([251]) Let E be an ordinary elliptic curve over Fq such

that n = #E(Fq ) = q + 1 ’ t is prime. Then the following table lists all the

possibilities for embedding degree k = 3, 4, 6:

kq t

3 12l ’ 1 ’1 ± 6l

2

4 l2 + l + 1 ’l or l + 1

1 ± 2l

6 4l2 + 1

It is an easy exercise to check that these group orders have the claimed em-

bedding degrees. The harder part is to show that any such curve with prime

order has these properties. Note that all these examples produce values for q

in quadratic progressions, which agrees with the results of Balasubramanian

and Koblitz.

Miyaji, Nakabayashi and Takano developed a method to construct such

curves using complex multiplication; see [ECC, Chapter VIII]. As is usual for

the CM method, the trick is to choose q and t in such a way that ∆ = t2 ’ 4q

is a large square times a small discriminant.

We give the details of their method in the case k = 6. For q = 4l2 + 1 and

t = 1 ± 2l we ¬nd that t2 ’ 4q = ’12l2 ± 4l ’ 3. Hence we must solve

’12l2 ± 4l ’ 3 = Dy 2

where D is a small CM discriminant. Multiplying by ’3 and completing

the square gives ’3Dy 2 = (6l “ 1)2 + 8. Hence, we seek solutions (x, y)

to the Diophantine equation x2 + 3Dy 2 = ’8. This equation is solved by

¬nding a single solution and then combining with solutions found using the

continued fraction method to the Pell equation x2 + 3Dy 2 = 1. If a solution

has x ≡ ±1 (mod 6), we can compute the corresponding l and test whether

4l2 + 1 is prime. Since the Diophantine equation has in¬nitely many solutions

we have a good chance of success.

Example: Take D = ’11. The ¬rst step is to ¬nd solutions to

x2 ’ 33y 2 = ’8

(note that ( ’8 ) = ( ’8 ) = 1 so we can hope to suceed). We ¬nd an initial

3 11

solution (x, y) = (5, 1).

210 IX. PAIRINGS

Now, to generate in¬nitely many solutions we ¬nd all the solutions to

x2 ’ 33y 2 = 1

using continued fractions. The ¬rst three solutions are (23, 4), (1057, 184) and

(48599, 8460). The ¬rst of these solutions combined with the initial solution

(5, 1) gives the solution (x, y) = (17, 3) to the original equation.

Since x is of the form 6l ± 1 we obtain l = 3 and thus q = 4l2 + 1 = 37,

which is prime. The trace is t = 1±2l so t = 7 can be obtained, and this gives

a curve with 31 points and the Frobenius has discriminant t2 ’ 4q = ’32 11.

The elliptic curve with complex multiplication by D = ’11 has j-invariant

equal to ’32768. Hence we ¬nd an equation

E : y 2 = x3 + 22x + 27

over F37 , which can be checked to have 31 points. One can check that

#E(F376 ) = 26 · 34 · 5 · 312 · 103.

IX.15.2. Obtaining Larger Values of k. We can now consider how to

generate curves with larger values for k using the CM method. The goal is

to ¬nd an elliptic curve E over Fq with complex multiplication by D such

that there is a large prime r dividing #E(Fq ) = q + 1 ’ t and such that r

divides (q k ’ 1) for a suitable value of k. The condition r divides (q k ’ 1)

does not preclude r dividing (q l ’ 1) for some l < k; hence we often use the

condition r divides ¦k (q) where ¦k (x) denotes the kth cyclotomic polynomial

(see Lang [210] Section VI.3) which is the factor of (xk ’ 1) which does not

appear as a factor of any polynomial (xl ’ 1) with l < k.

We can express the requirements by the equations

t2 ’ 4q = f 2 D (IX.2)

q + 1 ’ t ≡ 0 (mod r) (IX.3)

q k ’ 1 ≡ 0 (mod r). (IX.4)

Equation (IX.3) gives q ≡ t ’ 1 (mod r) and so equation (IX.4) is equivalent

to (t ’ 1)k ≡ 1 (mod r). In other words, t ’ 1 is a kth root of unity modulo

r. Equation (IX.2) gives 4q = t2 ’ f 2 D. If t = 2a is even, then f is even

and we obtain q = a2 ’ (f /2)2 D. If t = 2a + 1 is odd, then we obtain

q = a2 + a + (1 ’ f 2 D)/4.

If values for r and k are ¬xed, then there are only k ’ 1 possible values for

t modulo r and, for each of these choices, q is determined modulo r. One can

search for prime values of q by searching along a certain arithmetic progression

depending on r. This gives rise to the following algorithm (originally proposed

by Cocks and Pinch [84]) for generating curves using the CM method with

arbitrary embedding degree k and with a large prime factor r of any form.

We give the algorithm in the case D ≡ 0 (mod 4) (the case D ≡ 1 (mod 4)

is similar). Let b = f /2 so that we seek q = a2 ’ b2 D. Substituting this

IX.15. USING ORDINARY CURVES 211

expression and t = 2a into equation (IX.3) gives (a ’ 1)2 ’ b2 D ≡ 0 (mod r).

√

This implies that b = ±(a ’ 1)/ D (mod r). There are usually several

reasonable choices for g, a and b0 , and the algorithm should be run for all

choices to obtain optimal results.

Algorithm IX.4: Curve Construction for Arbitrary k

k, r, D ≡ 0 (mod 4) such that r is a prime, D is a

INPUT:

square modulo r and k divides (r ’ 1).

OUTPUT: p, t such that there is a curve with CM by D over Fp

with p + 1 ’ t points where r | (p + 1 ’ t) and r | (pk ’ 1).

1. Choose a primitive kth root of unity g in Fr .

2. Choose an integer a ≡ 2’1 (g + 1) (mod r).

3. If (gcd(a, D) = 1), then halt (or choose another g).

√

4. Choose an integer b0 ≡ ±(a ’ 1)/ D (mod r).

5. j ← 0.

6. Do

p ← a2 ’ D(b0 + jr)2 .

7.

j ← j + 1.

8.

9. Until p is prime.

10. t ← 2a.

11. Return p and t.

Example: We illustrate the above algorithm in an example. Let D = ’3,

k = 11 and r = 2147483713 = 231 + 26 + 1. Once can check that r is a prime

of low Hamming weight such that k divides (r ’ 1) and ( ’3 ) = 1.

r

An 11th root of unity modulo r is easily found by taking a random element

modulo r and raising it to the power (r ’ 1)/11. We take g = 865450015,

which gives a = (g + 1)/2 = 432725008. At this stage we know that r divides

((2a ’ 1)k ’ 1). √

Set b0 = (a ’ 1)/ D ≡ 1946126982 (mod r). Then r divides ((a ’

1)2 ’ Db2 ) and so, for every number of the form p = a2 ’ D(b0 + jr)2 , we

0

have r divides (p + 1 ’ 2a). For the values j = 17, 25, 41, 45, . . . we ¬nd that

a2 ’D(b0 +jr)2 is a prime. Taking j = 17 gives p = 4436167653364218931891

which has 72 bits.

The elliptic curve y 2 = x3 + 1 modulo p is seen to have p + 1 ’ 2a points

(which is divisible by r) and the ring generated by the Frobenius endomor-

phism has discriminant 4a2 ’ 4p = 4(b0 + 17r)2 D.

The main drawback of this algorithm is that p > r2 (compared with the

supersingular case, where we had p ≈ r). An algorithm with some features

similar to the above has been given by Dupont, Enge and Morain [109].

More sophisticated methods for generating curves with embedding degree

k > 6 have been given by Barreto, Lynn and Scott [17, 18] and Brezing and

212 IX. PAIRINGS

Weng [49]. In particular, their results have improved relationships between

the sizes of r and p for elliptic curves with embedding degree of special form

such as k = 2i 3j (e.g., k = 12). This problem is still an active area of research.

Appendix: Proof of Weil reciprocity

Before we can give the proof of Weil reciprocity we need some further

technical ingredients.

A non-constant rational map φ : C1 ’ C2 induces a map φ— : K(C2 ) ’

K(C1 ) on the function ¬elds given by φ— f = f —¦ φ. We can consider K(C1 )

as a ¬nite algebraic extension of φ— K(C2 ). The degree of φ is deg(φ) =

[K(C1 ) : φ— K(C2 )]. The map φ— : K(C1 ) ’ K(C2 ) is de¬ned by φ— f =

(φ— )’1 —¦NK(C1 )/φ— K(C2 ) (f ), where NK(C1 )/φ— K(C2 ) is the usual de¬nition of norm

for a ¬nite extension of ¬elds.

Given a non-constant rational map φ : C1 ’ C2 and a point P on C1

we may de¬ne the rami¬cation index eφ (P ) in terms of uniformizers (see

Silverman [307] II.2). The rami¬cation index satis¬es eφ (P )ordφ(P ) (f ) =

ordP (φ— f ) for any function f on C2 (see [307] Exercise 2.2). The map φ

induces maps between the divisors on C1 and C2 as follows. We have φ— :

Div(C2 ) ’ Div(C1 ) induced by φ— : (Q) ’ P ∈φ’1 (Q) eφ (P )(P ). We have

φ— : Div(C1 ) ’ Div(C2 ) induced by φ— : (Q) ’ (φ(Q)).

A non-constant function f on C can be thought of as a non-constant

rational map f : C ’ P1 over K. Given f : C ’ P1 we have (f ) =

f — ((0) ’ (∞)).

Lemma IX.26. Let φ : C1 ’ C2 be a non-constant rational map, let fi : Ci ’

P1 for i = 1, 2 be functions and let Di be divisors on Ci for i = 1, 2. We have

the following properties:

1. φ— ((f2 )) = (φ— f2 ).

2. φ— ((f1 )) = (φ— f1 ).

3. φ— —¦ φ— = [deg φ] in Div(C2 ).

4. f1 (φ— D2 ) = (φ— f1 )(D2 ).

5. f2 (φ— D1 ) = (φ— f2 )(D1 ).

Proof. For 1, 2 and 3 see Silverman [307, Proposition II.3.6]. For 4 and 5

see Silverman [307, Exercise 2.10].

Proof. (of Weil reciprocity Theorem IX.3) We ¬rst prove the result in the

case C = P1 . We identify P1 (K) with {a ∈ K} ∪ {∞}. A function f

on C is a ratio u(x, z)/v(x, z) of two homogeneous polynomials over K of

the same degree. In practice, we can consider the restriction of f to an

a¬ne set, and so write f as a ratio u(x)/v(x), where u(x), v(x) ∈ K[x].

If f = m (x ’ ai )nai , then (f ) = m

i=1 nai (ai ) ’ n∞ (∞), where n∞ =

i=1

m

i=1 nai = deg(u(x)) ’ deg(v(x)), and vice versa.

APPENDIX: PROOF OF WEIL RECIPROCITY 213

Let f be as above, let g = m (x ’ bj )nbj and suppose that both (f ) and

j=1

(g) have disjoint support with no points at in¬nity (in other words, ai = bj

for all i and j and m nai = m nbj = 0). Then

i=1 j=1

m m

(bj ’ ai )nai nbj

f ((g)) =

j=1 i=1

m m

m m

( nai nbj )

(ai ’ bj )nai nbj

i=1 j=1

= (’1)

j=1 i=1

= g((f ))

where the sign is 1 since

m m m m

= 0 · 0 = 0.

nai nbj = n ai nbj

i=1 j=1 i=1 j=1

The case where ∞ appears in the support of either (f ) or (g) arises when

the degree of the numerator is not equal to the degree of the denominator.

We de¬ne (∞ ’ bi )/(∞ ’ bj ) = 1 and the rest of the proof proceeds as before.

This proves the result for P1 .

In the general case let i be the identity function on P1 . Then (i) =

(0) ’ (∞) and as noted above (g) = g — ((i)). We therefore have

f ((g)) = f (g — ((i))) = (g— f )((i)).

Now, g— f is a function on P1 and so, by Weil reciprocity on P1 , we have

(g— f )((i)) = i((g— f )). To complete the proof we note that

i((g— f )) = (g — i)((f )) = i —¦ g((f )) = g((f )).

CHAPTER X

Cryptography from Pairings

K.G. Paterson

X.1. Introduction

This chapter presents a survey of positive applications of pairings in cryp-

tography. We assume the reader has a basic understanding of concepts from

cryptography such as public-key encryption, digital signatures, and key ex-

change protocols. A solid grounding in the general area of cryptography can

be obtained by reading [240].

We will attempt to show how pairings (as described in Chapter IX) have

been used to construct a wide range of cryptographic schemes, protocols and

infrastructures supporting the use of public-key cryptography. Recent years

have seen an explosion of interest in this topic, inspired mostly by three

key contributions: Sakai, Ohgishi and Kasahara™s early and much overlooked

work introducing pairing-based key agreement and signature schemes [284];

Joux™s three-party key agreement protocol as presented in [183]; and Boneh

and Franklin™s identity-based encryption (IBE) scheme built from pairings

[38]. The work of Verheul [335] has also been in¬‚uential because it eases

the cryptographic application of pairings. We will give detailed descriptions

of these works as the chapter unfolds. To comprehend the rate of increase

of research in this area, note that the bibliography of an earlier survey [273]

written in mid-2002 contains 28 items, while, at the time of writing in early

2004, Barreto™s website [15] lists over 100 research papers.1

Thus a survey such as this cannot hope to comprehensively cover all of

the pairing-based cryptographic research that has been produced. Instead,

we focus on presenting the small number of schemes that we consider to be

the high points in the area and which are likely to have a signi¬cant impact

on future research. We provide brief notes on most of the remaining literature

and omit some work entirely. We do not emphasise the technical details of

security proofs, but we do choose to focus on schemes that are supported by

such proofs.

1

A second source for papers on cryptography from pairings is the IACR preprint server

at http://eprint.iacr.org. Another survey on pairings and cryptography by Joux [184]

covers roughly the same topics as this and the previous chapter.

215

216 X. CRYPTOGRAPHY FROM PAIRINGS