以樹狀架構為基礎之計算分攤式小額付費系統設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.23.92.159

姓名

吳俊毅(Chun-Yi Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

以樹狀架構為基礎之計算分攤式小額付費系統設計
(The Design of Amortized Tree-based Micropayment Scheme)

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
★ 遮罩保護機制防禦差分能量攻擊之研究	★ AES資料加密標準之能量密碼分析研究
★ 小額電子付費系統之設計與密碼分析	★ 公平電子現金系統之研究
★ RSA公開金鑰系統之實體密碼分析研究	★ 保護行動代理人所收集資料之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著網際網路的迅速成長，促進電子商務的蓬勃發展，電子付費系統已是電
子商務中相當重要的議題。消費者能夠藉由電子錢幣向網路商家購買任何的服務
或商品，而大部分電子付費系統採用單向雜湊鏈 (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

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2013-7-25

推文