Cryptography Reference
In-Depth Information
Algorithm 13.1:
Miller's algorithm to compute
f
n
,
P
(
Q
)
=
i
=
0
n
i
2
i
Input
:
P
=
(
x
P
,
y
P
)
∈
G
1
,
Q
=
(
x
Q
,
y
Q
)
∈
G
2
and
n
Output
:
f
n
,
P
(
Q
)
∈
F
q
k
f
←
1
1
2
T
←
P
3
for
i
=
s
−
1
downto
0
do
f
2
←
·
l
T
,
T
(
Q
)/
v
2
·
T
(
Q
)
f
4
T
←[
2
]
T
5
if
n
i
=
1
then
6
f
2
f
←
·
l
T
,
P
(
Q
)/
v
T
+
P
(
Q
)
7
T
←
T
+
P
8
9
end
10
end
11
return
f
f
r
,
P
(
Q
)
r
e
W
(
P
,
Q
)
=
(
−
1
)
)
.
f
r
,
Q
(
P
The most important properties of the Weil pairing are that the pairing is bilinear,
nondegenerate, i.e., for every non-zero
P
∈
E
(
F
q
k
)
[
r
]
, there exists
Q
∈
E
(
F
q
k
)
[
r
]
such that
e
W
(
P
,
Q
)
=
1, and that it is reduced, i.e.,
e
W
(
P
,
Q
)
is an
r
th root of unity
in
F
q
k
. Note that the Weil pairing requires two evaluations of Miller functions.
13.2.2 The Tate Pairing
The Tate pairing [396], or more correctly the Tate-Lichtenbaum [145, 146, 255]
pairing, is defined as follows: let
P
∈
E
(
F
q
k
)
[
r
]
and
Q
∈
E
(
F
q
k
)/
rE
(
F
q
k
)
with
P
=
Q
; then
)
·
(
F
q
k
)
r
e
T
(
P
,
Q
)
=
f
r
,
P
(
Q
.
The result of the Tate pairing is only defined up to an
r
th power. In order to obtain
a unique value, the output is raised to the power
q
k
(
−
)/
1
r
, which results in the
reduced Tate pairing, namely
p
k
−
1
e
T
(
ˆ
,
)
=
f
r
,
P
(
)
.
P
Q
Q
r
The computation of
f
r
,
P
(
Q
)
is typically called the Miller loop, whereas the subse-
p
k
−
1
r
quent computation of
f
r
,
P
(
Q
)
is called the final powering (or final exponentia-
tion).
The main properties are similar to those of the Weil pairing. All other pairings
discussed in this chapter are simply efficient methods to compute a fixed power of the
