在電腦與通訊系統中，我們常採用加密的方式來保護資訊或作為限制資料存取的一種手段。加解密的過程中需要使用金鑰，而金鑰的產生與管理，關係著系統的效率及安全。在許多實際應用中，我們需要一種階層式的資料存取機制，依據各人的身分、付費的等級給予不同的存取資料的權限，而階層式金鑰指定演算法 (Hierarchical Key Assignment Scheme) 便是處理這類的問題的重要方法。

在本論文中，我們將對階層式金鑰指定演算法進行一系列深入的探討。我們試著將既有的階層式金鑰指定演算法加以分類，列出它的幾個變形，更重要地，我們將探討它的內在本質，並提出幾個重要的應用。第一章簡介階層式存取控制的問題，同時回顧文獻中關於階層式金鑰指定演算法的一些成果。第二章是階層式金鑰指定演算法的定義及分類。在第三章，我們介紹它的三種變形：具時間範圍的階層式金鑰指定演算法(Time-Bound Hierarchical Key Assignment Scheme)、具時間期限的階層式金鑰指定演算法(Time-Constraint Hierarchical Key Assignment Scheme)、具前向式安全之階層式金鑰指定演算法(Forward-Secure Hierarchical Key Assignment Scheme)。其中，具前向式安全之階層式金鑰指定演算法是我們所提出的一種新的變形。在這一章中除了介紹這三種變形的定義之外，我們還將示範如何將標準型的階層式金鑰指定演算法轉換成符合這三種變形的定義的演算法。

第四章是本論文最重要的貢獻，在這裡我們試著探討階層式金鑰指定演算法的內在本質，我們提出一個新的技術，稱之為融合(merging)。這個技術主要的構想是以原始金鑰(primitive keys)的角度來看待問題，來取代傳統上以階層(hierarchy)為主的思考模式。在觀念上，融合這個技術有點類似壓縮(compression)，利用這個技術，我們可以將數把金鑰融合成一把聚合金鑰(aggregate key)，藉此大幅減少金鑰的傳輸量及所需的儲存空間。基於融合技術，我們提出Akl-Taylor演算法的另一種實作方法，並設計出一個非常有效率的具時間範圍的階層式金鑰指定演算法，我們也利用它來構造一個Akl-Taylor演算法中的階層重整(hierarchy adjusting)法。除此之外，比起傳統上從階層的角度來看問題，我們發現直接採用融合的概念來思考常常會得到更好的解決安案。更重要地，我們指出，若未來可以找到其他適當的融合函數(merging functions)，我們也可以用同樣的方式來獲得新的階層式金鑰指定演算法及具時間範圍的階層式金鑰指定演算法。

第五章及第六章也是本論文的重要貢獻，在這裡我們利用階層式金鑰指定演算法及其變形提出兩個重要的應用。第五章的應用是付費電視系統的存取控制(Access Control of Pay-TV Systems)，傳統上，由於頻寬以及計算速度的限制，付費電視系統中在定期收費(period subscription)的服務中採行按月計費的方式，而且節目的選擇彈性也很有限。在本章中，我們以階層式金鑰指定演算法及其變形為基礎，設計出三個金鑰分配機制，系統供應者(service provider)可以利用這些機制，來提供更有彈性的服務，諸如按日計費、允許客戶訂閱任意組合的頻道等。在第六章，我們結合階層式金鑰指定演算法及簽章演算法(Digital Signature Scheme)，定義了一個新的簽章演算法：階層式簽章演算法(Hierarchical Signature Scheme)。在這裡，我們指出傳統的代理簽章演算法(Proxy Signature Scheme)的缺點，並說明如何從宏觀的角度，利用階層式簽章演算法來進行調控。我們以Mackinnon等人所提出的階層式金鑰指定演算法及GQ簽章演算法為基礎，具體設計了一個階層式簽章演算法，並証明其安全性。

最後，第七章是本論文的結論及未來的方向。

In computer and communication systems, information is often encrypted with keys, because of the sensitivity of information or the necessity of management. Meanwhile, we usually need an efficient key management mechanism to deal with the generations and distributions of keys. In many practical applications, we have to solve the problem of information access control in a hierarchy, in which some users might have larger access privileges than others. The hierarchical key assignment scheme is a solution of such a problem.

