Том 27, номер 2, 2020 г., Стр. 17-42

УДК 519.7
Деундяк В. М., Лелюк Е. А.
Теоретико-графовый метод декодирования некоторых групповых MLD-кодов

Аннотация:
Построен класс мажоритарно-декодируемых групповых кодов с помощью метода комбинирования, основанного на применении тензорного произведения и суммы кодов. Конструкция этого класса базируется на известном подходе Касами — Лина, при котором рассматриваются не отдельно взятые коды, а семейства кодов, и использует важную для мажоритарно-декодируемых кодов конструкцию $M$-ортогональности, предложенную Мэсси. Исследуемые в работе коды являются идеалами в групповых алгебрах над, вообще говоря, некоммутативными конечными группами. Для рассматриваемых групповых кодов разработана алгоритмическая модель мажоритарного декодирования на основе теоретико-графового подхода. Важной частью этой модели является построение специального декодирующего графа для декодирования одной координаты зашумлённого кодового слова, соответствующей этому графу. Групповые свойства кодов позволяют быстро находить декодирующие графы для остальных координат. Разработан алгоритм декодирования, который, обращаясь к декодирующим графам, исправляет ошибки во всех координатах зашумлённого кодового слова. В качестве примера семейств групповых кодов приводятся важные в криптографии двоичные коды Рида — Маллера. Кодовые криптосистемы рассматриваются как альтернатива широко применяемым в настоящее время теоретико-числовым криптосистемам, поскольку оказываются стойкими к атакам с помощью квантовых компьютеров. Актуальность решаемых в работе задач заключается в том, что использование групповых кодов и их различных комбинаций в настоящее время является одним из перспективных способов укрепления кодовых криптосистем, поскольку позволяет строить новые коды со сложной алгебраической структурой, что положительно сказывается на стойкости кодовой криптосистемы.
Ил. 2, библиогр. 11.

Ключевые слова: MLD-код, мажоритарное декодирование, групповой код, тензорное произведение, граф.

DOI: 10.33048/daio.2020.27.648

Деундяк Владимир Михайлович ^1,2
Лелюк Евгений Андреевич ¹
1. Институт математики, механики и компьютерных наук им. И. И. Воровича,
ул. Мильчакова, 8а, 344058 Ростов-на-Дону, Россия
2. Научно-исследовательский институт «Спецвузавтоматика»,
Газетный пер., 51, 344002 Ростов-на-Дону, Россия
е-mail: vl.deundyak@gmail.com, lelukevgeniy@mail.ru

Статья поступила 24 февраля 2019 г.
После доработки — 17 октября 2019 г.
Принята к публикации 27 ноября 2019 г.

Литература

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

[2] Кларк Дж. мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радиосвязь, 1981.

[3] Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида — Маллера // Дискрет. математика. 1994. Т. 6, № 2. С. 3–20.

[4] Циммерман К.-Х. Методы теории модулярных представлений в алгебраической теории кодирования. М.: МЦНМО, 2011.

[5] NIST reveals 26 algorithms advancing to the post-quantum crypto ‘Semi-finals’ // National Institute of Standards and Technology. Jan. 30, 2019. http://bib5.gov/news-events/news/2019/01/bib5-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. 2014. Vol. 26, No. 1. P. 273–280.

[7] Sidel’nikov V. M., Shestakov S. O. On an encoding system constructed on the basis of generalized Reed–Solomon codes // Discrete Math. Appl. 1992. Vol. 2, No. 4. P. 439–444.

[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). Heidelberg: Springer, 2007. P. 347–360. (Lect. Notes Comput. Sci.; Vol. 4515).

[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). Heidelberg: Springer, 2010. P. 61–72. (Lect. Notes Comput. Sci.; Vol. 6061).

[10] Деундяк В. М., Косолапов Ю. В. Криптосистема на индуцированных групповых кодах // Моделирование и анализ информ. систем. 2016. Т. 23, № 2. С. 137–152.

[11] Деундяк В. М., Косолапов Ю. В., Лелюк Е. А. Декодирование тензорного произведения MLD-кодов и приложения к кодовым криптосистемам // Моделирование и анализ информ. систем. 2017. Т. 24, № 2. С. 239–252.

[12] Kasami T., Lin S. On the construction of a class of majority-logic decodable codes // IEEE Trans. Inform. Theory. 1971. Vol. IT-17, No. 5. P. 600–610.

[13] Сидельников В. М. Теория кодирования. М.: ФИЗМАТЛИТ, 2008.

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

[15] Блох Э. Л., Зяблов В. В. Кодирование обобщённых каскадных кодов // Пробл. передачи информации. 1974. Т. 10, № 3. C. 45–50.

[16] Зиновьев В. А. Обобщённые каскадные коды // Пробл. передачи информ. 1976. Т. 12, № 1. С. 5–15.

[17] Деундяк В. М., Косолапов Ю. В. Алгоритмы для мажоритарного декодирования групповых кодов // Моделирование и анализ информ. систем. 2015. Т. 22, № 4. С. 464–482.

[18] Curtis C. W., Reiner I. Representation theory of finite groups and associative algebras. New York: Intersci. Publ., 1962.