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




Custom Search