隨著VLSI技術的進步，分散式的無線感測網路成為一種新興的網路型態，並帶來所許多全新的應用。但由於其應用場景以及硬體能力的特性，存在著許多嚴格的限制，因此如何在如此嚴苛的環境下，除了能執行感測網路本身的任務之外，還能加上安全性的考量，來抵抗許多已知及未知的攻擊，就成為了一個困難但必要的研究課題。
不同於目前大多數針對感測網路所提出的預先分配金鑰機制，本篇碩士論文提出一個全新的方法來產生金鑰池，在金鑰中預先存入隱藏的資訊，使得節點可以在滿足特定條件的情況下，經由我們所定義的 函數還原出金鑰中事先隱藏的額外資訊，進而經由這些額外的資訊提升系統效能。基於以上的構想，我們經由門檻法 (Threshold Scheme) 與 OSS 簽章系統 (OSS Signature Scheme) 的概念，分別提出了兩個 PTS 以及 POSS 預先分配金鑰機制。並經由模擬的結果，我們可以知道，感測節點所得到的額外資訊能大幅提升節點間的連結率，既使在節點配置較為稀疏或是不均勻的狀況下也能達到令人滿意的效能。此外，高連結率的特性可以加速感測網路中安全通道的建構時間，提供即時的訊息回應，以及降低感測節點間的無線通訊負載，延長節點壽命。這些特性提供了分散式無線感測網路的建構者，可以針對不同的網路環境調整適當的系統效能。

Because of the advancement of VLSI technology in recently years, Distributed Sensor Networks (DSNs) become a new developing type of wireless networks, which bring many novel applications. DSNs have many rigorous restrictions as a result of the application environment and hardware ability. Hence, it is a difficult but significant research topic that how to implement security into DSNs against many known and unknown attacks.
In this thesis, we propose a key predistribution model with a novel concept of key pool generation, which is different from most existing schemes. The hidden information is inserted into each key when key pool is generated. Nodes can use the function to obtain the hidden additional information from condition-satisfied keys. The additional information can elevate system performance. Based on above conception, we proposed PTS and POSS schemes, which are based on threshold scheme and OSS signature scheme respectively. We can know that the additional information improved great progress connectivity between nodes by simulated results even if the node deployment is sparse or nonuniform. Beside, the property of high connectivity speeds up the time of secure link establishment in sensor network as well as provides rapid message response. In addition, the high connectivity also decreases the energy consumption of wireless communication between sensor nodes to extend the life of nodes. These properties provide the wireless DSNs designers to adjust the appropriate network performance for different application requirements.

