臺灣博碩士論文加值系統

隨著網際網路的蓬勃發展與資訊設備的普及, 人們慢慢地從傳統交易方式延伸到透過網際網路來進行相關的電子商務活動, 諸如: 購物、拍賣、電子付款等。對商家來說, 透過網際
網路的交易平台來呈現商品資訊, 可以擴展銷售範圍, 打破地區性限制又能減少開店成本。
對於顧客來說, 也可以減少議價和收尋商品的時間成本。因此許多電子商務應用服務也越
來越活耀於網際網路環境中。為了讓電子商務的應用服務持續地蓬勃發展, 其中關鍵因素
是要發展出一個低成本且具有高度安全性的付款系統。
對於顧客來說, 他們會希望電子現金能夠像紙鈔一樣的匿名性, 而且在無法被其他人知道這個電子現金是被誰所擁有的情況下, 也能具有可驗證性, 不被偽造性之安全性。由於網際網路的不安全性, 所傳送的資訊有可能被惡意的攻擊者竄改、偽造、竊聽, 所以對於銀行來說, 他們會希望電子現金方案能夠具有可稽核性、可追蹤性、不可否認性之功能。為了解決這些問題, 有許多的電子現金方案被發表出來。但是這些方案都是假設在單一個銀行的情況下運作且需要依賴一個可信任的第三方機構。而在我們的現實生活中, 存在著許多銀行, 且在網際網路環境下找到一個可信任的第三方是困難的。而仔細地分析近期的相關電子現金方案之後, 也發現一些電子現金方案中仍需要改進的安全和效率問題。為解決上述所有問題本論文提出了一個更有效率且適用於多家銀行的電子現金方案。

With the rapid development of the Internet technology and the use of the information technology, people would change their shopping behavior from the traditional transactions to the e-commerce related activities which is conducted through the Internet environment. Since the Internet environment is not secure, there are many security concerns in the Internet environment. The malicious attacker will try to falsify, forge or eavesdrop the information sent through the network. For the customers, they hope their e-cash can not be stolen, forged to carry out other illegitimate action. Also they do not want the others can learn their true identities from the electronic cash. Thus, to solve these problems, many electronic cash schemes have been proposed. Most of the previous e-cash schemes only have a single bank, and they assumed the customer and the merchant belong to the same bank. However, there are many banks in our real life. For the merchants, they hope the used e-cash can store in their corresponding banks, and the e-cash is able to be verified for its correctness.
In 2008, an electronic cash scheme based on group signatures was proposed. The scheme used the group blind signature scheme based on bilinear pairings and the ID-based group signature scheme to generate an electronic cash for multiple banks. Also the bilinear pairings was used to verify the correctness of the electronic cash in the proposed protocols. However, we find some security problems in the proposed scheme. Also, the cost of communication and computation of the proposed scheme can be improved. In this thesis, we propose an efficient and secure e-cash scheme for multiple banks from bilinear pairings. Our proposed scheme can solve all the wellknown security problems. Also, compared with other related schemes, our proposed scheme provide lower computation and communication cost.

ABSTRACT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
誌謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Contents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Chapter1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter2 Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Bilinear pairings and the underlying assumptions . . . . . . . . . . . 5
2.2 ID-based systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Chen et al.’s new identity-based public key scheme from bilinear
pairings . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Zhang et al.’s short signature scheme in bilinear pairings . . . 7
2.3 Group signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Tan and Liu’s ID-based group signature scheme from bilinear pairings 10
2.5 ID-based group blind signature scheme . . . . . . . . . . . . . . . . . 12
Chapter3 Review of related works . . . . . . . . . . . . . . . . . . . . . 13
3.1 Popescu et al.’s e-cash Scheme . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Review of Popescu et al.’s e-cash Scheme . . . . . . . . . . . . 13
3.1.2 Weaknesses of Popescu et al.’s e-cash scheme . . . . . . . . . . 16
3.2 Wang et al.’s e-cash scheme . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.1 Review of Wang et al.’s e-cash scheme . . . . . . . . . . . . . 17
3.2.2 Weakness of Wang et al.’s e-cash Scheme . . . . . . . . . . . . 22
Chapter4 Our proposed scheme . . . . . . . . . . . . . . . . . . . . . . . 24
4.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 The setup protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 The registration protocol . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 The withdrawal protocol . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 The payment protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.6 The deposit protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.7 The customer tracing protocol . . . . . . . . . . . . . . . . . . . . . . 34
4.8 The revoking protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Chapter5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1.1 Correctness considerations . . . . . . . . . . . . . . . . . . . . 36
5.1.2 Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.1.3 Withstanding double spending . . . . . . . . . . . . . . . . . . 38
5.1.4 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.1.5 Non-repudiability . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.1.6 Tracing function . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Properties comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3 Efficiency analysis and comparison . . . . . . . . . . . . . . . . . . . 44
Chapter6 Conclusions and future works. . . . . . . . . . . . . . . . . . . 52
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

