Cryptanalysis of the system based on word problems using logarithmic signatures

Authors

  • Y. Kotukh Сумський державний університет, Ukraine
  • T. Okhrimenko Національний авіаційний університет, Ukraine
  • O. Dyachenko Маріупольський державний університет, Ukraine
  • N. Rotaneva Маріупольський державний університет, Ukraine
  • L. Kozina Національний університет "Чернігівська політехніка", Ukraine
  • D. Zelenskyi Харківський національний університет радіоелектроніки, Ukraine

DOI:

https://doi.org/10.30837/rt.2021.3.206.09

Keywords:

postquantum cryptography, logarithmic signature, group theory, coverage, cryptanalysis

Abstract

Rapid development and advances of quantum computers are contributing to the development of public key cryptosystems based on mathematically complex or difficult problems, as the threat of using quantum algorithms to hack modern traditional cryptosystems is becoming much more real every day. It should be noted that the classical mathematically complex problems of factorization of integers and discrete logarithms are no longer considered complex for quantum calculations. Dozens of cryptosystems were considered and proposed on various complex problems of group theory in the 2000s. One of such complex problems is the problem of the word. One of the first implementations of the cryptosystem based on the word problem was proposed by Magliveras using logarithmic signatures for finite permutation groups and further proposed by Lempken et al. for asymmetric cryptography with random covers. The innovation of this idea is to extend the difficult problem of the word to a large number of groups. The article summarizes the known results of cryptanalysis of the basic structures of the cryptosystem and defines recommendations for ways to improve the cryptographic properties of structures and the use of non-commutative groups as basic structures.

References

Kotukh Y., Khalimov G. Hard problems for non-abelian cryptography // 2021: Fifth International Scientific and Technical Conference "COMPUTER AND INFORMATION SYSTEMS AND TECHNOLOGIES", 2021, pp39-40, https://doi.org/10.30837/csitic52021232176

Lempken W. A public key cryptosystem based on non-abelian finite groups / W. Lempken, T. van Trung, S.S. Magliveras, W. Wei // Journal of Cryptology. 2009. Vol. 22 (1). P. 6274.

Gonzáles Vasco M. I. On minimal length factorizations of finite groups / M. I. Gonzáles Vasco, M. Rotteler, R. Steinwandt // Experimental Mathematics. 2003. Vol. 12 (1). P. 112.

Singhi N. Minimal logarithmic signatures for finite groups of Lie type / N. Singhi, N. Singhi, S. Magliveras // Designs, Codes and Cryptography. 2010. Vol. 55 (2). P. 243260.

Magliveras S. New approaches to designing public key cryptosystems using one-way functions and trap-doors in finite groups / S. Magliveras, D. Stinson, T. van Trung // Journal of Cryptology. 2002. Vol. 15. P. 285297.

Goldreich O. Foundations of Cryptography: Basic Tools // Cambridge University Press. 2001.

Nuss A. On group based public key cryptography [Electronic resource] : Phd thesis. Access mode : http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-63659.

Blackburn S. R. Cryptanalysis of the MST 3 public key cryptosystem / S. R. Blackburn, C. Cid, C. Mullan // Journal of Mathematical Cryptology. 2009. Vol. 3 (4). P. 321338.

Bohli J. Weak keys in MST / J. Bohli, M. I. Gonzáles Vasco, C. J. M. Martínez, R. Steinwandt // Designs, Codes and Cryptography. 2005. Vol. 37 (3). P. 509524.

Caranti A. The round functions of cryptosystem PGM generate the symmetric group / A. Caranti, F. D. Volta // Designs, Codes and Cryptography. 2006. Vol. 38 (1). P. 147155.

Magliveras S. Algebraic Properties of Cryptosystem PGM / S. Magliveras, N. D. Memon // Journal of Cryptology. 1992. Vol. 5 (3). P. 167183.

Mullan, Ciaran. Some Results in Group-Based Cryptography. (2011)//Thesis

Svaba P. and T. van Trung. Public key cryptosystem MST3 cryptanalysis and realization // Journal of Mathematical Cryptology. Vol.4. No.3. Pp.271–315,2010

Cong Y., Hong H., Shao J., Han S., Lin J. and Zhao S. A New Secure Encryption Scheme Based on Group Factorization Problem // IEEExplore, November 20, 2019 Digital Object Identifier 10.1109/ACCESS.2019.2954672 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8907845

T. van Trung. Construction of strongly aperiodic logarithmic signatures // J. Math. Cryptol. Vol. 12. No. 1. Pp. 23-35, 2018

Kotukh Y., Severinov E., Vlasov O., Tenytska A., Zarudna E. Some results of development of cryptographic transformations schemes using non-abelian groups. Radiotekhnika. 2021. No. 204. Р. 66–72. https://doi.org/10.30837/rt.2021.1.204.07

Kotukh E., Severinov O., Vlasov A., Kozina L., Tenytska A., Zarudna E. Methods of construction and properties of logariphmic signatures . Radiotekhnika 2021. No 205. Р. 94–99. https://doi.org/10.30837/rt.2021.2.205.09

Khalimov G. MST3 Cryptosystem Based on a Generalized Suzuki 2-Groups [Electronic resource] / G. Khalimov, Y. Kotukh, S. Khalimova. Access mode : http://ceur-ws.org/Vol-2711/paper1.pdf

Khalimov G., Kotukh Y., Khalimova S. MST3 cryptosystem based on the automorphism group of the hermitian function field' // IEEE International Scientific-Practical Conference: Problems of Infocommunications Science and Technology, PIC S and T 2019 – Proceedings, 2019. Pр. 865 – 868.

Khalimov G., Kotukh Y., Khalimova S. Encryption scheme based on the automorphism group of the Ree function field // 2020 7th International Conference on Internet of Things: Systems, Management and Security, IOTSMS 2020, 2020, 9340192.

Khalimov G., Kotukh Y., Didmanidze I., Sievierinov O., Khalimova S., Vlasov A. Towards three-parameter group encryption scheme for MST3 cryptosystem improvement // 2021 Fifth World Conference on Smart Trends in Systems Security and Sustainability (WorldS4), 2021, pp. 204-211, doi: 10.1109/WorldS451998.2021.9514009.

Published

2021-09-24

How to Cite

Kotukh, Y. ., Okhrimenko, T. ., Dyachenko, O. ., Rotaneva, N. ., Kozina, L. ., & Zelenskyi, D. . (2021). Cryptanalysis of the system based on word problems using logarithmic signatures. Radiotekhnika, 3(206), 106–114. https://doi.org/10.30837/rt.2021.3.206.09

Issue

Section

Articles