Cryptography Reference
In-Depth Information
Algorithm 4
Computing set of exponentials of products
INPUT:
N
1
,...,N
m
OUTPUT:
g
N/N
i
:1
{
≤
i
≤
m
}
1:
k
=
log
2
(
m
)
g
N
2
k
−
1
+
1
···
N
2
k
,
h
1
,
2
=
g
N
1
···
N
2
k
−
1
2:
h
1
,
1
=
3:
for
l
=
2to
k
do
1to2
l
do
for
j
=
4:
j
1
=
j/
2
5:
h
i
∈
S
l
−
1
,j
1
−
S
l,j
N
i
l
−
1
,j
1
h
l,j
=
6:
7:
end for
8:
end for
9:
return
{
h
k,
1
,...,h
k,m
}
Lemma 2.15.7
Algorithm
4
is correct and requires
≤
2
log
2
(
m
)
log(
N
)
group operations.
Proof
Almost everything is left as an exercise. The important observation is that lines 4 to
7 involve raising to the power
N
i
for all
i
∈
S
. Hence, the cost for each iteration of the loop
in line 3 is at most 2
2
k
i
=
1
log
2
(
N
i
)
=
2log
2
(
N
).
This method works efficiently in all cases (i.e., it does not require
m
to be large).
However, Exercise
2.15.8
shows that for small values of
m
there may be more efficient
solutions.
Exercise 2.15.8
Let
N
=
N
1
N
2
N
3
where
N
i
≈
N
1
/
3
for 1
≤
i
≤
3. One can compute
g
N/N
i
3 using Algorithm
4
or in the “naive” way. Suppose one uses the
standard square-and-multiply method for exponentiation and assume that each of
N
1
,N
2
and
N
3
has Hamming weight about half their bit-length.
Note that the exponentiations in the naive solution are all with respect to the fixed base
g
.
A simple optimisation is therefore to precompute all
g
2
j
for 1
for 1
≤
i
≤
log
2
(
N
2
/
3
). Determine
the number of group operations for each algorithm if this optimisation is performed. Which
is better?
≤
j
≤
Remark 2.15.9
Sutherland gives an improved algorithm (which he calls the
snowball
algorithm
) as Algorithm 7.4 of [
536
]. Proposition 7.3 of [
536
] states that the complexity
is
O
(log(
N
) log(
m
)
/
log(log(
m
)))
(2.6)
group operations.