Efficient protocols for group key establishment based on secret sharing

Document Type : Full Length Article

Authors

1 Department of Computer Science, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran.

2 Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

Abstract

Secure group communication is a fundamental requirement in modern distributed systems, relying on efficient and secure group key establishment protocols. While secret sharing has been effectively utilized to construct such protocols, existing approaches often incur significant computational overhead. This paper addresses this efficiency challenge by presenting novel improvements to the group key agreement protocol of Harn and Lin and the group key distribution protocol of Harn and Hsu. Our key insight is to replace the use of Shamir's (n,n) threshold secret sharing scheme in the existing protocols with Shamir's (2,2) threshold scheme, which consequently reduces the core polynomial operations from degree n to degree one. This optimization drastically lowers the computational cost associated with polynomial construction and interpolation, while maintaining the security guarantees of the original protocols. Security analysis demonstrates that the proposed protocols provably satisfy essential properties such as key confidentiality, authenticity, and forward secrecy under the hardness of the decisional Diffie-Hellman problem. Performance comparisons confirm that our constructions achieve superior efficiency in both computation and communication, making them highly practical for large-scale group applications.

Graphical Abstract

Efficient protocols for group key establishment based on secret sharing

Keywords

Main Subjects

References

 [1] W. Diffie, M. E. Hellman, New Directions in Cryptography, IEEE Trans. Inf. Theory, 22(6) (1976) 644–654. https://doi.org/10.1109/TIT.1976.1055638
[2] A. Joux, A one round protocol for tripartite Diffie-Hellman, International algorithmic number theory symposium, (2000) 385–393. https://doi.org/10.1007/10722028_23
[3] H. Yang, Y. Zhang, Y. Zhou, X. Fu, H. Liu, A. V. Vasilakos, Provably secure three-party authenticated key agreement protocol using smart cards, Computer Networks, 58 (2014) 29–38. https://doi.org/10.1016/j.comnet.2013.08.020
[4] Y. Xie, L. Wu, J. Shen, L. Li, Efficient two-party certificateless authenticated key agreement protocol under GDH assumption, Int. J. Ad Hoc Ubiquitous Comput., 30(1) (2019) 11–25. https://doi.org/10.1504/IJAHUC.2019.097093
[5] A. Ostad-Sharif, H. Arshad, M. Nikooghadam, D. Abbasinezhad-Mood, Three party secure data transmission in IoT networks through design of a lightweight authenticated key agreement scheme, Future Gener. Comput. Syst., 100 (2019) 882–892. https://doi.org/10.1016/j.future.2019.04.019
[6] I. Ingemarsson, D. Tang, C. Wong, A conference key distribution system, IEEE Trans. Inf. Theory, 28(5) (1982) 714–720. https://doi.org/10.1109/TIT.1982.1056542
[7] Y. Kim, A. Perrig, G. Tsudik, Group key agreement efficient in communication, IEEE Trans. Comput., 53(7) (2004) 905–921. https://doi.org/10.1109/TC.2004.31
[8] A. Shoufan, S. A. Huss, High-performance rekeying processor architecture for group key management, IEEE Trans. Comput., 58(10) (2009) 1421–1434. https://doi.org/10.1109/TC.2009.88
[9] Y. Sun, S. Yin, J. Liu, L. Teng, A Certificateless Group Authenticated Key Agreement Protocol Based on Dynamic Binary Tree, Int. J. Netw. Secur. 21(5) (2019) 843–849. https://doi.org/10.6633/IJNS.201909_21(5).17
[10] M. Burmester, Y. Desmedt, A secure and efficient conference key distribution system, Advances in Cryptology - EUROCRYPT’94 (1995) 275–286. https://doi.org/10.1007/BFb0053443
[11] Z. Eslami, M. Noroozi, S. Kabiri Rad, Provably Secure Group Key Exchange Protocol in the Presence of Dishonest Insiders, Int. J. Netw. Secur. 18(1) (2016) 33–42. https://doi.org/10.6633/IJNS.201601.18(1).03
[12] R. Dutta, R. Barua, Provably secure constant round contributory group key agreement in dynamic setting, IEEE Trans. Inf. Theory, 54(5) (2008) 2007–2025. https://doi.org/10.1109/TIT.2008.920224
[13] A. Shamir, How to share a secret, Commun. ACM, 22(11) (1979) 612–613. https://doi.org/10.1145/359168.359176
[14] G. Blakley, Safeguarding cryptographic keys, AFIPS Conference Proceedings (1979). https://doi.org/10.1109/MARK.1979.8817296
[15] P. Feldman, A practical scheme for non-interactive verifiable secret sharing, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) (1987). https://doi.org/10.1109/SFCS.1987.4
[16] T. Tassa, Hierarchical threshold secret sharing, Journal of cryptology, 20(2) (2007) 237–264. https://doi.org/10.1007/s00145-006-0334-8
[17] Z. Eslami, N. Pakniat, M. Noroozi, Hierarchical threshold multi-secret sharing scheme based on Birkhoff interpolation and cellular automata, 2015 18th CSI International Symposium on Computer Architecture and Digital Systems (CADS) (2015). https://doi.org/10.1109/CADS.2015.7377795 
 [18] C. S. Laih, J. Y. Lee, L. Harn, A new threshold scheme and its application in designing the conference key distribution cryptosystem, Inf. Process. Lett., 32(3) (1989) 95–99. https://doi.org/10.1016/0020-0190(89)90008-2
