在現今的網路環境上，有越來越多的應用程式提供群組式的網路服務，也就是群組中的通訊只有會員才能取得而非會員無法取得，為了達到這個目的，我們可以讓群組中的會員共同分享一把相同的金鑰，我們稱這把金鑰為群組金鑰，所有群組中的資訊在傳送前都必須用群組金鑰加密，這讓只有擁有群組金鑰的會員才可以對加密的資訊解密而獲得正確的資訊，不但如此，為了避免離開群組後的會員能繼續得到群組中的資訊，以及新加入的會員能得到在加入群組前的資訊，我們必須在群組的會員數有更動時更新群組金鑰，而我們的目標就是建構出一個協定，讓更新群組金鑰的動作能更有效率及安全。
在這篇論文中，我們將一個安全群組定義成(gk, U, SK, IK, R, C)的形式，並且利用四階層金鑰圖形描述它，我們所提出的協定不但不需要其它網路協定的配合，也不需額外硬體設備的支援，除此之外，我還提出一個稱為懶惰更新的機制，以減少協定中需要更新共享金鑰的負擔，在這個機制下，每一次會員加入群組的動作只需O(1)的計算複雜度，而每一次會員離開群組的動作需要O(N)的計算複雜度，其中N代表群組中的會員數，而且與參考文獻的[6]相比較時，我們所提出的協定在會員數增加時，其每次更新群組金鑰所需發送的訊息數以及每一位會員所持有的金鑰個數並不會增加。

Many emerging network applications such as pay per view, video
conferencing systems, and information services are based upon a
group communication. Therefore, secure multicasting and group
communication will become a significant networking issue. To
achieve secure multicasting, all authorized recipients form a
secure group and share a group key. For the sake of security, the group key should be updated after a user joins or leaves the
secure group. Our goal is aimed at finding a way to distribute an updated group key efficiently and securely.
In this paper, we formalize the notion of a secure group as a
hexad (gk, U, SK, IK, R, C) and then introduce a four-level key graph to specify the secure group. Our scheme does not require any underlying network topology and network hardware support. We also propose a mechanism, called lazy updating, to reduce computational loads for updating shared keys. With lazy updating, the computation complexity is O(1) per joining
operation and O(N) per leaving operation, where N is the
group size. Moreover, compared with [6], the number of rekey
messages and keys held by each member do not increase when the
group size grows.

