ГлавнаяАрхивО структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера

О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/2

Актуальной задачей криптографии является разработка криптосистем, стойких к атакам с использованием квантовых вычислений. Одной из перспективных схем шифрования считается система Мак-Элиса на кодах Гоппы. Однако эта система обладает рядом недостатков, обусловленных структурой кодов Гоппы, что делает актуальным поиск других кодов для схемы Мак-Элиса. Важными требованиями для этих кодов являются наличие быстрого декодера и обеспечение стойкости соответствующей криптосистемы к известным атакам, в том числе с использованием произведения Шура - Адамара. Многие попытки заменить коды Гоппы не привели к успеху, поскольку соответствующие криптосистемы оказались нестойкими к структурным атакам. В настоящей работе в качестве кода предлагается использовать D-конструкцию (D-код) на бинарных кодах Рида - Маллера. Эта конструкция является суммой специального вида тензорных произведений бинарных кодов Рида - Маллера. Для неё имеется быстрый алгоритм декодирования. С целью анализа стойкости схемы Мак-Элиса на D-кодах построена структурная атака с использованием произведения Шура - Адамара D-кода. Для выбора параметров, обеспечивающих стойкость криптосистемы к построенной атаке, исследуется разложимость степени D-кода в прямую сумму кодов Рида - Маллера и делается вывод о множестве стойких ключей криптосистемы.
  • Title О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера
  • Headline О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 57
  • Date:
  • DOI 10.17223/20710410/57/2
Ключевые слова
криптосистема типа Мак-Элиса, структурная стойкость, бинарные коды Рида - Маллера, сумма тензорных произведений, произведение Шура - Адамара
Авторы
Ссылки
http://csrc.nist.gov/projects/post-quantum-cryptography - National Institute of Standards and Technology (NIST). Post-Quantum Cryptography, 2021
McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report. 1978. P.42-44.
https://classic.mceliece.org/nist/mceliece-20201010.pdf. 2020.
Sidel’nikov V.M. Open coding based on Reed - Muller binary codes // Discr. Math. Appl. 1994. V. 4. No. 3. P.191-207.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems Control Inform. Theory. 1986. V. 15. No. 2. P. 159-166.
Berger T. and Loidreau P. How to mask the structure of codes for a cryptographic use // Des. Codes Cryptogr. 2005. V.35. No. 1. P.63-79.
Janwa H. and Moreno O. McEliece public cryptosystem using algebraic-geometric codes // Des. Codes Cryptogr. 1996. V. 8. P. 293-307.
Couvreur A., Marquez-Corbella I., and Pellikaan R. Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes // IEEE Trans. Inform. Theory. 2017. V. 8. No. 63. P. 5404-5418.
Chizhov I. V. and Borodin M. A. Effective attack on the McEliece cryptosystem based on Reed - Muller codes // Discr. Math. Appl. 2014. V.24. No. 5. P.273-280.
Wieschebrink C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes // LNCS. 2010. V.6061. P.61-72.
Sidel’nikov V.M. and Shestakov S. O. On an encoding system constructed on the basis of generalized Reed - Solomon codes // Discr. Math. Appl. 1992. V.4. No.2. P.439-444.
Деундяк В. М., Дружинина М. А., Косолапов Ю. В. Модификация криптоаналитического алгоритма Сидельникова - Шестакова для обобщенных кодов Рида - Соломона и ее программная реализация // Изв. вузов. Северо-Кавказский регион. Сер.: Технические науки. 2006. №4. С. 15-19.
Minder L. and Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // LNCS. 2007. V. 4515. P. 347-360.
Бородин М. А., Чижов И. В. Классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Дискретная математика. 2020. Т. 32. №1. С. 115-134.
Wieschebrink C. Two NP-complete problems in coding theory with an application in code based cryptography // IEEE Intern. Symp. Inform. Theory. 2006. P. 1733-1737.
Couvreur A., Gaborit P., Gauthier-Umana V., et al. Distinguisher-based attacks on public-key cryptosystems using Reed - Solomon codes // Des. Codes Cryptogr. 2014. V. 73. P. 641-666.
Otmani A. and Kalachi H. Square code attack on a modified Sidelnikov cryptosystem // LNCS. 2015. V. 9084. P.173-183.
Couvreur A. and Lequesne M. On the security of subspace subcodes of Reed - Solomon codes for public key encryption // IEEE Trans. Inform. Theory. 2022. V. 68. No. 1. P.632-648.
Morelos-Zaragoza R. H. The Art of Error Correcting Coding. John Wiley & Sons, Ltd. 2006. 263 p.
Деундяк В. М., Косолапов Ю. В. Криптосистема на индуцированных групповых кодах // Модел. и анализ информ. систем. 2016. Т. 23. №2. С. 137-152.
Деундяк В. М., Косолапов Ю. В. Анализ стойкости некоторых кодовых криптосистем, основанный на разложении кодов в прямую сумму // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. 2019. Т. 12. №3. С. 89-101.
Egorova E., Kabatiansky G., Krouk E., and Tavernier C. A new code-based public-key cryptosystem resistant to quantum computer attacks //j. Phys. Conf. Ser. 2019. V. 1163. P. 1-5.
Deundyak V. M., Kosolapov Yu. V., and Maystrenko I. A. On the decipherment of Sidel’nikov-type cryptosystems // LNCS. 2020. V. 12087. P.20-40.
Kasami T. and Lin S. On the construction of a class of majority-logic decodable codes // IEEE Trans. Inform. Theory. 1971. V. IT-17. No. 5. P.600-610.
Deundyak V.M., Kosolapov Yu. V., and Lelyuk E. A. Decoding the tensor product of MLD codes and applications for code cryptosystems // Automatic Control Comput. Sci. 2018. V. 52. No. 7. P. 647-657.
Deundyak V. M. and Lelyuk E. A. A graph-theoretical method for decoding some group MLD-codes //j. Appl. Industr. Math. 2020. V. 14. No.2. P.265-280.
Randriambololona H. On products and powers of linear codes under componentwise multiplication // Algorithmic Arithmetic Geometry Coding Theory. 2015. V. 637. P.3-78.
Deundyak V. M. and Kosolapov Yu. V. On the strength of asymmetric code cryptosystems based on the merging of generating matrices of linear codes // XVI Intern. Symp. Prob. of Redundancy in Information and Control Systems.Russia, 2019. P. 143-148.
Деундяк В. М., Косолапов Ю. В. О некоторых свойствах произведения Шура - Адамара для линейных кодов и их приложениях // Прикладная дискретная математика. 2020. №50. С. 72-86.
Сидельников В. М. Теория кодирования. М.: Физматлит, 2008.
Grassl M. and Rotteler M. Quantum block and convolutional codes from self-orthogonal product codes // Proc. IEEE Int. Symp. Inf. Theory. 2005. P. 1018-1022.
Henderson H. V. and Searle S. R. The vec-permutation matrix, the vec operator and Kronecker products: A review // Linear and Multilinear Algebra. 1981. No. 9. P.271-288.
О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/2
О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/2