Decoding the tensor product of $ \mathrm{MLD} $ codes and applications for code cryptosystems

V. M. Deundyak ; Yu. V. Kosolapov ; E. A. Lelyuk

Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 2, pp. 239-252

Résumé

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 $\mathrm{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).

Détail

Keywords: majority decoder, Reed–Muller–Berman codes, tensor product codes.