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

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.
I let you informed.
Thanks

Great!! Now under 2.sqrt(n)!

I would be nice too a comparison with the classic approach (no equivalence classes) with these modifications:

T' = [−2N/3, 2N/3 - (m/theta)]  
W' = [k − N, k − N/3 - m/theta] ∪ [k + N/3, k + N - m/theta]

To recap:
the standard 1.4 version takes 2.21.sqrt(n) and the new 'equivalence classes/symmetry' based version takes 2.sqrt(n), -15% ! There is room for improvement!

:-)
Beeeeeegest thank you.
Br.

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.

Thanks. I admittedly didn't understand your previous post.


I'm trying to resolve the classic discrete logarithm problem via a 3-dimensional discrete logarithm problem ( https://www.math.auckland.ac.nz/~sgal018/RamCiren.pdf) using endomorphism, probably not a good idea.

If you resolve Q=a*P + b*P' + c*P'' with P'=lambda*P, P'' = lambda^2*P,
then you have that Q = k*P, where k=a + b*lambda + c*lambda^2

https://www.math.auckland.ac.nz/~sgal018/RamCiren.pdf

Hi, for your tuning's problems you can apply the following considerations to the classic version. This paper doesn't deal with equivalence classes.




Considering the DP too:

Many thanks to all of you for your interest

I'm sorry but I didn't manage to make the algorithm in the paper working. I always get (at best) similar result than the classic version.
I tried to increase the random jump table size up 65536 (32768 positive random jumps and 32768 negative random  jumps) but still have lots of collision in same herd (using -d 0, it disable the distinguished point, so all collision and cycle are detected). The size of this table seems to no impact the bad collision number. I will read the ref[8] asap.

I tried several averages, sqrt(N) seems the best one.
I didn't tried yet to have different average length for Tame and Wild.

Try to implement endomorphism optimizations ASAP...

@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

I tested v1.4beta, and it found the keys for me ~25% faster (in time) and with 3-5% faster speed compared with v1.3
GeForce GTX 1080 Ti 11Gb

I used 5 keys in 2^75 range and made 10 tests (5 keys in original range, and the same 5 keys in adjusted range shift to the beginning).

First 5 keys were found for 1:11:51 hours (14:22min per key - the same as predicted by program(!)), and the second 5 keys for 1:35:36 hours (19:06min per key). And the whole average was 16:45min per key. Compared with 20-22min with version 1.3. Prevous tests with version 1.3 and same 2^75 ranges are here: https://bitcointalksearch.org/topic/m.54302113



But strange, I shifted the range (together with the public keys of course) to 0 (deducted start range) and expected that the 5 keys would be found faster or for the same time, but actually they were foound for a longer time.


I beleive this shift could make the calcualtions faster... We easily implement the symmetry (!)

Jean_Luc, is it easy to implement such shift of the range? Or just make such shift optional...
The whole range is not length, but a wheel Let us spin this wheel and set the center of the range to the Zero point 

I think you are missing the point I am making.

You will find a collision if the solution is in one of the additional ranges opened up by the endomorphism.

First what is "our problem"?  Finding a that some point Q = kP has a discrete log with respect to some point P in a specific compact range of k -- [0, 2^80].  But why?    Instead you can solve a related problem: Find k for Q = kP where k's value is [+/-]1*[0, 2^78]*lambda^[0,2] in less time, even though that 'sparse' range has 1.5x the possible values.

If the reason you are interested in DL is because someone has embedded a puzzle in a [0,2^80] range or something, then the ability to find solutions in the other range isn't interesting.

If, instead, the reason you are interested is because you have a cryptosystem that needs small range DL solving to recover data-- for example decrypting an elgammal encryption or recovering data from a covert nonce side-channel, or from a puzzle-maker that was aware of the endomorphism and used it in their puzle... then it is potentially very interesting.

I think also if the interest is just in DL solving bragging rights or just the intellectual challenge in exploiting all the struture, the endomorphism is also interesting-- for that there isn't a particular problem structure so why not use the one that results in the fastest solver.  In the prime order group essentially all k values are equivalent, which is why you're able to shift the search around to look for that range wherever you want it in the 2^256 interval.
 

You do not need any extra tables to search the additional ranges opened up by the endomorphisms.  That's why I pointed out point invariants that hold for all three--- x^3 or (is_even(y)?-1:1)*y.    If you do all your lookups using one of these canonicalized forms the table for six of the ranges is the same (and you'd have to check after finding a hit to determine which of the ranges the solution was actually in).

Good point, effectively they are just copies. 

What is the advantage of these 3 intervals? Actually they are all the same, just copies. The have the same scalar range, but different 3 types of points in every range. Also in order to implement it you need generate and store 3 tables of jumps (G, G' and G''). But what is the advantage of that 3 point ranges?

It looks the same if you put 3 times more angaroos at the same range (with G), but for this method you need less jump tables (only one jump table)

Great idea!

But for our problem it is not suitable, we have to maximize the chance to get a collision inside an interval.
In a small interval [a*G, ..., b*G] (80 bit) probably you won't find 2 points with the same x or the same y, we don't work in the entire space.

We tried to move [a*G, ..., b*G] to [-(b-a)/2*G, +(b-a)/2*G]  because it is precisely the way to have all points with the opposite in the same subgroup. Then for each 'x' we have 2 points for sure.



If you work in 3 spaces of points and you change the generator and the jumps accordingly:

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

you will have three intervals of consecutive points. In this way any movement in the interval 1 has its own "copy" in the other 2 intervals.

If you cube the x coordinate you will extinguish the group of the endomorphism-- all six keys P, lambda*P, lambda^2*P, -P, lambda*-P, and lambda^2*-P all share the same x^3 coordinate, so if the x^3 was used to select the next position, they'd all collapse to the same chain.

Alternatively, you could choose y or -y whichever is an even number (only one will be), because negating y MAY be faster than cubing x. I say may because you have to compute y and I think an optimal addition ladder will usually not need y for all points-- only for points which are non-termial.

The endomorphism might be less interesting though, because the cases you are selecting the DL is known to lie in a 'small' range from a specific base point, and the two endomorphism generated points do not.

That said, I've had applications-- e.g. using nonce's as a sidechannel -- where you can choose the range, and  [small]*lambda^[0,1,2]  would be a viable option.

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

This will be great, Luc. Biiiiiiiiiiiiiiiiiiig thanks.

Yes this small epsilon of ~0.1 (as they call it) is again a strange thing without lots of explanation. They say that it is an overload due the the "failure of random walks" where again we do not have lots of clear informations, I have to read the reference [8]. Last but not least they make test on a very small number of experiments so the error is large...
I have some doubt on few on their calculations too...


Yes at the beginning I used the y sign to select positive or negative jump then I tried an otehr set of random negative jumps without success.
It seems that this "bownian motion" is rather tricky to tune.

Tomorrow, I'll try other things...

Luc, then will be release avaliable ?


Big thank you.

Br.

If you shift the range [a,b] -> [-(b-a)/2, (b-a)/2], each point P in this interval has the property that -P is in interval too. No other operations are needed.

For the whole group with range [0, order] yes it is free to make -P from P. But for the subgroup within a pecified range you need to make scalar operations.

We do have fast inversions. Inversion in additive group means: -P, and -P is pratically for free.