Cryptography Reference
In-Depth Information
Exercise 14.5.6
Show that, with the above choice of
m
, the expected nu
mb
er of group
operations performed for the worst case of problem instances is (3
o
(1))
√
w
. Determine
the optimal choice of
m
to minimise the expected worst-case running time. What is the
expected worst-case complexity?
+
Exercise 14.5.7
A card trick known as
Kruskal's principle
is as follows. Shuffle a deck
of 52 playing cards and deal face up in a row. Define the following walk along the row of
cards: if the number of the current card is
i
then step forward
i
cards (if the card is a King,
Queen or Jack then step 5 cards). The magicican runs this walk (in their mind) from the
first card and puts a coin on the last card visited by the walk. The magician invites their
audience to choose a number
j
between 1 and 10, then runs the walk from the
j
th card. The
magician wins if the walk also lands on the card with the coin. Determine the probability
of success of this trick.
Exercise 14.5.8
Show how to use the kangaroo method to solve Exercises
13.3.8
,
13.3.10
and
13.3.11
of Chapter
13
.
Pollard's original proposal did not use distinguished points and the algorithm only had
a fixed probability of success. In contrast, the method we have described keeps on running
until it succeeds (indeed, if the DLP is insoluble then the algorithm would never terminate).
Van Oorschot and Wiener (see page 12 of [
423
]) have shown that repeating Pollard's original
metho
d u
ntil it succeeds leads to a method with expected running time of approximately
3
.
28
√
w
group operations.
Exercise 14.5.9
Suppose one is given
g
G
of order
r
, an integer
w
and an instance
generator for the discrete logarithm problem that outputs
h
∈
g
a
=
∈
G
such that 0
≤
a<w
according to some known distribution on
. Assume that the distribution
is symmetric with mean value
w/
2. How should one modify the kangaroo method to take
account of this extra information? What is the running time?
{
0
,
1
,...,w
−
1
}
14.5.4 Comparison with the rho algorithm
We now consider whether one should use the rho or kangaroo algorithm when solving a
general discrete logarithm problem (i.e., where the width
w
of t
he
interval is equal to, or
close to,
r
). If
w
r
then the rho method r
eq
uires roughly 1
.
25
√
r
group operations while
the kangaroo method requires roughly 2
√
r
group operations. The heuristic assumptions
underlying both methods are similar, and in practice they work as well as the theory
predicts. Hence, it is clear that the rho method is preferable, unless
w
is much smaller
than
r
.
=
Exercise 14.5.10
Determine the interval size below which it is preferable to use the
kangaroo algorithm over the rho algorithm.
