Быстрое вычисление циклических сверток и их приложения в кодовых схемах асимметричного шифрования
Андрей Николаевич Сушко,
Борис Яковлевич Штейнберг,
Кирилл Владимирович Веденев,
Антон Анатольевич Глухих,
Юрий Владимирович Косолапов https://doi.org/10.18255/1818-1015-2023-4-354-365
EDN: HEFJOO
Аннотация
Разработка быстрых алгоритмов генерации ключей, шифрования и дешифрования не только повышает эффективность соответствующих операций. Такие быстрые алгоритмы, например, для асимметричных криптосистем на квазициклических кодах, позволяют экспериментально исследовать зависимость вероятности ошибочного расшифрования от параметров кода для малых параметров безопасности и экстраполировать эти результаты на большие значения параметров безопасности. В этой статье мы исследуем эффективные алгоритмы циклической свертки, специально разработанные, в том числе, для использования в алгоритмах кодирования и декодирования квазициклических LDPC и MDPC кодов. Соответствующие свертки работают с двоичными векторами, которые могут быть как разреженными, так и плотными. Предлагаемые алгоритмы достигают высокой скорости за счет компактного хранения разреженных векторов, использования аппаратно поддерживаемых инструкций XOR и замены операций по модулю специализированными преобразованиями цикла. Эти быстрые алгоритмы имеют потенциальное применение не только в криптографии, но и в других областях, где используются свертки.
Об авторах
Андрей Николаевич Сушко
Южный федеральный университет
Россия
Россия
Борис Яковлевич Штейнберг
Южный федеральный университет
Россия
Россия
Кирилл Владимирович Веденев
Южный федеральный университет
Россия
Россия
Антон Анатольевич Глухих
Южный федеральный университет
Россия
Россия
Юрий Владимирович Косолапов
Южный федеральный университет
Россия
Россия
Список литературы
1. T. Holton, Digital signal processing: Principles and applications. Cambridge University Press, 2021.
2. 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.
3. 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.
4. 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.
5. N. R. Council and others, Getting up to speed: The future of supercomputing. National Academies Press, 2005.
6. N. Aragon et al., “BIKE: Bit Flipping Key Encapsulation.” Dec. 2017, [Online]. Available: https://hal.science/hal-01671903.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
Рецензия
Для цитирования:
Сушко А.Н., Штейнберг Б.Я., Веденев К.В., Глухих А.А., Косолапов Ю.В. Быстрое вычисление циклических сверток и их приложения в кодовых схемах асимметричного шифрования. Моделирование и анализ информационных систем. 2023;30(4):354-365. https://doi.org/10.18255/1818-1015-2023-4-354-365. EDN: HEFJOO
For citation:
Sushko A.N., Steinberg B.Y., Vedenev K.V., Glukhikh A.A., Kosolapov Yu.V. Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes. Modeling and Analysis of Information Systems. 2023;30(4):354-365. https://doi.org/10.18255/1818-1015-2023-4-354-365. EDN: HEFJOO
Просмотров:
262
Послать статью по эл. почте 