The McEliece-type cryptosystem based on $D$-codes

Yu. V. Kosolapov ; E. A. Lelyuk

Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 2, pp. 69-90

Résumé

The $\mathsf{Classic McEliece}$ code–based cryptosystem is one of the contenders for the asymmetric encryption standard selected as part of the NIST PQC competition. This cryptosystem is based on Goppa codes, which constitute a subclass of alternate codes. The main disadvantage of this cryptosystem is very large key size. Attempts to use Reed–Solomon codes, Reed–Muller codes, algebraic-geometric codes, low–density parity–check codes for reducing the key size have not been successful, since structural attacks on the corresponding cryptosystems were found. Therefore the problem of finding other efficiently decodable codes that provide high security of code–based cryptosystems is a relevant problem. One way to obtain new codes is to use code constructions based on known codes (base codes). We note that the use of such code constructions as the combination of codes, the direct sum of codes, the transition from field extensions to basic fields did not allow to increase the security. Nevertheless, code constructions are promising, since they make it possible to construct new efficiently decodable codes based on known codes. In general, new codes belong to a class that differs from the class of base codes, i.e. have a different structure (algebraic and/or combinatorial), so structural attacks on cryptosystems based on base codes are not directly applicable to cryptosystems based on new codes. An important example of a code construction is the tensor product codes, as it is widely used in telecommunication for error correction. In this paper, we study a McEliece-type cryptosystem based on $D$–codes, which are one of the generalizations of the tensor product codes. Namely, we consider $D$–codes based on families of Reed–Muller codes. Based on new and earlier results obtained by the authors regarding the properties of $D$-codes, the requirements for $D$-codes (including the tensor product codes) are determined, under which the security of the cryptosystem is guaranteed to structural attacks based on the Schur-Hadamard product as well as to the information set decoding attack. Parameters of $D$-codes based on binary Reed–Muller codes, which correspond to the strong keys of the cryptosystem, are given. We also compare the characteristics of the $\mathsf{Classic McEliece}$ cryptosystem with the corresponding characteristics of the proposed system on $D$–codes, both in the case of using a decoder operating within half the code distance, and in the case of a decoder operating outside these limits. This comparison shows that it is possible using a decoder operating beyond half the code distance to construct a system based on $D$-codes that has either greater security with a comparable key size, or a smaller key size with comparable security.

Bibliographie

[1] Bernstein D. J., Chou T., Lange T., von Maurich I., Misoczki R., Niederhagen R., Persichetti E., Peters Ch., Schwabe P., Sendrier N., Szefer J., Wang W., Classic McEliece: conservative code-based cryptography, NIST submissions, 2017

[2] Post-Quantum Cryptography, National Institute of Standards and Technology (NIST) http://csrc.nist.gov/projects/post-quantum-cryptography

[3] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Prob. Contr. Inform. Theory, 15:2 (1986), 157–166 | MR

[4] Sidelnikov V. M., “Otkrytoe shifrovanie na osnove dvoichnykh kodov Rida–Mallera”, Diskretnaya matematika, 6:2 (1994), 3–20 | Zbl

[5] Janwa H., Moreno O., “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography, 8:3 (1996), 293–307 | DOI | MR | Zbl

[6] Baldi M., Bianchi M., Chiaraluce F., “Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes”, IET Inf. Security, 7:3 (2013), 212–220 | DOI

[7] Sidelnikov V. M., Shestakov S. O., “O sisteme shifrovaniya, postroennoi na osnove obobschennykh kodov Rida–Solomona”, Diskretnaya matematika, 4:3 (1992), 57–63 | Zbl

[8] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, EUROCRYPT 2007, Lect. Notes Comput. Sci., 4515, 2007, 347–360 | DOI | MR | Zbl

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

[10] Couvreur A., Márquez-Corbella I., Pellikaan R., “Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes”, IEEE Trans. Inf. Theory, 63:8 (2017), 5404–5418 | DOI | MR | Zbl

[11] Fabšič T., Hromada V., Stankovski P., Zajac P., Guo Q., Johansson T., “A reaction attack on the QC-LDPC McEliece cryptosystem”, PQCrypto 2017, Lect. Notes Comput. Sci., 10346, 2017, 51–68 | DOI | MR | Zbl

[12] Couvreur A., Otmani A., Tillich J. P., “Polynomial time attack on wild McEliece over quadratic extensions”, IEEE Trans. Inf. Theory, 63:1 (2016), 404–427 | DOI | MR

[13] Elbro F., Majenz C., An algebraic attack against McEliece-like cryptosystems based on BCH codes, Cryptology ePrint Archive 2022/1715 https://eprint.iacr.org/2022/1715

[14] Couvreur A., Lequesne M., “On the security of subspace subcodes of Reed–Solomon codes for public key encryption”, IEEE Trans. Inf. Theory, 68:1 (2021), 632–648 | DOI | MR

[15] Egorova E., Kabatiansky G., Krouk E., Tavernier C., “A new code-based public-key cryptosystem resistant to quantum computer attacks”, J. Physics: Conf. Series, 1163:1, 012061, IOP Publishing | MR

[16] Zyablov V. V., Ivanov F. I., Kruk E. A., Sidorenko V. R., “O novykh zadachakh v asimmetrichnoi kriptografii, osnovannoi na pomekhoustoichivom kodirovanii”, Problemy peredachi informatsii, 58:2 (2022), 92–111 | Zbl

[17] Deundyak V. M., Kosolapov Y. V., Maystrenko I. A., “On the decipherment of Sidel'nikov-type cryptosystems”, CBCrypto 2020, Lect. Notes Comput. Sci., 12087, 2020, 20–40 | DOI | Zbl

