-snip-
But can you treat these points like if they were random? Can you apply in this case the birthday paradox?
The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that
pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case.
From here the definition (page 4, 1st par):
https://eprint.iacr.org/2014/565.pdfa point is a distinguished point - if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal
to zero. Whenever one of the parallel random walks reaches such a point it is stored on a central processor