On the Concatenated Structure of a Linear Code. - Sendrier, Nicolas
We address here the problem of finding a concatenated structure in a linear code ? given by its generating matrix, that is, if ? is equivalent to the concatenation of an inner code B 0 and an outer code E 0, then find two codes B and E such that their concatenation is equivalent to ?. If the concatenated structure exists and is non trivial (i.e. the inner code B is non trivial), the dual distance of ? is equal to the dual distance of B. If this dual distance is small enough to allow the computation of many small weight words in the dual of ?, it is possible to recover first an inner code B, then an outer code E whose concatenation is equivalent to ?. These two codes are equivalent respectively to the original inner and outer codes B 0 and E 0.
Keywords: Concatenated codes; Code equivalence; McEliece cryptosystem; Niederreiter cryptosystem