Topic: 5-7 kangaroo method (Read 69 times)

Yes, that approach works, but what are the consequences?

First, let's say the private key is 0x1. So, we would rather add G and then divide, otherwise we need to add a special condition check in the algorithm ("is P the point at infinity"), making it slower.

But after division, we have two resulting points:

[1/2]P
[1/2](P + G)

and we don't know which one of these two is the one that sits in the lower interval, and which one sits in another interval (points starting at keys [1/2 mod n] = (n+1)/2 onward).

So we must look for either of them. Since we now have two keys to search for, any algorithm will require two times more work at some stage, in an interval that is half in size (either the lower interval, or the [1/2 + k] interval)

Let's say our algorithm has an average run-time of C * sqrt(N) where C is some (any) constant factor and N is the size of the interval.

Let's simplify C to be 1 (we'll have the same end-result if C is either lower or greater then 1).

If we look for the private key in the original interval, average run-time is then sqrt(N)

If we look for 2 private keys in a half-range interval, average run-time is then 2 * sqrt(N/2) = sqrt(2) * sqrt(N) = 1.41 sqrt(N)

My conclusion (non-definitive and open for debates): the average run-time increases by 41% every time we  "divide public key by 2" and attempt to work-around the parity problem.

Now, the cited study uses values for the exponent as 6-decimal digit figures. Following the same logic, I would think that this means the predicted results of his analysis are only valid if the private key that is beaing searched is a multiple of 1.000.000. Otherwise, his wild starting points (the exponents are being used to compute initial wild kangaroo positions) are not really guaranteed to lie in the search interval, but rather in 1.000.000 different intervals.

Regarding this very specific problem, one limited approach I can think of is to subtract G from your initial pubkey and keep them both; the initial and the offset resulting from this subtraction.

Now one of these two is sure to have an even private key, as some pubkey minus G = its private key minus 0x1.

Then you "divide" them both and at least one resulting offset will be within the desired interval.

Maybe you could find a similar work around for your specific problem

So while rethinking a bit on Pollard's 3 kangaroo method I was reminded about this paper:

Kangaroo Methods for Solving the Interval Discrete Logarithm Problem
https://www.math.auckland.ac.nz/~sgal018/AFhons.pdf

In that, the author attempts to find better running times than the 4-kangaroo method presented by Pollard et. all in 2011 or so, and claims to have found them, at least by using 5 kangaroos. Then he also presents a 7-kangaroo algorithm with an almost similar run-time (but not really better).

However I'm either stupid or missed something obvious. The author uses some smart approximation algorithms to find some constants that should be used for the exponents of the Tame and Wild kangaroos.

But these constants are not integers, so the author suggests to use the closest integer values when multiplied by N (interval size). The entire analysis is based on the assumption that these Wild kangaroos start off inside the interval.

What I do not understand is: if we are given a public key. and are told it is found in some interval of size N, then the only known points that we can tell for sure are in some interval are:

- the public key itself
- the opposite point (between -N and -1)
- integer multiples of either of the above two points
- added or subtracted known deltas of any point in the above three cases

So, how did the author reached the conclusion of finding better algorithms, given that we can't be sure that when we do an exponentiation of the form:


then the resulting point will only ever lie in a known interval as the original only when both N and the private key are both divisible by 1000?

It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.

Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.

So, is this study wrong? There are also no given experimental tests.