Pollard's kangaroo ECDLP solver - page 145.

arulbero

legendary

Activity: 1932

Merit: 2077

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: 1932

Merit: 2077

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: 1932

Merit: 2077

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 59389 times)