<<

. 7
( 10)



>>

Bilinearity: For all P, P ∈ G1 and all Q, Q ∈ G2 we have
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

<<

. 7
( 10)



>>