Topic: Pollard's kangaroo ECDLP solver - page 142. (Read 59389 times)

There are only positive jumps in this table.
Loop are still possible because of the equivalence class switch "(xP,min{yP,q−yP})".

The bad news is that I had to put a large number of random jump (65536) to avoid cycles and this will decrease GPU performance
I will investigate on choosing these jumps in order to reduce probability of cycle and having the smallest possible jump table.

You have to change your jumps. But choose them in a "intelligent" way, I think it is not too difficult.
'Intelligent' means that a man can't do this, let the probability do it. I think that the main problem is that you want to choose the jumps by yourself. Why?

You should study separately a sequence of jumps such that the probability to come back before 2^DP steps is low. This study depends only from jumps, DP and m (the average jump), not from points/coordinates/N!

For example, with these jumps [+-1,+-2,+-4,+-8,+-16]  you try to generate many sequences (starting from 0). If the number of sequences with lenght < 2^DP (or < k*2^DP) is too high, change randomly the jumps and retry. Lenght of sequence: number of steps before to get back to 0. Deal simply with integer numbers.

This setting phase should be done automatically at the start of the program. In this way for each DP you will have configured the jumps in order to get a lower probability of generating loops.

The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields. Such elliptic curves are called pairing-friendly, and are not normally used for ordinary ECDH key agreement or ECDSA or EdDSA signatures like Bitcoin—secp256k1, for instance, ...

It works with dp=0 because random walk are not really important, they just generate random sequence, and you don't care about the path, so it correctly solve the key (the distance is also stored in the hastable) but with dp>0 paths are of course important.
You're right there is probably a bug with my storage of symmetric point.

You still exploit the symmetry. Instead of searching between [0,N] you search between [0,N/2] and there is few calculation to make when a collision on a tame.x and wild.x is reached in order to get the good key. I did test and it works as expected.
I think the trick may be that after sqrt(N) total steps the kangaroos starts to overlap each other, still investigating...

In fact i have removed the negative jump.
 ... you search a priv key between [0,N/2].  I spread my tame between [0,N/2.G] and the wild between [P-N/4.G,P+N/4.G] and it converges to expected average of 1.47sqrt(N) using dp=0.

Instead of searching between [0,N] you search between [0,N/2] and there is few calculation to make when a collision on a tame.x and wild.x is reached in order to get the good key.

with dp=0 there is not much bad collisions, no more than expected.
Strangely when using dp > 0, lots of dead kangaroos appear and probably cycle, even with a small number of kangaroo. I have to understand why may be bug somewhere...

In fact i have removed the negative jump.
There is no need to do complex thing in order to take benefit of symmetry, the main trick is just to translate the public key by -N/2.G and you search a priv key between [0,N/2]. The symmetry is 100% free.

As I have a large number of kangaroo, each kangaroo does not move a lot. The average distance for sqrt(N/2) steps in (N/2)/numberOfKangaroo.

with dp=0 there is not much bad collisions, no more than expected.
Strangely when using dp > 0, lots of dead kangaroos appear and probably cycle, even with a small number of kangaroo. I have to understand why may be bug somewhere...

@Luc

Can you realise in your code modificarion of ranges ?


From:

Start-dfggsdgdsfh1111111
End- FFFFFABC112222233

To:
O

ABC888888

Etc...

?



Biiigesr thank you.

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