Cryptography Reference
In-Depth Information
Proof
Bilinearity can be proved using ideas similar to those used to prove Lemma
26.3.2
(for all the details see Theorem IX.7 of [
61
]). Non-degeneracy in the case of finite fields
was shown by Frey and R uck [
196
], but simpler proofs can be found in Hess [
256
] and
Section 11.7 of Washington [
560
]. Galois invariance is straightforward (see Theorem IX.7
of [
61
]).
26.3.1 Miller's algorithm
We now briefly explain how to compute the Tate-Lichtenbaum pairing (and hence the Weil
pairing via equation (
26.1
)). The algorithm first appears in Miller [
383
].
Definition 26.3.4
Let
P
∈
E
(
k
) and
i
∈ N
.A
Miller function
f
i,P
∈ k
(
E
)isafunctionon
E
such that div(
f
i,P
)
O
E
). Furthermore, we assume that Miller
functions are “normalised at infinity” in the sense that the power series expansion at infinity
with respect to the canonical uniformiser
t
∞
=
=
i
(
P
)
−
([
i
]
P
)
−
(
i
−
1)(
x/y
is 1.
Exercise 26.3.5
Show that
f
1
,P
=
1. Show that if
f
i,P
and
f
j,P
are Miller functions then
one can take
f
i
+
j,P
=
f
i,P
f
j,P
l
(
x,y
)
/v
(
x,y
)
where
l
(
x,y
) and
v
(
x,y
) are the lines arising in the elliptic curve addition of [
i
]
P
to
[
j
]
P
(and so div(
l
(
x,y
))
=
([
i
]
P
)
+
([
j
]
P
)
+
(
−
[
i
+
j
]
P
)
−
3(
O
E
) and div(
v
(
x,y
))
=
([
i
+
j
]
P
)
+
(
−
[
i
+
j
]
P
)
−
2(
O
E
)).
We can now give Miller's algorithm to compute
f
n,P
(
D
) for any divisor
D
(see Algo-
rithm
28
). The basic idea is to compute the Miller function out of smaller Miller func-
tions using a “square-and-multiply” strategy. As usual, we write an integer
n
in binary as
(1
n
m
−
1
...n
1
n
0
)
2
where
m
=
log
2
(
n
)
. Note that the lines
l
and
v
in lines 6 and/or 10 may
be simplified if the operation is [2]
T
=
O
E
.
The main observation is that Miller's algorithm takes
O
(log
2
(
n
)) iterations, each of which
comprises field operations in
=
O
E
or
T
+
P
). There are
a number of important tricks to speed up Miller's algorithm in practice; we mention some
of them in the following sections and refer to Chapter IX of [
61
], Chapter XII of [
286
]or
Section 16.4 of [
16
] for further details.
k
if
P
and all points in the support of
D
lie in
E
(
k
Exercise 26.3.6
Give simplified versions of lines 6 and 10 of Algorithm
28
that apply when
[2]
T
=
O
E
or
T
+
P
=
O
E
.
26.3.2 The reduced Tate-Lichtenbaum pairing
Definition 26.3.7
Let
n,q
∈ N
be such that gcd(
n,q
)
=
1. Define the
embedding degree
(
q
k
(
q,n
)
k
(
q,n
)
∈ N
to be the smallest positive (non-zero) integer such that
n
|
−
1).
Let
E
be an elliptic curve over
F
q
and suppose
n
|
#
E
(
F
q
) is such that gcd(
n,q
)
=
1. Let
k
(
q,n
) be the embedding degree. Then
µ
n
⊆ F
q
k
(in some cases
µ
n
can lie in a proper
subfield of
k
=
F
q
k
/
(
F
q
k
)
n
. In practice,
F
q
k
) and so the Tate-Lichtenbaum pairing maps into
