maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-3-276-290mais-687Research ArticleОригинальные статьиArticlesОб алгоритме расщепления носителя для индуцированных кодовThe Support Splitting Algorithm for Induced Codeshttps://orcid.org/0000-0002-1491-524XКосолаповЮрий ВладимировичKosolapovYury V.

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

PhD

itaim@mail.ruhttps://orcid.org/0000-0001-6363-4332ШигаевАлексей НиколаевичShigaevAleksey N.

магистр

graduate student

aleksejshig@gmail.comЮжный Федеральный УниверситетРоссияSouth Federal UniversityRussian Federation201830062018253276290Copyright © Косолапов Ю.В., Шигаев А.Н., 20182018Косолапов Ю.В., Шигаев А.Н.Kosolapov Y.V., Shigaev A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/687

В 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.

In the paper, the analysis of the stability of the McEliece-type cryptosystem on induced codes for key attacks is examined. In particular, a model is considered when the automorphism group is trivial for the base code C, on the basis of which the induced code Flq ⊗ C is constructed. In this case, as shown by N. Sendrier in 2000, there exists such a mapping, called a complete discriminant, by means of which a secret permutation that is part of the secret key of a McEliece-type cryptosystem can be effectively found. The automorphism group of the code Flq ⊗ C is nontrivial, therefore there is no complete discriminant for this code. This suggests a potentially high resistance of the McEliece-type cryptosystem on the code Flq ⊗ C. The algorithm for splitting the support for the code Flq ⊗ C is constructed and the efficiency of this algorithm is compared with the existing attack on the key of the McElice type cryptosystem based on the code Flq ⊗ C.

групповые кодыиндуцированные групповые кодыалгоритм расщепления носителякриптосистема Мак-Элисаgroup codesinduced group codessupport splitting algorithmthe McEliece cryptosystemReferencesMcEliece R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, JPL Deep Space Network Progress Report, 1978, № 42–44, 114–116.McEliece R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, JPL Deep Space Network Progress Report, 1978, № 42–44, 114–116.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.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.Morelos-Zaragoza R. H., The Art of Error Correcting Coding, 2nd Edition, John Wiley & Sons, Inc., 2006.Morelos-Zaragoza R. H., The Art of Error Correcting Coding, 2nd Edition, John Wiley & Sons, Inc., 2006.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.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.Бородин М. А., Чижов И. В., “Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида–Маллера”, Дискрет. матем., 26:1 (2014), 10– 20.Borodin M. A., Chizhov I. V., “Effective attack on the McEliece cryptosystem based on Reed-Muller codes”, Discrete Mathematics and Applications, 24:5 (2014), 273–280.Деундяк В. М., Косолапов Ю. В., “Алгоритмы для мажоритарного декодирования групповых кодов”, Модел. и анализ информ. систем, 22:4 (2015), 464–482.Deundyak V. M., Kosolapov Yu. V., “Algorithms for majority decoding of group codes”, Model. Anal. Inform. Sist., 22:4 (2015), 464–482, (in Russian).Деундяк В. М., Косолапов Ю. В., “Криптосистема на индуцированных групповых кодах”, Модел. и анализ информ. систем, 23:2 (2016), 137–152.Deundyak V. M., Kosolapov Yu. V., “Cryptosystem based on induced group codes”, Model. Anal. Inform. Sist., 23:2 (2016), 137–152, (in Russian).Sendrier N., “Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm”, IEEE Trans. on IT, 46:4 (2000), 1193–1203.Sendrier N., “Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm”, IEEE Trans. on IT, 46:4 (2000), 1193–1203.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.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.Lenstra A. K., Verheul E. R., “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14:4 (2001), 255–293.Lenstra A. K., Verheul E. R., “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14:4 (2001), 255–293.Деундяк В. М., Косолапов Ю. В., “Использование тензорного произведения кодов Рида–Маллера в асимметричной криптосистеме типа Мак-Элиса и анализ ее стойкости к атакам на шифрограмму”, Вычислительные технологии, 22:4 (2017), 43–60.Deundyak V. M., Kosolapov Yu. V., “The use of the tensor product of Reed-Muller codes in asymmetric McEliece type cryptosystem and analysis of its resistance to attacks on the cryptogram”, Computational Technologies, 22:4 (2017), 43–60, (in Russian).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.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.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.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.

The authors declare that there are no conflicts of interest present.