In this dissertation, we present an in-depth investigation of the hierarchical key assignment scheme, its variants, its essence, and its applications. Chapter 1 presents an introduction of the problem of hierarchical key assignment and gives a review of related works in the literature. Then, Chapter 2 gives a formal model of the standard hierarchical key assignment scheme and its classifications. Chapter 3 presents the models of three other variants of the hierarchical key assignment schemes: time-bound hierarchical key assignment scheme, time-constrain hierarchical key assignment schemes, and forward-secure hierarchical key assignment scheme, which is a new variant. In addition to the models, we also demonstrate how to use the standard hierarchical key assignment scheme to implement these schemes. Chapter 4 is one of the major contributions of this dissertation. It is a try to explore the essence of the hierarchical key assignment scheme. Here, we propose a new technique, merging. The idea behind merging is to consider primitive keys instead of hierarchies. It is conceptually like the compression used in source coding. Through this technique, it is feasible to combine multiple keys into an aggregate key. Thus, communication and storage requirements are greatly reduced. This technique can also be used for an alternative implementation of Akl-Taylor scheme and a time-bound scheme. Moreover, it can be used to construct a systematic approach for adjusting hierarchies in Akl-Taylor scheme as well. We show that some problems that are usually addressed by the conventional key assignment schemes can be solved directly via merging, with better performance. Furthermore, we point out that, if other suitable merging functions are found in the future, new secure hierarchical key assignment schemes and time-bound schemes will be obtained accordingly.

Chapter 5 and Chapter 6 are also important contributions of this dissertation, where we propose two important applications based on the hierarchical key assignment scheme and its variants. The application in Chapter 5 is the access control of pay-TV systems. Conventionally, due to the restriction of bandwidth and computational capability, most pay-TV systems only supports the period subscription service that is charged on a month basis. Here, based on the concept of hierarchical key assignment and its variants, we propose three key distribution schemes for the access control of pay-TV systems. These schemes support more charging strategies for the service provider, such as a smaller charging unit and allowing the subscription of any subset of channels, with little communication and computational overhead. In Chapter 6, we propose and formalize a new signature scheme, the hierarchical signature scheme, by combining the notions of hierarchical key assignment scheme and digital signature scheme. Here, we point out the delegation issue of the conventional proxy signature schemes, and then illustrate how to deal with it in a global manner with the hierarchical signature scheme. We also point out that the forward-secure signature scheme, in a general sense, may be regarded as one of its special case. Furthermore, we demonstrate a concrete construction of the scheme and analyze its security by a reduction technique. Finally, the conclusion is drawn in Chapter 7.

