Quote from: Jean_Luc on April 27, 2020, 07:26:14 AM

I did a test, wanting to know the average time of the birthday paradox when searching collision between 2 tables (like the kangaroo problem).

The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where:
- you first travel a single tame kangaroo sqrt(n) steps to setup a trap
- then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps.
The factor 2 comes from that. There no need of a hashtable there.

Hi,

let's see if I have understood this Kangaroo algorithm:

P=k*G, you know P and you know that a < k < b, for semplicity : 0 < k < a, for example: 0 < k < 2^64 (starting interval)

you generate many sequence of 2 type of points:

1) tame: each sequence starts from a random point T0 that lies in the starting interval, then

T0, T1, T2, …. the difference between 2 consecutive points is: G, or 2*G, or 4*G, or 8*G, …, or 2^63*G

2) wild: each sequence starts from P + r*G, where r*G is a random points between 0 < k < 2^63, then:

W0, W1, W2, ….. the difference between 2 consecutive points is: G, or 2*G, or 4*G, …, or 2^63*G

each jump towards the next point depends on the x coordinate (mod 64 ) of the current point; in this way if a tame kangaroo reach a points already reached from a wild kangaroo (or viceversa), you have a collision and then same path from there.

In that case T = W -> t*G = w*G -> t*G = P + w*G -> t*G = k*G + w*G -> k = (t-w) mod n

Besides you use distinguished points to detect this collision.

In this example you generate about 2^32 points (T points) in the interval [1*G, (2^63+(2^32)(2^63))*G]
and about 2^32 points (W points) in the interval [P+r*G, ((k+r)+(2^32*2^63))*G]

let's say that both type of points have for sure their private keys in [1, 2^96] interval

But can you treat these points like if they were random? Can you apply in this case the birthday paradox?