Pollard's kangaroo ECDLP solver - page 145.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on May 01, 2020, 09:19:34 AM

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...

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)

Tamarindei

newbie

Activity: 17

Merit: 25

Quote from: Jean_Luc on May 01, 2020, 09:19:34 AM

I coded the stuff as it is described in the paper using this:

Code:

T={{a,−a}:a∈[−N/2,N/2]},
W={{n+a,−(n+a)}:a∈[−N/4,N/4]

And a of translation of -N/2.G of the public key to solve in order to have as specified:

Quote

Each experiment involved choosing uniformly at random−N/2≤n≤N/2 and solving the DLP for Q= [n]P.

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) Sad

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).

Jean_Luc

sr. member

Activity: 462

Merit: 701

I coded the stuff as it is described in the paper using this:

Code:

T={{a,−a}:a∈[−N/2,N/2]},
W={{n+a,−(n+a)}:a∈[−N/4,N/4]

And a of translation of -N/2.G of the public key to solve in order to have as specified:

Quote

Each experiment involved choosing uniformly at random−N/2≤n≤N/2 and solving the DLP for Q= [n]P.

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) Sad

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...

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks for the readings

I will try to see if this can be implemented on ECDLP.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Tamarindei on May 01, 2020, 01:29:30 AM

Quote from: Jean_Luc on May 01, 2020, 01:06:40 AM

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.

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:

Quote

Average number of group operations performed by our algorithm: 1.46 * sqrt(2^n)

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.

Tamarindei

newbie

Activity: 17

Merit: 25

Quote from: Jean_Luc on May 01, 2020, 01:06:40 AM

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.

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).

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on May 01, 2020, 01:06:40 AM

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

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.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on May 01, 2020, 12:44:43 AM

Quote from: arulbero on April 30, 2020, 02:50:08 PM

It is enough to modify slightly the way we generate the next jump:

+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y

(then I will indicate 'y' if y > p/2, '-y' if y < p/2)

in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

The tame and the wild will go on with 2 specular paths:

Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)

-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)

until they reach 2 symetric DP, for both of which we know the private key.

Quote from: Jean_Luc on April 30, 2020, 11:35:06 AM

May be a brownian motion can be interesting (having positive and negative jump).

I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.

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.

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on April 30, 2020, 02:50:08 PM

It is enough to modify slightly the way we generate the next jump:

+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y

(then I will indicate 'y' if y > p/2, '-y' if y < p/2)

in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

The tame and the wild will go on with 2 specular paths:

Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)

-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)

until they reach 2 symetric DP, for both of which we know the private key.

Quote from: Jean_Luc on April 30, 2020, 11:35:06 AM

May be a brownian motion can be interesting (having positive and negative jump).

I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.

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 ?

Jean_Luc

sr. member

Activity: 462

Merit: 701

Hello,

I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.

Thanks to test it and to share ideas of improvements here Wink

Topic: Pollard's kangaroo ECDLP solver - page 145. (Read 60189 times)