Pages:
Author

Topic: 5-7 kangaroo method - page 2. (Read 789 times)

newbie
Activity: 23
Merit: 2
October 10, 2024, 05:14:47 PM
#20
Stop promoting garbage. If you precompute certain values, you might lose the effect of the birthday paradox in the sense that you are reducing randomness and possible combinations. Precomputation can make the problem more deterministic and less dependent on the random coincidences that make the birthday paradox so surprising. You are leading people into a void.

Excellent!  Grin
I think now it's time for some magic circles, don't hesitate!


The birthday paradox is based on probability and randomness, which allows for finding collisions more efficiently than with brute force. By modifying the kangaroo algorithm in a more deterministic way, this probabilistic advantage is lost, and it becomes an approach closer to brute force.

The essence of the birthday paradox is that, with enough randomness, it is more likely to find collisions in a large set of data. By eliminating or reducing randomness, this property is lost, and the algorithm become less efficient.
?
Activity: -
Merit: -
October 10, 2024, 04:58:42 PM
#19
Stop promoting garbage. If you precompute certain values, you might lose the effect of the birthday paradox in the sense that you are reducing randomness and possible combinations. Precomputation can make the problem more deterministic and less dependent on the random coincidences that make the birthday paradox so surprising. You are leading people into a void.

Excellent!  Grin
I think now it's time for some magic circles, don't hesitate!
newbie
Activity: 23
Merit: 2
October 10, 2024, 04:37:28 PM
#18
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.


If the goal is to retrieve a private key in a 2^134 interval, there is no doubt: BSGS is not the algorithm to use.

But in a 2^64 interval, BSGS can be faster.  

For one 64bit point without precomputing - yes. For many points - kang with precomputed DPs is faster.
Of course you can do the same for BSGS, precompute more points to speedup it, but it won't be so effective as for kang, to speedup BSGS in 10 times you will have to precompute (and store) much more points than for kang (because BSGS does not use birthday paradox sqrt).

Stop promoting garbage. If you precompute certain values, you might lose the effect of the birthday paradox in the sense that you are reducing randomness and possible combinations. Precomputation can make the problem more deterministic and less dependent on the random coincidences that make the birthday paradox so surprising. You are leading people into a void.
?
Activity: -
Merit: -
October 10, 2024, 01:18:29 PM
#17
If we keep silence, maybe he will go away  Cheesy
member
Activity: 165
Merit: 26
October 10, 2024, 01:08:37 PM
#16
Kangaroo is only probabilistic, don't lose focus, Kangaroo doesn't need much power to play the birthday paradox puzzles. Be careful not to ruin the birthday paradox in the search for more speed.

How does that matter? You can't have fast memory in the order of 2**67 elements, and likely not in the lifetime of our grand-grand children. Don't confuse fast memory with storage capacity, the difference between these two is in the order of 5 magnitudes or more. So the only option is to use whatever can be applied to the constraints we're having, no matter if it's probabilistic or not. Kangaroo doesn't require fast memory at all, it requires zero memory actually, and whatever slow storage, only for the offline step (matching), which doesn't influence at all the computation parts. BSGS directly depends on having access to fast memory and this is part of the algorithm itself.
newbie
Activity: 23
Merit: 2
October 10, 2024, 12:16:41 PM
#15


And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.




BSGS algorithm  applied to secp256k1 curve only need 1.0 sqrt(N) operations (on average) and 1.5 sqrt(N) operations in the worst case:

https://eprint.iacr.org/2015/605.pdf

You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G
and compute in the worst case 1.0 * sqrt(N) keys (the giant steps)

Only additions and subtractions, no multiplications.

Quote
Conclusion

...

The new algorithms, like the original, have low overhead but high memory.
This means that our algorithms are useful only for discrete logarithm problems
small enough for the lists to fit into fast memory

Kangaroo doesn't need fast memory. Or any memory at all. I'd say it's a good trade-off.

Kangaroo is only probabilistic, don't lose focus, Kangaroo doesn't need much power to play the birthday paradox puzzles. Be careful not to ruin the birthday paradox in the search for more speed.
member
Activity: 165
Merit: 26
October 10, 2024, 12:04:22 PM
#14


And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.




BSGS algorithm  applied to secp256k1 curve only need 1.0 sqrt(N) operations (on average) and 1.5 sqrt(N) operations in the worst case:

https://eprint.iacr.org/2015/605.pdf

You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G
and compute in the worst case 1.0 * sqrt(N) keys (the giant steps)

Only additions and subtractions, no multiplications.

Quote
Conclusion

...

The new algorithms, like the original, have low overhead but high memory.
This means that our algorithms are useful only for discrete logarithm problems
small enough for the lists to fit into fast memory

Kangaroo doesn't need fast memory. Or any memory at all. I'd say it's a good trade-off.
?
Activity: -
Merit: -
October 10, 2024, 10:18:39 AM
#13
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.


