maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-4-354-365HEFJOOmais-1825Research ArticleTheory of DataБыстрое вычисление циклических сверток и их приложения в кодовых схемах асимметричного шифрованияFast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemeshttps://orcid.org/0009-0009-7528-8532СушкоАндрей НиколаевичSushkoAndrey N.andrew-sush@mail.ruhttps://orcid.org/0000-0001-8146-0479ШтейнбергБорис ЯковлевичSteinbergBoris Y.borsteinb@mail.ruhttps://orcid.org/0000-0002-7893-655XВеденевКирилл ВладимировичVedenevKirill V.vedenevk@gmail.comhttps://orcid.org/0009-0005-0160-3609ГлухихАнтон АнатольевичGlukhikhAnton A.Antong.21072003@gmail.comhttps://orcid.org/0000-0002-1491-524XКосолаповЮрий ВладимировичKosolapovYury V.itaim@mail.ruЮжный федеральный университетРоссияSouthern Federal UniversityRussian Federation202311122023304354365Copyright © Сушко А.Н., Штейнберг Б.Я., Веденев К.В., Глухих А.А., Косолапов Ю.В., 20232023Сушко А.Н., Штейнберг Б.Я., Веденев К.В., Глухих А.А., Косолапов Ю.В.Sushko A.N., Steinberg B.Y., Vedenev K.V., Glukhikh A.A., Kosolapov Y.V.Данная работа распространяется под лицензией 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/1825

Разработка быстрых алгоритмов генерации ключей, шифрования и дешифрования не только повышает эффективность соответствующих операций. Такие быстрые алгоритмы, например, для асимметричных криптосистем на квазициклических кодах, позволяют экспериментально исследовать зависимость вероятности ошибочного расшифрования от параметров кода для малых параметров безопасности и экстраполировать эти результаты на большие значения параметров безопасности. В этой статье мы исследуем эффективные алгоритмы циклической свертки, специально разработанные, в том числе, для использования в алгоритмах кодирования и декодирования квазициклических LDPC и MDPC кодов. Соответствующие свертки работают с двоичными векторами, которые могут быть как разреженными, так и плотными. Предлагаемые алгоритмы достигают высокой скорости за счет компактного хранения разреженных векторов, использования аппаратно поддерживаемых инструкций XOR и замены операций по модулю специализированными преобразованиями цикла. Эти быстрые алгоритмы имеют потенциальное применение не только в криптографии, но и в других областях, где используются свертки.

The development of fast algorithms for key generation, encryption and decryption not only increases the efficiency of related operations. Such fast algorithms, for example, for asymmetric cryptosystems on quasi-cyclic codes, make it possible to experimentally study the dependence of decoding failure rate on code parameters for small security levels and to extrapolate these results to large values of security levels. In this article, we explore efficient cyclic convolution algorithms, specifically designed, among other things, for use in encoding and decoding algorithms for quasi-cyclic LDPC and MDPC codes. Corresponding convolutions operate on binary vectors, which can be either sparse or dense. The proposed algorithms achieve high speed by compactly storing sparse vectors, using hardware-supported XOR instructions, and replacing modulo operations with specialized loop transformations. These fast algorithms have potential applications not only in cryptography, but also in other areas where convolutions are used.

