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




Custom Search