On the Berger--Loidreau cryptosystem on the tensor product of codes

V. M. Deundyak ; Yu. V. Kosolapov

Journal of computational and engineering mathematics, Tome 5 (2018) no. 2, pp. 16-33.

Résumé

In the post-quantum era, asymmetric cryptosystems based on linear codes (code cryptosystems) are considered as an alternative to modern asymmetric cryptosystems. However, the research of the strength of code McEliece-type cryptosystems shows that algebraically structured codes do not provide sufficient strength of these cryptosystems. On the other hand, the use of random codes in such cryptosystems is impossible because of the high complexity of its decoding. Strengthening of code cryptosystems is currently conducted, usually, either by using codes for which no attacks are known, or by modifying the cryptographic protocol. In this paper both of these approaches are used. On the one hand, it is proposed to use the tensor product $C^1\otimes C^2$ of the known codes $C^1$ and $C^2$, since for $C^1\otimes C^2$ in some cases it is possible to construct an effective decoding algorithm. On the other hand, instead of a McEliece-type cryptosystem, it is proposed to use its modification, a Berger–Loidreau cryptosystem. The paper proves a high strength of the constructed code cryptosystem to attacks on the key even in the case when code cryptosystems on codes $C^1$ and $C^2$ are cracked.

Détail

Keywords: the Berger–Loidreau cryptosystem, the tensor product of codes, the attack on the key.

Bibliographie

[1] A. K. Lenstra, E. R. Verheul, “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14 (2001), 255–293 | DOI | MR | Zbl

[2] D. J. Bernstein, J. Buchmann, E. Dahmen, Post-Quantum Cryptography, Springer, Berlin, 2009 | MR

[3] N. Sendrier, J. P. Tillich, Code-Based Cryptography: New Security Solutions Against a Quantum Adversary, } (accessed on June 4, 2018) {\tt https://hal.archives-ouvertes.fr/hal-01410068/document

[4] R. J. McEliece, “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, JPL Deep Space Network Progress Report, 1978, no. 42, 114–116

[5] D. J. Bernstein, “Grover vs. McEliece”, Lecture Notes in Computer Science, 6061, 2010, 73–80 | DOI | MR | Zbl

[6] T. Eisenbarth, T. Guneysu, S. Heyse, C. Paar, “MicroEliece: McEliece for Embedded Devices”, Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems, Springer, Berlin, 2009, 49–64 | Zbl

[7] V. M. Sidelnikov, Teoriya kodirovaniya, FIZMATLIT, M., 2008

[8] V. M. Sidel'nikov, S. O. Shestakov, “On an Encoding System Constructed on the Basis of Generalized Reed – Solomon Codes”, Discrete Mathematics and Applications, 2:4 (1992), 439–444 | DOI | MR | Zbl

[9] V. M. Deundyak, M. A. Druzhinina, Yu. V. Kosolapov, “Modifikatsiya kriptoanaliticheskogo algoritma Sidelnikova-Shestakova dlya obobschennykh kodov Rida – Solomona i ee programmnaya realizatsiya”, Izvestiya vysshikh uchebnykh zavedenii. Severo-Kavkazskii region. Tekhnicheskie nauki, 2006, no. 4, 15–19

[10] C. Wieschebrink, “Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes”, Third International Workshop, PQCrypto, Springer, Berlin, 2010, 61–72 | MR | Zbl

[11] L. Minder, A. Shokrollahi, “Cryptanalysis of the Sidelnikov Cryptosystem”, Lecture Notes in Computer Science, 4515, 2007, 347–360 | DOI | MR | Zbl

[12] M. A. Borodin, I. V. Chizhov, “Effektivnaya ataka na kriptosistemu Mak-Elisa, postroennuyu na osnove kodov Rida – Mallera”, Diskretnaya matematika, 26:1 (2014), 10–20 | DOI

[13] T. Berger, P. Loidreau, “How to Mask the Structure of Codes for a Cryptographic Use”, Designs, Codes and Cryptography, 35:1 (2005), 63–79 | DOI | MR | Zbl

[14] M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, D. Schipani, “Enhanced Public Key Security for the McEliece Cryptosystem”, Journal of Cryptology, 29:1 (2016), 1–27 | DOI | MR | Zbl

[15] I. V. Chizhov, M. A. Borodin, “Kriptoanaliz kriptosistemy Mak-Elisa, postroennoi na ($k-1$)-podkodakh koda Rida – Mallera”, PDM. Prilozhenie, 2016, no. 9, 73–75 | DOI

[16] V. M. Deundyak, Yu. V. Kosolapov, “Kriptosistema na indutsirovannykh gruppovykh kodakh”, Model. i analiz inform. sistem, 23:2 (2016), 137–152 | DOI | MR

[17] V. M. Deundyak, Yu. V. Kosolapov, E. A. Lelyuk, “Dekodirovanie tenzornogo proizvedeniya $\mathrm{MLD}$-kodov i prilozheniya k kodovym kriptosistemam”, Model. i analiz inform. sistem, 24:2 (2017), 239–252 | DOI | MR

[18] V. M. Deundyak, Yu. V. Kosolapov, “Algoritmy dlya mazhoritarnogo dekodirovaniya gruppovykh kodov”, Model. i analiz inform. sistem, 22:4 (2015), 464–482 | DOI | MR

[19] H. V. Henderson, S. R. Searle, “The Vec-Permutation Matrix, the Vec Operator and Kronecker Products: A Review”, Linear and Multilinear Algebra, 1981, no. 9, 271–288 | DOI | MR | Zbl

[20] R. H. Morelos-Zaragoza, The Art of Error Correcting Coding, John Wiley Sons, Chichester, 2006

[21] V. M. Deundyak, Yu. V. Kosolapov, “Ispolzovanie tenzornogo proizvedeniya kodov Rida – Mallera v asimmetrichnoi kriptosisteme tipa Mak-Elisa i analiz ee stoikosti k atakam na shifrogrammu”, Vychislitelnye tekhnologii, 22:4 (2017), 43–60 | MR

[22] R. Nojima, H. Imai, K. Kobara, K. Morozov, “Semantic Security for the McEliece Cryptosystem without Random Oracles”, Designs, Codes and Cryptography, 49:1-3 (2008), 289–305 | DOI | MR | Zbl