|
Article information
2017 , Volume 22, ¹ 4, p.43-60
Deundyak V.M., Kosolapov Y.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
Purpose. Increasing resistance of McEliece cryptosystem against structural attacks (attacks on the key). Methodology. To solve this problem it is encouraged to apply tensor product codes for which there are majority decoders. In this case, for the tensor product code there is a fast decoder, but there are no effective structural attacks for the McEliece cryptosystem based on the tensor product codes currently. Findings. The study has revealed that the tensor product codes on the one hand, increases the resistance of cryptographic code to the known attacks on key, but on the other hand reduces the cryptosystem to the attacks on the cryptogram. In this regard, the paper proposes a method for enhancing the stability of cryptosystems such as McEliece to the attacks on the cryptogram by the use of a randomized encryption. Originality/value. We have studied a method for constructing asymmetric cryptosystems code based on the tensor product codes. As shown by the calculations for tensor product of binary Reed -Muller codes, their resistance to attacks on cryptosystems is lower compared to the resistance of cryptosystems based on the ordinary Reed-Muller codes with comparable lengths. Despite this, cryptosystems based on the tensor product are presently more robust overall because they do not yet experience effective key attacks, while such attacks for cryptosystems based on Reed -Muller codes are already known. The disadvantages of cryptosystems based on tensor product codes include a large key size.
[full text]
Keywords: tensor product codes, Reed - Muller codes, the McEliece cryptosystem, ciphertext attacks
Author(s):
Deundyak Vladimir Mikhaylovich
Office: NII Spetsializirovannye Vychislitelnye Ustroystva Zashchity i Avtomatika
Address: 344006, Russia, Rostov
Kosolapov Yury Vladimirovich
PhD.
Position: Associate Professor
Office: South Federal University
Address: 344006, Russia, Rostov, Bol'shaya Sadovaya st., 105/42
E-mail: itaim@mail.ru
SPIN-code: 8308-5636 References:
[1] Rivest, R., Shamir, A., Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978; 21(2):120–126.
[2] Rabin, M. Digitalized signatures and public key functions as intractable as factorization. Cambridge: Massachusetts Institute of technology laboratory for Computer Science; 1979: 20. Available at: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf.
[3] ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete Logarithms. IEEE Trans. on Information Theory. 1985; 31(4):469–472.
[4] McEliece, R.J. A public-key cryptosystem based on algebraic coding theory. JPL Deep Space Network Progress Report. 1978; (42):114–116.
[5] eBACS: ECRYPT benchmarking of cryptographic systems. Available at: http://bench.cr.yp.to, 28 March 2017.
[6] Eisenbarth, T., Güneysu, T., Heyse, S., Paar, Ch. MicroEliece: McEliece for Embedded Devices. Lecture Notes in
Computer Science. 2009; (5747):49–64.
[7] Sendrier, N., Tillich, J.-P. Code-based cryptography: new security solutions against a quantum adversary. 2016: 3. Available at: https://hal.archives-ouvertes.fr/hal-01410068/document, (access 28 March 2017).
[8] Shor, P.W. Algorithms for quantum computation: Discrete logarithms and factoring. Proc. 35nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press; 1994: 124–134.
[9] Niebuhr, R. et. al. Selecting parameters for secure McEliece-based cryptosystems // Intern. J. of Inform. Security. 2012. Vol. 11, No. 3. P. 137–147.
[10] Niederreiter, H. Knapsack-type cryptosystem and algebraic coding theory. Problems of Control and Information Theory. 1986; (15):159–166.
[11] Gabidulin, E.M., Paramonov A.V., Tretjakov O.V. Ideals over a non-commutative ring and their application in
cryptology. Advances in Cryptology–EUROCRYPT’91. Ed. by D.W. Davies. Lecture Notes in Computer Science. 1991; (547):482–489.
[12] Sidel’nikov, V.M. Open coding based on Reed–Muller binary codes. Discrete Mathematics and Applications. 1994; 4(3):191–207.
[13] Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P. S. L. MDPC -McEliece: New McEliece variants from moderate density parity-check codes. IEEE Internat. Symposium on Information Theory—ISIT ’13, Istanbul, Turkey, 2013. IEEE; 2013: 2069–2073.
[14] Deundyak, V.M., Kosolapov, Yu.V. Cryptosystem based on induced group codes. Modeling and Analysis of Information Systems. 2016; 23(2):137–152. (In Russ.)
[15] Sidel’nikov, V.M., Shestakov, S.O. On an encoding system constructed on the basis of generalized Reed-Solomon codes. Discrete Mathematics and Applications. 1992; 2(4):439–444.
[16] Wieschebrink, C. Cryptanalysis of the niederreiter public key scheme based on GRS subcodes. Third International Workshop, PQCrypto 2010. Darmstadt, Germany, May 25–28. 2010: 61–72.
[17] Deundyak V.M., Drouzhinina M.A., V KosolapovY. Sidelnikov-Shestakov Kriptoanalytical Algorithm Modification for Generalized Rid-Solomon Codes and its Softwear Implementation. UNIVERSITY NEWS. NORTH-CAUCASIAN REGION. TECHNICAL SCIENCES. 2006; (4):15–20. (In Russ.)
[18] Couvreur, A., Gaborit, Ph., Gauthier-Umaña, V., Otmani, A., Tillich, J.-P. Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. Des. Codes Cryptography. 2014; 73(2):641–666.
[19] Gibson, J.K. The security of the gabidulin public key cryptosystem. Advances in Cryptology EUROCRYPT. 1996; (1070):212–223.
[20] Overbeck, R. Structural attacks for public key cryptosystems based on gabidulin codes. Journal of Cryptology. 2008; 21(2):280–301.
[21] Minder, L., Shokrollahi, A. Cryptanalysis of the Sidelnikov cryptosystem. Lecture Notes in Computer Science. 2007; (4515):347–360.
[22] Chizhov, I.V., Borodin, M.A. Vulnerability of McEliece cryptosystem based on binary Reed — Muller codes. Applied Discrete Mathematics. 2013; (6):48–49. (In Russ.)
[23] Borodin, M.A., Chizhov, I.V., Effective attack on the McEliece cryptosystem based on Reed–Muller codes. Discrete Mathematics and Applications. 2014; 24(5):273–280.
[24] Hamdaoui, Y., Sendrier, N. A non asymptotic analysis of information set decoding. IACR Cryptology ePrint Archive. 2013: 162.
[25] Torres, R.C., Sendrier, N. Analysis of information set decoding for a sub-linear error weight. Ed. Tsuyoshi,T. Post-Quantum Cryptography. Proceedings 7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016. Springer International Publishing; 2016: 144–161.
[26] Berson, T. A. Failure of the McEliece public-key cryptosystem under message-resend and related-message attack. Proceedings 17th Annual International Cryptology Conference, Santa Barbara, California, USA. August 17-21, 1997, CRYPTO '97. 1997; (1294):213–220.
[27] Gore, W.C. Futher Results on Product Codes. IEEE Transactions on Information Theory. 1970; IT-16(4):446–451.
[28] Kasami, T., Lin, S. On majority-logic decoding for duals of primitive polynomial codes. IEEE Transactions on Information Theory. 1971; IT-17(3):322–331.
[29] Fedorenko S.V. Metody bystrogo dekodirovaniya lineynykh kodov [Methods of fast decoding for linear codes]. SPb: GUAP; 2008: 199. (In Russ.)
[30] Zubkov, A.M., Kruglov V.I. Statistical characteristics of weight spectra of random linear codes over GF(𝑝). Mathematical Aspects of Cryptography. 2014; 5(1):27–38. (In Russ.)
[31] Kosolapov, Yu.V., Chekunov, E.S. SYMMETRIC CRYPTOSYSTEMS BASED ON ERROR CORRECTION CODES IN Φ-METRICS. Symmetric code cryptosystems based on codes in ℱ -metric. IZVESTIYA SFedU. ENGINEERING SCIENCES. 2010; 112(11):106–116. (In Russ.)
[32] Zhang, K., Tomlinson, M., Ahmed, M. Z. A Modified McEliece Public Key Encryption System with a Higher Security Level. IEEE International Conf. on Information Science and Technology. 2013; (1): 1-5.
[33] Morelos-Zaragoza, R.H. The art of error correcting coding, 2nd Edition. Chichester, West Sussex, England: John Wiley & Sons; 2006: 572.
Bibliography link:
Deundyak V.M., Kosolapov Y.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. 2017. V. 22. ¹ 4. P. 43-60
|
