Topic: Pollard's kangaroo ECDLP solver - page 143. (Read 60582 times)

I must say I'm a bit lost, they announced an algorithm in 1.36√N and they measured 1.47√N. They say that the complexity is actually (1.36 + epsilon)√N and they estimate this epsilon to ~0.1 without being clear on it.
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

If we compute the complexity of a symmetric set, we have well : (2(2−√2)PI)/√2 √N = 1.468√N !

So i would rather say that the complexity is (1.47+epsilon)√N with an epsilon which depend on number of kangaroo, dp and N as for the standard version.

I'm still fighting with collision, when using dp > 0, it seems that the symmetry generates a lot of wrong collisions.

I did a test using dp 0 (much slower):
The algorithm runs in 2^20.554 = ~1.47 sqrt(N) (1000 trials) as announced on the paper so it seems ok

i did a test with dp 3 and it also converge to 2^21 (same algorithm, no change on the range in function of dp).
This is tricky, there is something I need to understand with those random walks...

Only negative jumps? I would try with positive/negative jumps and a greater average (my sensation)
To me it looks promising. 1.50sqrt(N) would be amazing!
Another thing to pay attention to is: when we translate our interval, we have only 2^(n-1) x-coordinates, and then half DP. For the tuning it's like we worked in a 2^(n-1) space.


I was thinking another thing,
if you want to overcome/avoid the brownian-motion tuning problem,

go back and put together

1) the linearity (and therefore the simplicity) of the classic approach (that you used in the release 1.3)
2) the power of the symmetry

Exploiting the symmetry means that we use equivalence classes to increase the probability of a collision (same number of tries, half 'points'); in our case, given a point P(x,y), 'x' decides the width of the jump and 'y' only the direction.
In the secp256k1 there are 2 points that share the same 'x', (x,y) and (x,-y).

In a interval of consecutive points, all x-coordinates are different, but if we move the interval like we did it becomes symmetric.

The drawback of our approach is that the kangaroo, instead of going in only one direction, keep going back and forth, creating many loops. Besides, not only we don't know where a wild kangaroo is (obviously we don't know its position-private key), but we don't control even the direction of its motion (and often it comes out from the interval)


But this curve has another symmetry that respects the linearity (unlike the negative map that overturns the interval and the kangaroo algorithm): endomorphism.

There are 3 points with the same 'y' , that means that this curve has about 2^256 points and
 
1) 2^256 / 2 different x-coordinates
2) 2^256 / 3 different y-coordinates

Why don't we use the symmetry that mantains the linearity of the interval?

We can work on the y-coordinates, and a jump should be depend on 'y' and not on 'x'.
We set equivalence classes where [P] = {P, Q, R} if and only if  yP = yQ = yR

What is the relation between the private key of these points P, Q, R?

If P=k*G, then Q=k*lambda*G and R =k*lambda^2*G (endomorphism)
and P=(x,y) -> Q=(beta*x, y) -> R=(beta^2*x,y)

observation:

if P=k*G, i.e. k is the private key of P respect of the generator G, then
lambda*P = k*lambda*G, i.e. the private key of P'=lambda*P respect of the generator G'=lambda*G is always k.

