Cryptography Reference
In-Depth Information
26
Pairings on elliptic curves
This chapter is a very brief summary of the mathematics behind pairings on elliptic curves.
Some applications of pairings in elliptic curve cryptography have already been presented in
the topic (for example, the identity-based encryption scheme of Boneh and Franklin in Sec-
tion
23.3.2
and the Boneh-Boyen signature scheme in Section
22.2.3
). We present several
other important applications of pairings, such as the Menezes-Okamoto-Vanstone/Frey-
Ruck reduction of the discrete logarithm problem from elliptic curves to finite fields.
Due to lack of space we do not give full details of the subject. Good general references
for pairings and pairing-based cryptography are Chapters IX and X of [
61
], Chapters 6, 16
and 24 of [
16
] and [
286
].
26.1 Weil reciprocity
The following theorem is an important tool for studying pairings. Recall that a divisor on a
curve
C
over
a
field
=
P
∈
C
(
k
)
n
P
(
P
) (i.e.,
n
P
=
k
is a finite sum
D
0 for all but fini
te
ly
many
P
∈
C
(
k
)). The support of a divisor
D
is the set of points Supp(
D
)
={
P
∈
C
(
k
):
n
P
=
. To a function
f
on a curve one associates the divisor div(
f
) as in Definition
7.7.2
.
If
f
is a function on a curve and
D
is a divisor such that the support of
D
is distinct from
the support of div(
f
) then
f
(
D
) is defined to be
P
∈
C
(
k
)
,n
P
=
0
f
(
P
)
n
P
.
0
}
Exercise 26.1.1
Let
D
1
and
D
2
be divisors with disjoint support on a curve
C
. Suppose
D
1
is principal. Show that
f
(
D
2
) is well-defined, subject to div(
f
)
=
D
1
, if and only if
D
2
has degree 0.
k
∈ k
Theorem 26.1.2
(
Weil reciprocity
) Let C be a curve over a field
. Let f,g
(
C
)
be
functions such that
Supp(div(
f
))
∩
Supp(div(
g
))
= ∅
. Then
f
(div(
g
))
=
g
(div(
f
))
.
1
. Then
Proof
(Sketch) One first shows that the result holds for functions on
C
= P
1
and apply the pullback. We refer to the appendix of
Chapter IX of [
61
] for details. A proof over
take any covering
φ
:
C
→ P
C
is given in the appendix to Section 18.1 of
Lang [
328
].
