Cryptography Reference
In-Depth Information
is not necessarily optimal since #
S
3
. Kim and Cheon [
304
] generalised the
results of Section
13.6
to allow a more balanced time/memory tradeoff. This gives a small
improvement to the running time.
Cheon and Kim [
125
] give a further improvement to the attack, which is similar to
the use of equivalence classes in Pollard rho (see Section
14.4
). They noted that the sets
S
j
in the Hoffstein-Silverman proposal have the property that for every
a
S
1
#
S
2
=
#
∈
S
j
there is
some
a
∈
S
j
such that
g
a
π
p
(
g
a
). In other words,
π
p
permutes
=
S
j
and each element
a
∈
S
j
lies in an orbit of size
n
under this permutation. Cheon and Kim define a unique
representative of each orbit of
π
p
in
S
j
and show how to speed up the BSGS algorithm in
this case by a factor of
n
.
Exercise 13.7.1
Give the details of the Cheon-Kim algorithm. How many group opera-
tions does the algorithm perform when
n
=
163, and three sets with
w
=
7 are used?
