Cryptography Reference
In-Depth Information
Tate-Lichtenbaum pairing as a map
ˆ
t
r
:
E
[
r
]
×
E
[
r
]
→
µ
r
just as the Weil pairing is.
Exercise 26.3.10
Let
E
be an elliptic curve over
F
q
and let
r
be a prime such that
r
#
E
(
F
q
),
F
q
k
) and
r
2
gcd(
r,q
)
=
1,
E
[
r
]
⊆
E
(
#
E
(
F
q
k
), where
k
=
k
(
q,r
) is the embedding degree.
Show that
E
[
r
] is set of representatives for
E
(
F
q
k
)
/rE
(
F
q
k
).
In most cryptographic situations one restricts to the case of points of prime order
r
.
Further, one can often insist that
P
∈
F
q
) and
Q
∈
F
q
k
). An important observation is
E
(
E
(
∈ F
q
then
z
(
q
k
−
1)
/r
that if
k>
1 and
z
1. This allows us to omit some computations in
Miller's algorithm. A further trick, due
4
to Barreto, Kim, Lynn and Scott [
27
], is given in
Lemma
26.3.11
(a similar fact for the Weil pairing is given in Proposition 8 of Miller [
385
]).
=
Lemma 26.3.11
Let E be an elliptic curve over
F
q
, P
∈
E
(
F
q
)
a point of prime order r
(where r>
4
and
gcd(
q,r
)
=
1
) and Q
∈
E
(
F
q
k
)
−
E
(
F
q
)
where k>
1
is the embedding
degree. Then
f
r,P
(
Q
)
(
q
k
ˆ
t
r
(
P,Q
)
−
1)
/r
.
=
Proof
A proof for general curves (and without any restriction on
r
)isgiveninLemma1of
Granger, Hess, Oyono, Theriault and Vercauteren [
241
]. We give a similar argument.
We
ˆ
t
r
(
P,Q
)
(
R
))
(
q
k
−
1)
/r
have
=
f
r,P
((
Q
+
R
)
−
for
any
point
R
∈
E
(
F
q
k
)
−
∈ F
q
and
k>
1it
{
O
E
,P,
−
Q,P
−
Q
}
. Choose
R
∈
E
(
F
q
)
−{
O
E
,P
}
. Since
f
r,P
(
R
)
follows that
R
)
(
q
k
−
1)
/r
.
ˆ
t
r
(
P,Q
)
=
f
r,P
(
Q
+
Now, it is not possible to take
R
=
O
E
in the above argument. Instead we need to prove
R
)
(
q
k
f
r,P
(
Q
)
(
q
k
−
1)
/r
−
1)
/r
directly. It suffices to prove that
that
f
r,P
(
Q
+
=
(
Q
))
(
q
k
−
1)
/r
f
r,P
((
Q
+
R
)
−
=
1
.
To do this, note that (
Q
+
R
)
−
(
Q
)
≡
(
R
)
−
(
O
E
)
≡
([2]
R
)
−
(
R
). Set, for example,
R
=
[2]
P
so that ([2]
R
)
−
(
R
) has support disjoint from
{
O
E
,P
}
(this is where the con-
dition
r>
4 is used). Then there is a function
h
∈ F
q
k
(
E
) such that (
Q
+
R
)
−
(
Q
)
=
([2]
R
)
−
(
R
)
+
div(
h
). We have
f
r,P
((
Q
+
R
)
−
(
Q
))
=
f
r,p
(([2]
R
)
−
(
R
)
+
div(
h
))
=
f
r,P
(([2]
R
)
−
(
R
))
h
(div(
f
r,P
))
.
∈ F
q
and that
h
(div(
f
r,P
))
F
q
k
)
r
.
Finally, note that
f
r,P
(([2]
R
)
−
(
R
))
=
(
h
(
P
)
/h
(
O
E
))
r
∈
(
The result follows.
(
q
k/
2
Exercise 26.3.12
Let the embedding degree
k
be even,
r
−
1),
P
∈
E
(
F
q
) and
Q
=
(
x
Q
,y
Q
)
∈
E
(
F
q
k
) points of order
r
. Suppose
x
Q
∈ F
q
k/
2
(this is usually the case for
4
Though be warned that the “proof” in [
27
] is not rigorous.
