臺灣博碩士論文加值系統

近年來，雙線性函數已經成為密碼技術發展之重要工具之一，雙線性函數在密碼技術上之發展可分為兩大類，分別為身分碼與非身分碼之密碼技術。在本論文中，我們提出數個植基於雙線性函數之數位簽章協定並發展其應用。
本論文中，我們提出之簽章協定包含了身分碼簽章、身分碼多人簽章、身分碼聚集簽章以及盲簽章等協定，並進一步將所設計之盲簽章延伸為可驗證加密盲簽章及聚集盲簽章之形式。本論文中所提出之身分碼簽章協定適用於計算能力較低之設備上，例如：行動裝置。而文中提出之身分碼聚集簽章協定所需之雙性線函數運算次數不相依於參與之簽章者人數，故大幅降低了整個協定所需之運算量。
在應用方面，我們將所提出之盲簽章應用於電子現金系統中，加上可驗證加密盲簽章，此電子現金系統在交易過程中，顧客與商家即可各取所需、公平地完成交易，此外，銀行可利用聚集盲簽章有效地節省其資料庫之儲存空間，每隔一段時間，銀行將商家兌現後之電子錢的簽章聚集為一個單一的簽章，此簽章長度等同於原本之單一簽章，此舉能有效地節省銀行資料庫之儲存空間。
此外，我們也利用聚集簽章來設計能保障簽署者隱私之契約簽署協定，並利用可驗證之加密簽章達到提升此契約簽署協定之可靠性，以降低對可信任之第三者的信任程度，及防範其可能之舞弊行為。

In recent years, bilinear pairing has been one of the important tools of cryptography. Since the computational costs of pairing operation take the most part, we need to reduce the number of pairing operations as few as possible. In this thesis, we proposed several PKI-based signature schemes and ID-based signature schemes from bilinear pairings with fewer pairing operations. We further developed several applications on e-commerce.
In the basic building blocks, we proposed an ID-based signature scheme, an ID-based multisignature scheme and an ID-based aggregate signature scheme. Our ID-based signature and multisignature schemes are suitable for the devices with low computational ability. Moreover, our ID-based aggregate signature is more efficient than the previous works since the number of pairing operations of our scheme is independent of the number of signers. Furthermore, we proposed a PKI-based blind signature scheme from bilinear pairings, and extended it to be a verifiable encrypted blind signature and an aggregate blind signature.
In application, we apply the proposed blind signature to electronic-cash system. By utilizing verifiable encrypted blind signature, the customer and merchant can take what they needs in payment phase. Further, the bank can save the space of its database effectively by aggregating the valid electronic coins as the aggregate blind signature. Additionally, we also proposed an efficient contract signing protocol with off-line STTP using the aggregate signature proposed by Boneh and Gentry. The use of aggregate signature and bilinear pairings will effectually promote system reliability.

摘要 i
ABSTRACT ii
誌謝 iv
Contents v
List of Figures viii
List of Tables ix
Chapter 1 . Introduction 1
1.1 Introduction of Bilinear Pairing 1
1.2 Motivation 3
1.2.1 Signature Schemes Based on Bilinear Pairings 4
1.2.2 Applications 6
1.3 Organization of This Thesis 7
Chapter 2 . Overview 8
2.1 Bilinear pairing 8
2.2 Mathematical Problems in Bilinear Pairing 9
2.3 Literature Review 11
2.3.1 Boneh et al.’s Aggregate and Verifiable Encrypted Signatures 11
2.3.2 Hess’s ID-based signature scheme 13
2.3.3 Paterson’s ID-based signature scheme 14
2.3.4 Yi’s ID-based signature scheme 15
2.3.5 Cha and Cheon’s ID-based signature scheme 17
2.3.6 Cheng et al.’s ID-based signature scheme 18
Chapter 3 . Basic Building Blocks 20
3.1 ID-based Signature Scheme 21
3.2 ID-based Multisignature Scheme 23
3.3 ID-based Aggregate Signature Scheme 25
3.4 Blind Signature 28
3.5 Variations of the Basic Blind Signature 30
3.5.1 Aggregate Blind Signature 31
3.5.2 Verifiable Encrypted Blind Signature 31
3.6 Performance analysis 32
3.7 Security analysis 37
3.7.1 Signature and Multisignature 37
3.7.2 Aggregate Signature 38
3.7.3 Basic Blind Signature: 38
3.7.4 Aggregate Blind Signature 39
3.7.5 Verifiable Encrypted Blind Signature 40
Chapter 4 . Applications 41
4.1 An Efficient Contract Signing Protocol 41
4.1.1 Basic Model 44
4.1.2 Security Issues 47
4.1.3 Protocol Construction 49
4.1.4 The Contract Signing Protocol with Signers’ privacy 51
4.1.5 Reliability Consideration 53
4.1.6 Shared Verifiable Encrypted Signature 54
4.1.7 Performance Analysis 57
4.2 E-Cash System with Fair Payment 58
4.2.1 The Proposed E-Cash System 59
4.2.2 Performance analysis 66
4.2.3 Security Analysis 67
Chapter 5 . Conclusions and Future Researches 69
Reference 71
Appendix. MSBHS 76

