Some results of development of cryptographic transformations schemes using non-abelian groups
DOI:
https://doi.org/10.30837/rt.2021.1.204.07Keywords:
post-quantum cryptography, semi direct products, matrix groups, braid groups, logarithmic signatures, algebraic eraserAbstract
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.
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).