臺灣博碩士論文加值系統

隨著網際網路的迅速成長，促進電子商務的蓬勃發展，電子付費系統已是電
子商務中相當重要的議題。消費者能夠藉由電子錢幣向網路商家購買任何的服務
或商品，而大部分電子付費系統採用單向雜湊鏈 (one-way hash chain) 的方式形
成電子錢幣鏈，讓消費者能夠便捷的儲存與支付金錢。
雖然採用單向雜湊鏈的方式減少公開金鑰密碼系統的使用，得以提升整體的
運作效率，但是，在雜湊鏈長度過長時，所獲得計算方面之效益將會下降。如此
一來，對於計算能力不高的行動裝置或智慧卡 (smart card) 難以負擔最差的狀況
(worst case)。在我們的研究過程中，發現Jutla 等人提出的樹狀電子付費系統於
最差狀況下更加嚴重。而我們藉由改善Jutla 等人的方法並採用Coppersmith 等人
在鏈狀結構上提出的墊腳石(pebble)與分攤式(amortization)的概念，設計一個於樹
狀架構下的計算分攤式之系統，能夠大幅降低最差狀況，使得用戶端每次付費所
需之計算量能讓智慧卡得以負擔。
目前大多數的電子付費系統，雜湊連長度隨著電子錢幣數量而提升，造成用
戶端於每次付費時之計算需求增加，但對於商家方面卻不會帶來任何影響。一般
而言，商家之系統效能應優於用戶端之行動裝置或智慧卡。為此，我們轉嫁部分
負擔於商家，提出一個消弭此種不平衡現象之付費系統，使得智慧卡於付費時能
獲得一些便利，對於商家與銀行方面亦能夠容易地儲存所需要的資料。

The rapid growth of Internet promotes electronic commerce development. Micro-
payment system is an important issue in electronic commerce. Customer can spend
the electronic coin to vendor for services or goods by the Internet. However, most
of micropayment systems apply a technique, one-way hash chain, to produce an
electronic coin chain that makes customer could spend and store it easily.
Applying one-way hash chain reduces the usage of public key cryptography and
raises the eciency, but the benets will be decreased while the length of chain is
pretty long. However, the worst case is dicult to limited portable devices, such as
smart card, to compute it immediately. In this paper, we point out Jutla et al.'s
scheme which is dicult to smart card to aord the worst case while the amount of
money is large. Furthermore, we improve Jutla et al.'s scheme and adopt the concept
of pebble and amortization in chain structure that Coppersmith et al.'s mentioned to
propose an amortized tree-based micropayment scheme called Amortized One-way
Binary Tree (AOBT), which amortizes whole computational complexity to each coin
and decreases the worst case substantially. The amortization promotes the practi-
cability of payment system.
In most of micropayment systems, the length of chain is increased according to
the amount of electronic money. Customer has to aord this additional cost while
the length is increased, but vendor does not. Generally, vendor's computation and
storage abilities are better than customer's. This is unbalanced cost between cus-
tomer and vendor. Therefore, we transfer some costs from customer to vendor and
proposed PayConst scheme which makes customer get some benets while paying
coin. Besides, vendor and bank can release some unnecessary memory space for
saving the storage resources.

1 Introduction 1
1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminary 6
2.1 The Model of Micropayment System . . . . . . . . . . . . . . . . . . 6
2.2 Requirements of Micropayment System . . . . . . . . . . . . . . . . . 7
2.3 Hash Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Hash Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Hash Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Related Work 15
3.1 Review of PayWord . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Introduction to PayWord . . . . . . . . . . . . . . . . . . . . . 15
3.1.2 Protocol of PayWord . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.3 Remarks on PayWord . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Review of PayTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.1 Introduction to PayTree . . . . . . . . . . . . . . . . . . . . . 17
3.2.2 Remarks on PayTree . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Review of Unbalanced One-way Binary Tree . . . . . . . . . . . . . . 20
3.4 Review of Almost Optimal Hash Sequence . . . . . . . . . . . . . . . 23
4 Proposed Amortized One-way Binary Tree (AOBT) 27
4.1 Amortized Full Binary Tree (AFBT with disadvantage) . . . . . . . . 28
4.1.1 Rules of Amortization . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Construction of Amortized One-way Binary Tree (AOBT) . . . . . . 31
4.3 Micropayment Based on AOBT . . . . . . . . . . . . . . . . . . . . . 32
4.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5.1 Computational Analysis . . . . . . . . . . . . . . . . . . . . . 34
4.5.2 Storage Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Proposed PayConst Scheme 38
5.1 Protocol of PayConst . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.4.1 Computational Analysis . . . . . . . . . . . . . . . . . . . . . 44
5.4.2 Storage Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 44
6 Conclusions 47
6.1 Brief Review of Main Contributions . . . . . . . . . . . . . . . . . . . 47
6.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Bibliography 50

