Stern’s algorithm: A short introduction

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

\blacksquare ~ \textnormal{\textbf{Problem} \textsc{General Decoding}}
Given a random matrix \mathbf{A} \in \mathbb{F}_2^{k\times n} and a pertubed vector \mathbf{r}, find a vector \mathbf{x} = (x_1,x_2,\ldots,x_{k}) such that \mathbf{x}\cdot\mathbf{A} = \mathbf{y} = (y_1,y_2,\ldots,y_n) and \mathbf{r} = (r_1,r_2,\ldots,r_n) agrees in as many points as possible.

\blacksquare ~ \textnormal{\textbf{Algorithm} \emph{Stern's algorithm}}
Input: generator matrix \mathbf{G}

  1. Pick a random column permutation \pi and permute \mathbf{G}.
  2. Make \mathbf{G} systematic.
  3. Pick all possible sums of p/2 columns from the k/2 first rows of \mathbf{G} and store in list \mathcal{L} indexed by bits in the q-field.
  4. Same as above but with the next k/2 rows of \mathbf{G}. Look in \mathcal{L} for values indexed by the q-field. For each such collision, create the sum of the two vectors. Now they form a vector stemming from the p columns in the first the k columns that is zero in the q-field.
  5. For each such candidate, calculate the whole weight. If it is w, 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s