[AN97] R. Anderson, Invited lecture. Fourth Annual Conference on Computer and Communications Security, ACM, 1997.
[AT83] S.G. Akl and P.D. Taylor, "Cryptographic Solution to a Problem of Access Control in a Hierarchy," ACM Trans. Computer Systems, vol. 1, no. 3, pp. 239-248, 1983.
[BL91] R.E. Blahut, "Principles and Practice of Information Theory," Addison-Wesley, 1991.
[BM99] M. Bellare and S. Miner, "A forward-secure digital signature scheme," Crypto'99, vol. 1666 of LNCS, pp. 431-448. Springer-Verlag, 1999.
[BR96] M. Bellare and P. Rogaway, "The exact security of digital signatures – How to sign with RSA and Rabin," EuroCrypt'96, vol. 1070 of LNCS, pp. 399-416. Springer-Verlag, 1996.
[CC02] T.S. Chen and Y.F. Chung, "Hierarchical access control based on Chinese remainder theorem and symmetric algorithm," Computers & Security, vol. 21, no. 6, pp. 565-570, 2002.
[CGIM99] R. Canetti, J. Garey, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, "Multicast security: A taxonomy and some efficient constructions," Proceedings of IEEE Infocomm'99, vol. 2, pp. 708-716, Mar. 1999.
[CH04] H.Y. Chien, "Efficient Time-Bound Hierarchical Key Assignment Scheme," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 10, pp. 1301-1304, October 2004.
[DAMN86] D.E. Denning, S.G. Akl, M. Morgenstern and P.G. Neumann, "Views for multilevel database security," Proc. 1986 IEEE Symp. on Security and Privacy, Oakland, CA, pp. 156-172, April, 1986.
[DE84] D.E. Denning, "Cryptographic checksums for multilevel database security," Proc. 1984 IEEE Symp. on Security and Privacy, Oakland, CA, pp. 52-61, April 29-May 2, 1984.
[EBU95] EBU Project Group B/CA, "Functional model of a conditional access system", EBU Technical Review, pp. 64-77, Winter 1995.
[ETR289] ETR 289, Digital Video Broadcasting (DVB), "Support for Use of Scrambling and Conditional Access (CA) within Digital Broadcasting Systems," Oct. 1996.
[FIPS197] Advanced Encryption Standard (AES), FIPS 197, Nov. 26, 2001.
[FIPS46] National Institute of Standards and Technology (NIST). FIPS Publication 46-1: Data Encryption Standard. January 22, 1988.
[FN99] A. Fiat and M. Naor, "Broadcast Encryption," CRYPTO'93, LNCS 773, pp. 480-491, Springer-Verlag, 1999.
[FR83] L.J. Fraim, "Scomp: a solution to multilevel security problem," IEEE Computer, pp. 126-143, July 1983.
[FS87] A. Fiat and A. Shamir, "How to prove yourself: Practical solutions to identification and signature problems," Crypto'86, vol. 263 of LNCS, pp. 186-194, Springer-Verlag, 1987.
[GMR88] S. Goldwasser, S. Micali and R. Rivest, "A digital signature scheme secure against adaptive chosen-message attacks," SIAM Journal of Computing, vol. 17, no. 2, pp. 281-308, April 1988.
[GQ90] L.C. Guillou and J.J. Quisquater, "A paradoxical identity-based signature scheme resulting from zero-knowledge," Crypto'88, vol. 403 of LNCS, pp. 216-231. Springer-Verlag, 1990.
[HC04] H.F. Huang and C.C. Chang, "A new cryptographic key assignment scheme with time-constraint access control in a hierarchy," Computer Standards & Interfaces, vol. 26, no. 3, pp. 159-166, 2004.
[HL90] L. Harn and H.Y. Lin, "A Cryptographic Key Generation Scheme for Multilevel Data Security," Computers and Security, vol. 9, no. 6, pp. 539-546, 1990.
[HS03] J. Herranz and G. Sez, "Verifiable secret sharing for general access structures, with application to fully distributed proxy signatures," Proceedings of Financial Cryptography 2003, LNCS. Springer-Verlag, 2003.
[HS04] Y.L. Huang and S. Shieh, "Efficient Key Distribution Schemes for Secure Media Delivery in Pay-TV Systems," IEEE Transactions on Multimedia, Vol. 6, No. 5, pp. 760-769, October 2004.
[HW99] M.S. Hwang, "Extension of CHW Cryptographic Key Assignment Scheme in a Hierarchy," IEE Proc. Comput. Digit. Tech., vol. 146, no. 4, July 1999.
[IR01] G. Itkis and L. Reyzin, "Forward-secure signatures with optimal signing and verifying," Crypto 2001, vol. 2139 of LNCS, pp. 332-354. Springer-Verlag, 2001.
[ITU810] "Conditional-Access Broadcasting Systems," ITU-R Rec. 810, 1992.
[KA01] W. Kanjanarin and T. Amornraksa, "Scrambling and Key Distribution Scheme for Digital Television," Proc. 9th IEEE International Conference on Networks, pp. 140-145, 2001.
[KBLK01] H. Kim, J. Baek, B. Lee, and K. Kim, "Secret computation with secrets for mobile agent using one-time proxy signature," Cryptography and Information Security 2001.
[KN81] D.E. Knuth, "The Art of Computer Programming," vol. 2, Addison-Wesley, Reading, Mass., 1981.
[KPW97] S. Kim, S. Park, and D. Won, "Proxy signatures, revisited," ICICS'97, vol. 1334 of LNCS, pp. 223-232. Springer-Verlag, 1997.
[KSCL99] F.H. Kuo, V.R.L. Shen, T.S. Chen and F. Lai, "Cryptographic key assignment scheme for dynamic access control in a user hierarchy," IEE Proc. Computers & Digital Techniques, vol. 146, no. 5, pp. 235-240, September 1999.
[LA03] S. Lal and A. K. Awasthi, "Proxy blind signature scheme," Cryptology ePrint Archive, Report 2003/072. Available at http://eprint.iacr.org/, 2003.
[LE30] Lehmer, "An Extended Theory of Lucas Functions," Ann. Math., vol. 31, pp. 419-448, 1930.
[LE96] J.W. Lee, "Key distribution and management for conditional access system on DBS," Proc. Int. Conf. Cryptology and Information Security, 1996, pp. 82-86.
[LH91] C.S. Laih and T.L. Hwang, "A Branch Oriented Key Management Solution to Dynamic Access Control in a Hierarchy", IEEE Symposium on Applied Computing, 1991, pp. 422-429.
[LI01] C.H. Lin, "Hierarchical Key Assignment without Public-Key Cryptography," Computers and Security, vol. 20, no. 7, pp. 612-619, 2001.
[LI97] C.H. Lin, "Dynamic key management schemes for access control in a hierarchy," Computer Communications, vol. 20, no. 15, pp. 1381-1385, 1997.
[LS88] W.P. Lu and M.K. Sundareshaan, "A model for multilevel security in computer networks," Proc. 1988 INFCOM, New Orleans, LA, pp. 1095-1104, March 1988.
[LZJ04] B. Liu, W. Zhang, and T. Jiang, "A Scalable Key Distribution Scheme for Conditional Access System in Digital Pay-TV System," IEEE Transactions on Consumer Electronics, Vol. 50, No. 2, pp. 632-637, May 2004.
[MC87] D. McCullough, "Specifications for multi-level security and a hook-up property," Proc. 1987 IEEEE Symp. On Security and Privacy, Oakland, CA, pp. 161-166, April 1987.
[MQ95] B.M. Macq and J.J. Quisquater, "Cryptology for digital TV broadcasting," Proceedings of the IEEE, vol. 83, no. 6, pp. 944-957, June 1995.
[MTMA85] S.J. Mackinnon, P.D. Taylor, H. Meijer, and S.G. Akl, "An Optimal Algorithm for Assigning Cryptographic Keys to Control Access in a Hierarchy," IEEE Trans. Computers, vol. 34, no. 9, pp. 797-802, 1985.
[MUO96] M. Mambo, K. Usuda, and E. Okamoto, "Proxy signatures for delegating signing operation," The 3rd ACM Conference on Computer and Communications Security (CCS), pp. 48-57, ACM, 1996.
[MM86] J. McHugh and A.P. Moore, "A security policy and formal top level specification for a multi-level secure local area network," Proc. 1986 IEEEE Symp. on Security and Privacy, Oakland, CA, pp. 34-39, April 1986.
[NNL01] D. Naor, M. Naor, and J.B. Lotspiech, "Revocation and Tracing Schemes for Stateless Receivers," CRYPTO'01, LNCS 2139, pp. 41-62, 2001.
[OO98] K. Ohta and T. Okamato, "On concrete security treatment of signatures derived from identification," Crypto'98, vol. 1462 of LNCS, pp. 354-369. Springer-Verlag, 1998.
[OTO99] T. Okamoto, M. Tada, and E. Okamoto, "Extended proxy signatures for smart cards," ISW'99, vol. 1729 of LNCS. pp. 247-258, Springer-Verlag, 1999.
[RSA78] R.L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Comm. ACM, vol. 21, no. 2, pp. 120-126, Feb. 1978.
[SA88] R.S. Sandhu, "Cryptographic Implementation of a Tree Hierarchy for Access Control," Information Processing Letters, no. 27, pp. 95-98, 1988.
[SC02] V.R.L. Shen and T.S. Chen, "A novel key management scheme based on discrete logarithms and polynomial interpolations," Computers & Security, vol. 21, no. 2, pp. 164-171, 2002.
[SI91] K. Siil, "Adaptive applications to multilevel secure UNIX systems," Proc. 7th Int. Conf. And Exhibition on Information Security, Brighton, UK, May 1991.
[ST86] R. Stanley, "Enumerative Combinatorics," vol. 1, Wadsworth and Brooks/Cole, 1986.
[SU99] H. M. Sun, "An efficient nonrepudiable threshold proxy signature scheme with known signers," Computer Communications, 22(8), pp. 717-722, 1999.
[TLT99] F.K. Tu, C.S. Laih, and S.H. Toung, "On key distribution management for conditional access system on Pay-TV system," IEEE Transactions on Consumer Electronics, Vol. 45, No. 1, pp. 151-158, February 1999.
[TM05] Q Tang and C.J. Mitchell, "Comments on a cryptographic key assignment scheme," Computer Standards & Interfaces, vol. 27, no. 3, pp. 323-326, March 2005.
[TZ02] W.G. Tzeng, "A Time-Bound Cryptographic Key Assignment Scheme for Access Control in a Hierarchy," IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 1, pp. 182-188, Jan./Feb. 2002.
[TZ06] W.G. Tzeng, "A Secure System for Data Access Based on Anonymous Authentication and Time-Dependent Hierarchical Keys," ASIACCS'06, Taipei, Taiwan, March 21-24, 2006.
[WC01] T.C. Wu and C.C. Chang, "Cryptographic key assignment scheme for hierarchical access control," International Journal of Computer Systems Science and Engineering, vol. 16, no. 1, pp. 25-28, 2001.
[WHA99] D. Wallner, E. Harder, and R. Agee, "Key management for multicast: Issues and architectures," IETF, RFC 2627, 1999.
[WL06] S.Y. Wang, C.S. Laih. "Merging: An Efficient Solution for a Time-Bound Hierarchical Key Assignment Scheme," IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 1, pp. 91-100, January-March, 2006.
[WLB06] S.Y. Wang, C.S. Laih, and B.Y. Yang. "Partially Ordered Signature Schemes," The Third Taiwanese-French Conference on Information Technology: TFIT 2006, Nancy, France, pp. 633-646, March, 2006.
[YI05] X. Yi, "Security of Chien's efficient time-bound hierarchical key assignment scheme," IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 9, pp. 1298-1299, September 2005.
[YY03] X. Yi and Y. Ye, "Security of Tzeng's Time-Bound Key Assignment Scheme for Access Control in a Hierarchy," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 4, pp. 1054-1055, July/August 2003.
[ZH97] K. Zhang, "Threshold proxy signature schemes," Proceedings of 1st International Information Security Workshop, pp. 282-290, 1997.