To give credit where credit is due, the explanations were primarily adapted from those available in [1]. There are earlier explanations of the concept, but I feel this is the most readily understandable.
The Standard Version
\[ (a,b) \mapsto aP + bQ. \]
Given this collision \((a, a', b, b')\) we can, with high probability, compute the scalar \(n\). Finding this collision is done by iterating a function \(f\) that, from one linear combination of \(P, Q\), outputs another valid linear combination of \(P, Q\). The standard version simply computes one long chain of iterations until it detects a cycle in this chain, yielding the necessary collision.
If the output of \(f\) produces random linear combinations of \(P\) and \(Q\) and \(l\) is the order of \(P\), we expect to need \(\sqrt{\pi l / 2}\) iterations to succeed, as per the standard birthday problem. This is known as a random walk.
Figure 1: A collision in the standard version of Pollard's rho method. |
The Parallel Version
You could theoretically build a parallel version of Pollard rho by simply defining \(m\) distinct starting points for \(m\) chains. You then would run the algorithm in parallel on all the chains and wait for one to finish. However, we can do better.
While often Pollard's rho method is framed in terms of finding a cycle, we are actually finding a collision. This means we can apply Van Oorschot and Wiener's [2] techniques for parallel collision search. Intuitively, we still take \(m\) different starting points \(W_0^i\) and have them iterate a function \(f\). However, every walk now sends its point to the same central location. Here we simply keep track of all incoming points and when a collision is found we are done.
Figure 2: A collision in the parallel version of Pollard's rho method. |
Thankfully, we know how to solve this. We simply output only those points which have a particular property that occurs with a certain probability. We call these distinguished points and the related property the distinguished point property. The computation of this property should be efficient and it is very convenient if the probability can be tweaked.
For example, given a point \(P = (x,y)\), only output \(P\) if the binary representation of \(x\) has at least \(n\) leading zeroes. This is very fast to compute and it can be trivially adjusted by changing \(n\).
Note that we can do this without loss of functionality. Once a collision occurs between two walks, every subsequent point also collides. This means we find a collision at the next distinguished point the converged walks reach, assuming we do not enter a cycle before then.
References
[1] | Daniel J. Bernstein, Tanja Lange, and Peter Schwabe. On the correct use of the negation map in the Pollard rho method. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, Public Key Cryptography -- PKC 2011, volume 6571 of Lecture Notes in Computer Science, pages 128--146. Springer-Verlag Berlin Heidelberg, 2011. http://cr.yp.to/papers.html#negation. |
[2] | Paul C. Van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. Journal of cryptology, 12(1):1--28, 1999. |
No comments:
Post a Comment