[1] G. Ateniese, J. Camenisch, M. Joye and G. Tsudik, ”A practical and provably
secure coalition-resistant group signature scheme,” Proceedings of 20th Annual
International Cryptology Conference, LNCS, Vol. 1880, Springer Berlag, pp.
255-270, 2000.
[2] A. Boldyreva, ”Threshold signatures, multisignatures and blind signatures
based on the Gap-Diffie-Hellman-group signature scheme,” Proceedings of the
6th International Workshop on Theory and Practice, PKC 2003, LNCS, Vol.
2567, Springer-Verlag, pp. 31-46, 2003.
[3] D. Boneh, B. Lynn, and H. Shacham, ”Short signatures from the Weil pairing,”
Proceedings of 7th International Conference on the Theory and Application of
Cryptology and Information Security, ASIACRYPT 2001, LNCS, Vol. 2248,
Springer, pp. 514-532, 2001.
[4] C. Boyd, ”Digital multisignature,” Proceedings of Conference on Coding and
Cryptography, Cirencester, pp. 15-17, 1986.
[5] S. Brands, ”An efficient off-line electronic cash system based on the representation
problem,” Technical Report: CS-R9323, CWI, 1993.
[6] E. Brickell, P. Gemmell, andD. Kravitz. ”Trustee-based tracing extensions to
anonymous cash and the making of anonymous change,” Proceedings of the 6th
Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, pp. 457-466, 1995.
[7] J. Camenisch and M. Michels, ”A group signature scheme based on an RSAvariant,”
BRICS Technical Report in Cryptology, RS-98-27, 1998.
[8] J. Camenisch and M. Stadler, ”Efficient group signature schemes for large
groups,” Proceedings of 17th Annual International Cryptology Conference,
Crypto 1997, LNCS, Vol. 1294, Springer Berlag, pp. 410-424, 1997.
[9] S. Canard and A. Gouget, ”Divisible e-cash systems can be truly anonymous,”
Proceedings of 26th Annual International Conference on the Theory and Applications
of Cryptographic Techniques, EUROCRYPT 2007, LNCS, Vol. 4515,
Springer Verlag, pp. 482-497, 2007.
[10] S. Canard and J. Traor’e, ”On fair e-cash systems based on group signatures,”
Proceedings of 8th Australasian Conference, ACISP 2003, LNCS, Vol. 2727,
Springer Verlag, pp. 237-248, 2003.
[11] C. Castelluccia, ”How to convert any ID-based signature scheme into a group
signature scheme,” Cryptology ePrint Archive, Report 116, 2002.
[12] D. Chaum, ”Blind signature for untraceable payments,” Proceedings of Crypto
on Advances in Cryptology, Springer Verlag, pp. 199-203, 1983.
[13] D. Chaum and E. V. Heyst, ”Group signatures,” Proceedings of Eurocrypt
1991, LNCS, Vol. 547, Springer Verlag, pp. 257-265, 1991.
[14] L. Chen and C. J. Mitchell, ”An anonymous and undeniable payment scheme,”
Proceedings of First International Conference, ICIS ’97, Vol. 1334, Springer
Berlag, pp. 478-482, 1997.
[15] X. Chen, F. Zhang and K. Kim, ”New ID-based group signature from pairings,”
Journal of Electronics (China), Vol. 23, Science Press, co-published with
Springer-Verlag, pp. 892-900, 2006.
[16] J.S. Chou, Y. Chen, M.H. Cho, H.-M. Sun, ”A novel id-based electronic cash
system from pairings,” Cryptology ePrint Archive, Report 2009/339.
[17] S.S.M. Chow, L.C.K. Hui, S.M. Yiu, and K.P. Chow, ”Two improved partially
blind signature schemes from bilinear pairings,” Proceedings of 10th Australasian
Conference on Information Security and Privacy, ACISP 2005, LNCS,
vol. 3574, Springer Verlag, pp. 316-328, 2005.
[18] G. Cui, J. Zhu and S, Zhou, ”A group signature scheme with multiple strategies
from bilinear pairings,” First International Workshop on Education Technology
and Computer Science, ETCS ’09, Vol. 3, pp. 848-852, 2009.
[19] Y. Frankel, Y. Tsiounis and M. Yung, ”Indirect discourse proofs: achieving
efficient fair off-line e-cash,” Proceedings of International Conference on the
Theory and Applications of Cryptology and Information Security, ASIACRYPT
’96, LNCS, Vol. 1163, Springer Verlag, pp. 286-300, 1996.
[20] F. Hess, ”Efficient identity based signature schemes based on pairings,” 9th
Annual International Workshop on Selected Areas in Cryptography, LNCS,
Vol. 2595, Springer Verlag, pp. 310-324, 2003.
[21] I. R. Jeong and D. H. Lee, ”Anonymity control in multi-bank e-cash system,”
Proceedings of First International Conference in Cryptology, LNCS, Vol. 1977,
Springer-Verlag, pp. 104-106, 2000.
[22] Z. Li, J. Higgins, M. Clement, ”Performance of finite field arithmetic in an elliptic
curve cryptosystem,” Ninth IEEE International Symposium on Modeling,
Analysis, and Simulation of Computer and Telecommunications Systems, pp.
249-256, 2001.
[23] A. Lysyanskaya and Z. Ramzan, ”Group blind digital signatures: a scalable
solution to electronic cash,” Proceedings of Second International Conference,
FC ’98, LNCS, Vol. 1465, Springer Berlag, pp. 184-197, 1998.
[24] G. Maitland and C. Boyd, ”Fair electronic cash based on a group signature
scheme,” Proceedings of Third International Conference, ICICS 2001, Vol. 2229,
Springer Berlag, pp. 461-465, 2001.
[25] W. Mao and C.H. Lim, ”Cryptanalysis in prime order subgroups of Z∗
n,” Proceedings
of International Conference on the Theory and Application of Cryptology
and Information Security, Asiacrypt 1998, LNCS, Vol. 1514, Springer
Verlag, pp. 214-226, 1998.
[26] S. Park, S. Kim and D.Won, ”ID-based group signature,” Electronics Letters,
Vol. 33(19), pp. 1616-1617, 1997.
[27] C. Popescu, ”An off-line electronic cash system with revocable anonymity,”
Proceedings of the 12th IEEE Mediterranean on Electrotechnical Conference,
Vol.2, pp. 763-767, 2004.
[28] C. Popescu, H. Oros, ”An off-line electronic cash system based on bilinear pairings,”
14th International Workshop on Systems, Signals and Image Processing,
pp. 438-440, 2007.
[29] W. Qiu, K. Chen and D. Gu, ”A new offline privacy protecting e-cash system
with revokable anonymity,” Proceedings of 5th International Conference on
Information Security, ISC 2002, LNCS, Vol. 2433, Springer Verlag, pp. 177-
190, 2002.
[30] M. Stadler, M.M. Piveteau and J. Camenisch. ”Fair blind signatures,” International
Conference on the Theory and Application of Cryptographic Techniques,
EUROCRYPT ’95, LNCS, Vol. 921, Springer Verlag, pp. 209-219, 1995.
[31] A. Shamir, ”Identity-based cryptosystems and signature schemes,” Proceedings
of CRYPTO’ 84, LNCS, Vol. 196, Springer Verlag New York, pp. 47-53, 1985.
[32] S. von Solms and D. Naccache, ”On blind signatures and perfect crimes,” Computers
and Security, Vol. 11, Elsevier, pp. 581-583, 1992.
[33] Y. Su, Y. Zhu, ”A fair off-line e-cash system with group signature,” Wuhan
University Journal of Natural Sciences ,Vol. 9, Wuhan University, co-published
with Springer, pp. 745-748, 2004.
[34] Z. W. Tan and Z. J. Liu, ”A novel identity-based group signature scheme from
bilinear maps,” http://www.mmrc.iss.ac.cn/pub/mm22.pdf/17.pdf, 2003.
[35] J. Traor’e, ”Group signatures and their relevance to privacy-protecting offline
electronic cash systems,” 4th Australasian Conference, ACISP’99, LNCS, Vol.
1587, Springer Verlag, pp. 228-243, 1999.
[36] C. Wang, Q. Li and X. Yang, ”A fair and transferable off-line electronic cash
system with multiple banks,” IEEE International Conference on e-Business Engineering,
pp. 189-194, 2007.
[37] S. Wang, Z. Chen, X. Wang, ”A new certificateless electronic cash scheme with
multiple banks based on group signatures,” 2008 International Symposium on
Electronic Commerce and Security, pp. 362-366, 2008.
[38] G. S. Xu, Y. X. Yang, L. Z. Gu, X. X. Niu, ”ID-based multi-proxy sequential signature
system from bilinear pairing,” Proceedings of the 2007 IEEE/WIC/ACM
International Conferences on Web Intelligence and Intelligent Agent Technology,
pp. 315-318, 2007.
[39] F. Zhang and K. Kim, ”Efficient ID-based blind signature and proxy signature
from bilinear pairings,” Proceedings of 8th Australasian Conference on Information
Security and Privacy, LNCS, Vol. 2727, Springer Berlag, pp. 218-219,
2003.
[40] F. Zhang, R. Safavi-Naini and W. Susilo, ”An efficient signature scheme from
bilinear pairings and its applications,” Proceedings of 7th International Workshop
on Theory and Practice in Public Key Cryptography, LNCS, Vol. 2947,
Springer Verlog, pp. 277-290, 2004.
[41] F. Zhang, F. Zhang and Yumin Wang, ”Electronic cash system with multiple
banks,” Chinese Journal of Computers, Vol. 24(5), pp. 455-462, 2001.
[42] F. Zhang, C.Wang and Y.Wang, ”A new anonymity controlled e-cash scheme,”,
Journal of Electronics (China), Vol. 19, Springer-Verlag, pp. 369-374, 2002.
[43] J. Zhong and D. He, ”A new type of group blind signature scheme based on
bilinear pairings,” http://eprint.iacr.org/2006/439.pdf, 2006.
[44] M. Zhong, ”A faster single-term divisible electronic cash: ZCash,” Electronic
Commerce Research and Applications, Vol. 1, Elsevier, pp. 331-338, 2002.