臺灣博碩士論文加值系統

傳送端的資訊傳輸量太大一直是模糊傳送協定在研究發展上問題的癥結點，有鑑於此，在本論文中，我們提出了一種有效率的 中選取 項類型的模糊傳送協定，並且經過分析比較後發現，我們所設計的協定的確大幅地降低傳送端的資訊傳輸量，成果甚至優於之前最佳的方法。而且協定本身的安全性也是無庸質疑的，在我們的協定裡，傳送端無法得知接收端從 中選取了哪 項。另一方面，基於質因數分解的難題，接收端亦無從得知其它 項未選取的機密資料，當 值固定為1時，我們則是提出另一更有效率的解決方法。
價格模糊傳送的觀念與方法首先由Aiello等人所提出，其協定可以巧妙地應用於販售數位商品，並且妥善地保護消費者的隱私權，而目前價格模糊傳送的發展還是有其改善的空間，像是Aiello等人或Tobias所提出的方法中，買方每次只能 中選取1項商品，並且必需從賣方接收 項非必要性的資訊，如此的特性並不俱備實用性及可行性。因此在本論文中，我們發展出一種有效率的 中選取 項類型的價格模糊傳送協定，協定的安全性則是基於RSA公開金鑰加密系統。並且我們也明顯改善了賣方的資訊傳輸量太大的問題。

The oblivious transfer has a critical problem on the sender’s communication complexity. Therefore, in this thesis, we develop an efficient k-out-of-n Oblivious Transfer whose result is superior to all previous solutions in terms of sender’s communication complexity. In our k-out-of-n Oblivious Transfer protocol, the sender cannot determine which k secret messages the receiver received, and the receiver cannot get the other remaining n-k secret messages if solving the factorization problem is hard. When k=1, we particularly suggest an efficient solution.
The priced oblivious transfer which can be applied to sell digital goods, was introduced by Aiello et al. However, in the previous work, such as Aiello et al.’s and Tobias’s papers, a customer buys only one item in each transaction but must receive n ciphertexts from the vendor, which is inefficient because of increasing n-1 non-essential transmissions. For this reason, we present an efficient priced k-out-of-n scheme. In our scheme, the communication cost of the vendor can be greatly reduced.

Chinese Abstract i
English Abstract ii
Acknowledgement iii
List of Figures vi
List of Tables vii
Chapter 1. Introduction 1
1.1 Introduction of Oblivious Transfer 1
1.2 Motivations 3
1.2.1 An Efficient Oblivious Transfer with Common Cipher 3
1.2.2 A Priced k-out-of-n Oblivious Transfer Scheme 4
1.3 Organization of This Thesis 5
Chapter 2. Overview of Oblivious Transfer Schemes 6
2.1 Rabin’s Oblivious Transfer 6
2.2 1-out-of-2 Oblivious Transfer 8
2.3 1-out-of-n Oblivious Transfer 9
2.4 k-out-of-n Oblivious Transfer 10
Chapter 3. A New Efficient k-out-of-n Oblivious Transfer Scheme by means of Common Cipher 12
3.1 Preliminaries 12
3.1.1 k-out-of-n Oblivious Transfer 12
3.1.2 The RSA Problem 13
3.2 Common Cipher 13
3.2.1 Building Common Cipher 14
3.3 Efficient k-out-of-n Oblivious Transfer with Common Cipher 15
3.3.1 Basic Model 16
3.3.2 The Proposed Protocol 17
3.3.3 Security Analysis 20
3.3.4 When k=1 22
3.4 Overhead Comparison 23
Chapter 4. An Efficient Priced k-out-of-n Oblivious Transfer Scheme 27
4.1 Preliminaries 27
4.1.1 Priced k-out-of-n Oblivious Transfer 27
4.1.2 Proof of Knowledge System 28
4.2 Priced k-out-of-n Oblivious Transfer based on RSA 32
4.2.1 Proposed Protocol 33
4.2.2 Security Analysis 37
4.3 Overhead 39
4.3.1 Overheads of Our Proposed Protocol 39
4.3.2 Overheads of Boudot’s Zero-Knowledge Proof 41
4.3.3 Overhead Comparison 41
Chapter 5. Conclusions and Future Research 43
References 45

[1] W. Mao, Modern Cryptography: Theory and Practice, Prentice Hall, New Jersey, 2003.

[2] B. Aiello, Y. Ishai, and O. Reingold, “Priced Oblivious Transfer: How to Sell Digital Goods,” Proceedings of Advances in Cryptology - Eurocrypt 2001, LNCS 2045, pp.119-135, 2001.

[3] D. Beaver, S. Goldwasser, “Multiparty computation with faulty majority,” Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp.468-473, 1989.

[4] M. Bellare and S. Micali, “Non-Interactive Oblivious Transfer and Applications,” Proceedings of Advances in Cryptology - Crypto ’89, LNCS 435, pp.547-557, 1990.

[5] F. Boudot, “Efficient proofs that a committed number lies in an interval,” Proceedings of Advances in Cryptology - Eurocrypt 2000, LNCS 1807, pp.431-444, 2000.

[6] G. Brassard, C. Crépeau, and J.M. Robert, “All-or-nothing disclosure of secrets,” Proceedings of Advances in Cryptology - Crypto ’86, LNCS 263, pp.234-238, 1986.