[18] Vedenev K., Kosolapov Y., “Cryptanalysis of Ivanov–Krouk–Zyablov cryptosystem”, CBCrypto 2022, Lect. Notes Comput. Sci., 13839, 2023, 137–153 | DOI | Zbl

[19] Xu J., Chaichanavong P., Burd G., Wu Z., U.S. Patent No. 7,861,131, U.S. Patent and Trademark Office, Washington, DC, 2010

[20] Twitto M., Ari M. B., Dor A., Erez E., Kong J. J., Shany Y., U.S. Patent No. 10,333,554, U.S. Patent and Trademark Office, Washington, DC, 2019

[21] Yeo E., Yadav M. K., Chaichanavong P., Burd G., U.S. Patent No. 8,321,769, U.S. Patent and Trademark Office, Washington, DC, 2012

[22] Kosolapov Yu. V., Lelyuk E. A., “O strukturnoi stoikosti kriptosistemy tipa Mak-Elisa na summe tenzornykh proizvedenii binarnykh kodov Rida–Mallera”, Prikl. diskr. matem., 57 (2022), 22–39 | Zbl

[23] Kasami T., Lin S., “On the construction of a class of majority-logic decodable codes”, IEEE Trans. Inf. Theory, IT-17:5 (1971), 600–610 | DOI | MR | Zbl

[24] Deundyak V. M., Lelyuk E. A., “A graph-theoretical method for decoding some group MLD-codes”, J. Appl. Industr. Math., 14:2 (2020), 265–280 | DOI | MR | Zbl

[25] Morelos-Zaragoza R. H., The Art of Error Correcting Coding, John Wiley Sons, Ltd., 2006, 263 pp.

[26] Randriambololona H., “On products and powers of linear codes under componentwise multiplication”, Algorithmic Arithmetic Geometry Coding Theory, Contemporary Mathematics, 637, 2015, 3–78 | DOI | MR | Zbl

[27] Deundyak V. M., Kosolapov Yu. V., “O nekotorykh svoistvakh proizvedeniya Shura-Adamara dlya lineinykh kodov i ikh prilozheniyakh”, Prikl. diskr. matem., 50 (2020), 72–86 | MR | Zbl

[28] Slepian D., “Some further theory of group codes”, Bell Syst. Tech. J., 39:5 (1960), 1219–1252 | DOI | MR

[29] Abbe E., Shpilka A., Ye M., “Reed-Muller codes: Theory and algorithms”, IEEE Trans. Inf. Theory, 67:6 (2020), 3251–3277 | DOI | MR

[30] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 1978, 42–44

[31] Dottling N., Dowsley R., Muller-Quade J., Nascimento A.C.A., “A CCA secure variant of the McEliece cryptosystem”, IEEE Trans. Inf. Theory, 58 (2012), 6672–6680 | DOI | MR | Zbl

[32] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, M., 2004 | MR

[33] Brent R., Gao S., Lauder A., “Random Krylov spaces over finite fields”, SIAM J. Discr. Math., 16:2 (2002), 276–287 | DOI | MR

[34] Deundyak V. M., Kosolapov Yu. V., Lelyuk E. A., “Decoding the tensor product of MLD codes and applications for code cryptosystems”, Autom. Contr. and Computer Sci., 52:7 (2018), 647–657 | DOI | MR

[35] Deundyak V.M., Kosolapov Yu.V., “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

[36] Prange E., “The use of information sets in decoding cyclic codes”, IRE Trans. Inf. Theory, 8:5 (1962), 5–9 | DOI | MR

[37] Borodin M. A., Chizhov I. V., “Klassifikatsiya proizvedenii Adamara podkodov korazmernosti 1 kodov Rida–Mallera”, Diskretnaya matematika, 32:1 (2020), 115–134 | DOI | MR

[38] Bernstein D. J., et al., Classic McEliece: conservative code-based cryptography: cryptosystem specification, NIST submissions, 2022

[39] Sidelnikov V. M., Pershakov A. S., “Dekodirovanie kodov Rida–Mallera pri bolshom chisle oshibok”, Probl. peredachi inform., 28:3 (1992), 80–94 | MR | Zbl

[40] Geiselhart M., Elkelesh A., Ebada M., Cammerer S., Ten Brink S., “Iterative Reed–Muller decoding”, 2021 11th Int. Symp. Topics in Coding (ISTC), IEEE, 2021, 1–5

[41] Kamenev M., Kameneva Y., Kurmaev O., Maevskiy A., “A new permutation decoding method for Reed–Muller codes”, 2019 IEEE Int. Symp. Inf. Theory (ISIT), IEEE, 2019, 26–30 | DOI

[42] Ye M., Abbe E., “Recursive projection-aggregation decoding of Reed–Muller codes”, IEEE Trans. Inf. Theory, 66:8 (2020), 4948–4965 | DOI | MR | Zbl

[43] Guo Q., Johansson T., Wagner P.S., “A key recovery reaction attack on QC-MDPC”, IEEE Trans. Inf. Theory, 65:3 (2019), 1845–1861 | DOI | MR | Zbl

[44] Vedenev K., Kosolapov Yu., Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes, Cryptology ePrint Archive, Paper 2023/1224, 2023, 20 pp. | Zbl

[45] Baldi M., Barenghi A., Chiaraluce F., Pelosi G., Santini P., LEDAcrypt: Low-density parity-check code-based cryptographic systems. NIST round, 2, 2019 https://www.ledacrypt.org/documents/LEDAcrypt_v3.pdf