[1] R. Adler, M. Flanigan, J. Huang, R. Kling, N. Kushalnagar, L. Nachman, C. Y. Wang and M. Yarvis, “Intel Mote 2: An advanced platform for demanding sensor network applications” in Proceedings of the Second ACM Conferences on Embedded Networked Sensor Systems (SenSys), 2005.
[2] G.R. Blakley, “Safeguarding cryptographic keys,” Proceedings of AFIPS National Computer Conference, pp. 313-317, 1979.
[3] R. Blom, “An optimal class of symmetric key generation systems,” Proceedings of EUROCRYPT ’84 on Advances in Cryptology, pp. 335-338, 1985.
[4] C. Blundo, A.D. Santis, A. Herzberg, S. Kutten, U. Vaccaro and M.Yung, “Perfectly-secure key distribution for dynamic conferences,” Lecture Notes in Computer Science, vol. 740, pp. 471-486, 1993.
[5] D. Carman, P. Kruus and B. Matt, “Constraints and approaches for distributed sensor network security,” NAI Labs Technical Report #00-010, Sep. 2000.
[6] H. Chan, A. Perrig and D. Song, “Random key predistribution schemes for sensor networks,” in IEEE Symposium on Research in Security and Privacy, pp. 197-213, 2003.
[7] H. Chan, V.D. Gligor, A. Perrig and G. Muralidharan, “On the distribution and revocation of cryptographic keys in sensor networks,” IEEE Transactions on Dependable And Secure Computing, vol. 2, no. 3, July-Sep. 2005.
[8] W. Diffie and M.E. Hellman, “New directions in cryptography”. IEEE Transactions on Information Theory IT-22, , 644-654, Nov. 1976.
[9] W. Diffie, "The first ten years of public key cryptography". Proceedings of the IEEE, vol. 76, no. 5, pp.560-577, May 1988.
[10] W. Du, J. Deng, Y. Han and P. Varshney, “A pairwise key predistribution scheme for wireless sensor networks,” Proceedings of 10th ACM Conf. Computer and Comm. Security (CCS 2003), pp. 42-51, Oct. 2003.
[11] W. Du, J. Deng, Y. Han, P. Varshney, J. Katz and A. Khalili, “A pairwise key predistribution scheme for wireless sensor networks,” ACM Transactions on Information and System Security (TISSEC), vol. 8 no.1, pp. 41-77 Feb. 2005.
[12] W. Du, J. Deng, Y. S. Han and P. K. Varshney, “A key predistribution scheme for sensor networks using deployment knowledge,” IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 1, Jan.-March 2006.
[13] P. Erdős and A. Rényi, “On random graphs I,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290-297, 1959.
[14] L. Eschenauer and V.D. Gligor, “A key-management scheme for distributed sensor networks,” Proceedings of Ninth ACM Conf. Computer and Comm. Security (CCS), pp. 41-47, 2002.
[15] J. Hill, R. Szewczyk, A.Woo, S. Hollar, D. Culler and K. Pister, “System architecture directions for networked sensors,” in International Conference on Architectural Support for Programming Languages and Operating Systems.
[16] D.E. Knuth, The Art of Computer Programming, vol 2: Seminumerical Algorithms, Addison-Wesley, pp. 484-487, 1981.
[17] C.S. Laih, “Threshold schemes,” Proceedings of The first conference on Information Security, pp.107-145, Dec. 1990.
[18] D. Liu and P. Ning, “Establishing pairwise keys in distributed sensor networks,” Proceedings of 10th ACM Conf. Computer and Comm. Security (CCS), pp. 52-61, 2003.
[19] D. Liu, P. Ning and R. Li, “Establishing pairwise keys in distributed sensor networks,” ACM Transactions on Information and System Security (TISSEC), vol. 8 no.2, pp. 228-258, Feb. 2005.
[20] R. Merkle, “Secure communication over insecure channels,” Communications of the ACM, 1978.
[21] R. Merkle and M. Hellman, “Hiding information and signatures in trapdoor knapsacks,” IEEE Transactions on Information Theory, vol. IT-24 no. 5, pp. 525-530, Sept. 1978.
[22] R. Merkle, “Protocols for public key cryptosystems,” Proceedings of IEEE Symposium Research in Security and Privacy, pp. 122-134, Apr. 1980.
[23] B.C. Neuman and T. Tso, “Kerberos: An authentication service for computer networks,” IEEE Communication Magazine, vol. 32, no. 9, pp. 33-38, Sept. 1994.
[24] H. Ong, C.P. Schnorr and A. Shamir, “An efficient signature scheme based on quadratic equations,” Proceedings of the 16’th symposium on theory of computing, pp. 208–216, 1984.
[25] J. M. Pollard and C. P. Schnorr, “An efficient solution of the congruence x2 + ky2 = m (mod n)”. IEEE Transactions on Information Theory, 33, pp. 702-709, Sep. 1987.
[26] K.S.J. Pister, J.M. Kahn and B.E. Boser, “Smart Dust: Wireless networks of millimeter-scale sensor nodes,” in 1999 UCB Electronics Research Laboratory Research Summary, 1999.
[27] A. Perrig, R. Canetti, J. Tygar and D. Song, “Efficient authentication and signing of multicast streams over lossy channels”, in IEEE Symposium on Security and Privacy, 2000.
[28] A. Perrig, R. Szewczyk, V. Wen, D. Cullar and J.D. Tygar, “SPINS: Security protocols for sensor networks,” Proceedings of Seventh Ann. ACM/ IEEE Int’l Conf. Mobile Computing and Networking (MobiCom), pp. 189-199, July 2001.
[29] A. Perrig, R. Canetti, D. Song and J.D. Tygar, “Efficient and secure source authentication for multicast”, in Network and Distributed System Security Symposium, NDSS’01, 2001.
[30] C.E. Perkins, Ad Hoc Networking, Addison-Wesley, 2001.
[31] R. L. Rivest, A. Shamir and L. Adleman, “A method of obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, mo. 2, pp. 120-126, Feb. 1978.
[32] M.O. Rabin, “Digitalized signatures and public key functions as intractable as factoring”. Technical Report 212, Laboratory for Computer Science, Cambridge, Mass., 1979.
[33] A. Shamir, “How to share a secret,” Communications of the ACM, vol.22, no.11, pp.612-613, Nov. 1979.
[34] W. Stallings, Cryptography and Network Security: Principles and Practice, Prentice Hall, Upper Saddle River, New Jersey, 1999.
[35] 賴溪松、韓亮、張真誠，近代密碼學及其應用。旗標出版股份有限公司，2004年1月。