In other words, if we know that k lies in [a,b], resolving the problem P=k*G is equivalent to resolve the problem P'=k*G'
The interval is the same (from the scalar's point of view) but there are actually 3 different intervals of points. They are all consecutive from a different generator's point of view:

           point                                scalar
[a*G,   (a+1)*G, ....,  b*G]     <-> [a,b]   interval 1
[a*G',  (a+1)*G', ....,  b*G']    <-> [a,b]   interval 2  where G'=lambda*G
[a*G'', (a+1)*G'', ...., b*G'']   <-> [a,b]   interval 3  where G''=lambda*G

We could work on  3 "spaces" simultaneously :

P=k*G, with all points with generator G   -> interval 1     jumps (1*G, 2*G, ,,,2^(n-1)*G)

P'=k*G' with all points with generator G' -> interval 2     jumps(lambda*G, lambda*2*G, .... lambda*2^(n-1)*G)

P''=k*G'' with all points with generator G'' -> interval 3  jumps(lambda^2*G, lambda^2*2*G, .... lambda^2*2^(n-1)*G)

if the movements of a kangaroo depends only by the y-coordinates, that means that if a kangaroo reach a point T in the first interval and another kangaroo reachs a point W in the second interval with the same y, we will have a collision!
From that point they will walk together along the same path (across the same equivalence classes) until they reach a DP (in this case a y-coordinate with some zero bits), we detect this collision.

EDIT:
We work in this way in a space of 3*2^n points (3 intervals), but with only 2^n y-coordinates, then we should have a collision with a higher probability.  WRONG

Anyway i did a test with dp 3 and it also converge to 2^21 (same algorithm, no change on the range in function of dp).

This is tricky, there is something I need to understand with those random walks...

I have the feeling that this algorithm win in average complexity by favoriting keys on the middle of the range as the density of wild is increased in the center. It has a worse 'worst case' and a much better 'best case' than the classic algorithm.

-snip-
@MrFreeDragon
You need a large number of tests on key uniformly distributed in the range to get a correct estimation, at least 1000 trials.
Did you try with a jump table size of 32 or 64 ? NB_JUMP in GPUEngine.h:24 ?

I added the file I use for stats, it contains 1000 40 bits key uniformly distributed.
https://github.com/JeanLucPons/Kangaroo/blob/master/VC_CUDA8/in40_1000.txt

@COBRAS
I release the code ASAP

With these data:
N = 2^40
m = 2^11
θ = 2^−5

still 2^21?

I did a test using dp 0 (much slower):
The algorithm runs in 2^20.554 = ~1.47 sqrt(N) (1000 trials) as announced on the paper so it seems ok but I have to figure out why it is not the case for dp > 0. There is a relationship betwen dp and range size (m√2/3πθ) that I missed.
Will try to undersand, how to choose this m.

To detect small cycles we stored the previous 30 group elements in the walk
in the case N ≈ 2^34 (respectively, 30, 45 group elements for N ≈ 2^40, 2^48). Each
new step in the walk was compared with the previous 30 (respectively, 35, 45)
group elements visited. If this group element had already been visited then the
walk is in a cycle. We used a deterministic method to jump out of the cycle (using
a jump of distinct length from the other jumps used in the pseudorandom walk)
so that the pseudorandom walk as a whole remained deterministic. The cost of
searching the list of previous group elements is not included in our experimental
results, but our count of group operations does include the “wasted” steps from
being in a cycle.

The number of bad collision is also link to the kangaroo density.

Four Kangaroo Method. We can make a further improvement. The starting points of W1 and W2,
namely x and −x, are integers of the same parity. Hence, to obtain wild-wild collisions more quickly one
should take walks whose jumps are all even length. However, now there is the possibility that the wild walks
will never collide with the tame walk. The solution is to have two tame kangaroos, T1 and T2, starting on
adjacent integers (one even and one odd). There is no possibility of a useless tame-tame collision, but there
is a chance of tame-wild collisions, as desired (though with only one of the tame kangaroos).
...
We now estimate the complexity of the method.
...

Hence, using 4 kangaroos gives an algorithm for the DLP in an interval whose heuristic average case
expected running time is (1.714 + o(1)).sqrt(N) group operations.

Yes, i think this might be due to the average jump size which is too large for wild.
I will try other things and what you suggest.

To guard against bad steps of type 1 van Oorschot and Wiener [22] set a maximum number of steps in
a walk. They choose this maximum to be 20/θ steps and show that the proportion of bad
points of type 1 is at most 5 × 10^−8

...
Steven D. Galbraith and Raminder S. Ruprai:

We terminated walks which ran for 5/θ steps without arriving at a distinguished point (the usual recommendation is 20/θ steps; see [22]). This will give
us a slightly worse running time than optimal.

Exercise 14.5.12.
The distance between −a and a is even, so a natural trick is to use jumps of even length.  Since we don’t know whether a is even or odd, if this is done we don’t know whether to start the tame kangaroo at g^u or g^u+1.  However, one can consider a variant of the algorithm with two wild kangaroos (one starting from h and one from h−1) and two tame kangaroos (one starting from g^u and one from g^u+1) and with jumps of even length.
This is called the four-kangaroo algorithm.
Explain why the correct choice for the mean step size is m = 0.375√2w and why the heuristic average-case expected number of group operations is approximately 1.714√w. Galbraith, Pollard and Ruprai [226] have combined the idea of Exercise 14.5.12 and the Gaudry-Schost algorithm (see Section 14.7) to obtain an algorithm for the discrete logarithm problem in an interval of length w that performs (1.660 + o(1))√w group operations.

Galbraith, Ruprai and Pollard [226] showed that one can improve the kangaroo method by exploiting inversion in the group. This research actually grew out of writing this chapter. Sometimes it pays to work slowly.

Good news !
By changing the spreading of wild kangaroo to -N/8 N/8 the it seems to improve things. (using the Steven D. Galbraith?and Raminder S. method).
I got an average of 2^20.997 ~ 2.sqrt(n) on 1000 trials.

Good news !
By changing the spreading of wild kangaroo to -N/8 N/8 the it seems to improve things. (using the Steven D. Galbraith?and Raminder S. method).
I got an average of 2^20.997 ~ 2.sqrt(n) on 1000 trials.