[1] N. Asokan, V. Shoup, and M. Waidner, "Optimistic fair exchange of digital signature," IEEE Journal on Selected Areas in Communications, vol. 18, pp. 591-610, 2000.
[2] M. Blum, "How to exchange (secret) keys," ACM Transactions on Computer System, vol. 1, no. 2, pp. 175-193, 1983.
[3] F. Bao, R. H. Deng, and W. Mao, "Efficient and practical fair exchange protocols with off-line TTP," 1998 IEEE Symposium on Security and Privacy, IEEE Computer Press, 1998, pp. 77-85.
[4] A. Boldyreva, "Efficient Threshold Signature, Multisignature and Blind Signature Schemes Based on the Gap-Diffie-Hellman-Group Signature Scheme," PKC 2003, Lecture Notes in Computer Science, vol. 2136, pp. 31-46, 2003.
[5] D. Boneh and X. Boyen, "Secure identity based encryption without random oracles," Advances in Cryptology - CRYPTO '04, Lecture Notes in Computer Science, vol. 3152, pp. 443-459, 2004.
[6] D. Boneh, X. Boyen, and H. Shacham, "Short Group Signature," Advances in Cryptology - CRYPTO '04, Lecture Notes in Computer Science, vol. 3152, pp. 41-55, 2004.
[7] D. Boneh and M. Franklin, "Identity-based encryption from the Weil pairing," Advances in Cryptology - CRYPTO '04, Lecture Notes in Computer Science, vol. 2139, pp. 213-229, 2001.
[8] D. Boneh, X. Boyen, and E.-J. Goh, "Hierarchical Identity Based Encryption with Constant Size Ciphertext," Advances in Cryptology - EURPCRYPT '05, Lecture Notes in Computer Science, pp. 440-456, 2005.
[9] D. Boneh, C. Gentry, B. Lynn, and H. Shacham, "Aggregate and verifiably encrypted signature from bilinear maps," Advances in Cryptology - EURPCRYPT '03, Lecture Notes in Computer Science, vol. 2656, pp. 416-432, 2003.
[10] C. Boyd and E. Foo, "Off-line fair payment protocols using convertible signature," Advances in Cryptology - ASIACRYPT'98, Lecture Notes in Computer Science, vol. 1514, pp. 271-285, 1998.
[11] J. C. Cha and J. H. Cheon, "An Identity-Based Signature from Gap Diffie-Hellman Groups," In Practice and Theory in Public Key Cryptography ?PKC'2003, Lecture Notes on Computer Science (LNCS) 2567, 2003, pp. 18-30.

