Cryptography Reference
In-Depth Information
is well-distributed),
θ>
log(
r
)
/
√
r
and when the
using a good hash function (and hence
D
function
walk
is chosen at random.
Heuristic 14.2.13
1. Walks reach a distinguished point in significantly fewer than
√
r
steps (in other words,
there are no cycles in the walks and walks are not excessively longer tha
n 1
/θ
).
6
2. The expected number of group elements sampled before a collision is
√
πr/
2.
Theorem 14.2.14
Let the notation be as above and assume Heuristic
14.2
.13
. Then
t
he
rho algorithm wi
th
distinguished points has expected running time of
(
√
π/
2
o
(1))
√
r
+
≈
o
(1))
√
r group operations. The probability the algorithm fails is negligible.
(1
.
253
+
Proof
Heuristic
14.2.13
states there are no cycles or “wasted” walks (in the sense that
their steps do not contribute to potential collisions). Hence, before the first collision, after
N
steps of the algorithm we have visited
N
group elements. By Heuristic
1
4.2.13
,the
expected number of group elements to be sampled before the first collision is
√
πr/
2. The
collision is not detected until walks hit a distinguished point, which adds a further 2
/θ
to
the number of
steps
. Hence, the total numb
er
of steps (calls t
o
the function
walk
)inthe
algorithm is
√
πr/
2
2
/θ
. Since 2
/θ <
2
√
r/
log(
r
)
o
(1)
√
r
, the result follows.
+
=
g
a
j
h
b
j
be the collision. Since the starting values
g
a
0
h
b
0
are chosen
uniformly and independently at random, the values
b
i
and
b
j
are uniformly and indepen-
dently random. It follows that
b
i
≡
g
a
i
h
b
i
Let
x
=
=
b
j
(mod
r
) with probability 1
/r
, which is a negligible
quantity in the input size of the problem.
log(
r
)
/
√
r
then the expected storage of the rho algo-
rithm, assuming it takes
O
(
√
r
) steps, is
O
(log(
r
)) group elements (which is typically
O
(log(
r
)
2
) bits).
Exercise 14.2.15
Show that if
θ
=
Exercise 14.2.16
The algorithm requires storing a triple (
x
n
,a
n
,b
n
) for each distinguished
point. Give some strategies to reduce the number of bits that need to be stored.
be a group of order
r
2
Exercise 14.2.17
Let
G
=
g
1
,g
2
and exponent
r
.Designarho
g
a
1
g
a
2
. Determine the
algorithm which, on input
h
∈
G
outputs (
a
1
,a
2
) such that
h
=
complexity of this algorithm.
Exercise 14.2.18
Show that the Pollard rho algorithm with distinguished points has better
average-case running time than the BSGS algorithm (see Exercises
13.3.3
and
13.3.4
).
Exercise 14.2.19
Explain why taking
G
(i.e., all group elements distinguished) leads
to an algorithm that is much slower than the BSGS algorithm.
D
=
Suppose one is given
g,h
1
,...,h
L
(where 1
<L<r
1
/
4
) and is asked to find all
a
i
for
g
a
i
. Kuhn and Struik [
320
] propose and analyse a method to solve
1
≤
i
≤
L
such that
h
i
=
6
More realistically, one could assume that only a negligibly small proportion of the walks fall into a cycle before hitting a
distinguished point.
