Pollard's kangaroo ECDLP solver - page 141.

gmaxwell

staff

Activity: 4158

Merit: 8382

Quote from: arulbero on May 01, 2020, 05:52:24 PM

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.

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.

Quote from: MrFreeDragon on May 01, 2020, 06:14:33 PM

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)

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

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: MrFreeDragon on May 01, 2020, 06:14:33 PM

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)

Good point, effectively they are just copies. Roll Eyes

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 01, 2020, 05:52:24 PM

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

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)

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: gmaxwell on May 01, 2020, 05:07:00 PM

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.

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.

Quote from: gmaxwell on May 01, 2020, 05:07:00 PM

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.

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.

gmaxwell

staff

Activity: 4158

Merit: 8382

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.

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: Jean_Luc on May 01, 2020, 04:29:21 PM

Quote from: arulbero on May 01, 2020, 12:08:11 PM

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

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

COBRAS

member

Activity: 846

Merit: 22

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

Quote from: Jean_Luc on May 01, 2020, 04:29:21 PM

Tomorrow, I'll try other things...

This will be great, Luc. Biiiiiiiiiiiiiiiiiiig thanks.

Jean_Luc

sr. member

Activity: 462

Merit: 696

Quote from: MrFreeDragon on May 01, 2020, 02:18:15 PM

They also showed in practice that the total number of operations was not 1.36sqrt(N), but 1.46-1.49sqrt(N).

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

Quote from: arulbero on May 01, 2020, 12:08:11 PM

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

COBRAS

member

Activity: 846

Merit: 22

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

Luc, then will be release avaliable ?

Big thank you.

Br.

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: MrFreeDragon on May 01, 2020, 03:04:29 PM

Quote from: arulbero on May 01, 2020, 02:24:58 PM

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

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.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 01, 2020, 02:24:58 PM

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

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.

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: MrFreeDragon on May 01, 2020, 02:18:15 PM

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

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

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

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

Quote

we show how to speed up the Gaudry-Schost method in groups with fast inversion (such as elliptic curve ... )
Here fast inversion means that computing u^−1 for any u in the group is much faster than a general group operation.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

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

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

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?

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: Jean_Luc on May 01, 2020, 12:04:14 PM

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?

Jean_Luc

sr. member

Activity: 462

Merit: 696

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

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: Jean_Luc on May 01, 2020, 11:45:30 AM

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.

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

Jean_Luc

sr. member

Activity: 462

Merit: 696

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

Code:

