Для цитирования:
Рацеев С. М., Череватенко О. И. Об алгоритмах декодирования кодов Гоппы на случай ошибок и стираний // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2022. Т. 22, вып. 1. С. 28-47. DOI: 10.18500/1816-9791-2022-22-1-28-47, EDN: SKXHVX
Об алгоритмах декодирования кодов Гоппы на случай ошибок и стираний
В 1978 г. Мак-Элис построил первую кодовую криптосистему с открытым ключом, которая основана на применении помехоустойчивых кодов. Данная криптосистема именно на основе кодов Гоппы считается перспективной и криптостойкой с учетом квантовых вычислений. При этом эффективные атаки на секретные ключи этой криптосистемы до сих пор не найдены. В работе исследуются алгоритмы декодирования кодов Гоппы на случай ошибок и стираний. Приводятся четыре алгоритма декодирования на основе алгоритмов для кодов Рида–Соломона, предложенных Гао, Берлекэмпом и Месси, Сугиямой и др. Первые два алгоритма строятся на основе алгоритма Гао и относятся к алгоритмам бессиндромного декодирования, остальные — к алгоритмам синдромного декодирования. При этом любой из этих алгоритмов применим и для случая канала связи только с ошибками. Также приводятся примеры декодирования сепарабельных кодов Гоппы с использованием данных алгоритмов.
- Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. National Institute of Standards and Technology. Internal Report 8240. January, 2019. 27 p. https://doi.org/10.6028/NIST.IR.8240
- Гоппа В. Д. Новый класс линейных корректирующих кодов // Проблемы передачи информации. 1970. Т. 6, № 3. С. 24–30.
- Мак-Вильямc Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки : пер. с англ. Москва : Связь, 1979. 744 с.
- Блейхут Р. Теория и практика кодов, контролирующих ошибки / пер. с англ. И. И. Грушко, В. М. Блиновский ; под ред. К. Ш. Зигангирова. Москва : Мир, 1986. 576 с.
- Gao S. A new algorithm for decoding Reed–Solomon codes // Communications, Information and Network Security / eds.: V. Bhargava, H. V. Poor, V. Tarokh, S. Yoon. Norwell, MA : Kluwer, 2003. Vol. 712. P. 55–68.
- Huffman W. C., Pless V. Fundamentals of Error-Correcting Codes. New York ; Cambridge : Cambridge University Press, 2003. 646 p.
- Рацеев С. М. Элементы высшей алгебры и теории кодирования : учеб. пособие для вузов. Санкт-Петербург : Лань, 2022. 656 с.
- Федоренко С. В. Простой алгоритм декодирования алгебраических кодов // Информационно-управляющие системы. 2008. № 3. С. 23–27.
- Gohberg I., Olshevsky V. The fast generalized Parker–Traub algorithm for inversion of Vandermonde and related matrices // Journal of Complexity. 1997. Vol. 13, iss. 2. P. 208–234. https://doi.org/10.1006/jcom.1997.0442
- Yan S., Yang A. Explicit algorithm to the inverse of Vandermonde matrix // 2009 International Conference on Test and Measurement. Hong Kong, 2009. P. 176–179. https://doi.org/10.1109/ICTM.2009.5413083
- Rawashdeh E. A. A simple method for finding the inverse matrix of Vandermonde matrix // MATEMATICKI VESNIK. 2019. Vol. 71, № 3. P. 207–213.
- Рацеев С. М., Череватенко О. И. Об алгоритмах декодирования обобщенных кодов Рида–Соломона на случай ошибок и стираний // Вестник Самарского университета. Естественнонаучная серия. 2021. Т. 26, № 3. С. 17–29. http://doi.org/10.18287/2541-7525-2020-26-3-17-29
- 1753 просмотра