[19] S. Berkovits, How to broadcast a secret, Advances in Cryptology - EUROCRYPT’91 (1991) 535–541. https://doi.org/10.1007/3-540-46416-6_50
[20] C. Li, J. Pieprzyk, Conference key agreement from secret sharing, Australasian Conference on Information Security and Privacy, (1999) 64–76. https://doi.org/10.1007/3-540-48970-3_6
[21] G. Saez, Generation of key predistribution schemes using secret sharing schemes, Discrete Appl. Math., 128(1) (2003) 239–249. https://doi.org/10.1016/S0166-218X(02)00448-1
[22] L. Harn, C. Lin, Efficient group Diffie–Hellman key agreement protocols, Comput. Electr. Eng., 40(6) (2014) 1972–1980. https://doi.org/10.1016/j.compeleceng.2013.12.018
[23] L. Harn, C. Hsu, A practical hybrid group key establishment for secure group communications, The Computer Journal, 60(11) (2017) 1582–1589. https://doi.org/10.1093/comjnl/bxx003
[24] J. Cai, Z. Zhang, M. Li, N. Li, A group authenticated key agreement protocol for secure communication between distributed power terminal devices, Comput. Electr. Eng., 118 (2024) 109214. https://doi.org/10.1016/j.compeleceng.2024.109214
[25] J. Chen, X. Zhou, W. Fu, Y. Mao, Enhancing Efficiency in Trustless Cryptography: An Optimized SM9-Based Distributed Key Generation Scheme, Sensors, 24(24) (2024) 7874. https://doi.org/10.3390/s24247874
[26] R. Subrahmanyam, N. R. Rekha, Y. V. S. Rao, Authenticated Distributed Group Key Agreement Protocol Using Elliptic Curve Secret Sharing Scheme, IEEE Access, 11 (2023) 45243–45254. https://doi.org/10.1109/ACCESS.2023.3274468
[27] P. Dzurenda, S. Ricci, R. C. Marques, J. Hajny, P. Cika, Secret sharing-based authenticated key agreement protocol, Proceedings of the 16th international conference on availability, reliability and security, (2021) 1–10. https://doi.org/10.1145/3465481.3470057 
Journal of Discrete Mathematics and Its Applications
Volume 11, Issue 3
September 2026
Pages 177-191

Files

History

  • Receive Date: 23 November 2025
  • Revise Date: 08 December 2025
  • Accept Date: 22 December 2025
  • First Publish Date: 30 August 2026
  • Publish Date: 01 September 2026

Share

How to cite

Statistics