Geodesic
On the parameters of a McEliece-type cryptosystem on~$D$-codes based on binary Reed~--- Muller codes
Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 7-35.

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

The characteristics of a McEliece-type code cryptosystem on a special sum of tensor products of base codes, called $D$-code, are investigated. Binary Reed — Muller codes were chosen as the base codes. Previously, conditions were found for these $D$-codes, under which the corresponding cryptosystem is resistant to known structural attacks based on the Schur — Hadamard product. However, when using a decoder operating within half the code distance, a McEliece-type system on $D$-codes provides security comparable to the strength of the classical McEliece cryptosystem on Goppa codes, with a significantly larger key size. In this paper, two probabilistic decoders for $D$-codes are constructed. In the case of using these decoders, parameters of some $D$-codes have been found that provide comparable resistance to information set decoding type attacks, while having a smaller key size than in the classical system. However, the presence of a non-negligible decoding failure rate currently limits the scope of application of the $D$-code cryptosystem to ephemeral session key encapsulation mechanisms (IND-CPA KEM).
Mots-clés : $D$-codes
Keywords: McEliece scheme, key encapsulation mechanism. 
@article{PDM_2025_1_a1,
     author = {Yu. V. Kosolapov and E. A. Lelyuk},
     title = {On the parameters of a {McEliece-type} cryptosystem on~$D$-codes based on binary {Reed~---} {Muller} codes},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {7--35},
     publisher = {mathdoc},
     number = {1},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2025_1_a1/}
}
TY  - JOUR
AU  - Yu. V. Kosolapov
AU  - E. A. Lelyuk
TI  - On the parameters of a McEliece-type cryptosystem on~$D$-codes based on binary Reed~--- Muller codes
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2025
SP  - 7
EP  - 35
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2025_1_a1/
LA  - ru
ID  - PDM_2025_1_a1
ER  - 
%0 Journal Article
%A Yu. V. Kosolapov
%A E. A. Lelyuk
%T On the parameters of a McEliece-type cryptosystem on~$D$-codes based on binary Reed~--- Muller codes
%J Prikladnaâ diskretnaâ matematika
%D 2025
%P 7-35
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2025_1_a1/
%G ru
%F PDM_2025_1_a1
Yu. V. Kosolapov; E. A. Lelyuk. On the parameters of a McEliece-type cryptosystem on~$D$-codes based on binary Reed~--- Muller codes. Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 7-35. http://geodesic.mathdoc.fr/item/PDM_2025_1_a1/

[1] Weger V., Gassner N., and Rosenthal J., A Survey on Code-Based Cryptography, 2024, 168 pp., arXiv: 2201.07119

[2] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, Deep Space Network Progress Report, 1978, no. 44, 114–116

[3] Albrecht M. R., Bernstein D. J., Chou T., et al., Classic McEliece: Conservative Code-Based Cryptography, Round 4 Submission, NIST PQC Call for Proposals, 2022 https://classic.mceliece.org/nist/mceliece-20201010.pdf

[4] Alagic G., Apon D., Cooper D., et al., Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, NIST, 2022 https://csrc.nist.gov/pubs/ir/8413/upd1/final

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

[6] Albrecht M., Cid C., Paterson K. G., et al., “Nts-kem”, NIST PQC Round, 2 (2019), 4–13

[7] Couvreur A., Mora R., and Tillich J.-P., A New Approach Based on Quadratic Forms to Attack the McEliece Cryptosystem, Cryptology ePrint Archive, No 2023/950, 2023 | MR

[8] Bardet M., Mora R., and Tillich J.-P., Polynomial Time Key-Recovery Attack on High Rate Random Alternant Codes, 2023, arXiv: 2304.14757 | MR

[9] Mora R. and Tillich J.-P., “On the dimension and structure of the square of the dual of a Goppa code”, Des. Codes Cryptogr., 2023, no. 91, 1351–1372 | DOI | MR

[10] Ivanov F., Kabatiansky G., Krouk E., and Rumenko N., “A new code-based cryptosystem”, LNCS, 12087, 2020, 41–49

[11] Lau T. Sh. C., Ivanov F., Ariffin M. R. K., et al., “New code-based cryptosystems via the IKKR framework”, J. Inform. Security Appl., 76 (2023), 103530

[12] Krouk E., Kabatiansky G., and Tavernier C., “McEliece-type cryptosystem based on correction of errors and erasures”, 2023 XVIII Intern. Symp. REDUNDANCY (Moscow, Russia), 2023, 173–177

[13] Kosolapov Yu. V. and Lelyuk E. A., “On the structural security of a McEliece-type cryptosystem based on the sum of tensor products of binary Reed — Muller codes”, Prikladnaya Diskretnaya Matematika, 2022, no. 57, 22–39 (in Russian)

[14] Kosolapov Yu. V. and Lelyuk E. A., “The McEliece-type cryptosystem based on D-codes”, Matematicheskie Voprosy Kriptografii, 15:2 (2024), 69–90 (in Russian) | DOI | MR

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

