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

S. N. Chukanov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 3, pp. 408-418.

Résumé

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.

Bibliographie

[1] Diffie W., Hellman M. E., “New directions in cryptography”, IEEE Transactions on Information Theory, 22:6 (1976), 644–654 | DOI | Zbl

[2] Anshel I., Anshel M., Goldfeld D., “An algebraic method for public-key cryptography”, Mathematics Research Letter, 6:3 (1999), 287–291 | DOI | Zbl

[3] Hecht P., “Un modelo compacto de criptografia asimetrica empleando anillos no conmutativos”, Actas del V Congreso Iberoamericano de Seguridad Informatica CIBSI'09, 2009, 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”, Advances in Cryptology – CRYPTO 2000, Lecture Notes in Computer Science, 1880, ed. M. Bellare, Springer, Berlin–Heidelberg, 2000, 166–183 | DOI | Zbl

[5] Miasnikov A. G., Shpilrain V., Ushakov A., Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Mathematical Surveys and Monographs, 177, AMS, 2011, 385 pp. | DOI | Zbl

[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), 2015, 6 pp. (in Spain) | DOI

[7] Bayro-Corrochano E., Geometric Algebra Applications, in 2 vols, v. 1, Computer Vision, Graphics and Neurocomputing, Springer, 2020, 742 pp. | DOI | Zbl

[8] Bayro-Corrochano E., Geometric Algebra Applications, in 2 vols, v. 2, Robot Modelling and Control, Springer, 2020, 600 pp. | DOI | Zbl

[9] Hamilton W. R., Elements of Quaternions, Longmans, Green, Co, London, UK, 1866, 762 pp.

[10] Branets V N., Shmyglevsky I. P., Introduction to the Theory of Strapdown Inertial Navigation System, Nauka, M., 1992, 280 pp. (in Russian)

[11] Chelnokov Yu. N., “Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. I”, Cosmic Research, 51:5 (2013), 350–361 | DOI | DOI

[12] Chelnokov Yu. N., “Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. II”, Cosmic Research, 52:4 (2014), 304–317 | DOI | DOI

[13] Chelnokov Yu. N., “Quaternion regularization in celestial mechanics and astrodynamics and trajectory motion control. III”, Cosmic Research, 53:5 (2015), 394–4097 | DOI | DOI

[14] Baez J. C., “The octonions”, Bulletin of the American Mathematical Society, 39:2 (2002), 145–205 | DOI | Zbl

[15] Clifford W. K., “Applications of Grassmann's extensive algebra”, American Journal of Mathematics, 1:4 (1878), 350–358 | DOI | Zbl

[16] Clifford W. K., “Preliminary sketch of biquaternions”, Proceedings of the London Mathematical Society, s1-4:1 (1873), 381–395 | DOI | Zbl

[17] Clifford Multivector Toolbox, , 2020 (accessed 15 July 2020) http://clifford-multivector-toolbox.sourceforge.net/

[18] Sangwine S. J., Hitzer E., “Clifford multivector toolbox (for MATLAB)”, Advances in Applied Clifford Algebras, 27:1 (2017), 539–558 | DOI | Zbl

[19] Mann S., Dorst L., Bouma T., “The making of GABLE: A geometric algebra package in Matlab”, Geometric Algebra with Applications in Science and Engineering, eds. E. Bayro-Corrochano, G. Sobczyk, Birkhäuser, Boston, 2001, 491–511 | DOI

[20] Ablamowicz R., Fauser B., Clifford/Bigebra, a Maple package for Clifford (co)algebra computations (accessed 15 July 2020) http://www.math.tntech.edu/rafal/