Cryptography Reference
In-Depth Information
Theorem 26.2.3
The Weil pairing satisfies the following properties.
1. (Bilinear)
For P
1
,P
2
,Q
∈
E
[
n
]
, e
n
(
P
1
+
P
2
,Q
)
=
e
n
(
P
1
,Q
)
e
n
(
P
2
,Q
)
and
e
n
(
Q,P
1
)
e
n
(
Q,P
2
)
.
2. (Alternating) For P
e
n
(
Q,P
1
+
P
2
)
=
∈
E
[
n
]
, e
n
(
P,P
)
=
1
.
3. (Non-degenerate) If e
n
(
P,Q
)
=
1
for all Q
∈
E
[
n
]
then
P
=
O
E
.
4. (Galois invariant) If E is defined over
k
and σ
∈
Gal(
k
/
k
)
then e
n
(
σ
(
P
)
,σ
(
Q
))
=
σ
(
e
n
(
P,Q
))
.
5. (Compatible) If P
∈
E
[
nm
]
and Q
∈
E
[
n
]
then
=
e
nm
(
P,Q
)
e
n
([
m
]
P,Q
)
.
Proof
See Theorem III.8.1 of Silverman [
505
] or Theorem 11.7 of Washington [
560
]. The
non-degeneracy proof in [
505
] is ve
ry
sketchy (the reference to 4.10(b) only relates the
translation map to a Galois map on
(
E
)), but the treatment in [
560
] fills in the missing
details. The non-degeneracy also needs the fact that the genus of
E
is not zero, so there is
no function with divisor (
P
)
k
−
(
O
E
) (see Corollary
8.6.5
).
Exercise 26.2.4
Show that any function
e
:
E
[
n
]
µ
n
that has the properties of
the Weil pairing as in Theorem
26.2.3
also has the following properties.
×
E
[
n
]
→
1.
e
(
O
E
,P
)
=
e
(
P,
O
E
)
=
1 for all
P
∈
E
[
n
].
e
(
P,Q
)
−
1
2.
e
(
−
P,Q
)
=
for all
P,Q
∈
E
[
n
].
e
(
Q,P
)
−
1
3.
e
(
P,Q
)
=
for all
P,Q
∈
E
[
n
].
4. If
{
P,Q
}
generate
E
[
n
] then the values of
e
on
E
[
n
]
×
E
[
n
] are uniquely determined
by the single value
e
(
P,Q
).
Exercise 26.2.5
Let
E
be an elliptic curve over
F
q
and let
n
∈ N
. Prove that
E
[
n
]
⊆
E
(
F
q
)
implies
n
|
(
q
−
1).
C
For elliptic curves over
the Weil pairing has a very simple interpretation. Recall that
C
C
an elliptic curve over
/L
where
L
is a lattice of
rank 2 and that this isomorphism also preserves the group structure. Fix a pair
is isomorphic (as a manifold) to
{
z
1
,z
2
}
of
1
generators for
L
as a
Z
-module. The points of order
n
are
n
L/L
, so are identified with
{
(
az
1
+
bz
2
)
/n
:0
≤
a,b<n
}
. The function
e
n
((
az
1
+
bz
2
)
/n,
(
cz
1
+
dz
2
)
/n
)
=
exp(2
πi
(
ad
−
bc
)
/n
)
is easily checked to be bilinear, non-degenerate and alternating. Hence, it is (a power of)
the Weil pairing. We refer to the appendix of Section 18.1 of Lang [
328
] for further details.
Connections with the intersection pairing are discussed in Section 12.2 of Husemoller [
272
]
and Edixhoven [
174
].