Geodesic
Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes
Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 4, pp. 354-365.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: fast algorithms, encryption schemes.
Mots-clés : cyclic convolutions 
@article{MAIS_2023_30_4_a3,
     author = {A. N. Sushko and B. Y. Steinberg and K. V. Vedenev and A. A. Glukhikh and Y. V. Kosolapov},
     title = {Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {354--365},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a3/}
}
TY  - JOUR
AU  - A. N. Sushko
AU  - B. Y. Steinberg
AU  - K. V. Vedenev
AU  - A. A. Glukhikh
AU  - Y. V. Kosolapov
TI  - Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2023
SP  - 354
EP  - 365
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a3/
LA  - en
ID  - MAIS_2023_30_4_a3
ER  - 
%0 Journal Article
%A A. N. Sushko
%A B. Y. Steinberg
%A K. V. Vedenev
%A A. A. Glukhikh
%A Y. V. Kosolapov
%T Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes
%J Modelirovanie i analiz informacionnyh sistem
%D 2023
%P 354-365
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a3/
%G en
%F MAIS_2023_30_4_a3
A. N. Sushko; B. Y. Steinberg; K. V. Vedenev; A. A. Glukhikh; Y. V. Kosolapov. Fast computation of cyclic convolutions and their applications in code-based asymmetric encryption schemes. Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 4, pp. 354-365. http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a3/

[1] T. Holton, Digital signal processing: Principles and applications, Cambridge University Press, 2021, 1058 pp. | Zbl

[2] D. S. Taubman, M. W. Marcellin, M. Rabbani, “JPEG2000: Image compression fundamentals, standards and practice”, Journal of Electronic Imaging, 11:2 (2002), 286–287 | DOI

[3] V. Holub, J. Fridrich, T. Denemark, “Universal distortion function for steganography in an arbitrary domain”, EURASIP Journal on Information Security, 2014:1 (2014), 1 | DOI

[4] IntelR oneAPI Deep Neural Network Library, Intel, , 2023 https://software.intel.com/content/www/us/en/develop/articles/intel-mkl-dnn-part-1-library-overview-and-installation.html

[5] N. R. Council et al, Getting up to speed: The future of supercomputing, National Academies Press, 2005, 306 pp.

[6] N. Aragon et al, BIKE: Bit Flipping Key Encapsulation, Submission to the NIST post quantum standardization process, , Dec 2017 https://hal.science/hal-01671903

[7] T. B. Paiva, R. Terada, “Faster constant-time decoder for MDPC codes and applications to BIKE KEM”, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022:4 (2022), 110–134 | DOI

[8] P. Santini, M. Battaglioni, M. Baldi, 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, 68:8 (2020), 4648–4660 | DOI

[9] K. Vedenev, Y. Kosolapov, “Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes”, Code-Based Cryptography, Springer, 2023, 35–55 | DOI

[10] Q. Guo, T. Johansson, P. S. Wagner, “A key recovery reaction attack on QC-MDPC”, IEEE Transactions on Information Theory, 65:3 (2018), 1845–1861 | DOI | MR

[11] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, P. Santini, “Performance bounds for QC-MDPC codes decoders”, Code-Based Cryptography Workshop, Springer, 2021, 95–122

[12] S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, A. Robinson, “A study of error floor behavior in QC-MDPC codes”, International Conference on Post-Quantum Cryptography, Springer, 2022, 89–103 | DOI | MR | Zbl

[13] S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, A. Robinson, Raw data and decoder for the paper" a study of error floor behavior in QC-MDPC codes, 2022 https://github.com/HastD/BIKE-error-floor

[14] A. Vasilenko, V. Veselovskiy, E. Metelitsa, N. Zhivykh, B. Steinberg, O. Steinberg, “Precompiler for the acelan-compos package solvers”, Parallel Computing Technologies: 16th International Conference, PaCT 2021 (Kaliningrad, Russia, September 13-18, 2021), Springer, 2021, 103–116 | DOI

[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, v. 2, 2018, 1–29 | DOI | Zbl

[16] N. Drucker, S. Gueron, “A toolbox for software optimization of QC-MDPC code-based cryptosystems”, Journal of Cryptographic Engineering, 9:4 (2019), 341–357 | DOI