Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Wikipedia states that McEliece is open to "information set decoding attack". What is an "information set decoding attack" and how serious is the vulnerability? (is it just a matter of choosing proper padding/parameters or is the issue deeper)
(motivated by Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?)
An old thread, but I thought it deserved an answer.
Information-set decoding
In short, the idea behind information-set decoding is to pick a sufficiently large set of error-free coordinates in a sent codeword such that the corresponding columns in the generator matrix form an invertible submatrix. Then, the information sequence can easily be obtained by linear algebra.
A plain information-set decoding algorithm is the simplest form of information-set decoding. It randomly selects an information set and then computes the information by solving linear equations. Consider the following. Let $\mathbf u \in \mathbb F_{2}^{n}$ be an unknown information sequence and
\begin{equation} \mathbf r = \begin{pmatrix}r_1 & r_2 & \cdots & r_n\end{pmatrix} = \mathbf u \mathbf G + \mathbf e \in \mathbb F_{2}^{n} \end{equation} a received codeword encoded by an $[n,k]$ linear code with generator matrix \begin{equation} \mathbf G = \begin{pmatrix} \mathbf g_1^T& \mathbf g_2^T& \cdots & \mathbf g_n^T\end{pmatrix}. \end{equation}
Suppose we pick an information set $\mathcal I \subset {1,2,\ldots,n}$ of size $k$. Recall that $\mathcal I$ is an information set if and only if the vectors $(\mathbf g_i)_{i \in \mathcal I}$ are all linearly independent. Now, define a masking function $\phi$ such that $ \phi(\mathbf G) = (\mathbf g_i^T)_{i \in \mathcal I} $ and, thus, \begin{equation} \phi(\mathbf r) = (r_i)_{i \in \mathcal I} = (\mathbf u \mathbf G + \mathbf e)_{i \in \mathcal I} = (\mathbf u \mathbf G)_{i \in \mathcal I} + (\mathbf e)_{i \in \mathcal I}. \end{equation} There is non-zero probability that symbols in the information set being perturbed by error, and therefore the procedure usually needs to be iterated with different information sets until it finds one that is entirely error free. Whenever the selected information set $\mathcal I$ is non-corrupted, i.e., $ (\mathbf e)_{i \in \mathcal I} = \mathbf 0 \iff \mathcal I \cap supp(\mathbf e) = \emptyset$, then the information symbols can be obtained by computing \begin{equation} \phi(\mathbf r)\phi(\mathbf G)^{-1} = \phi(\mathbf u \mathbf G)\phi(\mathbf G)^{-1} = \mathbf u. \end{equation} If, on the other hand, the information set contains a non-zero number of errors, then consequently $\phi(\mathbf r)\phi(\mathbf G)^{-1} \neq \mathbf u$, and therefore another different $\mathcal I$ must be chosen, until a solution satisfying the weight constraint is found.
There are several improvements to this technique, involving birthday techniques. One classic and commonly referenced algorithm is Stern's algorithm.
Decoding attack
Message recovery: Recovery of the message from a ciphertext is best done (if no structure can be exploited) by information-set decoding algorithms, by finding a minimum-weight codeword in the coset $\mathbf r+ \mathcal C$. This can be accomplished by constructing an extended code with the generator matrix $$ \mathbf G' = \begin{pmatrix}\mathbf G\\ \mathbf r\end{pmatrix}. $$ Then, an information-set decoding algorithm may be applied to find the minimum-weight codeword $\mathbf{e}$.
Key recovery: The purpose of a key recovery (structural attack) is to recover the private key from the public key. Many codes used in information transmission have a structure which allows for an efficient decoding procedure. In the context of information transmission, it does not pose a problem to have a structured code. In contrast, for code-based cryptography such as McEliece, security of the cryptosystem relies on that the public-key generator matrix is indistinguishable from a random one. Therefore, when structured codes are used, security will degrade because of the inherent structure of the public key. It is sometimes possible to recover the private key by looking for low-weight codewords in the code generated by the public key. By exploiting the structure of the code, this procedure can sometimes be accelerated.
Information-set decoding is a big hammer
Information-set decoding applies to basically all code-based cryptography. Therefore, it serves as an upper bound on the security and naturally, parameters are designed according to this bound. The linear decoding problem is NP-hard and therefore breaking McEliece remains exponential in the worst case. If or when a new, more efficient information-set decoding algorithm is invented, the old parameters must re-scaled.
