Welcome to the resource topic for 2025/1932
Title:
Decoding Balanced Linear Codes With Preprocessing
Authors: Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
Abstract:Prange’s information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any \mathbb{F}_2-linear code C of message length n up to relative error rate O(\log n / n) in \mathsf{poly}(n) time. We show that the error rate can be improved to O((\log n)^2 / n), provided: (1) the decoder has access to a polynomial-length advice string that depends on C only, and (2) C is n^{-\Omega(1)}-balanced.
As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate.
Our main technical result is that the Hamming weight of Hw, where H is a random sample of short dual codewords, measures the proximity of a word w to the code in the regime of interest. Given such H as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding Hw for an arbitrary polynomial-size advice matrix H.
ePrint: https://eprint.iacr.org/2025/1932
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .