Syndrome decoding algorithms

Question

Overbeck et al. state in "Code-based Cryptography" from 2009:

A syndrome decoding algorithm takes as input a syndrome -- not a codeword. Each syndrome decoding algorithm leads immediately to an decoding algorithm and vice versa.

I have two questions about this:

1. Why does syndrome decoding work? Aren't there generally more error vectors $e$ than syndromes $He$ (for a parity check matrix $H$ with dimensions $(n - k) \times n$? How can syndromes be uniquely decoded into error vectors if that is true?
2. How can a decoding algorithm (which computes the closest codeword to a given message) be used to construct a syndrome decoding algorithm?

I understand that the opposite is simple, given a syndrome decoding algorithm one can construct a decoding algorithm by first computing the syndrome of the received message, applying the syndrome decoding algorithm and subtracting the resulting error vector from the received message.

Answer 1

Aren't there generally more error vectors $e$ than syndromes $He$?

Yes. The equation $s = r H = e H$ has, for a given (computed) syndrome $s$ many solutions in terms of $e$ - namely, as many as codewords: $2^k$. Indeed, if $e_1$ is a solution, then also $e_1 + c_j$ (where $c_j$ is any non-null codeword) is a solution.

How can syndromes be uniquely decoded into error vectors if that is true?

They cannot be "uniquely decoded", if by that you mean without uncertainty. We just choose, among the set of $2^k$ possible error patterns (what we call the coset), the most probable one (what we call the coset leader), because in that way we minimize (but don't preclude) the probability of wrong decoding. Which is the most probable $e$, depends on the statistics of the channel - typically (namely, for a BSC with $p<0.5$) that corresponds to the error pattern with fewest ones (minimal weight) - which also corresponds to choosing the closest codeword to the received message.

Answer 2

Answer to Question 2

Let the algorithm $A(r)$ with received word $r$ be a decoding algorithm that decodes to the nearest codeword, where a linear code is assumed (otherwise syndrome decoding wouldn't work). We also need to assume that the nearest codeword $c$ to $r$ is unique, i.e., $d_H(c,r)\leq t_c$ where $t_c$ is the error correcting radius of the code and $d_H$ is the Hamming distance.

Let $e=r\oplus A(r)$ then $e$ is the error vector between the received word and the nearest codeword. Then $$S(e):=H\cdot e=H\cdot (r\oplus A(r))\quad(1)$$ is the right syndrome to choose for this error.

Now let $e'$ range over the set $$e \oplus \left[S(n,t_c) \setminus \{e\}\right]$$ where $S(n,t_c)$ is the Hamming sphere of radius $t_c$ centred at the all zero vector of length $n,$ and for each $e'$ compute the syndrome $S(e')$ as in (1) to obtain a syndrome table for all nonzero error patterns in $S(n,t_c).$

Edit:

1. Since there are essentially $$\exp\left[\binom{n}{t_k}\right]$$ steps, yes this is exponential in complexity. But so is forming a Syndrome table.

2. A syndrome table is also calculated by going over each correctable error pattern $e$ and computing the syndrome $H\cdot e$. So, same complexity.

3. By definition these correctable error patterns $e$ are the minimum weight vectors in the corresponding coset $$e \oplus \mathcal{C},$$ of the code and thus we decode by adding the error $e$ corresponding to the syndrome to the received word. Google John Hall's Error Correction Code lecture notes at michigan state for a wonderful detailed explanation.