The Support Splitting Algorithm for Induced Codes
https://doi.org/10.18255/1818-1015-2018-3-276-290
Abstract
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 Flq ⊗ 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 Flq ⊗ 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 Flq ⊗ C. The algorithm for splitting the support for the code Flq ⊗ 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 Flq ⊗ C.
About the Authors
Yury V. Kosolapov
South Federal University
Russian Federation
PhD
Russian Federation
PhD
Aleksey N. Shigaev
South Federal University
Russian Federation
graduate student
Russian Federation
graduate student
References
1. McEliece R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, JPL Deep Space Network Progress Report, 1978, № 42–44, 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.
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.
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).
7. Deundyak V. M., Kosolapov Yu. V., “Cryptosystem based on induced group codes”, Model. Anal. Inform. Sist., 23:2 (2016), 137–152, (in Russian).
8. Sendrier N., “Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm”, IEEE Trans. on IT, 46:4 (2000), 1193–1203.
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.
10. Lenstra A. K., Verheul E. R., “Selecting Cryptographic Key Sizes”, Journal of Cryptology, 14:4 (2001), 255–293.
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.
13. Sendrier N., Simos D. E., “The Hardness of Code Equivalence over Fq and its Application to Code-based Cryptography”, Post-Quantum Cryptography. PQCrypto 2013, Lecture Notes in Computer Science, 7932, 2013, 203–216.
14.
Review
For citations:
Kosolapov Yu.V., Shigaev A.N. The Support Splitting Algorithm for Induced Codes. Modeling and Analysis of Information Systems. 2018;25(3):276-290. (In Russ.) https://doi.org/10.18255/1818-1015-2018-3-276-290
Views:
906
Email this article 