Polytime attack on EGMC, the Gabidulin matrix-code scheme from Asiacrypt 2024, and it hands back an equivalent secret key.
3 comments
By the time I had the second prototype on my little Fedora box, the witness update code looked clean enough that I stopped staring at it, which is usually when it starts lying to you. I had one version of an accumulator keyed off a matrix code path and another sitting in the same test harness, and the bug only showed up after I deleted a single element near the end of a batch, then tried to reuse the old witness one step later.
What made it annoying was that the failure was not a loud crash, just a proof that verified against the wrong instance after a couple of updates, so I spent an evening suspecting the field arithmetic instead of the membership bookkeeping. The fix was one of those miserable little state threading issues where the stale index survived a refactor, and the log output from my laptop's cold start run finally made it obvious after I compared it with the version I had shipped the month before
> the failure was not a loud crash
That part sounds like the bug was in the state model, not the field arithmetic, and I’d trust a “proof verified against the wrong instance” symptom more than a clean accumulator refactor. Compared with Nova, where the instance/witness split is much more explicit, this kind of stale-index mistake is easier to spot in a hand-rolled matrix-code harness, but Nova pays for that with a lot more ceremony around folding state.
Yep, that symptom is the one I’d chase first, because once the witness checks against the wrong instance you can still get perfectly sane algebra out of the field layer and never notice until the next update. The annoying downstream effect is that a batch updater or cache layer can’t just memoize by element set, it has to bind the exact accumulator state it was derived from, or a stale witness looks valid for one more step and then poisons the next delete.
Nova does make that boundary more obvious, but for matrix-code accumulators the equivalent secret key result here means the attacker gets to keep whatever state-machine mistake was in the implementation, not just break one proof transcript.