Cryptography Reference
In-Depth Information
Algorithm 28
Miller's algorithm
INPUT:
n
=
(1
n
m
−
1
...n
1
n
0
)
2
∈ N
,
P
∈
E
(
k
), such that [
n
]
P
=
O
E
,
D
∈
Div
(
E
)
k
OUTPUT:
f
n,P
(
D
)
1:
f
=
1
2:
T
=
P
3:
i
=
m
−
1
=
log
2
(
n
)
−
1
4:
while
i
≥
0
do
Calculate lines
l
and
v
for doubling
T
5:
f
2
f
=
·
l
(
D
)
/v
(
D
)
6:
T
=
[2]
T
7:
if
n
i
=
1
then
8:
Calculate lines
l
and
v
for addition of
T
and
P
9:
f
=
f
·
l
(
D
)
/v
(
D
)
10:
T
=
T
+
P
11:
end if
12:
i
=
i
−
1
13:
14:
end while
15:
return
f
it is inconvenient to have a pairing taking values in this quotient group, as cryptographic
protocols require well-defined values. To have a canonical representative for each coset in
F
q
k
/
(
F
q
k
)
n
it would be much more convenient to use
µ
n
. This is easily achieved using the
facts that if
z
∈ F
q
k
then
z
(
q
k
−
1)
/n
F
q
k
)
n
and
z
2
(
F
q
k
)
n
are equal
∈
µ
n
, and that the cosets
z
1
(
if and only if
z
(
q
k
−
1)
/n
z
(
q
k
−
1)
/n
=
. Also, exponentiation is a group homomorphism from
1
2
F
q
k
/
(
F
q
k
)
n
to
µ
n
.
For this reason, one usually considers the
reduced Tate-Lichtenbaum pairing
t
n
(
P,Q
)
(
q
k
ˆ
t
n
(
P,Q
)
−
1)
/n
,
=
F
q
)[
n
]
×
F
q
)
/nE
(
F
q
)to
µ
n
.
The exponentiation to the power (
q
k
−
which maps
E
(
E
(
1)
/n
is called the
final exponentiation
.
(
q
k
Exercise 26.3.8
Let
n
|
N
|
−
1). Show that
t
n
(
P,Q
)
(
q
k
t
N
(
P,Q
)
(
q
k
−
1)
/n
−
1)
/N
.
=
Exercise 26.3.9
Explain why working in a group whose order has low Hamming weight
leads to relatively fast pairings. Suppose
n
n
does
not. Explain how to compute the reduced Tate-Lichtenbaum pairing
ˆ
t
r
(
P,Q
) efficiently if
n/r
is small.
=
E
(
F
q
) has low Hamming weight but
r
|
In the applications, one usually chooses the elliptic curve
E
to satisfy the mild conditions
in Exercise
26.3.10
. In these cases, it follows from the Exercise that we can identify
E
(
F
q
k
)
/rE
(
F
q
k
) with
E
(
F
q
k
)[
r
]. Hence, if the conditions hold, we may interpret the reduced