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 ].
Search WWH ::




Custom Search