Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Chukanov S. N. The key exchange protocol based on non-commutative elements of Clifford algebra. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2021, vol. 21, iss. 3, pp. 408-418. DOI: 10.18500/1816-9791-2021-21-3-408-418, EDN: GCYQYB

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 1370)
Article type: 

The key exchange protocol based on non-commutative elements of Clifford algebra

Chukanov Sergei N., Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Omsk Branch

Many of the asymmetric cryptography protocols are based on operations performed on commutative algebraic structures, which are vulnerable to quantum attacks. The development of algorithms in non-commutative structures makes it possible to strengthen these protocols. Cryptography is a branch of mathematics that solves the problem of transmitting information through unsafe channels. For this, information is encrypted, so it cannot be used without first decrypting it. In encrypted communication, subtasks are distinguished: secure key exchange, and then encryption/decryption of the message. Public key cryptography uses the Diffie – Hellman key exchange protocol.  Since the beginning of this century, interest has increased in the development of alternative asymmetric cryptosystems that are resistant to attacks by quantum computer algorithms. Most of these schemes are non-commutative cryptography algorithms, such as a scheme of matrix polynomial ring. One of the tasks for the development of cryptographic schemes – the task of conjugacy search, can be formulated over finite non-commutative groups. The security of information transmission can be built based on the undecidability of the conjugacy search problem, which is defined over finite non-commutative groups. The aim of this work is to develop a model of the Diffie – Hellman protocol using the algebraic structure of the Clifford algebra (which includes the quaternions) and the structures of the polynomial ring. Safety ensuring of the algorithm using Clifford algebras is based on the non-commutative structure of these algebras and the ability to work in a space of any dimension $n \ge 1 $. Clifford algebra groups are non-commutative structures, as are matrix polynomials and braid groups. However, Clifford algebra groups are more compact and show shorter execution times in many comparable operations. The use of elements of Clifford algebras and exponents of integers as coefficients allows us to reduce the requirement for processor registers (do not use floating-point processors) and significantly increase the performance of forming the Diffie – Hellman protocol.

This work was supported by the Russian Foundation for Basic Research (projects Nos. 18-07-00526, 18-08-01284).
  1. Diffie W., Hellman M. E. New directions in cryptography. IEEE Transactions on Information Theory, 1976, vol. 22, no. 6, pp. 644–654. https://doi.org/10.1109/ TIT.1976.1055638
  2. Anshel I., Anshel M., Goldfeld D. An algebraic method for public-key cryptography. Mathematics Research Letter, 1999, vol. 6, no. 3, pp. 287–291. http://dx.doi.org/0.4310/ MRL.1999.v6.n3.a3
  3. Hecht P. Un modelo compacto de criptografia asimetrica empleando anillos no conmutativos. Actas del V Congreso Iberoamericano de Seguridad Informatica CIBSI’09, 2009. pp. 188–201.
  4. Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, Choonsik Park. New public-key cryptosystem using braid group. In: M. Bellare, ed. Advances in Cryptology — CRYPTO 2000. (Lecture Notes in Computer Science, vol. 1880). Springer, Berlin, Heidelberg, 2020, pp. 166–183. https://doi.org/10.1007/3-540-44598-6_10
  5. Miasnikov A. G., Shpilrain V., Ushakov A. Non-Commutative Cryptography and Complexity of Group-Theoretic Problems. (Mathematical Surveys and Monographs, vol. 177). AMS, 2011. 385 p.
  6. Kamlofsky J. A., Hecht J. P., Masih S., Izzi O. A Diffie – Hellman compact model over non-commutative rings using quaternions. MEMORIAS CIBSI 2015 (VIII Congreso Iberoamericano de Seguridad Informatica). Quito, Ecuador, 2015. 6 p. (in Spain). https://doi.org/10.13140/RG.2.1.4063.1760
  7. Bayro-Corrochano E. Geometric Algebra Applications. Vol. 1: Computer Vision, Graphics and Neurocomputing. Springer, 2020. 742 p. https://doi.org/10.1007/978-3-319-74830-6
  8. Bayro-Corrochano E. Geometric Algebra Applications. Vol. 2: Robot Modelling and Control. Springer, 2020. 600 p. https://doi.org/10.1007/978-3-030-34978-3
  9. Hamilton W. R. Elements of Quaternions. London, UK, Longmans, Green, & Co, 1866. 762 p.
  10. Branets V N., Shmyglevsky I. P. Vvedenie v teoriiu besplatformennoi inertsial’noi navigatsionnoi sistemy [Introduction to the Theory of Strapdown Inertial Navigation System]. Moscow, Nauka, 1992. 280 p. (in Russian).
  11. Chelnokov Yu. N. Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. I. Cosmic Research, 2013, vol. 51, iss. 5, pp. 350–361. https://doi.org/10.1134/S001095251305002X
  12. Chelnokov Yu. N. Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. II. Cosmic Research, 2014, vol. 52, iss. 4, pp. 304–317. https://doi.org/10.1134/S0010952514030022
  13. Chelnokov Yu. N. Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. III. Cosmic Research, 2015, vol. 53, iss. 5, pp. 394–4097. https://doi.org/10.1134/S0010952515050044
  14. Baez J. C. The octonions. Bulletin of the American Mathematical Society, 2002, vol. 39, no. 2, pp. 145–205.
  15. Clifford W. K. Applications of Grassmann’s extensive algebra. American Journal of Mathematics, 1878, vol. 1, no. 4, pp. 350–358. https://doi.org/10.2307/2369379
  16. Clifford W. K. Preliminary sketch of biquaternions. Proceedings of the London Mathematical Society, 1873, vol. s1-4, iss. 1, pp. 381–395. https://doi.org/10.1112/plms/s1- 4.1.381
  17. Clifford Multivector Toolbox. Available at: http://clifford-multivector-toolbox.sourceforge. net/ (accessed 15 July 2020).
  18. Sangwine S. J., Hitzer E. Clifford multivector toolbox (for MATLAB). Advances in Applied Clifford Algebras, 2017, vol. 27, iss. 1. pp. 539–558. https://doi.org/10.1007/s00006-016- 0666-x
  19. Mann S., Dorst L., Bouma T. The making of GABLE: A geometric algebra package in Matlab. In: E. Bayro-Corrochano, G. Sobczyk, eds. Geometric Algebra with Applications in Science and Engineering. Boston, Birkhauser, 2001, pp. 491–511. https://doi.org/10.1007/ 978-1-4612-0159-5_24
  20. Ablamowicz R., Fauser B. Clifford/Bigebra, a Maple package for Clifford (co)algebra computations. Available at: http://www.math.tntech.edu/rafal/ (accessed 15 July 2020).