Armadillo ECDSA-113

[WhoCares]

@cjack

Please confirm whether the issues described in the attachment are real bugs. Thanks.

[cjack]

Hey WhoCares,

I owe you a correction — and a big one.

In my previous reply, I said your point #3 (walk partition not Frobenius-invariant) was "a legitimate optimization opportunity, not a correctness bug." I was wrong, and I want to be upfront about it.

After a deeper analysis, we realized this is actually the root cause of why our collision is taking so long. Here's what we found:

The walk function uses p = x.lo & 31 (actual affine x bits) for the partition. Since τ(x,y) = (x², y²) produces completely different low bits, walks through P and τ(P) diverge immediately. There's no walk merging between orbit members, which means the 226× Frobenius speedup we assumed in our probability formula was never active.

The numbers speak for themselves:

What we thought: P = 94.5%, past the median, "just unlucky"
Reality: P = 1.28%, only 14% of the way to the median
Search space: We were walking in ORDER (5.19×10³³), not ORDER/226 (2.30×10³¹)
The canonicalization at DP time is mathematically correct (the server handles all Frobenius cases perfectly, as I described before), but it only helps with DP-space birthday collisions — which are negligible at our DP count (expected: 2.6×10⁻¹⁵). The dominant mechanism is walk merging, and that requires Frobenius-invariant iteration.

We're already working on the fix. The plan is to implement canonical lifting at every walk step:

Canonicalize the current point each step (112 squarings in GF(2¹¹³) — cheap in binary fields)
Use canonical x bits for the walk partition
Adjust (a,b) coefficients by λ^i at each canonicalization
Walk from the canonical representative
Cost: ~25-35% overhead per step. Gain: 226× from walk invariance. Net: ~178× speedup.

With this fix, the post-fleet timeline goes from years to weeks — completely changes the game.

You nailed the critical issue. Your analysis was more right than our initial review gave it credit for, and I should have dug deeper before replying. This is exactly why external reviews matter — thank you for pushing on this.

We'll keep you posted on the implementation progress.