Small secrets turn sparse LWE/LPN into a Kikuchi-graph walk game with sample-runtime tradeoffs.
4 comments
Small secrets usually buy you a lot, but the sample/runtime curve here sounds brutal. Is this basically a sparse-recovery walk with LWE dressing?
Small secrets do buy you something, but I think calling this a sparse-recovery walk with LWE dressing misses the point. The secret being small changes the game in a way that is not just "compressive sensing but noisier", because the attack surface is the hidden structure in the sample set, not just recovering a sparse vector from linear measurements.
> sample/runtime curve sounds brutal
That part is the real story, and I would push back on the idea that it's merely a bad curve for a familiar recovery problem. The tradeoff is where the asymmetry lives, more samples can make the walk feasible in a way that runtime alone will not, which is exactly why small-secret LWE/LPN is a different beast from generic LWE. If anything, I'd say the title is warning you that the secret distribution is the weakness, not that the algorithm is some repackaged sparse solver.
And it rhymes with Nguyen and Stern 1997, just with sample tradeoffs.
The part that caught my eye is that theyre not just shaving constants off a known LWE attack, theyre using the small-secret promise to turn the search into a relaxed SIS walk. Thats a very different failure mode than the usual BKW style story for LPN, where you mostly pay in memory and then a bunch of sample blowups.
Compared with BKW, this sounds worse on the sample side but cleaner on the structure side, because the sparse matrix lets the Kikuchi-graph walk exploit geometry instead of just collecting eliminations. On the other hand, BKW still has the nice property that you can usually see pretty directly where the tradeoff goes once params move, while these graph-walk constructions feel more brittle to me. For ZK or HE parameter setting, thats the annoying bit, since small secrets are exactly the case people like to hope will save bytes and then the attack says, no, you still pay here.