Об алгоритме расщепления носителя для индуцированных кодов
https://doi.org/10.18255/1818-1015-2018-3-276-290
Аннотация
В 2000 г. Н. Сендриер показал, что если для линейного [n, k, d]-кода C(⊆ Fnq ) длины n и размерности k с кодовым расстоянием d группа автоморфизмов PAut(C) этого кода тривиальна, то может быть построен детерминированный алгоритм расщепления носителя, позволяющий для кода D, перестановочно-эквивалентного коду C, найти такую перестановку σ, что σ(C) = D. Этот алгоритм, в частности, может быть применен для осуществления атаки на ключ кодовой криптосистемы типа Мак-Элиса на коде C. Целью настоящей работы является построение и анализ алгоритма расщепления носителя для кода Flq ⊗ C, индуцированного кодом C, l ∈ N. Так как группа автоморфизмов PAut(Flq ⊗ C) нетривиальна даже в случае, когда группа автоморфизмов базового кода C тривиальна, то это позволяет предположить потенциально высокую стойкость криптосистемы типа Мак-Элиса на коде Flq ⊗C к атаке на основе расщепления носителя. В работе строится алгоритм расщепления носителя для кода Flq ⊗ C и сравнивается эффективность этого алгоритма с имеющейся атакой на ключ криптосистемы типа Мак-Элиса на основе кода Flq ⊗ C.
Об авторах
Юрий Владимирович Косолапов
Южный Федеральный Университет
Россия
канд. техн. наук
Россия
канд. техн. наук
Алексей Николаевич Шигаев
Южный Федеральный Университет
Россия
магистр
Россия
магистр
Список литературы
1. McEliece R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, JPL Deep Space Network Progress Report, 1978, № 42–44, 114–116.
2. Sendrier N., Tillich J. P., Code-Based Cryptography: New Security Solutions Against a Quantum Adversary, ERCIM News, ERCIM, 2016 https://hal.archives-ouvertes. fr/hal-01410068/document.
3. Morelos-Zaragoza R. H., The Art of Error Correcting Coding, 2nd Edition, John Wiley & Sons, Inc., 2006.
4. Sidel’nikov V. M., Shestakov S. O, “On an encoding system constructed on the basis of generalized Reed-Solomon codes”, Discrete Mathematics and Applications, 2:4 (1992), 439–444.
5. Бородин М. А., Чижов И. В., “Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида–Маллера”, Дискрет. матем., 26:1 (2014), 10– 20.
6. Деундяк В. М., Косолапов Ю. В., “Алгоритмы для мажоритарного декодирования групповых кодов”, Модел. и анализ информ. систем, 22:4 (2015), 464–482.
7. Деундяк В. М., Косолапов Ю. В., “Криптосистема на индуцированных групповых кодах”, Модел. и анализ информ. систем, 23:2 (2016), 137–152.
8. Sendrier N., “Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm”, IEEE Trans. on IT, 46:4 (2000), 1193–1203.
9. Haily A., Harzalla D., “On Binary Linear Codes Whose Automorphism Group is Trivial”, Journal of Discrete Mathematical Sciences and Cryptography, 18:5 (2015), 495–512.
10. Lenstra A. K., Verheul E. R., “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14:4 (2001), 255–293.
11. Деундяк В. М., Косолапов Ю. В., “Использование тензорного произведения кодов Рида–Маллера в асимметричной криптосистеме типа Мак-Элиса и анализ ее стойкости к атакам на шифрограмму”, Вычислительные технологии, 22:4 (2017), 43–60.
12. Girault M., “A (non-practical) three-pass identification protocol using coding theory”, Advances in Cryptology AUSCRYPT ’90, Lecture Notes in Computer Science, 453, 1990, 265–272.
13. Sendrier N., Simos D. E., “The Hardness of Code Equivalence over Fq and its Application to Code-based Cryptography”, Post-Quantum Cryptography. PQCrypto 2013, Lecture Notes in Computer Science, 7932, 2013, 203–216.
Рецензия
Для цитирования:
Косолапов Ю.В., Шигаев А.Н. Об алгоритме расщепления носителя для индуцированных кодов. Моделирование и анализ информационных систем. 2018;25(3):276-290. https://doi.org/10.18255/1818-1015-2018-3-276-290
For citation:
Kosolapov Yu.V., Shigaev A.N. The Support Splitting Algorithm for Induced Codes. Modeling and Analysis of Information Systems. 2018;25(3):276-290. (In Russ.) https://doi.org/10.18255/1818-1015-2018-3-276-290
Просмотров:
890
Послать статью по эл. почте 