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.

Bibliographie

[1] Shor P. W., “Algorithms for quantum computation: Discrete logarithms and factoring”, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994, 124–134 | DOI | MR

[2] Sendrier N., Tillich J.-P., “Code-Based Cryptography: New Security Solutions Against a Quantum Adversary”, ERCIM News, 106, Special Theme Cybersecurity (2016) https://hal.archives-ouvertes.fr/hal-01410068

[3] McEliece R. J., A Public-Key Cryptosystem Based on Algebraic Coding Theory, JPL Deep Space Network Progress Report, No 42, 1978, 114–116

[4] Niederreiter H., “Knapsack-Type Cryptosystem and Algebraic Coding Theory”, Probl. Control and Inform. Theory, 15 (1986), 94–34 | MR

[5] Gabidulin E. M. et al., “Ideals Over a Non-Commutative Ring and Their Application in Cryptology”, Advances in Cryptology-EUROCRYPT'91, Lect. Notes in Comp. Sci., 547, ed. D. W. Davies, Springer-Verlag, 1991, 482–489 | DOI | MR

[6] Sidel'nikov V. M., “Open coding based on Reed–Muller binary codes”, Diskr. Mat., 6:2 (1994), 3–20 (in Russian) | Zbl

[7] Sidel'nikov V. M., Shestakov S. O., “O sisteme shifrovanija, osnovannoj pa obobshhennyh kodah Rida–Solomona”, Diskr. Mat., 3:3 (1992), 57–63 (in Russian) | Zbl

[8] Deundyak V. M. et al., “Modifikatsiya kriptoanaliticheskogo algoritma Sidel'nikova–Shestakova dlya obobshchennykh kodov Rida-Solomona i ee programmnaya realizatsiya”, Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Tekhnicheskie nauki, 2006, no. 4, 15–20 (in Russian)

[9] Overbeck R., “Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes”, Journal of Cryptology, 21:2 (2008), 280–301 | DOI | MR | Zbl

[10] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Lecture Notes in Computer Science, 4515, 2007, 347–360 | DOI | MR | Zbl

[11] Chizhov I. I., Borodin M. A., “Jeffektivnaja ataka na kriptosistemu Mak-Jelisa, postroennuju na osnove kodov Rida–Mallera”, Diskr. Mat., 26:1 (2014), 10–20 (in Russian) | DOI | MR | Zbl

[12] Deundyak V. M., Kosolapov Yu. V., “Cryptosystem Based on Induced Group Codes”, Modeling and Analysis of Information Systems, 23:2 (2016), 137–152 (in Russian) | MR

[13] Deundyak V. M., Kosolapov Yu. V., “Algorithms for Majority Decoding of Group Codes”, Modeling and Analysis of Information Systems, 22:4 (2015), 464–482 (in Russian) | MR

[14] Tsimmerman K.-Kh., Metody teorii modulyarnykh predstavleniy v algebraicheskoy teorii kodirovaniya, MTsNMO, M., 2011 (in Russian)

[15] Curtis C. W., Reiner I., Representation Theory of Finite Groups and Associative Algebras, Intersclence Publishers, New York, 1962 | MR | Zbl

[16] Lenstra A. K., Verheul E. R., “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14 (2001), 255–293 | DOI | MR | Zbl