Cryptography Reference
In-Depth Information
There is an alternative definition
1
of the Weil pairing that is more useful for imple-
mentation, but for which it is harder to prove non-degeneracy. For
P,Q
∈
E
[
n
]let
D
P
and
D
Q
be degree 0 divisors such tha
t
D
P
≡
(
P
)
−
(
O
E
),
D
Q
≡
(
Q
)
−
(
O
E
) and
Supp(
D
P
)
∩
Supp(
D
Q
)
= ∅
.Let
f
P
,f
Q
∈ k
(
E
) be functions such that div(
f
P
)
=
nD
P
and div(
f
Q
)
=
nD
Q
. Then
=
e
n
(
P,Q
)
f
Q
(
D
P
)
/f
P
(
D
Q
)
.
(26.1)
The equivalence is shown in Theorem 4 of the extended and unpublished version of
Hess [
256
], and in Section 11.6.1 of Washington [
560
].
The Weil pairing can be generalised from
E
[
n
]
ker(
φ
)
×
E
[
n
]toker(
φ
)
×
⊆
E
[
n
]
×
E
[
n
] where
φ
:
E
→
E
is an isogeny. For details see Exercise 3.15 of Silverman [
505
]or
Garefalakis [
219
]. For the Weil pairing on Jacobian varieties of curves of genus
g>
1we
refer to Section 20 of Mumford [
398
].
26.3 The Tate-Lichtenbaum pairing
Tate defined a pairing for Abelian varieties over local fields and Lichtenbaum showed how to
compute it efficiently in the case of Jacobian varieties of curves. Frey and Ruck [
196
]showed
how to compute it for elliptic curves over finite fields, and emphasised its cryptographic
relevance. This pairing is the basic building block of most pairing-based cryptography.
Exercise 26.3.1
Let
E
be an elliptic curve over a finite field
F
q
and let
n
∈ N
be such that
gcd(
n,q
)
=
1 and
n
|
#
E
(
F
q
). Define
nE
(
F
q
)
={
[
n
]
Q
:
Q
∈
E
(
F
q
)
}
.
Show
that
nE
(
F
q
)
is
a
group.
Show
that
E
(
F
q
)[
n
]
={
P
∈
E
(
F
q
):[
n
]
P
=
O
E
}
,
F
q
/
(
F
q
)
n
are finite groups of exponent
E
(
F
q
)
/nE
(
F
q
)
={
P
+
nE
(
F
q
):
P
∈
E
(
F
q
)
}
and
n
.
Let notation be as in Exercise
26.3.1
.Let
P
∈
E
(
F
q
)[
n
] and
Q
∈
E
(
F
q
). Then
n
(
P
)
−
n
(
O
E
) is principal, so there is a function
f
∈ F
q
(
E
) such that div(
f
)
=
n
(
P
)
−
n
(
O
E
). Let
D
be a divisor on
E
with support disjoint from Supp(div(
f
))
={
O
E
,P
}
but such that
D
is
(
R
) for some point
2
R
equivalent to (
Q
)
−
(
O
E
) (for example,
D
=
(
Q
+
R
)
−
∈
E
(
F
q
),
R
∈{
O
E
,P,
−
Q,P
−
Q
}
). We define the
Tate-Lichtenbaum pairing
to be
t
n
(
P,Q
)
=
f
(
D
)
.
(26.2)
We will explain below that
→ F
q
/
(
F
q
)
n
.
t
n
:
E
(
F
q
)[
n
]
×
E
(
F
q
)
/nE
(
F
q
)
1
The literature is inconsistent and some of the definitions (for example, Section 18.1 of Lang [
328
], Exercise 3.16 of Silver-
man [
505
] and Section 3 of Miller [
383
]) are actually for
e
n
(
Q,P
)
=
e
n
(
P,Q
)
−
1
. For further discussion of this issue see
Remark 11.3 and Section 11.6 of Washington [
560
]. Also see the “Warning” at the end of Section 4 of Miller [
385
].
2
One can usually take
R
∈
E
(
F
q
), but see page 187 of [
61
] for an example that shows that this is not always possible.