If the goal is to retrieve a private key in a 2^134 interval, there is no doubt: BSGS is not the algorithm to use.

But in a 2^64 interval, BSGS can be faster.  

For one 64bit point without precomputing - yes. For many points - kang with precomputed DPs is faster.
Of course you can do the same for BSGS, precompute more points to speedup it, but it won't be so effective as for kang, to speedup BSGS in 10 times you will have to precompute (and store) much more points than for kang (because BSGS does not use birthday paradox sqrt).
newbie
Activity: 23
Merit: 2
October 10, 2024, 10:13:21 AM
#12


And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.




BSGS algorithm  applied to secp256k1 curve only need 1.0 sqrt(N) operations (on average) and 1.5 sqrt(N) operations in the worst case:

https://eprint.iacr.org/2015/605.pdf

You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G
and compute in the worst case 1.0 * sqrt(N) keys (the giant steps)

Only additions and subtractions, no multiplications.

BSGS is faster, but Kangaroo is very good at aiming, how good will he be?
legendary
Activity: 1932
Merit: 2077
October 10, 2024, 10:03:52 AM
#11
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.


If the goal is to retrieve a private key in a 2^134 interval, there is no doubt: BSGS is not the algorithm to use.

But in a 2^64 interval, BSGS can be faster. 
?
Activity: -
Merit: -
October 10, 2024, 09:47:51 AM
#10
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.
legendary
Activity: 1932
Merit: 2077
October 10, 2024, 08:47:53 AM
#9


And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.




BSGS algorithm  applied to secp256k1 curve only need 1.0 sqrt(N) operations (on average) and 1.5 sqrt(N) operations in the worst case:

https://eprint.iacr.org/2015/605.pdf

You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G
and compute in the worst case 1.0 * sqrt(N) keys (the giant steps)

Only additions and subtractions, no multiplications.
member
Activity: 165
Merit: 26
October 09, 2024, 02:28:34 PM
#8

I also discovered that C can go as low as 1.05 if we also allow 1.05 sqrt(N) stored items, with 3 kangaroos alone, and only addition group operations. And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.


Can you provide a link?

https://bitcointalksearch.org/topic/m.64515007

I only have experimental proofs (e.g "it works as advertised"). Don't ask why though. I'm not a number theorist. It's basically the 3 kangaroo method combined with the van Oorschot parallelization method, without using DPs.
legendary
Activity: 1932
Merit: 2077
October 09, 2024, 10:56:44 AM
#7

I also discovered that C can go as low as 1.05 if we also allow 1.05 sqrt(N) stored items, with 3 kangaroos alone, and only addition group operations. And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.


Can you provide a link?
?
Activity: -
Merit: -
October 08, 2024, 02:49:38 PM
#6
OK, I don't insist, see no reasons to do that if you are happy with 1.7 Grin
member
Activity: 165
Merit: 26
October 08, 2024, 02:16:49 PM
#5
Such papers is just a way to get a degree, zero new ideas.
And all this is not important actually.
The main problem that you won't get better than K=1.7 this way even if you use 1000 instead of 3-4-5-7 kangs.
K=1.7 is boring, really. It's like solving puzzles #6x  Grin
Why don't you try this? https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
Going this way (a long way btw) you can "invent" something interesting and get real K (not in theory but real) around 1.2 if you are smart enough Cheesy I call this approach "mirrored" kangs.
But, of course, this way is not so easy as "normal" kangs that always jump in one direction.
Just a tip for you because it seems you read some papers instead of creating magic circles/code as most people here Cheesy
Though I doubt that you will break #135, it's always fun to invent and discover so you can spend a lot of time having fun...

Thanks, we all already know about that paper, and I discussed it a few times in some of my posts. I also implemented it (even in my public Python kangaroo script) and it indeed brings C to ~ 1.25 - 1.45 but at the expense of much more complex logic, since we can have cycles in the side by side walks, which need to be handled. In addition, that method completely ignores the cost of having to create new starting points, which is not something to be ignored (in fact, is very very costly). This problem is also mentioned in the 3 & 4 kangaroo methods paper (which was actually a follow up to the paper you cited).

There is also a more recent "fix" to the Gaudry-Schost method (but it is written in Chinese) which brings down C a little bit more, by refining the wild set bounds.

However even though C is lower than 1.7, the actual runtime is worse, because of the additional restarts, and cycle detection logic. That means it requires more computing power and additional registers, at the machine level. If well optimized, it can beat 4-Kangaroo on a CPU + RAM, but on a GPU the added requirements (cycle detection, more registers) do not reach the efficiency (throughput) of Kangaroo method, which is simple and direct: jump forward, check if DP, repeat.

I don't intend on ruining someone's tenure, but I also highly suspect that the paper about 5 and 7 kangaroos was not reviewed by supervisors or even by the peer community..

I also discovered that C can go as low as 1.05 if we also allow 1.05 sqrt(N) stored items, with 3 kangaroos alone, and only addition group operations. And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.

