Elementary Analysis of the Communication Complexity of Divide-and-Conquer Diffie-Hellman Key Agreement Protocol

Muhammad Arzaki

Abstract


We present a rigorous elementary analysis of the communication complexity of the Divide-and-Conquer Diffie-Hellman Key Agreement Protocol (DC-DHKA). The analysis is conducted by first determining the number of transmissions in DC-DHKA and then comparing the resulting communication complexity of this protocol with other variants of Diffie-Hellman key agreement protocols that utilize regular Diffie-Hellman key, namely the ING, GDH.1, GDH.2, and GDH.3 protocols. The mathematical and numerical analyses show that the total number of bits transmitted in the DC-DHKA protocol is always fewer than those of ING, GDH.1, and GDH.2 protocols for a group of N >= 19 participants. In addition, we also prove that the total number of bits required for the entire messages’ transmissions in DC-DHKA protocol for N participants that uses the multiplicative group Fq* is log2(q) 2^(log2(N)) (log2(N) + 1) - 2.

Keywords


Communication Complexity; DC-DHKA; Diffie-Hellman; Key Agreement

Full Text:

PDF

References


T. Hardjono and L. R. Dondeti, Security in Wireless LANS and MANS (Artech House Computer Security). Artech House, Inc., 2005.

M. B. Yassein, S. Aljawarneh, E. Qawasmeh, W. Mardini, and Y. Khamayseh, “Comprehensive study of symmetric key and asymmetric key encryption algorithms,” in 2017 international conference on engineering and technology (ICET). IEEE, 2017, pp. 1–7.

Y. Kim, A. Perrig, and G. Tsudik, “Tree-based group key agreement,” ACM Transactions on Information and System Security (TISSEC), vol. 7, no. 1, pp. 60–96, 2004.

P. Jaiswal, A. Kumar, and S. Tripathi, “Design of Secure Group Key Agreement Protocol using Elliptic Curve Cryptography,” in High Performance Computing and Applications (ICHPCA), 2014 International Conference on. IEEE, 2014, pp. 1–6.

W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, vol. IT.22 No. 6, pp. 644–654, 1976.

I. Ingemarsson, D. T. Tang, and C. K. Wong, “A Conference Key Distribution System,” IEEE Transactions on Information Theory, vol. 28, no. 5, pp. 714–720, 1982.

M. Burmester and Y. Desmedt, “A Secure and Efficient Conference Key Distribution System,” in Workshop on the Theory and Application of of Cryptographic Techniques. Springer, 1994, pp. 275–286.

M. Steiner, G. Tsudik, and M. Waidner, “Diffie-Hellman Key Distribution Extended to Group Communication,” in Proceedings of the 3rd ACM Conference on Computer and Communications Security. ACM, 1996, pp. 31–37.

K. Becker and U. Wille, “Communication complexity of group key distribution,” in Proceedings of the 5th ACM conference on Computer and communications security, 1998, pp. 1–6.

S. A. Gaonkar and H. M. Pai, “Extension of Diffie Hellman Algorithm for Multiple Participants,” International Journal of Innovative Research in Electrical, Electronics, Instrumentation and Control Engineering, pp. 42–47, 2015.

R. Dewoprabowo, M. Arzaki, and Y. Rusmawati, “On Generalized Divide and Conquer Approach for Group Key Distribution: Correctness and Complexity,” in 2018 6th International Conference on Information and Communication Technology (ICoICT). IEEE, 2018, pp. 416–424.

R. Dewoprabowo, M. Arzaki, and Y. Rusmawati, “Formal Verification of Divide and Conquer Key Distribution Protocol Using ProVerif and TLA+,” in 2018 10th International Conference on Advanced Computer Science and Information Systems (ICACSIS). IEEE, 2018, pp. 451–458.

A. Rao and A. Yehudayoff, Communication Complexity: and Applications. Cambridge University Press, 2020.

A. C.-C. Yao, “Some complexity questions related to distributive computing (preliminary report),” in Proceedings of the eleventh annual ACM symposium on Theory of computing, 1979, pp. 209–213.

E. Kushilevitz, “Communication complexity,” in Advances in Computers. Elsevier, 1997, vol. 44, pp. 331–360.

I. Haitner, N. Mazor, R. Oshman, O. Reingold, and A. Yehudayoff, “On the communication complexity of key-agreement protocols,” arXiv preprint arXiv:2105.01958, 2021.

J. Hoffstein, J. C. Pipher, and J. H. Silverman, An introduction to mathematical cryptography, 2nd ed. Springer, 2014.

K. H. Rosen, Discrete Mathematics and Its Applications, 8th Edition. McGraw-Hill Education, 2018. [Online]. Available: https://books.google.co.id/books?id=rwZLAgAAQBAJ

M. Arzaki, “On the Generalizations of Megrelishvili Protocol for Group Key Distribution,” Indonesian Journal on Computing (Indo-JC), vol. 2, no. 2, pp. 55–78, 2017.

X. L. Jintai Ding, Xiang Xie, “A simple provably secure key exchange scheme based on the learning with errors problem,” Cryptology ePrint Archive, Report 2012/688, 2012, https://eprint.iacr.org/2012/688.




DOI: http://dx.doi.org/10.12962/j24775401.v8i2.13414

Refbacks




View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.