Декодирование тензорного произведения MLD-кодов и приложения к кодовым криптосистемам


https://doi.org/10.18255/1818-1015-2017-2-239-252

Полный текст:


Аннотация

Для практического применения кодовой криптосистемы типа Мак-Элиса необходимо, чтобы используемый в основе криптосистемы код имел быстрый алгоритм декодирования. С другой стороны, используемый код должен быть таким, чтобы нахождение секретного ключа по известному открытому ключу было практически неосуществимо при относительно небольшом размере ключа. В связи с этим в настоящей работе  предлагается в криптосистеме типа Мак-Элиса использовать тензорное произведение \(C_1\otimes C_2\) групповых \(\textrm{MLD}\)-кодов \(C_1\) и \(C_2\). Алгебраическая структура кода \(C_1\otimes C_2\) в общем случае отличается от структуры кодов \(C_1\) и \(C_2\), поэтому представляется возможным построение стойких криптосистем типа Мак-Элиса даже на основе кодов \(C_i\), для которых известны успешные атаки на ключ. Однако на этом пути возникает проблема декодирования кода \(C_1\otimes C_2\). Основной результат настоящей работы -- построение и обоснование набора необходимых для декодирования этого кода быстрых алгоритмов. Процесс построения декодера существенно опирается на групповые свойства кода \(C_1\otimes C_2\). В качестве приложения в работе построена криптосистема типа Мак-Элиса на коде \(C_1\otimes C_2\) и приводится оценка ее стойкости к атаке на ключ в предположении, что для кодовых криптосистем на кодах \(C_i\) возможна эффективная атака на ключ. Полученные результаты численно проиллюстрированы в случае, когда \(C_1\), \(C_2\)  -- коды Рида--Маллера--Бермана, для которых соответствующая кодовая криптосистема взломана Л. Миндером и А. Шокроллахи (2007 г.).


Об авторах

Владимир Михайлович Деундяк
ФГНУ НИИ "Спецвузавтоматика" Южный Федеральный Университет
Россия

 канд. физ.-мат. наук, доцент

пер. Газетный, 51, г. Ростов-на-Дону, 344002 Россия

ул. Большая Садовая, 105/42, г. Ростов-на-Дону, 344006 Россия



Юрий Владимирович Косолапов
Южный Федеральный Университет
Россия

канд. техн. наук

ул. Большая Садовая, 105/42, г. Ростов-на-Дону, 344006 Россия



Евгений Андреевич Лелюк
Южный Федеральный Университет
Россия

магистрант

ул. Большая Садовая, 105/42, г. Ростов-на-Дону, 344006 Россия



Список литературы

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.

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

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

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

5. Gabidulin E. M. et al., “Ideals Over a Non-Commutative Ring and Their Application in Cryptology”, Advances in Cryptology–EUROCRYPT’91 / Ed. by D.W. Davies. Lect. Notes in Comp. Sci., 547 (1991), 482–489.

6. Сидельников В.М., “Открытое шифрование на основе двоичных кодов Рида– Маллера”, Дискретная математика, 6:2 (1994), 3–20; [Sidel’nikov V. M., “Open coding based on Reed–Muller binary codes”, Diskr. Mat., 6:2 (1994), 3–20, (in Russian).]

7. Сидельников В.М., Шестаков С.О., “О системе шифрования, основанной на обобщенных кодах Рида–Соломона”, Дискретная математика, 3:3 (1992), 57–63; [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).]

8. Деундяк В.М. и др., “Модификация криптоаналитического алгоритма Сидельникова– Шестакова для обобщенных кодов Рида–Соломона и ее программная реализация”, Известия высших учебных заведений. Северо-Кавказский регион. Технические науки, 2006, № 4, 15–20; [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, № 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.

10. Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Lecture Notes in Computer Science, 4515 (2007), 347–360.

11. Чижов И.И., Бородин М.А., “Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида–Маллера”, Дискрет. матем., 26:1 (2014), 10– 20; [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).]

12. Деундяк В.М., Косолапов Ю.В., “Криптосистема на индуцированных групповых кодах”, Модел. и анализ информ. систем, 23:2 (2016), 137–152; [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).]

13. Деундяк В.М., Косолапов Ю.В., “Алгоритмы для мажоритарного декодирования групповых кодов”, Модел. и анализ информ. систем, 22:4 (2015), 464–482; [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).]

14. Циммерман К.-Х., Методы теории модулярных представлений в алгебраической теории кодирования, МЦНМО, М., 2011; [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.

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


Дополнительные файлы

Для цитирования: Деундяк В.М., Косолапов Ю.В., Лелюк Е.А. Декодирование тензорного произведения MLD-кодов и приложения к кодовым криптосистемам. Моделирование и анализ информационных систем. 2017;24(2):239-252. https://doi.org/10.18255/1818-1015-2017-2-239-252

For citation: Deundyak V.M., Kosolapov Y.V., Leluk E.A. Decoding the Tensor Product of MLD Codes and Applications for Code Cryptosystems. Modeling and Analysis of Information Systems. 2017;24(2):239-252. (In Russ.) https://doi.org/10.18255/1818-1015-2017-2-239-252

Просмотров: 305

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)