Cryptography Reference
In-Depth Information
It is appropriate to ignore the computation performed by the server and instead to focus
on the number of group operations performed by each client running Algorithm
17
. Each
execution of the function
walk
(
x,a,b
) involves a single group operation. We must also
count the number of group operations performed in line 3 of Algorithm
17
; though this
term is negligible if walks are long on average (i.e., if
is a sufficiently small subset of
G
).
It is an open problem to give a rigorous analysis of the distributed rho method. Hence, we
make the following heuristic assumption. We believe th
is
assumption is reasonable when
r
is sufficiently large,
n
S
is sufficiently large, log(
r
)
/
√
r<θ
,theset
D
of distinguished
points is determined
by a
good hash function, the number
N
P
of clients is sufficiently
D
small (e.g.,
N
P
<θ
√
πr/
2
/
log(
r
), see Exercise
14.3.3
) and the function
walk
is chosen at
random.
Heuristic 14.3.1
1. The expected num
ber o
f group elements to be sampled before the same element is
sampled twice is
√
πr/
2.
2. Walks reach a distinguished point in significantly fewer than
√
r/N
P
steps (in other
words, there are no cycles in the walks and walks are not excessively long). More
realistically, one could assume that only a negligible proportion of the walks fall into a
cycle before hitting a distinguished point.
Theorem 14.3.2
Let the notation be as above, in particular let N
P
be the (fixed, inde-
pendent of r) number of clients. Let θ the probability that a group element is a dis-
tinguished point and suppose
log(
r
)
/
√
r<θ. Assume Heuristic
14.3.1
and the above
assumptions about the reliability and equal power of the processors hold. Then the expected
number of group
oper
ations performed by each client of the
dist
ributed rho m
et
hod is
(1
o
(1
))
√
r
group
operations when θ<
1
/
log(
r
)
2
. The storage requirement on the server is θ
√
πr/
2
2log(
r
)
θ
)
√
πr/
2
/N
P
+
1
/θ group operations. This is
(
√
π/
2
/N
P
+
+
+
N
P
points.
Proof
Heuristic
14.3.1
states that we expect to sample
√
πr/
2 group elements in total
before a collision arises. Since this work is distributed over
N
P
clie
nts o
f equal speed it
follows that each client is expected to call the f
uncti
on
walk
about
√
πr/
2
/N
P
times. The
total number of group operations is therefore
√
πr/
2
/N
P
plus 2 log(
r
)
θ
√
πr/
2
/N
P
for the
work of line 3 of Algorithm
17
. The server will not detect the collision until the second
client hits a distinguished point, which is expected to take 1
/θ
further step
s by t
he heuristic
(part 3 of Lemma
14.2.12
). Hence, each client needs to run an expected
√
πr/
2
/N
P
+
1
/θ
steps of the walk.
Of course, a collision
g
a
h
b
g
a
h
b
can be useless in the sense that
b
≡
=
b
(mod
r
). A
collision implies
a
+
g
c
; there are
r
such pairs (
a
,b
)for
each pair (
a,b
). Since each walk starts with uniformly random values (
a
0
,b
0
) it follows that
the values (
a,b
) are uniformly distributed over the
r
possibilities. Hence, the probability
of a collision being useless is 1
/r
and the expected number of collisions required is 1.
cb
≡
a
+
cb
(mod
r
) where
h
=
