I'd like to take credit for the below informal conjectures.
Solving ECDLP on an interval in 1.0 sqrt(b) group operations with 1.0 sqrt(b) stored items.This beats BSGS by a factor of 2x since BSGS requires 2 sqrt(b) operations (worse, I think they are actually scalar multiplications). This also beats any known kangaroo or other algorithm when DP = 0.
T1 -> T2 ->
-N/2. -4N/5 | 4N/5. N/5
Shift interval to [-N/2, N/2) (there's a twist to this though, 0 is not needed**)
Start two tames at -4N/5 and 4N/5
Start two wilds at Q=kG and -Q
Jump alternatively T1, W1, T2 and W2, use Y as jump function. Before each jump, check if the min(y, p - y) coordinate is mapped to a previous visit (type, distance). If so:
if type = T1 and visit.type = T1: continue walk, kangaroo jumped from left to right through opposite points
if type = T1 or T2 and visit.type = W1 or W2: DLP solved
if type = W1 and visit.type = W1: DLP solved* (it sounds absurd, but we have (-k + d1) == -(-k + d2)
if type = W2 and visit.type = W2: DLP solved* since (k + d1) == -(k + d2)
if type = W1 and visit.type = W2: DLP solved*, since -k + d1 = k + d2
if type = W2 and visit.type = W1: DLP solved* since k + d1 = -k + d2
if dlp not solved, move one of the two kangaroos forward
*: only if deltas don't cancel each other out (rarely but can happen)
**: can get rid of 0 because
8045a5248dae8d1dea3c4eab7caac0b35142851038eea7d1f2556bf08e47ccf0What happens?
Forward jumps by any kangaroo are equivalent to backward jumps of the same distance. Even if those points are not actually visited and stored.
T1 moving forward == T2 moving backward
W1 is moving forward while also mirroring a W2 walking in the opposite direction. Double win.
If W1 or W2 catch each other, or catch some arbitrary point AND its opposite after passing through the middle, DLP is solved. That is right, we can solve DLP using
a single wild kangaroo which sounds insane but is true, when k < 0 or -k < 0 and the walk passes through any -P & P points.
When these details are factored into the usual analysis of catching kangaroos, the probabilities of collision are multiplied because now the chance of hitting a visited point is actually quadrupled or so at each jump of any kangaroo:
- points that are symmetric are "the same point" basically = miss chance is halved
- kangs go in a sort of "meet in the middle" walk = more "visited" spots per average jump size
- kangs also jump in their usual forward walk ofcourse in the same time - classic analysis
So now there are 4 walks instead of two, but because of the much higher density of "already visited" probabilities, number of group operations to solve ECDLP is on average
< 1.03 sqrt(b) and number of scalar multiplications is basically zero (except initial setup) in 99.999% of the cases.
So now the big question: what happens if we want to decrease storage and use DP?
Well, I don't have any actual proof, but some parts of the above still hold, and depending on the ratio between the interval size and the chosen 2**DP there will still be an increased larger chance of collisions between DPs that are found on both halfs by misc. pairs of walks, and as such decreasing the total number of group operations that are expected, anywhere between 1.5 to 1.7 sqrt(b) - it is likely that as the interval increases, and the DP increases, complexity still stays around the same level or vey slightly increases.
