Pollard's kangaroo method for solving ECDLP

Hey everyone, I wanna share an interval ECDLP solver that uses Pollard's kangaroo technique. It's totally open source and you can find it on GitHub: https://github.com/JeanLucPons/Kangaroo. The program has GPU support (only CUDA) and it runs on both Linux and Windows. It's still in development, so I'd appreciate any testing and feedback on how to improve it.

I'm not sure to fully understand your idea. You want to add a condition on the y parity to determine the jump ? You let the starting positions as they are or you translate them ?

The start interval must be: [-(b-a)/2, +(b-a)/2] and yes, I want to add a condition on the y parity to determine the jump's direction. In this way a wild and a tame collide if they reach: 1) the same point 2) two symetric points In the interval [-(b-a)/2, +(b-a)/2], the x-coordinates of [1, +(b-a)/2] are equal to the x-coordinates of [-(b-a)/2, -1]; we should get more collisions, because we work in a space of 2^(n-1) points instead of 2^n. We introduce a equivalence class [P], where P ~ Q if Q = -P and the jump function goes from [P] to [P1], i.e. it is defined between 2 equivalence classes instead of between 2 points. A problem could be that many paths could enter in a loop before they reach a DP, because each kangaroo jumps back and forth and then a single kangaroo can collide with itself.

OK i will try this. But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.

Now: tamei = rand(0..(k2-k1)) # Scalar operation wildi = rand(0..(k2-k1)) - (k2-k1)/2 # Scalar operation wildPosi = P + wildi.G # Group operation My proposal (assuming that private key of P is for sure in [-(k2-k1)/2, (k2-k1)/2]) tamei = rand(0,..(k2-k1)/2) # Scalar operation (you can avoid negative numbers for tame) wildi = rand(-(k2-k1)/4,...(k2-k1)/4) # Scalar operation wildPosi = P + wildi.G # Group operation

I think there's a paper about this already: https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).

Many thanks!!!  I didn't know it ! EDIT: from the article:

Thanks for the readings I will try to see if this can be implemented on ECDLP.

Hello everybodey. Big thanks for your work. My GPU is ready for tests !!!!

I coded the stuff as it is described in the paper using this: And a of translation of -N/2.G of the public key to solve in order to have as specified: It found as expected from time to time the symmetric point. It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n) But, they are not very clear on the jumps and especially the average distance of the jumps. As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested). I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry... To be continued...

Did you also re-randomize the point after distinguished point was found (they are using gaudry schost method in the paper)? Edit: Another way to optimize memory access and speed: Don't save jumped distances. When a collision between wild and tame was found you know T and W starting offsets and replay the walk for this pair only but this time with jump distances saved (replay of single pair on CPU should be sufficient). I got this idea from another paper which I can't remember right now. This is straightforward with Pollard Kangaroo but you have to account for the re-randomization when using Gaudry Schost method (remember new offsets).

You cannot loose the symmetry. Are you sure that the algorithm goes outside the range so often? I don't think so, with this kind of jump (back and forth), I would use longer jumps, because you in sqrt(n) steps shouldn't go outside of the interval (on average) like the classic version. I suppose the main problem is the loops (a single kangaroo with itself)

Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase. The idea of replaying walk is good, I do like this in my BTCCollider. Here is an output on 30 trials. The final private key is not reconstructed here, you need to add (mod n) start range + N/2

Your jumps are: +-G, +-2*G, ...., +-2^19*G ?

Not in this release, I use a random set of jump [32 jumps] with an average of 2^20.

But with both signs (+-) or not? Could you try with an average of 2^21 - 2^22 instead?

Thank for this reading. In abstract it was noted that the method "to solve the DLP in an interval of size N with heuristic average case expected running time of close to 1.36√N group operations for groups with fast inversion". We do not have fast inversions. They also showed in practice that the total number of operations was not 1.36sqrt(N), but 1.46-1.49sqrt(N). 1.49 is 25% less than 2. Th question is, if we perform 2sqrt(N) operations with the speed 1000MKey/sec, what will be the speed for 1.49sqrt(N) operations? If it is only 5-10% less, probably nice. But if it decreases down twice to 500MKey/sec?

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

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.

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.