A statistical estimation algorithm of the weight distribution of a linear code is shown, based on using its generator matrix as a compression function on random bit strings.
@cite_11: Decoding random linear codes is a fundamental problem in complexity theory and lies at the heart of almost all code-based cryptography. The best attacks on the most prominent code-based cryptosystems such as McEliece directly use decoding algorithms for linear codes. The asymptotically best decoding algorithm for random linear codes of length n was for a long time Stern’s variant of information-set decoding running in time O 20.05563n . Recently, Bernstein, Lange and Peters proposed a new technique called Ball-collision decoding which offers a speed-up over Stern’s algorithm by improving the running time to O 20.05558n . In this paper, we present a new algorithm for decoding linear codes that is inspired by a representation technique due to Howgrave-Graham and Joux in the context of subset sum algorithms. Our decoding algorithm offers a rigorous complexity analysis for random linear codes and brings the time complexity down to O 20.05363n .
The Lee-Brickell algorithm can be written as follows (see @cite_11 ): Compute the permuted syndrome @math . Fix a weight @math . If then we can choose another set @math of @math columns from @math to obtain a set @math of columns of @math that sum to @math . Otherwise, restart with a different @math .