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

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

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 algebraic coding 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 ReedMuller 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

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

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

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

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

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

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

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

27. Lee Y., Cho J., Kim Y.-S., No J.-S. Cryptanalysis of the IvanovKabatiansky-Krouk-Rumenko cryptosystems // IEEE Communications Letters. 2020. V. 24. N 12. P. 2678–2681. https://doi.org/10.1109/LCOMM.2020.3019054

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

29. Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.