doi: 10.17586/2226-1494-2022-22-2-324-331


УДК 004.056.55

Современные вариации криптосистем Мак-Элиса и Нидеррайтера

Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В. Современные вариации криптосистем Мак-Элиса и Нидеррайтера // Научно-технический вестник информационных технологий, механики и оптики. 2022. Т. 22, № 2. С. 324–331. doi: 10.17586/2226-1494-2022-22-2-324-331


Аннотация
Предмет исследования. Исследованы классические криптосистемы, предложенные Робертом Мак-Элисом в 1978 году и Гарольдом Нидеррайтером в 1986 году и их современные вариации. Метод. Выполнен детальный обзор пяти кодовых криптосистем с открытым ключом. Основные результаты. Показано, что некоторые из современных интерпретаций классических систем Мак-Элиса и Нидеррайтера имеют значительные недостатки. Установлено, что допущен ряд неточностей в описании криптосистемы XGRS на расширенных кодах Рида–Соломона, которая не обеспечивает заявленного уровня безопасности к атаке по информационным совокупностям. Продемонстрировано, что время генерации ключей и время расшифрования в современных кодовых криптосистемах достаточно велико, а открытый и секретный ключи занимают большой объем памяти. Практическая значимость. Выявленные неточности в рассмотренных схемах могут быть учтены при их улучшении и коррекции, а также при построении более точной оценки их уровня безопасности и эффективности. Представленные в работе кодовые криптосистемы могут рассматриваться как стандарты постквантовой криптографии и использоваться для защиты данных после появления мощного квантового компьютера.

Ключевые слова: постквантовая криптография, криптосистема Мак-Элиса, криптосистема Нидеррайтера, двоичные коды Гоппы, расширенные коды Рида–Соломона

Благодарности. Работа выполнена в рамках НИР № 620164 Университета ИТМО. Работа частично финансировалась Федеральной программой академического лидерства Приоритет 2030. Выражается благодарность Жан-Мишелю Дакуо за помощь в программной реализации.

Список литературы
  1. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 1994. P. 124–134. https://doi.org/10.1109/SFCS.1994.365700
  2. McEliece R.J. A public-key cryptosystem based on algebraiccoding theory // DSN Progress Report 42-44,1978. P. 114–116.
  3. Гоппа В.Д. Рациональное представление кодов и (L,g)-коды //Проблемы передачи информации. 1971. Т. 7. № 3. С. 41–49.
  4. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems of Control and Information Theory. 1986. V. 15. N 2. P. 159–166.
  5. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.:Связь, 1979. С. 506–507.
  6. Сидельников В.М., Шестаков С.О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискретная математика. 1992. Т. 4. № 3. С. 57–63.
  7. Peters C. Information-set decoding for linear codes over Fq // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. V. 6061. P. 81–94. https://doi.org/10.1007/978-3-642-12929-2_7
  8. Sidelnikov V.M. A public-key cryptosystem based on binary Reed-Muller codes // Discrete Mathematics and Applications. 1994. V. 4.N 3. P. 191–207. https://doi.org/10.1515/dma.1994.4.3.191
  9. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2007. V. 4515. P. 347–360. https://doi.org/10.1007/978-3-540-72540-4_20
  10. Gabidulin E.M. Public-key cryptosystems based on linear codes: Report 95-30 / Delft University of Technology, Faculty of Technical Mathematics and Informatics, 1995. P. 17–31.
  11. Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes // Journal of Cryptology. 2008. V. 21. N 2. P. 280–301. https://doi.org/10.1007/s00145-007-9003-9
  12. Baldi M., Chiaraluce F. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2007. P. 2591–2595. https://doi.org/10.1109/ISIT.2007.4557609
  13. Otmani A., Tillich J.P., Dallot L. Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes // Proc. of the First International Conference on Symbolic Computation and Cryptography. LMIB Beihang University, 2008. P. 69–81.
  14. Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes // Designs, Codes and Cryptography. 1996. V. 8. N 3. P. 293–307. https://doi.org/10.1023/A:1027351723034
  15. Faure C., Minder L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes // Proc. of the 11th International Workshop on Algebraic and Combinatorial Coding Theory. 2008. P. 99–107.
  16. Loidreau P. Strengthening McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2000. V. 1976. P. 585–598. https://doi.org/10.1007/3-540-44448-3_45
  17. Kobara K., Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC // IEEE Transactions on Information Theory. 2003. V. 49. N 12. P. 3160–3168. https://doi.org/10.1109/TIT.2003.820016
  18. Bernstein D.J., Lange T., Peters C. Attacking and defending the McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. V. 5299. P. 31–46. https://doi.org/10.1007/978-3-540-88403-3_3
  19. Bernstein D.J. et al. Classic McEliece: conservative code-based cryptography /NIST. 2017.
  20. Khathuria K., Rosenthal J., Weger V. Encryption scheme based on expanded reed-solomon codes // Advances in Mathematics of Communications. 2021. V. 15. N 2. P. 207–218. https://doi.org/10.3934/amc.2020053
  21. Reed I.S., Solomon G. Polynomial codes over certain finite fields // Journal of the Society for Industrial and Applied Mathematics. 1960. V. 8. N 2. P. 300–304. https://doi.org/10.1137/0108018
  22. Ivanov F., Kabatiansky G., Krouk E., Rumenko N. A new code-based cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2020. V. 12087. P. 41–49. https://doi.org/10.1007/978-3-030-54074-6_3
  23. Berlekamp E., McEliece R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. 1978. V. 24. N 3. P. 384–386. https://doi.org/10.1109/TIT.1978.1055873
  24. Augot D., Finiasz M., Sendrier N. A family of fast syndrome based cryptographic hash functions // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. V. 3715. P. 64–83. https://doi.org/10.1007/11554868_6
  25. Azouaoui A., Chana I., Belkasmi M. Efficient information set decoding based on genetic algorithms // International Journal of Communications, Network and System Sciences. 2012. V. 5.N 7. P. 423–429. https://doi.org/10.4236/ijcns.2012.57052
  26. Gauthier V., Otmani A., Tillich J.P. A Distinguisher-based attack on a variant of McEliece's cryptosystem based on Reed-Solomon codes // arXiv.org.2012. arXiv:1204.6459.https://doi.org/10.48550/arXiv.1204.6459
  27. Torres R.C., Sendrier N. Analysis of information set decoding for a sub-linear error weight // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2016. V. 9606. P. 144–161. https://doi.org/10.1007/978-3-319-29360-8_10
  28. Lee Y., Cho J., Kim Y.-S., No J.-S. Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko cryptosystems // IEEE Communications Letters. 2020. V. 24. N 12. P. 2678–2681. https://doi.org/10.1109/LCOMM.2020.3019054
  29. Patterson N. The algebraic decoding of Goppa codes // IEEE Transactions on Information Theory. 1975. V. 21. N 2. P. 203–207. https://doi.org/10.1109/TIT.1975.1055350
  30. Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2022 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика