2
$\begingroup$

I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group.

He has a Kangaroo Algorithm (page 4) which allows you, if you know that $x$ is in a range of size $w$, to find $x$ in time $O (\sqrt{w})$ and constant space. Very cool. This algorithm is also well described on the Wikipedia page.

There doesn't seem to be a complete analysis of the failure probability, though. For instance, if the size of the set, $|S|=1$, then each hop will be of the same length, and so the "wild kangaroo" has a pretty good chance of escaping all the traps. So it seems that the size of the set should affect the failure probability, but this parameter does not seem to appear in any of the analysis (except maybe in some examples on page 6).

Is there a good analysis of the failure probability of this protocol? Also what set $S$ is good in practice? Pollard suggests powers of 2 but this is based on a fairly small set of possible $S$ he looked at--has any analysis since Pollard's original paper confirmed that this is a good choice of $S$?

$\endgroup$
1
$\begingroup$

Edlyn Teske has had a look at this question in her paper, specifically in section 6.3. I restate it in your notation:

Kangaroos running in cycles During a kangaroo's travel, there is a possibility that the sequence of its spots beomes periodic. While cycles are the ultimate goals in the rho method, they do not reveal any information about $x$ (the discrete log) in the kangaroo method. [..] They don't find new distinguished points, they slow down the algorithm and even might cause it to fail.

We show that if $w\leq order(g)/4$, this is very unlikely to happen. As before, we first assume that we have only one tame and one wild kangaroo and that we work with jump distances of mean value $\beta=\sqrt{w}/2.$

She is looking at parallelization, but the above is for the non-parallel method. She then proves that the probability $\mathbb{P}$ that a kangaroo ends up in a cycle before a useful collision has occured is upper bounded by $$ \mathbb{P}\leq \exp(-(4n/w)-2), $$ where $n$ is the order of $g,$ in the discrete log problem $h=g^x$ under consideration.

Furthermore, Teske remarks that assuming uniformity of DL values, this bound can be tightened.

$\endgroup$
  • $\begingroup$ This is a good paper, but I don't think it deals with the choice of $S$ either. There is an analysis in section 6.1, but it assumes that, once the following kangaroo catches up with the leading kangaroo, the probability of a collision in each round is $1/\beta$, where $\beta$ is the mean of the elements of $S$. But if, for instance, $S$ only contains one element, then this will not be true. And in the case where $S$ were powers of 2, it is not obvious for me why the probability would be $1/\beta$ if $S$ either. $\endgroup$ – Daniel-耶稣活着 Jun 17 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.