The support splitting algorithm for induced codes

Yu. V. Kosolapov ; A. N. Shigaev

Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 3, pp. 276-290.

Résumé

In the paper, the analysis of the stability of the McEliece-type cryptosystem on induced codes for key attacks is examined. In particular, a model is considered when the automorphism group is trivial for the base code $C$, on the basis of which the induced code $ \mathbb{F}^l_q \otimes C $ is constructed. In this case, as shown by N. Sendrier in 2000, there exists such a mapping, called a complete discriminant, by means of which a secret permutation that is part of the secret key of a McEliece-type cryptosystem can be effectively found. The automorphism group of the code $ \mathbb{F}^l_q \otimes C $ is nontrivial, therefore there is no complete discriminant for this code. This suggests a potentially high resistance of the McEliece-type cryptosystem on the code $ \mathbb{F}^l_q \otimes C $. The algorithm for splitting the support for the code $ \mathbb{F}^l_q \otimes C $ is constructed and the efficiency of this algorithm is compared with the existing attack on the key of the McElice type cryptosystem based on the code $ \mathbb{F}^l_q \otimes C $.

Détail

Mots-clés : group codes
Keywords: induced group codes, support splitting algorithm, the McEliece cryptosystem.

Bibliographie

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

[2] Sendrier N., Tillich J. P., Code-Based Cryptography: New Security Solutions Against a Quantum Adversary, ERCIM News, , ERCIM, 2016 https://hal.archives-ouvertes.fr/hal-01410068/document

[3] Morelos-Zaragoza R. H., The Art of Error Correcting Coding, 2nd Edition, John Wiley Sons, Inc., 2006

[4] Sidel'nikov V. M., Shestakov S. O, “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

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

[6] Deundyak V. M., Kosolapov Yu. V., “Algorithms for majority decoding of group codes”, Model. Anal. Inform. Sist., 22:4 (2015), 464–482 (in Russian) | MR

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

[8] Sendrier N., “Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm”, IEEE Trans. on IT, 46:4 (2000), 1193–1203 | DOI | MR | Zbl

[9] Haily A., Harzalla D., “On Binary Linear Codes Whose Automorphism Group is Trivial”, Journal of Discrete Mathematical Sciences and Cryptography, 18:5 (2015), 495–512 | DOI | MR

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

[11] Deundyak V. M., Kosolapov Yu. V., “The use of the tensor product of Reed-Muller codes in asymmetric McEliece type cryptosystem and analysis of its resistance to attacks on the cryptogram”, Computational Technologies, 22:4 (2017), 43–60 (in Russian)

[12] Girault M., “A (non-practical) three-pass identification protocol using coding theory”, Advances in Cryptology, AUSCRYPT '90, Lecture Notes in Computer Science, 453, 1990, 265–272 | DOI

[13] Sendrier N., Simos D. E., “The Hardness of Code Equivalence over $\mathbb{F}_q$ and its Application to Code-based Cryptography”, Post-Quantum Cryptography, PQCrypto 2013, Lecture Notes in Computer Science, 7932, 2013, 203–216 | DOI | MR | Zbl