Contents
Abstract i
List of Figures v
List of Tables vi
1 Introduction 1
2 Background Knowledge 4
2.1 Multicasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Key Management in Secure Multicasting . . . . . . . . . . . . 5
3 A New Key Graph for Secure Multicasting 9
3.1 Secure Group . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Four-level Key Graph . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Joining a Four-level Key Graph . . . . . . . . . . . . . . . . . 13
3.4 Leaving a Four-level Key Graph . . . . . . . . . . . . . . . . . 15
3.5 Generating a Unused Combinatorial Sequence . . . . . . . . . 17
3.6 Lazy Updating . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.7 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 20
ii
4 Related Work and Performance Comparisons 22
4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.1 Iolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.2 Key Graph . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.3 Reversible Parametric Sequences (RPS) . . . . . . . . . 29
4.1.4 KDSM . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Performance Comparisons . . . . . . . . . . . . . . . . . . . . 39
4.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Key Storage Requirement . . . . . . . . . . . . . . . . 39
4.2.3 Messages Needed . . . . . . . . . . . . . . . . . . . . . 40
4.2.4 Execution Time . . . . . . . . . . . . . . . . . . . . . . 41
4.2.5 Topology and Trusted Third-party Requirement . . . . 43
4.2.6 Characteristics Comparisons . . . . . . . . . . . . . . . 44
4.2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Conclusions 46
Bibliography 47
iii
List of Figures
2.1 Basic unicast service . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Multicast transport service . . . . . . . . . . . . . . . . . . . . 5
2.3 The requirement for a secure multicast group . . . . . . . . . . 6
2.4 A secure multicasing environment . . . . . . . . . . . . . . . . 7
3.1 A four-level key graph . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Four-level key graphs before and after u3 joins . . . . . . . . . 13
3.3 Four-level key graphs before and after u3 leaves . . . . . . . . 16
3.4 The result of the array and the queue before and after u7 joins 18
3.5 Example of lazy updating . . . . . . . . . . . . . . . . . . . . 20
4.1 Example of a secure distribution tree . . . . . . . . . . . . . . 23
4.2 Rekey message on a JOIN . . . . . . . . . . . . . . . . . . . . 24
4.3 Rekey message on a LEAVE . . . . . . . . . . . . . . . . . . . 24
4.4 A key graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.5 Key trees before and after a join . . . . . . . . . . . . . . . . . 27
4.6 Key trees before and after a leave . . . . . . . . . . . . . . . . 29
4.7 Two RPSf sequences over a tree . . . . . . . . . . . . . . . . 31
4.8 A simple tree with three RPSf . . . . . . . . . . . . . . . . . 32
4.9 User mi joins/leaves the group . . . . . . . . . . . . . . . . . . 33
iv
4.10 User m0 joins the secure multicast group . . . . . . . . . . . . 37
4.11 User m3 leaves the secure multicast group . . . . . . . . . . . 38
v
List of Tables
3.1 a simple rule to generate an unused combinatorial sequence . . 17
3.2 the available combinatorial sequences after including sk6 to
SK set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1 Key Storage Requirement . . . . . . . . . . . . . . . . . . . . 40
4.2 Messages Needed . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Topology and Trusted Third-party Requirement . . . . . . . . 44
4.5 Characteristics Comparisons . . . . . . . . . . . . . . . . . . . 44
4.6 Drawbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

[1] A. Ballardie. Scalable multicast key distribution. RFC 1949, May 1996
[2] H. Harney and C. Muckenhirn. Group key management protocol (gkmp)
architecture. RFC 2093, July 1997
[3] H. Harney and C. Muckenhirn. Group key management protocol (gkmp)
architecture. RFC 2094, July 1997
[4] G. H. Chiou and W. T. Chen. Secure broadcasting using the secure lock.
IEEE Trans. Software. Eng., 15:929-934, 1989.
[5] S. Mittra. Iolus: A framework for scalable secure multicasting. In Proc.
ACM SIGCOMM ’97, pages 277-288.
[6] M. G. C. K. Wong and S. S. Lam. Secure group communication using
key graphs. In Proc. ACM SIGCOMM ’98, pages 68-79.
[7] E. J. H. D. M. Wallner and R. C. Agee. Key management for multicast:
Issues and architectures. RFC 2627, June 1999.
[8] G. I. D. M. M. N. R. Canetti, J. Garay and B. Pinkas. Multicast security:
A taxonomy and some ecient constructions. In Proc. INFOCOM ’99,
pages 708-716.
47
Chapter 4. Related Work and Performance Comparisons 48
[9] G. T. M. Steiner and M. Waidner. Cliques: A protocol suit for key
agreement in dynamic groups. Technical report, IBM Zurich Res. Lab,
Switzerland, Res. Rep. RZ 2984 No. 93030, Dec. 1997.
[10] R. Molva and A. Pannetrat. Scalable multicast security in dynamic
groups. In Proc. ACM CCS ’99, pages 101-112.
[11] D. S. N. W. M. Waldvogel, G. Caronni and B. Plattner. The versakey
framework: Versatile group key management. IEEE J. Selected area in
Commun., 17:1614-1631, Sept. 1999.
[12] K. P. Wu, F. Lai. On key distribution in secure multicasting. In Proc.
IEEE LCN, peges 208-212, Nov. 2000.
[13] D. E. Knuth The Art of Computer Programming, Seminumerical Algorithms.
Addison-Wesley, Reading, Mass., 1988.