無線感測網路是由一群低成本的微型感測器所組成的無線通訊網路，它們可能散佈在某特定區域進行感測資料收集的任務。在無線感測網路中有關安全的議題愈來愈受到重視，而金鑰分發則是影響了訊息加密與認證等安全機制能否正常運作的基本前提。本論文提出了一個具有可擴充性、群組式之隨機金鑰分發機制，它將所有節點分為多個群組並利用單向函數來產生群組對群組的金鑰，以提高金鑰之連結性與最大支援節點數。在效能評估上，我們分析出在目前所有基於隨機預先分發的金鑰機制中，本機制能夠提供最大支援的節點數，而在安全性方面模擬結果也顯示此機制對於入侵節點之攻擊有著良好的抵禦能力。
　　除此之外，為了降低已遭入侵之節點對網路的不良影響，本論文也提出了一個分散式節點撤銷機制，此機制採用了投票的方式，對已遭入侵之節點進行撤銷的動作，並且利用Threshold Secret Sharing的概念來降低記憶體空間成本。

The security issue in distributed sensor networks (DSNs) has been drawing considerable research attention in recent years. Key management, a basic security service, becomes the core design for various security services like encryption and authentication. This thesis presents a Scalable Grouping (SG) random key predistribution scheme which divides all nodes into several groups and uses the one-way function to generate group-to-group pairwise keys to increase the connectivity of each key and to enlarge the maximum supportable network size. Experimental results show that the SG scheme is able to yield more enhanced resilience against node capture in large-scale networks, generate higher scalability than existing random key based schemes, and limit global payoff from local compromised nodes.
　Besides, in order to reduce the effect from compromised nodes, we also propose a distributed node revocation scheme based on the SG scheme. It can revoke the existing compromised node by voting and adopt the concept of Threshold Secret Sharing to reduce the memory cost.

中文摘要..............................Ⅰ
英文摘要..............................Ⅱ
目錄..............................Ⅲ
圖表目錄..............................Ⅴ

第一章 緒論..............................1
第二章 相關研究背景..............................5
2.1 Random Key Based Distribution Scheme..............................5
2.1.1 The Random Key Predistribution Scheme..............................5
2.1.2 The q-Composite Keys Scheme..............................8
2.1.3 The Random-Pairwise Keys Scheme..............................10
2.1.4 The Unique Assigned One-way (UAO) Function Scheme..............................11
2.2 Node Revocation Scheme..............................14
2.2.1 EG Scheme..............................14
2.2.2 CPS Scheme..............................15
2.2.3 Merkle Tree之介紹..............................18
2.3 Key Discovery Scheme..............................21
2.3.1 Key Index Notification..............................21
2.3.2 Challenge Response..............................21
2.3.3 Pseudo Random Key Index Transformation..............................22
2.3.4 PRK Scheme (Pseudo-Random Key Pre-Deployment)..............................22
第三章 新金鑰分發機制之架構..............................25
第四章 新金鑰分發機制之效能評估..............................30
4.1 參數說明..............................31
4.2 安全性之評估..............................32
4.3 網路最大節點數之評估..............................35
4.4 Limited Global Payoff Requirement..............................39
第五章 新節點撤銷機制之想法..............................43
5.1 Threshold Secret Sharing之介紹..............................43
5.2 新節點撤銷機制之架構..............................45
第六章 結論..............................47
參考文獻..............................50

圖 2.1：Path key建立路徑示意圖..............................6
圖 2.2：q-composite scheme與basic scheme安全性之比較..............................9
圖 2.3：UAO scheme與random-pairwise keys scheme其最大支援節點數之比較..............................13
圖 2.4：CPS scheme其空間複雜度之示意圖..............................17
圖 2.5：Merkle tree的範例..............................19
圖 2.6：CPS scheme加入Merkle tree後，其空間複雜度之示意圖..............................20
圖 3.1：Link key setup algorithm運作流程..............................28
圖 3.2：SG scheme之運作範例..............................29
圖 4.1：節點入侵抗性之比較（n = 1000, n’ = 60, p = 0.33）..............................33
圖 4.2：節點入侵抗性之比較（n = 2000, n’ = 60, p = 0.33）..............................34
圖 4.3：各種金鑰分發機制其最大支援節點數..............................37
圖 4.4：2-SG scheme對於Limited global payoff requirement之評估..............................41
圖 4.5：3-SG scheme對於Limited global payoff requirement之評估..............................42

表 4.1：各種金鑰分發機制所使用的key ring size（p = 0.33）..............................33

[1] I. F. Akyildiz, Su Weilian, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, Vol. 40, Aug. 2002, pp. 102-114

[2] A. Perrig, R. Szewczyk, J.D. Tygar, V. Wen, and D. E. Culler, “SPINS: security protocols for sensor networks,” Wireless Networks, Vol. 8, Sept. 2002, pp. 521-534.

[3] S. Zhu, S. Setia, and S. Jajodia, “LEAP: Efficient Security Mechanisms for Large-Scale Distributed Sensor Networks,” Proc. 10th ACM Conference on Computer and communication security, Oct. 2003, pp. 62-72.

[4] L. Eschenauer and V. D. Gligor, “A key-Management Scheme for Distributed Sensor Networks,” Proc. 9th ACM Conference on Computer and Communication Security, Nov. 2002, pp. 41-47.

[5] S. Y. Wu and S. P. Shieh, “Adaptive Random Key Distribution Schemes for Wireless Sensor Networks,” Proc. 2003 International Workshop on Advanced Developments in Software and Systems Security, Dec. 2003.

[6] A. Shamir, “How to Share a Secret,” Communications of the ACM, Vol. 22, No. 11, Nov. 1979, pp. 612-613.

[7] H. Chan, A. Perrig, and D. Song, “Random Key Predistribution Schemes for Sensor Networks,” Proc. IEEE Symposium on Research in Security and Privacy, May 2003, pp. 197-213.

[8] J. Spencer, The Strange Logic of Random Graphs, Algorithms and Combinatorics.22, Springer-Verlag, 2000.

[9] R. Merkle, “Protocols for public key cryptosystems,” Proc. 1980 IEEE Symposium on Security and Privacy, Apr. 1980, pp. 122-134.

[10] D. Liu and P. Ning, “Establishing pairwise keys in distributed sensor networks,” Proc. 10th ACM Conference on Computer and Communications Security (CCS ’03), Oct. 2003, pp. 52-61.

[11] S. Zhu, S. Xu, S. Setia, and S. Jajodia, “Establishing pairwise keys for secure communication in ad hoc networks: a probabilistic approach,” Proc. 11th IEEE International Conference on Network Protocols (ICNP ’03), Nov. 2003, pp. 326-335.

[12] R. D. Pietro, L. V. Mancini, and A. Mei, “Efficient and Resilient Key Discovery Based on Pseudo-Random Key Pre-Deployment,” Proc. 18th International Parallel and Distributed Processing Symposium, Apr. 2004.