Elementary Algorithms Analysis of Megrelishvili Protocol

Muhammad Arzaki (Computing Laboratory, School of Computing, Telkom University)

Indonesian Journal on Computing (Indo-JC)
Vol. 1 No. 1 (2016): March, 2016

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.