But with both signs (+-) or not?
Could you try with an average of 2^21 - 2^22 instead?
u try with an average of 2^21 - 2^22 instead?
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...
Yes, but it looks promising. 1,50 would be amazing!
I was thinking another thing:
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).
But this curve has another symmetry, 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
In a interval of consecutive points, all x-coordinates are different, but if we move the interval like we did it becomes symmetric.
If we want to exploit y-coordinates, a jump should be depend on 'y' and not on 'x'.
We can work then with equivalence classes where [P] = {P, Q, R} and 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.
Besides, 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 actually 3 different intervals of points. All consecutive from a different generator's point of view.
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 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!
when they reach a DP (in this case a y-coordinate with some zero bits), we detect this collision.
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.