Cryptanalysis of the system based on word problems using logarithmic signatures
DOI:
https://doi.org/10.30837/rt.2021.3.206.09Keywords:
postquantum cryptography, logarithmic signature, group theory, coverage, cryptanalysisAbstract
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. 6274.
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. 112.
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. 243260.
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. 285297.
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. 321338.
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. 509524.
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. 147155.
Magliveras S. Algebraic Properties of Cryptosystem PGM / S. Magliveras, N. D. Memon // Journal of Cryptology. 1992. Vol. 5 (3). P. 167183.
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.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).