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

Abstract

For the practical application of code cryptosystems such as McEliece, the code used in the cryptosystem should have a fast decoding algorithm. On the other hand, the code used must ensure that finding a secret key from a known public key is impractical with a relatively small key size. In this connection, in the present paper it is proposed to use tensor product \({{C}_{1}} \otimes {{C}_{2}}\) of group MLD codes \({{C}_{1}}\) and \({{C}_{2}}\) in a McEliece-type cryptosystem. The algebraic structure of code \({{C}_{1}} \otimes {{C}_{2}}\) in a general case differs from the structure of 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 code \({{C}_{1}} \otimes {{C}_{2}}\). The main result of this paper is the construction and validation of a series of fast algorithms needed for decoding this code. The process of constructing the decoder relies heavily on the group properties of code \({{C}_{1}} \otimes {{C}_{2}}\). As an application, the McEliece-type cryptosystem is constructed on 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}}\) and \({{C}_{2}}\) are Reed–Muller–Berman codes for which the corresponding code cryptosystem was hacked by L. Minder and A. Shokrollahi (2007).