Oh and BTW 3 & 4-kang methods are already "mirrored", this is basically the reason why C was brought down from 2.0 to 1.72.
?
Activity: -
Merit: -
October 08, 2024, 11:26:12 AM
#4
Such papers is just a way to get a degree, zero new ideas.
And all this is not important actually.
The main problem that you won't get better than K=1.7 this way even if you use 1000 instead of 3-4-5-7 kangs.
K=1.7 is boring, really. It's like solving puzzles #6x  Grin
Why don't you try this? https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
Going this way (a long way btw) you can "invent" something interesting and get real K (not in theory but real) around 1.2 if you are smart enough Cheesy I call this approach "mirrored" kangs.
But, of course, this way is not so easy as "normal" kangs that always jump in one direction.
Just a tip for you because it seems you read some papers instead of creating magic circles/code as most people here Cheesy
Though I doubt that you will break #135, it's always fun to invent and discover so you can spend a lot of time having fun...
member
Activity: 165
Merit: 26
October 08, 2024, 05:34:32 AM
#3

It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.

Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.


Regarding this very specific problem, one limited approach I can think of is to subtract G from your initial pubkey and keep them both; the initial and the offset resulting from this subtraction.

Now one of these two is sure to have an even private key, as some pubkey minus G = its private key minus 0x1.

Then you "divide" them both and at least one resulting offset will be within the desired interval.

Maybe you could find a similar work around for your specific problem


Yes, that approach works, but what are the consequences?

First, let's say the private key is 0x1. So, we would rather add G and then divide, otherwise we need to add a special condition check in the algorithm ("is P the point at infinity"), making it slower.

But after division, we have two resulting points:

[1/2]P
[1/2](P + G)

and we don't know which one of these two is the one that sits in the lower interval, and which one sits in another interval (points starting at keys [1/2 mod n] = (n+1)/2 onward).

So we must look for either of them. Since we now have two keys to search for, any algorithm will require two times more work at some stage, in an interval that is half in size (either the lower interval, or the [1/2 + k] interval)

Let's say our algorithm has an average run-time of C * sqrt(N) where C is some (any) constant factor and N is the size of the interval.

Let's simplify C to be 1 (we'll have the same end-result if C is either lower or greater then 1).

If we look for the private key in the original interval, average run-time is then sqrt(N)

If we look for 2 private keys in a half-range interval, average run-time is then 2 * sqrt(N/2) = sqrt(2) * sqrt(N) = 1.41 sqrt(N)

My conclusion (non-definitive and open for debates): the average run-time increases by 41% every time we  "divide public key by 2" and attempt to work-around the parity problem.

Now, the cited study uses values for the exponent as 6-decimal digit figures. Following the same logic, I would think that this means the predicted results of his analysis are only valid if the private key that is beaing searched is a multiple of 1.000.000. Otherwise, his wild starting points (the exponents are being used to compute initial wild kangaroo positions) are not really guaranteed to lie in the search interval, but rather in 1.000.000 different intervals.
member
Activity: 43
Merit: 10
October 07, 2024, 02:52:20 PM
#2

It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.

Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.


Regarding this very specific problem, one limited approach I can think of is to subtract G from your initial pubkey and keep them both; the initial and the offset resulting from this subtraction.

Now one of these two is sure to have an even private key, as some pubkey minus G = its private key minus 0x1.

Then you "divide" them both and at least one resulting offset will be within the desired interval.

Maybe you could find a similar work around for your specific problem
member
Activity: 165
Merit: 26
October 07, 2024, 04:00:21 AM
#1
So while rethinking a bit on Pollard's 3 kangaroo method I was reminded about this paper:

Kangaroo Methods for Solving the Interval Discrete Logarithm Problem
https://www.math.auckland.ac.nz/~sgal018/AFhons.pdf

In that, the author attempts to find better running times than the 4-kangaroo method presented by Pollard et. all in 2011 or so, and claims to have found them, at least by using 5 kangaroos. Then he also presents a 7-kangaroo algorithm with an almost similar run-time (but not really better).

However I'm either stupid or missed something obvious. The author uses some smart approximation algorithms to find some constants that should be used for the exponents of the Tame and Wild kangaroos.

But these constants are not integers, so the author suggests to use the closest integer values when multiplied by N (interval size). The entire analysis is based on the assumption that these Wild kangaroos start off inside the interval.

What I do not understand is: if we are given a public key. and are told it is found in some interval of size N, then the only known points that we can tell for sure are in some interval are:

- the public key itself
- the opposite point (between -N and -1)
- integer multiples of either of the above two points
- added or subtracted known deltas of any point in the above three cases

So, how did the author reached the conclusion of finding better algorithms, given that we can't be sure that when we do an exponentiation of the form:

Code:
g**0.815N * h

then the resulting point will only ever lie in a known interval as the original only when both N and the private key are both divisible by 1000?

It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.

Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.

So, is this study wrong? There are also no given experimental tests.
Pages:
Jump to: