臺灣博碩士論文加值系統

廣播加密(broadcast encryption)是一種廣播者可以透過公用網路，廣播被加密的訊息區塊給接收者，只有被授權的接收者才能解出正確訊息的機制。廣播加密除了可以運用於付費電視系統、數位版權管理等系統外，本篇論文就接收者對於所廣播內容需求量的不同，提出一個實現資訊粗細度(information granularity)特性的安全廣播加密機制，來達成接收者不同的需求，也就是安全等級(security clearance level) 越高的接收者可以解出的訊息越多；另外因為異質感測網路(heterogeneous sensor networks)的方便性與可移動性等因素，使得它非常適用在醫療保健遠端病患監控，環境災害的預警，軍事任務的感測與追蹤等應用，在針對某些機密且及時的資訊時，安全群體的溝通(secure group communication)就非常地重要，本論文運用廣播加密的機制，提出一個基於橢圓曲線密碼學(elliptic curve cryptography，ECC)的群組金鑰管理(group key management)機制，建立群組金鑰以達到安全群體溝通的需求。
在本篇論文所提出實現資訊粗細度特性的安全廣播加密機制中，廣播的訊息區塊是由許多的訊息子區塊所組成，廣播者將訊息子區塊及接收者劃分為不同的安全等級，接收者的安全等級越高，所能解出的訊息越多。我們所提出的廣播加密機制具有下述幾個特點：(i) 廣播訊息的資料量與接收者人數和安全等級個數無關；(ii) 每一位接收者只需儲存一把相對應於他/她的安全等級的解密金鑰；(iii) 任何接收者即使與其他接收者共謀，也無法推出比他/她安全等級還高的交談金鑰(session key)；(iv) 任何接收者可以動態地加入/離開本系統，而廣播者無需重新分配(re-key)解密金鑰給現有已授權的接收者。

在本篇論文所提出另一個基於橢圓曲線密碼學，異質感測網路的群組金鑰管理機制中，由於感測節點(sensor node)本身基於電力、記憶體與計算能力等資源有限的因素下，面臨著電力耗盡的挑戰與被敵人破解的威脅，基地台(base station)必需具備有新增與撤銷感測節點的能力，因此為了達到安全群體的溝通，群組金鑰管理是一個很重要的議題。我們所提出的群組金鑰管理機制具有下述幾個特點：(i) 每一個感測節點只需儲存一把秘密金鑰用於推出交談金鑰；(ii) 基地台可以很容易地新增/撤銷感測節點；(iii) 在random oracle model下，我們的機制證明是安全的，並可以抵抗感測節點被捕獲攻擊(node capture attack)與偽造攻擊(masquerade attack)。

A broadcast encryption scheme enables a broadcaster to distribute an encrypted message block to a set of receivers via public network such that only the authorized receivers can decrypt it and recover the message block. In the past decades, broadcast encryption has been successfully deployed to several practical applications, such as the pay-TV systems and the secure multicast systems for distribution of copyrighted materials. In this thesis, we propose a new secure broadcasting scheme realizing the property of “information granularity” to achieve the receivers’ different requirements for the broadcasted message block. That is, a receiver with a higher security clearance level has the natural capability to recover a larger amount of information from the broadcasted message block. On the other hand, heterogeneous sensor networks are plausible in several practical applications, such as remotely monitoring patients for healthcare, pre-alarming environmental disasters, and sensing and tracking military missions due to their convenience and mobility in essence. Secure group communication is one of the important services in heterogeneous sensor networks for efficient transmission and rapid response in the case that certain sensitive or emergent applications are required. For secure group communication in heterogeneous sensor networks, we present an ECC-based group key management scheme in this thesis.

In the proposed new secure broadcasting scheme realizing information granularity, we consider the case that a broadcasted message block consists of a set of disjoint message sub-blocks, and each of the receivers and each of the broadcasted message sub-blocks are respectively associated with a security clearance level pre-defined by the broadcaster. A receiver can recover the broadcasted message sub-blocks if and only if his/her security clearance level is greater than or equal to those of the message sub-blocks. The proposed scheme achieves the following features: (i) the length of the enabling block is independent of the number of receivers and the number of security clearance levels; (ii) each receiver holds only one small fixed-size decryption key corresponding to his/her security clearance level; (iii) it is computationally feasible for any receiver to derive a session key of a lower but never a higher security clearance level, even taking into account collusion with other receivers; (iv) any receiver can dynamically join or leave the system without resolving the re-keying problem for the existing receivers.

In the proposed ECC-based group key management scheme for heterogeneous sensor networks, the sensor nodes face the challenge of power-exhaustion problem caused by running out of battery. They also face the threats of being compromised by adversaries. To resolve the challenges mentioned above, the base station of a heterogeneous sensor network should have the ability to easily handle the case of adding/revoking several sensor nodes in the deployed network if necessary. Thus, group key management is one of the crucial considerations for secure group communication in heterogeneous sensor networks. The proposed scheme achieves the following features: (i) each sensor node only stores one secret key that is used to efficiently derive the session key without extra communication overhead; (ii) as compared to previous work, the proposed scheme can easily handle the case of adding/revoking several sensor nodes in the deployed network if necessary; (iii) the proposed scheme is secure in the random oracle model and resilient against the node capture attack and the masquerade attack.

中文摘要 ii
英文摘要 iv
誌謝 vii
目錄 viii
圖索引 x
表索引 xi
Chapter 1 Introduction 1
Chapter 2 Preliminaries 7
2.1 Elliptic Curve Cryptography 7
2.2 Bilinear Pairing 13
2.3 Complexity Assumptions 14
2.4 Mathematical Backgrounds 16
Chapter 3 Secure Broadcasting Mechanism Realizing Information Granularity 19
3.1 System Model 20
3.2 Proposed Scheme 22
3.3 Security Analysis 27
3.3.1 Security Proof 27
3.3.2 Choices of Parameters 33
3.4 Performance Evaluation 34
Chapter 4 Group Key Management Mechanism for Heterogeneous Sensor Networks 38
4.1 System Model 40
4.2 Proposed Scheme 42
4.3 Security Analysis 48
4.4 Performance Evaluation 52
Chapter 5 Conclusions and Future Work 55
5.1 Conclusions 55
5.2 Further Work 56
Bibliography 57
Biography 67

[AT83]S.G. Akl and P.D. Taylor, “Cryptographic solution to a problem of access control in a hierarchy,” ACM Transactions on Computer Systems, Vol. 1, No. 3, pp. 239-248 (1983).
[BBG05]D. Boneh, X. Boyen, and E.J. Goh, “Hierarchical identity based encryption with constant size ciphertext,” Proceedings of Advances in Cryptology - ?nEUROCRYPT’05, LNCS 3494, pp. 440-456 (2005).
[BF01]D. Boneh and M. Franklin, “Identity-based encryption from the Weil pairing,” Proceedings of Advances in Cryptology - ?nCRYPTO’01, LNCS 2139, pp. 213-229 (2001).
[BGW05]D. Boneh, C. Gentry, and B. Waters, “Collusion resistant broadcast encryption with short ciphertexts and private keys,” Proceedings of Advances in Cryptology - ?nCRYPTO’05, LNCS 3621, pp. 258-275 (2005).
[BKLS02]P.S.L.M. Barreto, H.Y. Kim, B. Lynn, and M. Scott, “Efficient algorithms for pairing-based cryptosystems,” Proceedings of Advances in Cryptology - CRYPTO’02, LNCS 2442, pp. 354-368 (2002).
[BS96]E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1, MIT Press (1996).
[BSL01]D. Boneh, H. Shacham, and B. Lynn, “Short signatures from the Weil pairing,” Proceedings of Advances in Cryptology - AISACRYPT’01, LNCS 2248, pp. 514-532 (2001).

[BSS99]I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series 265, Cambridge University Press (1999).
[C06]J.H. Cheon, “Security analysis of the strong Diffie-Hellman problem,” Proceedings of Advances in Cryptology - ?nEUROCRYPT’06, LNCS 4004, pp. 1-11 (2006).
[CCS08]H.Y. Chien, R.C. Chen, and A. Shen, “Efficient key pre-distribution for sensor nodes with strong connectivity and low storage space,” Proceedings of the 22nd International Conference on Advanced Information Networking and Applications, pp. 327-333 (2008).
[CGIM99]R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, “Multicast security: a taxonomy and some efficient constructions,” Proceedings of IEEE INFOCOM’99, Vol. 2, pp. 708-716 (1999).
[CLH07]J.T. Chung, C.M. Li, and T. Hwang, “All-in-one group-oriented cryptosystem based on bilinear pairing,” Information Sciences, Vol. 177, No. 24, pp. 5651-5663 (2007).
[COP05]H. Chabanne, D.H. Ohan, and D. Pointcheval, “Public traceability in traitor tracing schemes,” Proceedings of Advances in Cryptology - ?nEUROCRYPT’05, LNCS 3494, pp. 542-558 (2005).
[CPD03]H. Chan, A. Perrig, and S. Dong, “Random key predistribution schemes for sensor networks,” Proceedings of IEEE Symposium on Security and Privacy, pp. 197-213 (2003).
[CR09]E. Cayirci and C. Rong, Security in wireless ad hoc and sensor networks, John Wiley & Sons (2009).
[DDHV03]W. Du, J. Deng, Y.S. Han, and P.K. Varshney, “A pairwise key pre-distribution scheme for wireless sensor networks,” Proceedings of the 10th ACM Conference on Computer and Communications Security, pp. 42-51 (2003).
[DGXC09]X. Du, M. Guizani, Y. Xiao, and H.H. Chen, “A routing-driven elliptic curve cryptography based key management scheme for heterogeneous sensor networks”, IEEE Transaction on Wireless Communications, Vol. 8, No. 3, pp. 1223-1229 (2009).
[DL02]E.J. Duarte-Melo and M. Liu, “Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks,” Proceedings of the IEEE Global Telecommunications Conference (Globecom’02), pp. 21-25 (2002).
[DL03]E.J. Duarte-Melo and M. Liu, “Data-gathering wireless sensor networks: organization and capacity,” Computer Networks, Vol. 43, No. 4, pp. 519-537 (2003).
[DPP07]C. Delerablee, P. Paillier, and D. Pointcheval, “Fully collusion secure dynamic broadcast encryption with constant-size ciphertexts or decryption keys,” Proceedings of Pairing’07, pp. 39-59 (2007).
[DXGC07]X. Du, Y. Xiao, M. Guizani, and H.H. Chen, “An efficient key management scheme for heterogeneous sensor networks,” Ad Hoc Networks, Vol. 5, pp. 24-34 (2007).
[EG02]L. Eschenauer and V.D. Gligor, “A key-management scheme for distributed sensor networks,” Proceedings of the 9th ACM Conference on Computer and Communication Security, pp. 41-47 (2002).
[FN94]A. Fiat and M. Naor, “Broadcast encryption,” Proceedings of Advances in Cryptology - ?nCRYPTO’93, LNCS 773, pp. 480-491 (1994).
[GA02]C. Gentry and A. Silverberg, “Hierarchical ID-based cryptography,” Proceedings of Advances in Cryptology – AISACRYPT’02, LNCS 2501, pp. 548-66 (2002).
[GHS02]S.D. Galbraith, K. Harsison, and D. Soldera, “Implementing the Tate pairing”, ANTS, Springer-Verlag 5381, pp. 324-337 (2002).
[GK00]P. Gupta and P.R. Kumar, “The capacity of wireless networks,” IEEE Transaction on Information Theory, Vol. 46, No. 2, pp. 388-404 (2000).
[GPWES04]N.Gura, A. Patel, A. Wander, H. Eberle, and S.C. Shantz, “Comparing Elliptic Curve Cryptography and RSA on 8-bit CUPs,” Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems, pp. 318-324, 2004.
[Her75]I.N. Herstein, Topics in Algebra, Second Edition, Wiley International Editions (1975).
[HC02]J.L. Hill and D.E. Culler, “Mica: A wireless platform for deeply embedded networks”, IEEE Micro, Vol 22, No 6, pp.12-24 (2002).
[HS02]D. Halevy and A. Shamir, “The LSD broadcast encryption scheme,” Proceedings of Advances in Cryptology - ?nCRYPTO’02, LNCS 2442, pp. 47-60 (2002).
[Jou00]A. Joux, “A one round protocol for tripartite Diffie-Hellman,” Proceedings of the 4th Algorithmic Number Theory Symposium, ANTS IV, pp. 385-394 (2000).
[JM97]A. Jurisic and A.J. Menezes, “Elliptic curves and cryptography,” Dr. Dobb's Journal, Vol. 22, No. 4, pp. 26-32 (1997).
[JYFD06]Z. Jun, Z. Yu, M. Fanyuan, G. Dawu, and B. Yingcai, “An extension of secure group communication using key graph,” Information Sciences, Vol. 176, No. 20, pp. 3060-3078 (2006).
[Kob87]N. Koblitz, "Elliptic curve cryptosystems," Mathematics of Computation, Vol. 48, No. 177, pp. 203-209 (1987).
[KMV00]N. Koblitz, A.J. Menezes, and S. Vanstone, “The state of elliptic curve cryptography,” Design, Codes and Cryptography, Vol. 19, No. 2, pp. 173-193 (2000).
[Lin09]H.Y. Lin, “High-Effect Key Management Associated With Secure Data Transmission Approaches in Sensor Networks Using a Hierarchical-based Cluster Elliptic Curve Key Agreement”, Fifth International Joint Conference on INC, IMS and IDC, pp. 308-314 (2009).
[LN08]A. Liu and P. Ning, ”TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks”, Proceedings of the 2008 International Conference on Information Processing in Sensor Networks, pp. 245-256 (2008).
[LS98]M. Luby and J. Staddon, “Combinatorial bounds for broadcast encryption,” Proceedings of Advances in Cryptology - EUROCRYPT’98, LNCS 1403, pp. 512-526 (1998).
[LT08]Y.R. Liu and W.G. Tzeng, “Public key broadcast encryption with low number of keys and constant decryption time,” Proceedings of Public Key Cryptography’08, pp. 380-396 (2008).
[LWZH05]C.Y. Lin, T.C. Wu, F. Zhang, and J.J. Hwang, “New identity-based society oriented signature schemes from pairings on elliptic curves,” Applied Mathematics and Computation, Vol. 160, pp. 245-260 (2005).
[Mil85]V. Miller, “Use of elliptic curves in cryptography,” Proceedings of Advances in Cryptology - CRYPTO’ 85, LNCS 218, pp. 417-426 (1985).
[Mil86]V. Miller, “Short programs for functions on curves,” unpublished manuscript (1986).
[MOV93]A.J. Menezes, T. Okamoto, and S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Transaction on Information Theory, Vol. 39, pp. 1639-1646 (1993).
[MSK02]S. Mitsunari, R. Sakai, and M. Kasahara, “A new traitor tracing,” IEICE Trans. Fundamentals, Vol. E85-A, No. 2, pp. 481-484 (2002).
[MSL03]Y. Mu, W. Susilo, and Y.X. Lin, “Identity-based broadcasting,” Proceedings of Advances in Cryptology - INDOCRYPT’03, LNCS 2904, pp. 177-190 (2003).
[MV01]Y. Mu and V. Varadharajan, “Robust and secure broadcast,” Proceedings of Advances in Cryptology - INDOCRYPT’01, LNCS 2247, pp. 223-231 (2001).
[NAES]NIST FIPS 197, “Advanced Encryption Standard (AES),” National Institute of Standards and Technology, U.S. Department of Commerce (2001).
[NDES]NIST FIPS 46-3, “Data Encryption Standard (DES) specifies the DES and Triple DES algorithms,” National Institute of Standards and Technology, U.S. Department of Commerce (1999).
[NIST06]National Institute of Standards and Technology, “Recommendation for Key Management - Part 1: General (Revised),” NIST Special Publication 800-57, http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf (2006).
[NNL01]D. Naor, M. Naor, and J. Lotspiech, “Revocation and tracing schemes for stateless receivers,” Proceedings of Advances in Cryptology - ?nCRYPTO’01, LNCS 2139, pp. 41-62 (2001).
[OAMD07]L.B. Oliveira, D.F. Aranha, E. Morais, and F. Daguano, “TinyTate: computing the Tate pairing in resource-constrained sensor nodes,” Proceedings of the 6th IEEE International Symposium on Network Computing and Applications (NCA’07), pp. 318-324 (2007).
[ODLD07]L.B. Oliveira, R. Dahab, J. Lopez, F. Daguano, and A. A. F. Loureiro, “Identity-based encryption for sensor networks,” Proceedings of the 5th IEEE International Conference on Pervasive Computing and Communications Workshop (PerComW’07), pp. 290-294 (2007).
[Pol78]J. Pollard, “Monte Carlo methods for index computation mod p,” Mathematics of Computation, Vol. 32, No. 143, pp. 918-924 (1978).
[PH78]S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,” IEEE Transactions on Information Theory, Vol. 24, No. 1, pp. 106-110 (1978).
[PKSL08]J.H. Park, H.J. Kim, M.H. Sung, and D.H. Lee, “Public key broadcast encryption schemes with shorter transmissions,” IEEE Transactions on Broadcasting, Vol. 54, No. 3, pp. 401-411 (2008).
[RNS08]S.M.M. Rahman, N. Nasser, and K. Saleh, “Identity and pairing-based secure key management scheme for heterogeneous sensor networks,” Proceedings of the IEEE International Conference on Wireless & Mobile Computing, Networking & Communication, pp. 423-428 (2008).
[Ros98]M. Rosing, Implementing Elliptic Curve Cryptography, ISBN: 1-884777-69-4 (1998).
[RZL06]K. Ren, K. Zeng, and W. Lou, “A new approach for random key pre-distribution in large scale wireless sensor networks” Wiley Journal of Wireless Communication and Mobile Computing, Vol. 6, Issue 3, pp. 307-318 (2006).
[SK03]R. Song and L. Korba, “Pay-TV system with strong privacy and non-repudiation protection,” IEEE Transactions on Consumer Electronics, Vol. 49, No. 2, pp. 408-413 (2003).
[SM03]A.T. Sherman and D.A. McGrew, “Key establishment in large dynamic groups using one-way function trees,” IEEE Transactions on Software Engineering, Vol. 29, No. 5, pp. 444-458 (2003).
[Vor07]G. Voronoi, “Nouvelles applications des paramètres continus à la théorie des formes quadratiques,” Journal für die Reine und Angewandte Mathematik, Vol. 133, pp. 97-178 (1907).
[W00]A. Wool, “Key management for encrypted broadcast,” ACM Transactions on Information and System Security, Vol. 3, No. 2, pp. 107-134 (2000).
[WGE05]A. Wander, N. Gura, H. Eberle, V. Gupta, and S. Shantz, “Energy analysis of public key cryptography for wireless sensor networks,” Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communication (PerCom’05), pp. 324-328 (2005).
[WHA98]D.M. Wallner, E.J. Harder, and R.C. Agee, “Key Management for Multicast: Issues and Architectures,” Internet Request for Comments 2627, Available: ftp://ftp.ietf.org/rfc/rfc2627.txt (1998).
[XWD09]X. Xiong, D.S. Wong, X. Deng, “TinyPairing: Computing Tate Pairing on Sensor Nodes with Higher Speed and Less Memory”, Eighth IEEE International Symposium on Network Computing and Applications, pp. 187-194 (2009).
[YFDL04]D. Yao, N. Fazio, Y. Dodis, and A. Lysyanskaya, “ID-Based encryption for complex hierarchies with applications to forward security and broadcast encryption,” Proceedings of the 11th ACM conference on Computer and Communications Security, pp. 354-363 (2004).
[YKS05]M. Yarvis, N. Kushalnagar, H. Singh, et al., “Exploiting heterogeneity in sensor networks,” Proceedings of the 24rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05), pp. 878-890 (2005).
[ZK02]F. Zhang and K. Kim, “Id-based blind signature and ring signature from pairings,” Proceedings of Advances in Cryptology - AISACRYPT’02, LNCS 2501, pp. 533-547 (2002).