  Due to the recent challenges in post-quantum cryptography, several new
approaches for code-based cryptography have been proposed. For example, a
variant of the McEliece cryptosystem based on interleaved codes was proposed.
In order to deem such new settings secure, we first need to understand and
analyze the complexity of the underlying problem, in this case the problem of
decoding a random interleaved code. A simple approach to decode such codes,
would be to randomly choose a vector in the row span of the received matrix and
run a classical information set decoding algorithm on this erroneous codeword.
In this paper, we propose a new generic decoder for interleaved codes, which is
an adaption of the classical idea of information set decoding by Prange and
perfectly fits the interleaved setting. We then analyze the cost of the new
algorithm and a comparison to the simple approach described above shows the
superiority of Interleaved Prange.