[12] D. Chaum, "Blind signatures for untraceable payments," Advances in Cryptology - CRYPTO '82, 1983, pp. 199-203.
[13] L. Chen, "Efficient fair exchange with verifiable confirmation of signatures," Advances in Cryptology - ASIACRYPT '98, Lecture Notes in Computer Science, vol. 1514, pp. 286-299, 1998.
[14] X. Chen, F. Zhang, and K. Kim, "A New ID-based Group Signature Scheme from Bilinear Pairings," Proceedings of WISA'2003, August 2003, Jeju Island(KR), 2003, pp. 585-592.
[15] X. Cheng, J. Liu, and X. Wang, "An identity-based signature and its threshold version,", 1 ed Advanced Information Networking and Applications, 2005. AINA 2005. 19th International Conference, 2005, pp. 973-977.
[16] S. S. M. Chow, L. C. K. Hui, S. M. Yiu, and K. P. Chow, "Two Improved Partially Blind Signature Schemes from Bilinear Pairings," Cryptology ePrint Archive 2004/108, 2004.
[17] R. H. Deng, L. Gong, A. A. Lazar, and W. Wang, "Practical protocol for certified electronic mail," Journal of Network and Systems Management, vol. 4, no. 3, pp. 279-297, 1996.
[18] E. Even, O. goldreich, and A. Lempel, "A randomized protocol for signing contracts," CACM, vol. 28, no. 6, pp. 637-647, 1985.
[19] M. K. Franklin and M. K. Reiter, "Fair exchange with a semi-trusted third party," 4th ACM Conference on Computer and Communications Security, 1997, pp. 1-5.
[20] G. Frey and H. Ruck, "A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves," Mathematics of Computation, vol. 62, pp. 865-874, 1994.
[21] J. Furukawa and H. Imai, "An Efficient Group Signature Scheme from Bilinear Maps," Proceedings of Information Security and Privacy: 10th Australasian Conference, ACISP 2005, Brisbane, Australia, July 4-6, 2005, 2005, pp. 455-467.
[22] J. A. Garay, M. Jakobsson, and P. MacKenzie, "Abuse-free optimistic contract signing," Advances in Cryptology - CRYPTO '99, Lecture Notes in Computer Science, vol. 1666, pp. 449-466, 1999.
[23] C. Gentry and A. Silverberg, "Hierarchical ID-Based Cryptography," Advance in Cryptology - ASIACRYPT '02, Lecture Notes in Computer Science, vol. 2501, pp. 548-566, 2002.
[24] L. Gong, "Increasing availability and security of an authentication service," IEEE Journal on Selected Areas in Communications, vol. 11, no. 5, pp. 657-662, 1993.
[25] F. Hess, "Efficient identity based signature schemes based on pairings," Selected Areas in Cryptography: 9th Annual International Workshop, SAC 2002, Lecture Notes in Computer Science, vol. 2595, pp. 310-324, 2002.
[26] J. Horwitz and B. Lynn, "Toward Hierarchical Identity-Based Encryption," Advances in Cryptology - EURPCRYPT '02, Lecture Notes in Computer Science, vol. 2332, pp. 466-481, 2002.
[27] A. Joux, "A one-round protocol for tripartite Diffie-Hellman," Algorithm Number Theory Symposium (ANTS IV), Lecture Notes in Computer Science, vol. 1838, pp. 385-394, 2000.
[28] N. Lan and S.-N. Rei, "Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings," Asiacrypte '04, 2004, pp. 372-386.
[29] M. Lee, G. Ahn, J. Kim, and J. Park, "Design and Implementation of an Efficient Fair Off-line E-Cash System based on Elliptic Curve Discrete Logarithm Problem," Journal of Communication and Networks, vol. 4, no. 2, pp. 81-89, 2002.
[30] A. Menezes, T. Okamoto, and S. Vanstone, "Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field," IEEE Transactions on Information Theory, vol. 39, pp. 1639-1646, 1993.
[31] D. Nalla and K. C. Reddy, "Signcryption scheme for Identity-based Cryptosystems," Cryptology ePrint Archive, Report 2003/044,2003.
[32] T. Nakanishi, F. Kubooka, N. Hamada, and N. Funabiki, "Group Signature Schemes with Membership Revocation for Large Groups," Information Security and Privacy: 10th Australasian Conference, ACISP 2005, Brisbane, Australia, July 4-6, 2005, 2005, pp. 443-454.
[33] T. Okamoto and K. Ohta, "How to simultaneously exchange secrets by general assumption," 2nd ACM Conference on Computer and Communications Security, 1994, pp. 184-192.
[34] K. G. Paterson, "ID-based signatures from pairings on elliptic curves," Electronic Letters, vol. 38, no. 18, pp. 1025-1026, 2002.
[35] A. Shamir, "Identity-based cryptosystems and signature schemes," Advances in Cryptology - CRYPTO '84, Lecture Notes in Computer Science, vol. 196, pp. 47-53, 1984.
[36] M. Stadler, "Publicly verifiable secret sharing," Advances in Cryptology - EURPCRYPT '96, Lecture Notes in Computer Science, vol. 1070, pp. 190-199, 1996.
[37] M. Scott, "Faster Identity Based Encryption," Electronic Letters, vol. 40, no. 14, p. 864, 2004.
[38] Z.-W. Tan and Z.-J. Liu, "A Novel Identity-based Group Signature Scheme from Bilinear Maps," MM Research Preprint,2003.
[39] V. K. Wei, T. H. Yuen, and F. Zhang, "Group Signature Where Group Manager, Members and Open Authority Are Identity-Based," Information Security and Privacy: 10th Australasian Conference, ACISP 2005, Brisbane, Australia, 2005, pp. 468-480.
[40] X. Yi, "An identity-based signature scheme from the Weil pairing," IEEE Communication Letters, vol. 7, no. 2, pp. 76-78, 2003.
[41] F. Zhang and K. Kim, "ID-based blind signature and ring signature from pairings," Advance in Cryptology - ASIACRYPT '02, Lecture Notes in Computer Science, pp. 533-547, 2002.
[42] F. Zhang and R. Safavi-Naini, "An efficient signature scheme from bilinear pairings and its applications," In Public Key Cryptology 2004, Lecture Notes in Computer Science, vol. 2947, pp. 277-290, 2004.
[43] F. Zhang and K. Kim, "Efficient ID-Based Blind Signature and Proxy Signature from Bilinear Pairings," 8thAustralasian Conference on Information Security and Privacy - ACISP'2003, Lecture Notes in Computer Science, vol. 2727, pp. 312-323, 2003.
[44] Y. Zhu and D. Xu, "An Efficient Key-Evolving Signature Scheme Based on Pairing," 10th IEEE International Workshop on Future Trends of Distributed Computing Systems (FTDCS'04), 2004, pp. 68-73.
[45] J. Zhou and D. Gollmann, "A fair non-repudiation protocol," In Proceedings of the 1996 IEEE Symposium on Security and Privacy, IEEE Computer Press, 1996, pp. 55-61.
[46] J. Zhou and D. Gollmann, "An efficient non-repudiation protocol," In Proceedings of the 1997 IEEE Computer Security Foundations Workshop (CSFW 10), 1997, pp. 126-132.