Decoding the Tensor Product of MLD Codes and Applications for Code Cryptosystems

Abstract

For the practical application of code cryptosystems such as McEliece, it is necessary that the code used in the cryptosystem should have a fast decoding algorithm. On the other hand, the code used must be such that finding a secret key from a known public key would be impractical with a relatively small key size. In this connection, in the present paper it is proposed to use the tensor product \( C_1 \otimes C_2 \) of group \(\textrm{MLD}\) codes \( C_1 \) and \( C_2 \) in a McEliece-type cryptosystem. The algebraic structure of the code \( C_1 \otimes C_2 \) in the general case differs from the structure of the codes \( C_1 \) and \( C_2 \), so it is possible to build stable cryptosystems of the McEliece type even on the basis of codes \( C_i \) for which successful attacks on the key are known. However, in this way there is a problem of decoding the code \( C_1 \otimes C_2 \). The main result of this paper is the construction and justification of a set of fast algorithms needed for decoding this code. The process of constructing the decoder relies heavily on the group properties of the code \( C_1 \otimes C_2 \). As an application, the McEliece-type cryptosystem is constructed on the code \( C_1 \otimes C_2 \) and an estimate is given of its resistance to attack on the key under the assumption that for code cryptosystems on codes \( C_i \) an effective attack on the key is possible. The results obtained are numerically illustrated in the case when \( C_1 \), \( C_2 \) are Reed--Muller--Berman codes for which the corresponding code cryptosystem was hacked by L. Minder and A. Shokrollahi (2007).