циклические сверткибыстрые алгоритмысхемы шифрованияcyclic convolutionsfast algorithmsencryption schemesReferencesT. Holton, Digital signal processing: Principles and applications. Cambridge University Press, 2021.T. Holton, Digital signal processing: Principles and applications. Cambridge University Press, 2021.D. S. Taubman, M. W. Marcellin, and M. Rabbani, “JPEG2000: Image compression fundamentals, standards and practice,” Journal of Electronic Imaging, vol. 11, no. 2, pp. 286–287, 2002.D. S. Taubman, M. W. Marcellin, and M. Rabbani, “JPEG2000: Image compression fundamentals, standards and practice,” Journal of Electronic Imaging, vol. 11, no. 2, pp. 286–287, 2002.V. Holub, J. Fridrich, and T. Denemark, “Universal distortion function for steganography in an arbitrary domain,” EURASIP Journal on Information Security, vol. 2014, no. 1, p. 1, 2014.V. Holub, J. Fridrich, and T. Denemark, “Universal distortion function for steganography in an arbitrary domain,” EURASIP Journal on Information Security, vol. 2014, no. 1, p. 1, 2014.Intel, “Intel® oneAPI Deep Neural Network Library.” 2023, Accessed: 07, 2023. [Online]. Available: https://software.intel.com/content/www/us/en/develop/articles/intel-mkl-dnn-part-1-library-overview-and-installation.html.Intel, “Intel® oneAPI Deep Neural Network Library.” 2023, Accessed: 07, 2023. [Online]. Available: https://software.intel.com/content/www/us/en/develop/articles/intel-mkl-dnn-part-1-library-overview-and-installation.html.N. R. Council and others, Getting up to speed: The future of supercomputing. National Academies Press, 2005.N. R. Council and others, Getting up to speed: The future of supercomputing. National Academies Press, 2005.N. Aragon et al., “BIKE: Bit Flipping Key Encapsulation.” Dec. 2017, [Online]. Available: https://hal.science/hal-01671903.N. Aragon et al., “BIKE: Bit Flipping Key Encapsulation.” Dec. 2017, [Online]. Available: https://hal.science/hal-01671903.T. B. Paiva and R. Terada, “Faster constant-time decoder for MDPC codes and applications to BIKE KEM,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2022, no. 4, pp. 110–134, 2022.T. B. Paiva and R. Terada, “Faster constant-time decoder for MDPC codes and applications to BIKE KEM,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2022, no. 4, pp. 110–134, 2022.P. Santini, M. Battaglioni, M. Baldi, and F. Chiaraluce, “Analysis of the error correction capability of LDPC and MDPC codes under parallel bit-flipping decoding and application to cryptography,” IEEE Transactions on Communications, vol. 68, no. 8, pp. 4648–4660, 2020.P. Santini, M. Battaglioni, M. Baldi, and F. Chiaraluce, “Analysis of the error correction capability of LDPC and MDPC codes under parallel bit-flipping decoding and application to cryptography,” IEEE Transactions on Communications, vol. 68, no. 8, pp. 4648–4660, 2020.K. Vedenev and Y. Kosolapov, “Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes,” in Code-Based Cryptography, 2023, pp. 35–55.K. Vedenev and Y. Kosolapov, “Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes,” in Code-Based Cryptography, 2023, pp. 35–55.Q. Guo, T. Johansson, and P. S. Wagner, “A key recovery reaction attack on QC-MDPC,” IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1845–1861, 2018.Q. Guo, T. Johansson, and P. S. Wagner, “A key recovery reaction attack on QC-MDPC,” IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1845–1861, 2018.M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini, “Performance bounds for QC-MDPC codes decoders,” in Code-Based Cryptography Workshop, 2021, pp. 95–122.M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini, “Performance bounds for QC-MDPC codes decoders,” in Code-Based Cryptography Workshop, 2021, pp. 95–122.S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, and A. Robinson, “A study of error floor behavior in QC-MDPC codes,” in International Conference on Post-Quantum Cryptography, 2022, pp. 89–103.S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, and A. Robinson, “A study of error floor behavior in QC-MDPC codes,” in International Conference on Post-Quantum Cryptography, 2022, pp. 89–103.S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, and A. Robinson, “Raw data and decoder for the paper ‘A study of error floor behavior in QC-MDPC codes.’” 2022, Accessed: 07, 2023. [Online]. Available: https://github.com/HastD/BIKE-error-floor.S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, and A. Robinson, “Raw data and decoder for the paper ‘A study of error floor behavior in QC-MDPC codes.’” 2022, Accessed: 07, 2023. [Online]. Available: https://github.com/HastD/BIKE-error-floor.A. Vasilenko, V. Veselovskiy, E. Metelitsa, N. Zhivykh, B. Steinberg, and O. Steinberg, “Precompiler for the ACELAN-COMPOS Package Solvers,” in Parallel Computing Technologies: 16th International Conference, PaCT 2021, Kaliningrad, Russia, September 13--18, 2021, Proceedings 16, 2021, pp. 103–116.A. Vasilenko, V. Veselovskiy, E. Metelitsa, N. Zhivykh, B. Steinberg, and O. Steinberg, “Precompiler for the ACELAN-COMPOS Package Solvers,” in Parallel Computing Technologies: 16th International Conference, PaCT 2021, Kaliningrad, Russia, September 13--18, 2021, Proceedings 16, 2021, pp. 103–116.Z. Gong et al., “An empirical study of the effect of source-level loop transformations on compiler stability,” Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, pp. 1–29, 2018.Z. Gong et al., “An empirical study of the effect of source-level loop transformations on compiler stability,” Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, pp. 1–29, 2018.N. Drucker and S. Gueron, “A toolbox for software optimization of QC-MDPC code-based cryptosystems,” Journal of Cryptographic Engineering, vol. 9, no. 4, pp. 341–357, 2019.N. Drucker and S. Gueron, “A toolbox for software optimization of QC-MDPC code-based cryptosystems,” Journal of Cryptographic Engineering, vol. 9, no. 4, pp. 341–357, 2019.

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