Parallel Pollard's Rho: Number of distinguished points

Question

When using the parallel version of Pollard's Rho algorithm for discrete logs, each processor performs its own random walk to find distinguished points, and reports the starting point and the distinguished point to the server. If two processors report the same distinguished point, then the server can re-do the random walk and find where the collision occurred and solve the discrete logarithm.

The average number of steps each processor must perform before finding a distinguished point depends on the number of distinguished bits. On average it is $2^d$ where $d$ is the number of distinguished bits.

If the attack is being run on systems with lots of slow processors (e.g. 100,000 GPUs each with thousands of threads), then its possible to come up with the required number of distinguished points without each processor coming close to $2^d$ iterations.

Suppose we have a 128-bit discrete log problem. We need ~$2^{64}$ group elements to solve it. We can do this with $2^{32}$ distinguished points with $32$ distinguished bits.

Suppose we are using a 50 billion processors that each do 20 steps per second (generate a trillion points per second).

So that is ~$2^{40} (\dfrac{1}{2^{32}})$ = $256$ distinguished points per second.

It will take about 194 days to find $2^{32}$ distinguished points.

But if each processor only walks $20$ steps per second, then each processor could only have walked at most $335,232,000$ steps, far less than the expected $2^{32}$.

That means each distinguished point reported to the server represents at most $369,782,000$ steps taken. So the total number of points between the starting points and distinguished points is far less than $2^{64}$

Question:

Does this mean it will require far more than $2^{32}$ distinguished points?

I think it will because the total number of points reported isn't enough to make a collision probable. We could say that each distinguished point represents $2^{32}$ points, but since the walks were so short, its more likely that any collision was the result of one random walk stepping into the starting point of another random walk, in which case the collision is useless (they call this a "Robin Hood" in the literature).

I think Parallel Pollards Rho favors a few very fast processors over many slow processors. Or many slow processors with short walks (fewer distinguished bits, more distinguished points) and lots of storage.

Answer 1

The expected number of points $\sqrt(\frac{n\cdot \pi}{2})$ is calculated via the birthday paradox and it applies to the number of calculated (not just distinguished/reported) points. As you said, each distinguished point represents $2^{32}$ points. Even if a collision is not reported (because it is not on a distinguished point), the two walks which collided will continue on the same path and eventually find the same distinguished point. That is where the ...$+\frac{1}{\theta}$ comes from in the complexity in the original Oorschot et Wiener paper. $\theta$ is the probability that a point is distinguished. So you have, the number of computations until a collision occurs, + the number of computations before that collision is reported i.e. before you reach the next distinguished point.

In practice, I haven't had a problem with Robin hoods, but Oorschot et Wiener seem to suggest that to avoid Robin hoods you need to take $\theta$ small enough that trails are long.