ENG
РУС
Поиск
Меню
О журнале
Политика открытого доступа
Редакционная коллегия
Редакционная политика
Редакционная этика
Правила рецензирования статей
Требования к оформлению статей
Формы представляемых документов
Рекомендации по оформлению ссылок на наш журнал
Редакция
Информация для подписчиков
Аннотации номера
Список авторов
Выпуски
Лицензионное соглашение
Порядок работы с персональными данными
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры













































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-2025 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

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