[1] R. Anderson, H. Manifavas, and C. Sutherland, \Netcard: A Practical Elec-
tronic Cash System," Proc. of 4th Cambridge Workshop on Security Protocols,
LNCS vol. 1189, pp. 49-57, 1996.
[2] M. Bellare, J. Garay, R. Hauser, A. Herzberg, H. Krawczyk, M. Steinter, G.
Tsudik, and M. Waidner, \iKP Family of Secure Electronic Payment Proto-
cols," Proc. of 1st USENIX Workshop on Electronic Commerce, pp. 89-106,
1995.
[3] J. Balasch, B. Ege, T. Eisenbarth, B. Grard, Z. Gong, T. Gneysu, S. Heyse, S.
Kerckhof, F. Koeune, T. Plos, T. Pppelmann, F. Regazzoni, F.X. Standaert,
G. Van Assche, R. Van Keer, L. Van Oldeneel Tot Oldenzeel, I. Von Maurich,
\Compact Implementation and Performance Evaluation of Hash Functions in
ATtiny Devices," Smart Card Research and Advanced Application Conference
{ CARDIS '12, LNCS vol. 7771,pp. 158-172, 2013.
[4] D. Coppersmith, M. Jakobsson, \Almost Optimal Hash Sequence Traversal,"
Proc. of 6th International Conference on Financial Cryptography { FC '02,
LNCS vol. 2357, pp. 102-119, 2003.
[5] L. Chen, X. Li, and M. Shi, \A Novel Micro-payment Scheme for M-commerce
Based on Self-renewal Hash Chains," Proc. of International Conference on
Communications, Circuits, and Systems, pp. 1343-1346, 2007.
[6] A. Esmaeeli, M. Shajari, \MVPayword: Secure and Ecient Payword-Based
Micropayment Scheme," Proc. of 2nd International Conference on the Applica-
tion of Digital Information and Web Technologies { ICADIWT '09, pp. 609-614,
2009.
[7] N.M. Haller, \The S/KEY One-time Password System," Proc. of Symposium
on Network and Distributed System Security, pp. 151-157, 1994.
[8] M.S. Hwang, I.C. Lin, and L.H. Li, \A Simple Micropayment Scheme," The
Journal of Systems and Software, vol. 55, pp. 221-229, 2001.
[9] M.S. Hwang, P.C. Sung, \A Study of Micropayment Based on One-way Hash
Chain," International Journal of Network Security, vol. 2, no. 2, pp. 81-90,
2006.
[10] M. Hosseinkhani, E. Tarameshloo, and M. Shajari, \AMVPayword: Secure
and Ecient Anonymous Payword-Based Micropayment Scheme," Interna-
tional Conference on Computational Intelligence and Security { CIS '10, pp.
551-555, 2010.
[11] A. P. Isern-Deya, M. M. Payeras-Capella, M. Mut-Puigserver, and J. L. Ferrer-
Gomila, \Untraceable, Anonymous and Fair Micropayment Scheme," Proc. of
9th International Conference on Advances in Mobile Computing and Multimedia
{ MoMM '11, pp. 42-49, 2011.
[12] C. Jutla, M. Yung, \PayTree: \Amortized-Signature" for Flexible Micropay-
ments," Proc. of 2nd USENIX Workshop on Electronic Commerce, pp. 213-221,
1996.
[13] M. Jakobsson, \Fractal Hash Sequence Representation and Traversal," Proc. of
IEEE International Symposium on Information Theory { ISIT '02, pp. 437-444,
2002.
[14] S. Kim, W. Lee, \A PayWord-based Micropayment Protocol Supporting Mul-
tiple Payments," Proc. of 12th International Conference on Computer Commu-
nications and Networks { ICCCN '03, pp. 609-612, 2003.
[15] L. Lamport, \Password Authentication with Insecure Communication," Com-
munications of ACM, vol. 24, no. 11, pp. 770-772, 1981.
[16] M. Lee, K. Kim, \A Micro-payment System for Multiple-Shopping," Proc. of
Symposium on Cryptography and Information Security { SCIS '02, vol. 1/2,
pp. 229-234, 2002.
[17] R.C. Merkle, \A Certied Digital Signature," Proc. of Advances in Cryptology
{ CRYPTO '89, LNCS vol. 435, pp. 218-238, 1989.
[18] M.S. Manasse, \The Millicent Protocols for Electronic Commerce," Proc. of 1st
USENIX Workshop on Electronic Commerce { EC '95, pp. 117-123, 1995.
[19] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, \Handbook of Applied
Cryptography," CRC Press, 1997.
[20] K. Q. Nguyen, Y. Mu, and V. Varadharajan, \Digital Coins Based on Hash
Chain," Proc. of 20th National Information Systems Security Conference, pp.
72-79, 1997.
[21] A. Perrig, \The BiBa One-time Signaturer and Broadcast Authentication Pro-
tocol," Proc. of 8th ACM Conference on Computer and Communications Secu-
rity { CCS '01, pp. 28-37, 2001.
[22] R. L. Rivest, \The MD5 Message Digst Algorithm," RFC 1321, 1992.
[23] R. L. Rivest, A. Shamir, \PayWord and MicroMint: Two Simple Micropayment
Schemes," CryptoBytes, vol. 2, no. 1, pp. 7-11, 1996.
[24] J. Stern, S. Vaudenay, \SVP: a Flexible Micropayment Scheme," Proc. of 1st
Financial Cryptography { FC '97, LNCS vol. 1318, pp. 161-171, 1997.
[25] M. Sirbu, J. D. Tygar, \NetBill: An Internet Commerce System Optimized for
Network Delivered Services," Proc. of IEEE Personal Communications, vol. 2,
pp. 34-39, 1995.
[26] M. Sirbu, J. D. Tygar, and M. Sirbu, \NetBill Security and Transaction Pro-
tocol," Proc. of 1st USENIX Workshop on Electronic Commerce, pp. 77-88,
1995.
[27] C.T. Wang, C.C. Chang, and C.H. Lin, \A New Micropayment System Using
General Payword Chain," Electronic Commerce Research Journal, vol. 2, no.
1-2, pp. 155-162, 2002.
[28] L.C. Wuu, K.Y. Chen, C.M. Lin, \O-line Micropayment Scheme with Dual
Signature," Journal of Computers, vol. 19, no. 1, 2008.
[29] H. Wang, J. Ma, and J. Sun, \Micro-payment Protocol Based on Multiple
Hash Chain," Proc. of 2nd International Symposium on Electronic Commerce
and Security { ISECS '09, pp. 71-74, 2009.
[30] S.M. Yen, L.T. Ho, and C.Y. Huang, \Internet Micropayment Based on Un-
balanced One-way Binary Tree," Proc. of International Workshop on Crypto-
graphic Techniques and E-Commerce, pp. 155-162, 1999.
[31] S.M. Yen, Y. Zheng, \Weighted One-way Hash Chain and its Applications,"
Proc. of International Workshop on Information Security, pp. 135-148, 2000.
[32] S.M. Yen, \PayFair: A Prepaid Internet Micropayment Scheme Ensuring Cus-
tomer Fairness," IEE Proceedings: Computers and Digital Techniques, vol. 148,
no. 6, pp. 207-213, 2001.
[33] Z. Yang, W. Lang, Y. Tan, \A new Fair of Micropayment System Based on Hash
Chain," Proc. of IEEE International Conference on e-Technology, e-Commerce
and e-Service, pp. 139-145, 2004.
[34] S.M. Yen, H.C. Lin, Y.C. Chen, J.J. Hung, and J.M. Wu, \PayStar: A Denom-
ination Flexible Micropayment Scheme," Proc. of International Conference on
Web Information Systems and Technologies { WEBIST '08, vol. 2, pp. 387-393,
2008.
[35] C.N. Yang, C.C. Wu, C.Y. Chiu, and W.C. Liao, \Micropayment Schemes
with Ability to Return Changes," Proc. of 11th International Conference on
Information Integration and Web-based Applications & Services { iiWAS '09,
pp. 356-363, 2009.
[36] Y. Zheng, J. Pieprzyk, and J. Seberry, \HAVAL - A One-way Hashing Algo-
rithm with Variable Length of Output," Advanced in Cryptology - AUSCRYPT
'92, LNCS vol. 718, pp. 81-104, 1993.
[37] X. Zhao, Y. Lv, and W. He, \A Novel Micropayment Scheme with Complete
Anonymity," Proc. of 5th Information Conference on Information Assurance
and Security { IAS '09, pp. 638-642, 2009.
[38] FIPS 180-1, \Secure Hash Standard," NIST, US Department of Commerce,
Washington, D.C., 1995.
[39] Atmel ATiny45 available at http://www.atmel.com/devices/attiny45.aspx