Cryptography Reference
In-Depth Information
point visited by another processor then the walks from that point agree and both walks end
at the same distinguished point. When the server receives two triples (
x,a,b
) and (
x,a
,b
)
for the same group element
x
but with
b
g
a
h
b
and can
solve the DLP as in the serial (i.e., non-parallel) case. The server therefore computes the
discrete logarithm problem and sends a terminate signal to all processors. Pseudocode for
both server and clients are given by Algorithms
16
and
17
. By design, if the algorithm halts
then the answer is correct.
b
(mod
r
) then it has
g
a
h
b
≡
=
Algorithm 16
The distributed rho algorithm: server side
INPUT:
g,h
G
OUTPUT:
c
such that
h
∈
g
c
1:
Randomly choose a walk function
walk
(
x,a,b
)
2:
Initialise an easily searched structure
L
(sorted list, binary tree etc) to be empty
3:
Start all processors with the function
walk
4:
while
DLP not solved
do
5:
=
Receive triples (
x,a,b
) from clients and insert into
L
if
first coordinate of new triple (
x,a,b
) matches existing triple (
x,a
,b
)
then
6:
if
b
≡
b
(mod
r
)
then
7:
Send terminate signal to all clients
8:
a
)(
b
−
b
)
−
1
return
(
a
−
(mod
r
)
9:
10:
end if
11:
end if
12:
end while
Algorithm 17
The distributed rho algorithm: client side
INPUT:
g,h
G
, function
walk
1:
while
terminate signal not received
do
2:
∈
Choose uniformly at random 0
≤
a,b<r
g
a
h
b
Set
x
=
3:
∈
D
while
x
do
4:
=
(
x,a,b
)
walk
(
x,a,b
)
5:
6:
end while
7:
Send (
x,a,b
)toserver
8:
end while
We now analyse the performance of this algorithm. To get a clean result we assume that
no client ever crashes, that communications between server and client are perfectly reliable,
that all clients have the same computational efficiency and are running continuously (in
other words, each processor computes the same number of group operations in any given
time period).
