Elementary Algorithms Analysis of Megrelishvili Protocol

  • Muhammad Arzaki Computing Laboratory, School of Computing, Telkom University
Abstract views: 681 , PDF downloads: 457


This article presents an investigation of asymptotic time complexities of several algorithms related to Megrelishvili protocol. The analysis are carried out for the private keys computations and public exchange of values, public key constructions, as well as an elementary exhaustive search attack algorithm. We show that the complexities of these algorithms are higher than the complexities of elementary algorithms involved in the conventional Diffie - Hellman protocol (DHP) or its variant on elliptic curves (ECDHP). This condition also implies that Megrelishvili protocol is more secure than DHP and ECDHP against exhaustive search attack.


Download data is not yet available.


Diffie, W. and Hellman, M.E., 1976. New directions in cryptography. Information Theory, IEEE Transactions on, 22(6), pp.644-654.[Crossref]

Joux, A., 2000. A one round protocol for tripartite Diffie–Hellman. In Algorithmic number theory (pp. 385-393). Springer Berlin Heidelberg.

Law, L., Menezes, A., Qu, M., Solinas, J. and Vanstone, S., 2003. An efficient protocol for authenticated key agreement. Designs, Codes and Cryptography, 28(2), pp.119-134.

Menezes, A.J. and Wu, Y.H., 1997. The discrete logarithm problem in GL (n, q). Ars Combinatoria, 47, pp.23-32.

Nelson, J.B., 2003. The Diffie-Hellman key exchange in matrices over a field and a ring (Doctoral dissertation, Texas Tech University).

Doliskani, J.N., Malekian, E. and Zakerolhosseini, A., 2008. A cryptosystem based on the symmetric group Sn. International Journal of Computer Science and Network Security, 8(2), pp.226-234.

Megrelishvili, R., Chelidze, M. and Chelidze, K., 2006. On the construction of secret and public-key cryptosystems. Appl. Math., Inform. Mech, 11(2), pp.29-36.

Cormen, T.H., 2009. Introduction to algorithms. MIT press.

Lidl, R. and Niederreiter, H., 1994. Introduction to finite fields and their applications. Cambridge university press.

Hoffstein, J., Pipher, J., Silverman, J.H. and Silverman, J.H., 2008. An introduction to mathematical cryptography (Vol. 1). New York: Springer.

Niven, I., 1948. Fermat’s theorem for matrices. Duke Mathematical Journal, 15(3), pp.823-826.


Horn, R.A. and Johnson, C.R., 2012. Matrix analysis. Cambridge university press.

Megrelishvili, R. and Sikharulidze, A., 2009, June. New matrix sets generation and the cryptosystems. In Proceedings of the European Computing Conference and Proceedings of the 3rd International Conference on Computational Intelligence, Tbilisi, Georgia (pp. 253-253).


Beletsky, A., Beletsky, A. and Kandyba, R., 2013. Matrix Analogues of the Diffie-Hellman Protocol. In ICTERI (pp. 352-359).

Ambainis, A., Filmus, Y. and Gall, F.L., 2014. Fast matrix multiplication: Limitations of the laser method. arXiv preprint arXiv:1411.5414.

Coppersmith, D. and Winograd, S., 1987, January. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (pp. 1-6). ACM.

Stothers, A.J., 2010. On the complexity of matrix multiplication.

Williams, V.V., 2014. Multiplying matrices in O (n2. 373) time. preprint, http://theory. stanford. edu/~ virgi/matrixmult-f. pdf, Stanford, CA.

Strassen, V., 1969. Gaussian elimination is not optimal. Numerische Mathematik, 13(4), pp.354-356.

Freivalds, R., 1977. Probabilistic Machines Can Use Less Running Time. In IFIP congress (Vol. 839, p. 842).

Megrelishvili, R., Chelidze, M. and Besiashvili, G., 2010, September. Investigation of new matrix-key function for the public cryptosystems. In Proceedings of The Third International Conference, Problems of Cybernetics and Information (Vol. 1, pp. 6-8).

Beletsky, A.J. and Beletsky, А.А., 2012. Synthesis of Primitive Matrices over a Finite Galois Fields and their Applications. Information Technology in Education: Collected Works, 13, pp.23-43.

——, “Conveyor analog matrix for Diffie-Hellman protocol (in Russian),” Information Technologies in Education, vol. 14,

pp. 11–16, 2013.

How to Cite
Arzaki, M. (2016). Elementary Algorithms Analysis of Megrelishvili Protocol. Indonesian Journal on Computing (Indo-JC), 1(1), 11-23. https://doi.org/10.21108/INDOJC.2016.1.1.52