植基於駐留時間之合作式群組金鑰樹重建機制

Residence Time-Based Key Tree Reconstruction Strategies for Collaborative Group Key Agreement

郭啟志(Chii-Jyh Guo)

指導教授 ： 黃育銘

國立暨南國際大學/科技學院/資訊工程學系/博士(2012年)

https://doi.org/10.6837/NCNU.2012.00274

摘要

在群體導向的網路環境中，藉由金鑰產生中心(Key Generation Center)或群組成員推舉主席，以集中式管控、分配群體金鑰的方法，很容易因為金鑰分配者無法有效地完成分配任務，進而造成系統無法正常運作。而合作式金鑰協定由於能避免這類問題，因此適合運用在群體導向的網路環境中。過去文獻中指出，系統成員的拓樸情況與群體金鑰的重建策略對於系統效能有著極密切的關係，而且在成員變動頻繁以及成員量較大的環境中尤其顯著。
本篇論文中，我們首先修改Lee等人提出的QB金鑰重建機制，修改後的IQB金鑰重建機制能使佇列樹(Queue Tree)有更淺的附掛位置，在模擬實驗中也證實IQB的確可有效降低金鑰的重建成本。此外，基於樹狀結構及批次金鑰更新的概念，我們提出植基於駐留時間之合作式群組金鑰樹重建機制(RBR)，藉此處理成員的異動事件以保證系統的順向與逆向機密。我們的機制包含佇列樹 (Queue-Tree)、佇列樹合併(QT-Merge)、子樹合併(ST-Merge)以及換位 (Relocation)共四個階段。藉由分群與駐留時間的概念，我們所設計的金鑰樹拓樸可以使異動(加入或離開)成員更靠近樹根，因此有效地降低金鑰的更新成本。最後，藉由數學分析以及模擬實驗，相較於其他機制，我們所提之植基於駐留時間之合作式群組金鑰樹重建機制能有更佳的效能。

關鍵字

動態群組 ； 合作式群組金鑰協議 ； 樹狀結構式之群組金鑰協議 ； 時間間隔式之金鑰更新 ； 批次式之金鑰更新 ； 基於駐留時間之金鑰樹重建機制

並列摘要

The contributory group key agreement is suitable for real group-oriented network environments because it avoids the drawbacks of the centralized key generation center and the problem with the single point of failure in three different types of group-oriented communication schemes. Previous studies have pointed out that the scheme performance closely depends on the group member topology and the group key reconstruction strategy, especially for the group with frequent member changes and large group sizes.
In this dissertation, we first propose an IQB (improved queue batch) algorithm and make a simulation experiment to compare the rekeying time cost of IQB with that of Lee et al.’s proposed scheme for meeting the reality. Using the strategy of IQB, the shallower position the temporary queue tree will append to, the more enhancements in efficiency the algorithm will have. Next, based on the idea of tree-based and interval-based batch rekeying, we propose the Residence Time-based Key tree reconstruction strategies, called the Residence Time-based Batch Rekeying (RBR) algorithm, to deal with the membership dynamic events for efficient rekeying to maintain the forward/backward secrecy. The strategies consist of four phases, namely the Queue-Tree phase, the QT-Merge phase, the ST-Merge phase, and the Relocation phase. Using the concepts of subtree division and residence time classification, we design a new key tree topology to ensure that the join/leave member’s location is as near as possible to the root node of key tree to reduce the rekeying cost. Finally, we show that the rekeying cost of RBR is lower than that of any other proposed scheme via both mathematical analysis and simulation experiment.

並列關鍵字

Dynamic peer groups ； Contributory group key agreement ； Tree-based group key agreement ； Interval-based rekeying ； Residence time-based key tree reconstruction

參考文獻

[1]N. Asokan and P. Ginzboorg. Key Agreement in Ad Hoc Networks. Computer Communications, vol. 23, no. 17, pp. 1627-1637, Nov. 2000.

[2]W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Transaction on Information Theory, vol. IT-22, no. 6, pp. 644-654, Nov. 1976.

[3]C.K.Wong, M. Gouda, and S. S. Lam. Secure Group Communications Using Key Graphs. IEEE/ACM Transaction on Networking, vol. 8, no. 1, pp. 16-30, Feb. 2000.

[4]A. Perrig, D. Song, and J. D. Tygar. ELK, A New Protocol for Efficient Large-group Key Distribution. in Proceeding of IEEE Symposium on Security Privacy, 2001, pp. 247-262.

[5]H. Harney and C. Muckenhirn. Group Key Management Protocol (GKMP) Specification. RFC 2093, 1997