[7] D. Chaum, “Blind Signatures for Untraceable Payments,” Proceedings of Advances in Cryptology - Crypto ’82, pp.199-203, 1982.

[8] C. Crepeau, J. van de Graaf, and A. Tapp, “Committed oblivious transfer and private multi-party computations,” Proceedings of Advances in Cryptology – Crypto’95, LNCS 963, pp.110-123, 1995.

[9] G. D. Crescenzo, T. Malkin, and R. Ostrovsky, “Single Database Private Information Retrieval Implies Oblivious Transfer,” Proceedings of Advances in Cryptology - Eurocrypt 2000, LNCS 1807, pp.122-138, 2000.

[10] S. Even, O. Goldreich, and A. Lemple, “A randomized protocol for signing contracts,” Communications of the ACM, vol. 28, pp.637-647, 1985.

[11] E. Fujisaki and T. Okamoto, “Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations,” Proceedings of Advances in Cryptology - Crypto ’97, LNCS 1294, pp.16-30, 1997.
[12] J. A. Garay and P. Mackenzie, “Concurrent Oblivious Transfer,” Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pp.314-324, 2000.

[13] H. F. Huang and C.C. Chang, “A New Design for Efficient t-out-n Oblivious Transfer Scheme,” The First International Workshop on Information Networking and Applications (INA 2005), Vol. 2, Taiwan, Mar. 2005, pp.499-502.

[14] J. Kilian, “Founding Cryptography on Oblivious Transfer,” Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp.20-31, 1988.

[15] K. Kurosawa and Q.V. Duong, “How to Design Efficient Multiple-Use 1-out-n Oblivious Transfer,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E87-A, no. 1, pp.141-146, 2004.

[16] E. Kushilevitz, S. Micali, and R. Ostrovsky, “Reducibility and completeness in multi-party private computations,” Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), pp.478-489, 1994.

[17] C. H. Lim and P.J. Lee, “Modified Maurer-Yacobi’s scheme and its applications,” Proceedings of Advances in Cryptology - Asiacrypt ’92, LNCS 718, pp.308-323, 1992.

[18] D. Malkhi and Y. Sella, “Oblivious Transfer Based on Blind Signatures,” Technical report, Leibniz Center For Research in Computer Science: Report 2003/31, 2003.

[19] S. Matsuo and W. Ogata, “Matching Oblivious Transfer: How to Exchange Valuable Data,” IEICE Transactions on Fundamentals of Electronics, Communication and Computer Sciences, vol. E86-A, no. 1, pp.189-193, 2003.

[20] U. M. Maurer and Y. Yacobi, “Non-interactive Public-Key Cryptography,” Proceedings of Advances in Cryptology - Eurocrypt ’91, LNCS 547, pp.498-507, 1991.

[21] J. H. Moore, “Protocol failures in cryptosystems,” Proceedings of the IEEE, vol. 76, issue: 5, pp.594-602, 1988.

[22] Y. Mu, J. Zhang, and V. Varadharajan, “m out of n Oblivious Transfer,” Australasian Conference on Information Security and Privacy (ACISP) 2002, LNCS 2384, pp.395-405, 2002.

[23] Y. Mu, J. Zhang, V. Varadharajan, and Y.X. Lin, “Robust Non-Interactive Oblivious Transfer,” IEEE Communications Letters, vol. 7, no. 4, pp.153-155, 2003.
[24] M. Naor and B. Pinkas, “Distributed Oblivious Transfer,” Proceedings of Advances in Cryptology - Asiacrypt 2000, LNCS 1976, pp.205-219, 2000.

[25] M. Naor and B. Pinkas, “Efficient Oblivious Transfer Protocols,” Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA), pp.448-457, 2001.

[26] W. Ogata and K. Kurosawa, “Oblivious Keyword Search,” Technical report, Cryptology ePrint Archive: Report 2002/182, 2002.

[27] W. Ogata and R. Sasahara, “k out of n Oblivious Transfer without Random Oracles,” IEICE Transactions on Fundamentals of Electronics, Communication and Computer Sciences, vol. E87-A, no. 1, pp. 147-151, 2004.

[28] M. Rabin, “How to Exchange Secrets by Oblivious Transfer,” Technical Report TR-81, Aiken Computation Lab., Harvard University, 1981.

[29] C. Tobias, “Practical Oblivious Transfer Protocols,” Information Hiding (IH) 2002, LNCS 2578, pp.415-426, 2002.

[30] W. G. Tzeng, “Efficient 1-out-n oblivious transfer schemes,” Public Key Cryptography (PKC) 2002, LNCS 2774, pp.159-171, 2002.

[31] W. G. Tzeng, “Efficient 1-out-of-n Oblivious Transfer Schemes with Universally Usable Parameters,” IEEE Transactions on Computers, vol. 53, no. 2, pp.232-240, 2004.

[32] Q. H. Wu, J. H. Zhang, and Y. M. Wang, “Practical t-out-n Oblivious Transfer and Its Applications,” International Conference on Information and Communications Security (ICICS) 2003, LNCS 2836, pp.226-237, 2003.

[33] A. Yao, “How to generate and exchange secrets,” Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS), pp.162-167, 1986.

[34] A. Chan, Y. Frankel, and Y. Tsiounis, “Easy Come – Easy Go Divisible Cash,” Updated version with corrections, GTE Tech. Rep. (1998), available at http://www.ccs.neu.edu/home/yiannis/