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.