Some results of development of cryptographic transformations schemes using non-abelian groups

Authors

DOI:

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

Keywords:

post-quantum cryptography, semi direct products, matrix groups, braid groups, logarithmic signatures, algebraic eraser

Abstract

Implementation of a successful attack on classical public key cryptosystems becomes more and more real with the advent of practical results in the implementation of Shor's and Grover's algorithms on quantum computers. Modern results in tackling the problem of building a quantum computer of sufficiently power justify the need to revise the existing approaches and determine the most effective in terms of solving problems of post-quantum cryptography. One of these promising research priorities is the study of the cryptosystems based on non-abelian groups.

The problems of conjugacy search, membership search, and others are difficult to solve in the theory of non-abelian groups and are the basis for building provably secure public key cryptosystems. This paper gives an overview of the most frequently discussed algorithms using non-abelian groups: matrix groups braid groups, semi direct products, and algebraic erasers (AE). The analysis of the construction of encryption and decryption schemes, key establishment mechanisms is given. Many non-abelian group-based key establishment protocols are associated with the Diffie – Hellman (DH) protocol. The paper analyzes the properties of non-abelian group public key encryption schemes. Various cryptographic primitives using non-commutative groups as a basis for post-quantum schemes are considered.

References

Shor P. Polynomial-time algorithms for prime factorization and discrete logarithm problems // SIAM Journal on Computing, vol. 26, pp. 1484-1509, 1997.

Magliveras S. S. A cryptosystem from logarithmic signatures of finite groups // Proceedings of the 29th Midwest Symposium on Circuits and Systems, pp. 972–975. Elsevier Publishing, Amsterdam, The Netherlands, 1986.

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.

Magliveras S. S., Svaba P, van Trung T, et al. On the security of a realization of cryptosystem MST3 // Tatra Mt Math Publ, 2008, 41: 1–13

T. van Trung. Construction of strongly aperiodic logarithmic signatures // J. Math. Cryptol., vol. 12, no. 1, pp. 23-35, 2018.

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. MST3 cryptosystem based on a generalized Suzuki 2 – Groups // CEUR Workshop Proceedings, 2020, 2711, pр. 1–15.

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.

Wagner N. R., Magyarik M. R. A public key cryptosystem based on the word problem // Advances in Cryptology (CRYPTO’84). Lecture Notes in Computer Science, vol. 196, pp. 19-36, 1985.

Yamamura A. Public-key cryptosystems using the modular group // 1st Internationa Workshop on Practice and Theory in Public Key Cryptography (PKC’98), Lecture Notes in Computer Science, vol. 1431, pp. 203-216, 1998.

Steinwandt R. Loopholes in two public key cryptosystems using the modular group // Lecture Notes in Computer Science, vol. 1992, pp. 180-189, 2002.

Rososhek S. K. New practical algebraic public-key cryptosystem and Some related algebraic and computational aspects // Applied Mathematics, vol. 4, no, 7, pp. 1043-1049, 2013.

Rososhek S. K. Modified matrix modular cryptosystems // Britsh Journal of Mathematics & Computer Science, vol. 5, no. 5, pp. 613-636, 2015.

Artin E. Theory of braids // Annal of Mathematics, vol. 48, pp. 101-126, 1947. International Journal of Network Security, Vol.20, No.2, PP.278-290, Mar. 2018 (DOI: 10.6633/IJNS.201803.20(2).09) 289.

Anshel I., Anshel M., Goldfeld D., Lemieux S. Key agreement, the algebraic eraserTM, and lightweight cryptography // Contemporary Mathematics, vol. 418, pp. 1-34, 2006.

Anshel I., Anshel M., Goldfeld D. An algebraic method for public-key cryptography // Mathematics Research Letter, vol. 6, pp. 287-291, 1999.

Ko K. H., Choi D. H., Cho M. S., Lee S. J. New Signature Scheme using Conjugacy Problem, 2002. (http://eprint.iacr.org/2002/168)

Ko K. H., Lee S. J., Cheon J. H., Han J. W., Kang J. S., Park C. New public key cryptosystem using braid groups // Advances in Cryptology (CRYPTO’00), pp. 166-184, 2000.

Cheon J., Jun B. A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem // Advances in Cryptography (CRYPTO’03), Lecture Notes in Computer Science, vol. 2729, pp. 212-224, 2003.

Stickel E. A New Public-Key. Cryptosystem in Non-Abelian Groups, 2003. (https: //www.semanticscholar.org)

Stickel E. A new method for exchanging secret keys // Proceedings of the Third International Conference on Information Technology and Applications (ICITA’05), pp. 426-430, 2005.

Shpilrain V. Cryptanalysis of stickel’s key exchange scheme // Lecture Notes in Computer Science, vol. 5010, pp. 283-288, 2008.

Published

2021-04-09

How to Cite

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

Issue

Section

Articles