[16] Abbe E., Sberlo O., Shpilka A., and Ye M., “Reed — Muller codes”, Foundations and Trends in Commun. Inform. Theory, 20:1–2 (2023), 1–156 | DOI | MR

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

[18] Hofheinz D., Hövelmanns K., and Kiltz E., “A modular analysis of the Fujisaki — Okamoto transformation”, LNCS, 10677, 2017, 341–371 | MR

[19] Arago N., Barreto P., Bettaieb S., et al., BIKE: Bit Flipping Key Encapsulation, , 2017 https://hal.science/hal-01671903/document

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

[21] Vedenev K. V. and Kosolapov Y. V., “A reaction attack against cryptosystems based on quasi-group MDPC codes”, 2023 XVIII Intern. Symp. REDUNDANCY, Russia, M., 2023, 70–75

[22] Joux A., Loss J., and Wagner B., Kleptographic Attacks against Implicit Rejection, , 2024 https://eprint.iacr.org/2024/260

[23] Campagna M. and Crockett E., Hybrid Post-Quantum Key Encapsulation Methods (PQ KEM) for Transport Layer Security 1.2 (TLS), , 2021 https://www.ietf.org/archive/id/draft-campagna-tls-bike-sike-hybrid-07.html

[24] Drucker N., Gueron S., and Kostic D., A Lean BIKE KEM Design for Ephemeral Key Agreement, , 2024 https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/a-lean-bike-kem.pdf

[25] Baldi M., Barenghi A., Chiaraluce F., et al., LEDAcrypt: Low-dEnsity parity-check coDe-bAsed cryptographic systems, , 2019 https://www.ledacrypt.org/documents/LEDAcrypt_v3.pdf

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

[27] Both L. and May A., “Decoding linear codes with high error rate and its impact for LPN security”, LNCS, 10786, 2018, 25–46 | MR

[28] May A. and Ozerov I., “On computing nearest neighbors with applications to decoding of binary linear codes”, LNCS, 9056, 2015, 203–228 | MR

[29] Kudekar S., Kumar S., Mondelli M., et al., “Reed — Muller codes achieve capacity on erasure channels”, Proc. STOC'16, ACM, N.Y., 2016, 658–669 | MR

[30] Abbe E. and Sandon C., “A proof that Reed — Muller codes achieve Shannon capacity on symmetric channels”, IEEE 64th Ann. Symp. FOCS (Santa Cruz, CA, USA), 2023, 177–193 | MR

[31] Reed I. S., “A class of multiple-error-correcting codes and the decoding scheme”, IEEE Trans. Inform. Theory, 4:4 (1954), 38–492 | MR

[32] Massey J. L., Threshold Decoding, MIT Press, Cambridge, MA, 1963 | MR

[33] Tsimmerman K.-Kh., Methods of the Modular Representations Theory in Algebraic Coding Theory, MCCME, M., 2011 (in Russian)

[34] Sidel'nikov V. M. and Pershakov A. S., “Decoding of Reed — Muller codes with a large number of errors”, Problems Inform. Transmission, 28:3 (1992), 269–281 | MR

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

[36] Sidel'nikov V. M., “Open coding based on Reed — Muller binary codes”, Discrete Math. Appl., 4:3 (1994), 191–207 | DOI | MR

[37] Kabatiansky G. and Tavernier C., “A new code-based cryptosystem via pseudorepetition of codes”, 16th Intern. Workshop Algebraic Combinat. Coding Theory (Svetlogorsk, Russia), 2018, 189–191

[38] Egorova E., Kabatiansky G., Krouk E., and Tavernier C., “A new code-based public-key cryptosystem resistant to quantum computer attacks”, J. Phys. Conf. Ser., 1163 (2019), 1–5 | DOI

[39] Minder L. and Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, LNCS, 4515, 2007, 347–360 | MR

[40] Borodin M. A. and Chizhov I. V., “Effective attack on the McEliece cryptosystem based on Reed — Muller codes”, Discrete Math. Appl., 24:5 (2014), 273–280 | DOI | DOI | MR

[41] Vysotskaya V. V, “Reed-Muller code square and equivalence classes of secret keys of the McEliece-Sidelnikov cryptosystem”, Prikladnaja diskretnaja matematika. Prilozhenie, 2017, no. 10, 66–68 (in Russian)

[42] Vysotskaya V. V., “On the structural features of the key space of the McEliece — Sidelnikov cryptosystem based on generalized Reed — Solomon codes”, Diskretnaya Matematika, 36:4 (2024), 28–43 (in Russian) | DOI

[43] Davletshina A. M., “Search for equivalent keys of the McEliece — Sidelnikov cryptosystem built on the Reed — Muller binary codes”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2019, no. 12, 98–100 (in Russian)

[44] Chizhov I. V. and Borodin M. A., “Classification of Hadamard products of one-codimensional subcodes of Reed — Muller codes”, Discrete Math. Appl., 32:5 (2022), 297–311 | DOI