Kangaroo v1.3
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :1000
Number of CPU thread: 2
Range width: 2^40
Jump Avg distance: 2^20.00
Number of kangaroos: 2^11.00
Suggested DP: 8
Expected operations: 2^21.15
Expected RAM: 6.5MB
DP size: 5 [0xF800000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos

Key# 0 S3Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
[ 0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)

Key# 1 S3Pub: 0x03CB4F9578029F67C76438379DBA854BB9AE6F8EFB219614404A3B4F9FE8D50DC6
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EA329D8F1
[ 1] 2^21.520 Dead:4 Avg:2^21.618 (2^21.148)

Key# 2 S0Pub: 0x021CCEE21580FFDCFB8DD18A21B9931E1A585E6A381F3BFAC8B84FC57152FD706F
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E0D7752C567
[ 2] 2^19.253 Dead:0 Avg:2^21.166 (2^21.148)

Key# 3 S3Pub: 0x027CAEB7E334C27E5881F37317FC16E220D425E11DC3ABB6E1D4FEC8651F9672F7
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8012448821
[ 3] 2^20.289 Dead:1 Avg:2^20.992 (2^21.148)

Key# 4 S3Pub: 0x0266556C83D982677B2BD1BFA996828A1F4F7004E92BBE5AA4B393B46999C3B3B5
Priv: 0x4EF20EBCFE
[ 4] 2^20.205 Dead:0 Avg:2^20.865 (2^21.148)

Key# 5 S0Pub: 0x03A20F2F01ED2C30EEFDDA39369ECA064B42784C1828B64EA07B350A9B1E989264
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E4F6D1E4921
[ 5] 2^21.066 Dead:1 Avg:2^20.901 (2^21.148)

Key# 6 S0Pub: 0x02AC1FC88FB9AFF706E26C61D0B35491BD0F6F515A4307D46E183991C87DF530C3
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E2ED6F15717
[ 6] 2^20.659 Dead:1 Avg:2^20.869 (2^21.148)

Key# 7 S3Pub: 0x03753BFF59D2EA1A5DC79BE76279EF6E4B2714043A8DBB747F0147AF566C8D537A
Priv: 0x636F05D644
[ 7] 2^22.343 Dead:8 Avg:2^21.158 (2^21.148)

Key# 8 S0Pub: 0x03A57000087A7CF565318CDD11F379C329A0DA2A28F3D251EAF6D8B29A7DAC799D
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E410D2DB133
[ 8] 2^19.576 Dead:0 Avg:2^21.047 (2^21.148)

Key# 9 S3Pub: 0x035C394D4E9654206CA0A894FB95D76840BB728673403A41101C02E13A8C2DA78A
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8B56E16E5A
[ 9] 2^20.700 Dead:1 Avg:2^21.016 (2^21.148)

Key#10 S3Pub: 0x02E7C093503548B3E41C4912913FD0601FDCE26BBEE94740812931737B663C90CB
Priv: 0x6F1F0B5EF4
[ 10] 2^21.156 Dead:0 Avg:2^21.029 (2^21.148)

Key#11 S0Pub: 0x03FDFC12CCD11AA5113A12DE3DA7F75A74F57B9D2C9E163A6502C69997373CFA5B
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EC4A94243
[ 11] 2^19.762 Dead:1 Avg:2^20.957 (2^21.148)

Key#12 S3Pub: 0x029942527E4DE7EA2DD931C284A71FCD2C6F86988C3BCC343CF25639599D183958
Priv: 0x61625FF76D
[ 12] 2^22.054 Dead:4 Avg:2^21.078 (2^21.148)

Key#13 S3Pub: 0x03EDE29C2AA47726E75B9FF565A97907671BD2255DE2AE9C639F5E57B2ED64B509
Priv: 0x70A6A72B9C
[ 13] 2^22.660 Dead:8 Avg:2^21.270 (2^21.148)

Key#14 S0Pub: 0x0361354FA9C10998E21B18BF911CF85C9CC9CC7314ECFFE2F2FE62DBBAC7528462
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E234F90C389
[ 14] 2^19.719 Dead:1 Avg:2^21.206 (2^21.148)

Key#15 S3Pub: 0x03EE26BFC9AC228D6313797F11C0ED0D57BC2AA2909AA4CB938825EC571685A104
Priv: 0xD513ABE3E
[ 15] 2^21.614 Dead:2 Avg:2^21.235 (2^21.148)

Key#16 S3Pub: 0x023D8A5B0DFDDAF4974CBCA698C11A7CFF77C3432E0A528CDB00B39DFA94F35CE1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1875ED6231
[ 16] 2^21.401 Dead:1 Avg:2^21.245 (2^21.148)

Key#17 S3Pub: 0x032BD888A2DD0ED92A1E938F4546565CFD35172D502B36CA51CD3094C68B5A8F99
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8629B915FA
[ 17] 2^20.966 Dead:1 Avg:2^21.231 (2^21.148)

Key#18 S3Pub: 0x02BC1AA451042525998B3EB746F90F33B04CC87D525F0C576AD133FB60BD390635
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E84E933A860
[ 18] 2^22.359 Dead:6 Avg:2^21.318 (2^21.148)

Key#19 S0Pub: 0x02C379FD7FF86C5F5EDA2EA7EC2A17E629A6C5E550CFD1480F942224C96ADB29B4
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E16BAA606C7
[ 19] 2^19.383 Dead:0 Avg:2^21.264 (2^21.148)

Key#20 S0Pub: 0x03BB6EE07839B4652D2E5E542E1D566756908C92A325212BF77C47F986CA49E50C
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1894FE660B
[ 20] 2^20.533 Dead:0 Avg:2^21.236 (2^21.148)

Key#21 S3Pub: 0x0365D82BF4021C9BDA3F3518368D92E2D5B5B31A74F656DA795F945CF3452B388E
Priv: 0x18C8633EB7
[ 21] 2^20.180 Dead:1 Avg:2^21.202 (2^21.148)

Key#22 S3Pub: 0x02F68338FAB7DFB6B826B0B516671EA9744BF87A9105EEF57CB04B8262C246197C
Priv: 0x54698374C2
[ 22] 2^21.979 Dead:5 Avg:2^21.246 (2^21.148)

Key#23 S3Pub: 0x026B0539B338B11BC3BF89CAB51182D8AA9EFA27C40CAAC90CA30B1184548D7380
Priv: 0x1EC240D56C
[ 23] 2^20.536 Dead:0 Avg:2^21.222 (2^21.148)

Key#24 S3Pub: 0x0296F8ECE1DD51B1B15E6A9D0A2545C8AAC9C4CFA72BBBE1DCD6C03D1D51E21C42
Priv: 0x11274B7F03
[ 24] 2^20.651 Dead:0 Avg:2^21.203 (2^21.148)

Key#25 S3Pub: 0x03D013A7A59A42D1EB6333EFBE1DA208586DD3940BCFB381ADEA98F76C4D26B2B5
Priv: 0x414A6EFD99
[ 25] 2^20.480 Dead:0 Avg:2^21.181 (2^21.148)

Key#26 S0Pub: 0x02D5FEDD123EF2BDCC3FE37C4D79DD1E5B2EC95AD9B2C7452907391A1CCC5EF9C0
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E137A8D7A6F
[ 26] 2^21.945 Dead:7 Avg:2^21.218 (2^21.148)

Key#27 S0Pub: 0x02B227090548A1497FCDCAFB0DB7900851872CF7E0AD2A0B7EC832DAA7BA30637C
Priv: 0xE2511D7A
[ 27] 2^21.535 Dead:1 Avg:2^21.231 (2^21.148)

Key#28 S1Pub: 0x024A4FCE4455879E9CB6806DB6367D7287A28A2C59CF29B156EDF016EDB377BDB4
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1E87F79995
[ 28] 2^21.683 Dead:2 Avg:2^21.249 (2^21.148)

Key#29 S2Pub: 0x02F81D6B0179834773E92F8FCB23014727E8B78BDD30C605F50BBCC205EEB1C386
Priv: 0x7F0B60C903
[ 29] 2^21.590 Dead:3 Avg:2^21.262 (2^21.148)

Key#30 S2Pub: 0x034848FA03EC2FA52ACAE70BE58720A5621CF90565BBC925D624BFB31CDC1ACB66
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8016BDBA3D
[ 30] 2^19.910 Dead:1 Avg:2^21.233 (2^21.148)

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: Jean_Luc on May 01, 2020, 10: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, 10: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: 696

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

Topic: Pollard's kangaroo ECDLP solver - page 141. (Read 55599 times)