Elementary Algorithms Analysis of Megrelishvili Protocol

Authors

  • Muhammad Arzaki Computing Laboratory, School of Computing, Telkom University

DOI:

https://doi.org/10.21108/INDOJC.2016.1.1.52

Abstract

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.

Downloads

Download data is not yet available.

References

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.

[crossref]

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).

Megrelishvili, R., ON THE ORIGINAL ONE-WAY FUNCTION AND THE NEW DIGITAL SIGNATURE SCHEME.

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.

Indonesian Journal on Computing Volume 1, Issue 1, March 2016

Downloads

Published

2016-03-31

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

Issue

Vol. 1 No. 1 (2016): March, 2016

Section

Articles

License

  • Manuscript submitted to IndoJC has to be an original work of the author(s), contains no element of plagiarism, and has never been published or is not being considered for publication in other journals. 
  • Copyright on any article is retained by the author(s). Regarding copyright transfers please see below.
  • Authors grant IndoJC a license to publish the article and identify itself as the original publisher.
  • Authors grant IndoJC commercial rights to produce hardcopy volumes of the journal for sale to libraries and individuals.
  • Authors grant any third party the right to use the article freely as long as its original authors and citation details are identified.
  • The article and any associated published material is distributed under the Creative Commons Attribution 4.0License