Geodesic
A graph-theoretical method for~decoding~some~group~MLD-codes
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 17-42.

Voir la notice de l'article provenant de la source Math-Net.Ru

We construct the class of majority-logical decodable group codes using a method for combining the codes that are based on the tensor product and the sum of codes. The construction of this class rests on the Kasami–Lin technique, which allows us to consider not only individual codes but also families of codes and utilizes the $M$-orthogonality construction presented by Massey that is important for the majority-logical decodable codes. The codes under study are ideals in group algebras over, generally speaking, noncommutative finite groups. Some algorithmic model of the majority decoding for the codes under consideration is developed that is based on the graph-theoretic approach. An important part of this model is the construction of a special decoding graph for decoding one coordinate of a noisy codeword corresponding to this graph. The group properties of the codes enable us to quickly find decoding graphs for the remaining coordinates. We develop some decoding algorithm that corrects the errors in all coordinates of the noisy codeword using this decoding graphs. As an example of families of group codes, we give the Reed–Muller binary codes important in cryptography. The code cryptosystems are considered as an alternative to the number-theoretic cryptosystems widely used at present since they are resistant to attacks by quantum computers. The relevance of the problem under consideration lies in the fact that the use of group codes and their various combinations is currently one of the promising ways to increase the stability of code cryptosystems because enables us to construct new codes with a complex algebraic structure, which positively affects the stability of the code cryptosystems. Illustr. 2, bibliogr. 18.
Mots-clés : MLD-code, group code
Keywords: majority decoding, tensor product, graph. 
@article{DA_2020_27_2_a1,
     author = {V. M. Deundyak and E. A. Lelyuk},
     title = {A graph-theoretical method {for~decoding~some~group~MLD-codes}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--42},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_2_a1/}
}
TY  - JOUR
AU  - V. M. Deundyak
AU  - E. A. Lelyuk
TI  - A graph-theoretical method for~decoding~some~group~MLD-codes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 17
EP  - 42
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_2_a1/
LA  - ru
ID  - DA_2020_27_2_a1
ER  - 
%0 Journal Article
%A V. M. Deundyak
%A E. A. Lelyuk
%T A graph-theoretical method for~decoding~some~group~MLD-codes
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 17-42
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_2_a1/
%G ru
%F DA_2020_27_2_a1
V. M. Deundyak; E. A. Lelyuk. A graph-theoretical method for~decoding~some~group~MLD-codes. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 17-42. http://geodesic.mathdoc.fr/item/DA_2020_27_2_a1/

[1] Massey J. L., Threshold decoding, MIT Press, Cambridge, MA, 1963 | MR

[2] G. C. Clark (Jr.), J. B. Cain, Error-Correction Coding for Digital Communications, Plenum Press, New York, 1981 | MR

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

[4] K.-Kh. Tsimmerman, Methods of the Modular Representations Theory in Algebraic Coding Theory, MTsNMO, M., 2011 (Russian)

[5] NIST reveals 26 algorithms advancing to the post-quantum crypto 'Semifinals', National Institute of Standards and Technology (accessed May 23, 2020) http://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals

[6] Borodin M. A., Chizhov I. V., “Effective attack on the McEliece cryptosystem based on Reed–Muller codes”, Discrete Math. Appl., 26:1 (2014), 273–280 | MR | Zbl

[7] Sidel'nikov V. M., Shestakov S. O., “On an encoding system constructed on the basis of generalized Reed–Solomon codes”, Discrete Math. Appl., 2:4 (1992), 439–444 | DOI | MR | Zbl

[8] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Advances in Cryptology – EUROCRYPT 2007, Proc. 26th Annu. Int. Conf. Theory Appl. Cryptogr. Tech. (Barcelona, Spain, May 20–24, 2007), Lect. Notes Comput. Sci., 4515, Springer, Heidelberg, 2007, 347–360 | DOI | MR | Zbl

[9] Wieschebrink C., “Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes”, Post-Quantum Cryptography, Proc. 3rd Int. Workshop (Darmstadt, Germany, May 25–28, 2010), Lect. Notes Comput. Sci., 6061, Springer, Heidelberg, 2010, 61–72 | DOI | MR | Zbl

[10] V. M. Deundyak, Yu. V. Kosolapov, “Cryptosystem based on induced group codes”, Model. Anal. Inf. Sist., 23:2 (2016), 137–152 (Russian) | MR

[11] V. M. Deundyak, Yu. V. Kosolapov, E. A. Lelyuk, “Decoding the tensor product of MLD codes and applications for code cryptosystems”, Autom. Control Comput. Sci., 52:7 (2018), 647–657 | DOI | MR

[12] Kasami T., Lin S., “On the construction of a class of majority-logic decodable codes”, IEEE Trans. Inform. Theory, IT-17:5 (1971), 600–610 | DOI | MR | Zbl

[13] V. M. Sidel'nikov, Coding Theory, FIZMATLIT, M., 2008 (Russian)

[14] Morelos-Zaragoza R. H., The art of error correcting coding, Wiley, Chichester, 2006

[15] Eh. L. Blokh, V. V. Zyablov, “Coding by generalized concatenated codes”, Probl. Inf. Transm., 10:3 (1974), 218–222 | MR | MR | Zbl

[16] V. A. Zinov'ev, “Generalized concatenated codes”, Probl. Peredachi Inf., 12:1 (1976), 5–15 (Russian) | MR | Zbl

[17] V. M. Deundyak, Y. V. Kosolapov, “Algorithms for majority decoding of group codes”, Model. Anal. Inf. Sist., 22:4 (2015), 464–482 (Russian) | MR

[18] Curtis C. W., Reiner I., Representation theory of finite groups and associative algebras, Interscience, New York, 1962 | MR | Zbl