Stern’s algorithm is an algorithm for solving the following:

Given a random matrix and a pertubed vector , find a vector such that and agrees in as many points as possible.

Input: generator matrix

- Pick a random column permutation and permute .
- Make systematic.
- Pick all possible sums of columns from the first rows of and store in list indexed by bits in the -field.

- Same as above but with the next rows of . Look in for values indexed by the -field. For each such collision, create the sum of the two vectors. Now they form a vector stemming from the columns in the first the columns that is zero in the -field.

- For each such candidate, calculate the whole weight. If it is , output it. If none is found, repeat from 1.

The description here is a bit short and the reader is advised to read this post on information-set decoding.

Advertisements