Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19508
標題: 私密資訊擷取機制及其應用之研究
Private Information Retrieval Schemes and their Applications
作者: 陳俊華
Chen, Chun-Hua
關鍵字: private information retrieval(PIR)
私密的資訊擷取
fair privacy
secure coprocessor(SC)
e-payment
e-voting
公平的私密性
安全共同處理器
電子付費
電子投票
出版社: 資訊科學與工程學系所
引用: [1] B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, “Private information retrieval,” Proc. of the 36th IEEE Symposium on Foundations of Computer Science (FOCS95), pp. 41-50, 1995. [2] Y. Gertner, Y. Ishai, E. Kushilevitz and T. Malkin, “Protecting data privacy in private information retrieval schemes,” Proc. of 30st Annual ACM Symposium on the Theory of Computing (STOC98), pp.151-160, 1998. [3] B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, “Private information retrieval,” Journal of ACM, vol. 45, pp. 965-981, 1998. [4] A. Beimel and Y. Ishai, “Information-theoretic private information retrieval: a unified construction,” Electronic Colloquium on Computational Complexity, TR01-15, 2001; Extended abstract in ICALP 2001, Lecture Notes in Computer Science, vol. 2076, pp. 89-98, 2001. [5] A. Ambainis, “Upper bound on the communication complexity of private information retrieval,” Proc. of 24th ICALP 97, Lecture Notes in Computer Science, vol. 1256, pp. 401-407, 1997. [6] A. Beimel, Y. Ishai, E. Kushilevit and J. F. Raymond, “Breaking the barrier O(n1/(2k-1)) for information- theoretic private information retrieval,” Proc. of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS02), pp. 261-270, 2002. [7] B. Chor and N. Gilboa, “Computationally private information retrieval,” Proc. of the 29th annual ACM symposium on Theory of computing, pp. 304-313, 1997. [8] A. Beimel, Y. Ishai and T. Malkin, “Reducing the server's computation in private information retrieval: PIR with preprocessing,” Journal of Cryptology, vol. 17, pp. 125-151, 2004. [9] A. Beimel and Y. Stahl, “Robust information-theoretic private information retrieval,” Proc. of the 3rd Conference on Security in Communication Networks, Lecture Notes in Computer Science, vol. 2576, pp. 326-341, 2002. [10] E. Y. Yang, J. Xu and K. H. Bennett, “A fault- tolerant approach to secure private retrieval,” Proc. of 21st IEEE Symposium on Reliable Distributed Systems, pp.12-21, 2002. [11] E. Y. Yang, J. Xu and K. H. Bennett, “Private information retrieval in the presence of malicious failures,” Proc. of the 26th IEEE Annual International Computer Software and Applications Conference, pp. 805-810, 2002. [12] E. Kushilevitz and R. Ostrovsky, “Replication is not needed: single-database computationally private information retrieval,” Proc. of the 38th IEEE Symposium on Foundations of Computer Science (FOCS97), pp. 364-373, 1997. [13] C. Cachin, S. Micali and M. Stadler, “Computationally private information retrieval with polylogarithmic communication,” Proc. on Advances in Cryptology- EUROCRYPT' 99, Lecture Notes in Computer Science, vol. 1592, pp. 402-414, 1999. [14] C. H. Chen and G. Horng, “Protecting the privacy of users in e-commerce environment,” Proc. of International Conference on Computer, Communication and Control Technologies (CCCT 2004), August 14-17, Austin, Texas, USA, vol. 1, pp. 63-67, 2004. [15] C. H. Chen, “The users' privacy protecting scheme based on knapsack problem,” to appear in Proc. of the IEEE 2008 International Conference on Innovative Computing, Information and Control (ICICIC 2008), June 18-20, Dalian, China, 2008. [16] S. W. Smith and D. Safford, “Practical private information retrieval with secure coprocessors,” Technical report, IBM Research Division, T.J. Watson Research Center, July 2000. [17] S.W. Smith and D. Safford, “Practical server privacy using secure coprocessors,” IBM System Journal, vol. 40, no.3, pp. 683-695, 2001. [18] A. Iliev and S.W. Smith, “Protecting client privacy with trusted computing at the server,“ IEEE Security and Privacy Magazine, vol. 3, no. 2, pp. 20-28, 2005. [19] D. Asonov, M. Schaal and J.-C. Freytag, “Absolute privacy in voting,” Proc. of the 4th Information Security Conference (ISC''01), Malaga, Spain, October 2001; Lecture Notes in Computer Science, vol. 2200, pp. 95-109, 2001. [20] C. H. Chen, C. M. Lan and G. Horng, “A practical voting system for small-scale election,” Proc. of the IEEE 3rd International Conference on Information Technology: Research and Education (ITRE 2005), June 27-30, Hsinchu, Taiwan, pp. 322-326, 2005. [21] D. Asonov and J.-C. Freytag, “Almost optimal private information retrieval,” Pre- and Postproc. of 2nd Workshop on Privacy Enhancing Technologies (PET2002), San Francisco, USA, 2002; Lecture Notes in Computer Science, vol. 2482, pp. 239-243, 2003. [22] T. Itoh, “Efficient private information retrieval,” IEICE Transactions on Fundamentals, vol. E82-A(1), pp.11-20, 1999. [23] T. Itoh, “On lower bounds for the communication complexity of private information retrieval,” IEICE Transactions on Fundamentals, vol. E84-A(1), pp.157-164, 2001. [24] C. H. Chen, G. Horng and C. H. Hsu, “A novel private information retrieval scheme with fair privacy in the user side and the server side,” to appear International Journal of Innovative Computing, Information and Control, vol.5, no.4, April, 2009. [25] C. H. Chen, C. M. Lan and G. Horng, “Protecting customer's privacy in querying valuable information combined with e-payment scheme,” Proc. of the IEEE 3rd International Conference on Information Technology and Applications (ICITA''2005), July 4-7, Sydney, Australia, pp. 580-583, 2005. [26] C. H. Chen, J. K. Jan and C. H. Hsu, “One-server private information retrieval scheme combined with mutual authentication by ElGamal signature,” Proc. of the IEEE 2006 International Conference on innovative Computing, Information and Control (ICICIC 2006), Beijing, China, pp. 300-303, 2006. [27] C. H. Chen, G. Horng and C. H. Hsu, “Protecting the privacy of users in retrieving valuable information by a PIR scheme with mutual authentication by RSA signature algorithm,” Proc. of the IEEE 2007 International Conference on Innovative Computing, Information and Control (ICICIC 2007), Kumamoto, Japan, Page 75, 2007. [28] C. H. Chen and G. Horng, “More robust private information retrieval scheme,” Proc. of the SECRYPT 2006, International Conference on Security and Cryptography, Aug. 7-10, Setúbal, Portugal, pp. 297- 302, 2006. [29] C. H. Chen, ”One-server private information retrieval scheme with mutual authentication capability,” Journal of Chienkuo Technology University, vol. 26, no. 2, pp. 119-132, 2007. [30] Dmitri Asonov, “Private information retrieval - an overview and current trends,” Proc. of the ECDPvA Workshop, Informatik 2001, Vienna, Austria, September, pp. 889-894, 2001. [31] B. Chor, N. Gilboa and M. Naor, “Private information retrieval by keywords,” Technical report CS0917, Technion: Israel Institute of Technology, 1997. [32] Y. Gertner, S. Goldwasser and T. Malkin, “A random server model for private information retrieval,” Proc. of 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM98), Lecture Notes in Computer Science, vol. 1518, pp. 200-217, 1998. [33] I. Kerenidis and R. d. Wolf, “Quantum symmetrically- private information retrieval,” Information Processing Letters, vol. 90, no. 3, pp. 109-114, 2004. [34] S. Wehner and R. d. Wolf, “Improved lower bounds for locally decodable codes and private information retrieval,” Lecture Notes in Computer Science, vol. 3580, pp. 1424-1436, 2005. [35] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469-472, 1985. [36] R. L. Rivest, A. Shamir and L. M. Adleman, “A method for obtaining digital signatures and public key cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp.120-126, 1978. [37] P. Gutmann, “An open-source cryptographic coprocessor,” Proc. of the 9th Usenix Security Symposium, Denver, Colorado, USA, Aug. 14-17, pp. 97-112, 2000. [38] Z. Zhang, B. Fang, M. Hu and H. Zhang, “Security analysis of session initiation protocol,” International Journal of Innovative Computing, Information and Control, vol. 3, no. 2, pp. 457-469, 2007. [39] J. A. Buchmann, Introduction to cryptography, second edition, (pp. 41-42), Springer, 2004. [40] B. Aiello, Y. Ishai and O. Reingold, “Priced oblivious transfer: how to sell digital goods,” Proc. on Advances in Cryptology- EUROCRYPT'01, Lecture Notes in Computer Science, vol. 2045, pp. 119-135, 2001. [41] D. Chaum, “Blind signatures for untraceable payments”, Proc. on Advances in Cryptology- CRYPTO' 82, pp. 199-203, 1982. [42] D. Chaum, A. Fiat and M. Naor, “Untraceable electronic cash”, Proc. on Advances in Cryptology- CRYPTO'88, pp. 319-327, 1990. [43] R. C. Merkle, “A fast software one-way hash function,” Journal of Cryptology, vol. 3, no. 1, pp. 43-58, 1990. [44] D. E. Knuth, The Art of computer programming, Addison- Wesley, second edition, vol. 2, 1981. [45] C. Blundo, P. D. Arco and A. D. Santis, “A t-private k-database information retrieval scheme,” International Journal of Information Security, vol. 1, no. 1, 2001. [46] C. Rackoff and D. Simon, “Non-interactive zero- knowledge proof of knowledge and chosen ciphertext attack,” Advances in Cryptology- CRYPTO'91, Lecture Notes in Computer Science, vol. 576, pp. 433-444, 1991. [47] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, “Relations among notions of security for public key encryption schemes,” Advances in Cryptology- CRYPTO' 98, Lecture Notes in Computer Science, vol. 1462, pp. 26-46, 1998. [48] D. Dolev, C. Dwork, and M. Naor, “Non-malleable cryptography,” Proc. of the twenty third annual ACM symposium on theory of computing, ACM press, pp. 542- 552, 1991. [49] M. Bellare and P. Rogaway, “Entity authentication and key distribution,” Proc. on Advances in Cryptology- CRYPTO'93, Lecture Notes in Computer Science, vol. 773, pp. 232-249, 1993. [50] R. Canetti and H. Krawczyk, “Analysis of key- exchange protocols and their use for building secure channels”, Proc. on Advances in Cryptology- EUROCRYPT'01, Lecture Notes in Computer Science, vol. 2045, pp. 453-474, 2001. [51] E. Gabber, P. B. Gibbons, D. M. Kristol, Y. Matias and A. Mayer, “Consistent, yet anonymous, web access with LPWA,” CACM Journal, vol. 42, no. 2, pp. 42-47, 1999. [52] T. Okamoto, “Provably secure and practical identification schemes and corresponding signature schemes,” Advances in Cryptology-CRYPTO'92, Lecture Notes in Computer Science, vol. 740, pp. 31-53, 1992. [53] M. G. Reed, P. F. Syverson and D. M. Goldschlag, “Anonymous connections and onion routing,” IEEE Journal on Selected Areas in Communication, vol. 16, no. 4, pp.482-494, 1998. [54] Y. Y. Chen, J. K. Jan and C. L. Chen, “The design of a secure anonymous internet voting system,” Computers & Security, vol. 23, pp. 330-337, 2004. [55] C. I. Fan, and C. L. Lei, “Multi-recastable ticket schemes for electronic voting,” IEICE Transactions on Fundamentals, vol. E81-A(5), pp. 940-949, 1998. [56] A. Riera, J. Borrell and J. Rifa, “An uncoercible verifiable electronic voting protocol,” IT Global Security, IFIP SEC'98, Austrian Computer Society, Vienna, pp. 206-215, 1998. [57] K. Sako, “Electronic voting schemes allowing open objection to the tally,” IEICE Transactions on Fundamentals, vol. E77-A(1), pp. 24-30, 1994. [58] Murat Kantarcioglu, Wei Jiang, Ying Liu and Bradley Malin, “A cryptographic approach to securely share and query genomic sequences,” to appear IEEE Transaction on Information Technology in Biomedicine, accepted for publication August 24, 2007.
摘要: 在網際網路的環境中,要對使用者所查詢的伺服器保護使用者的隱私,一般認為這是不可能的,直到私密資訊擷取(Private Information Retrieval: PIR)問題被提出及有解決的方案為止。私密資訊擷取機制允許使用者從線上資料庫伺服器查詢資料項,但能對資料庫伺服器隱藏所查詢的資料項。私密資訊擷取的起始研究是由Chor等人在1995年所提出。 從n個資料項查詢一個資料項的通訊量複雜度,是衡量私密資訊擷取機制成本的一個方式。在資訊理論上安全的條件下,單一伺服器私密資訊擷取機制的通訊量複雜度已被證明是O(n),其中n是代表資料庫資料量的大小;但這在應用上是無法被接受的,因為這等於將整個資料庫下載。但藉著Chor等人所提出的k伺服器私密資訊擷取機制,通訊量複雜度能被改進到O(n1/k)。後續有些研究著眼於繼續降低k伺服器私密資訊擷取機制的通訊量複雜度。 在此論文中我們指出k伺服器私密資訊擷取機制的嚴重缺點,因為管理這些伺服器並保持其資料庫的一致性,是非常大的負擔。令人讚嘆的,在計算上安全(比資訊理論上安全稍弱)的條件下,Kushilevitz等人根據二次剩餘假定提出一個單一伺服器的私密資訊擷取機制。Kushilevitz等人的單一伺服器私密資訊擷取機制克服了需管理k伺服器的沉重負擔。但我們發現Kushilevitz等人的私密資訊擷取機制的缺點,他們的機制洩露了伺服器的隱私(資料),使用者在每次對單一資料項的查詢中可以不止查到一個資料項。在真實世界的應用中使用者對每一次查詢付費,因為在Kushilevitz等人的機制讓使用者在每次的查詢中平均可以查到 個資料項,這樣對伺服器端並不公平。在此論文第二章中,我們提出對使用者也對伺服器具有公平私密性的單一伺服器私密資訊擷取機制。 在此論文中的第三、四章,我們將焦點放在私密資訊擷取機制的應用上。第三章我們考慮在網際網路的環境中保護使用者隱私於查詢有價資訊時。我們提出一個具有電子付費(e-payment)功能的私密資訊擷取機制。第四章我們使用單一伺服器私密資訊擷取機制的概念在電子投票中。我們提出了一個低成本、高效率且具實用性的新電子投票系統。在第三、四章中所提出的機制,我們均使用硬體:安全共同處理器(secure coprocessor: SC),以提升該機制的效率,這想法是由於Smith和 Asonov等人的啟發。在第五章中,我們指出Smith和 Asonov等人使用安全共同處理器的私密資訊擷取機制仍有安全上的漏洞;我們也提出了我們的私密資訊擷取機制以加強安全性。 總結此論文,我們介紹私密資訊擷取機制,並提出一個在計算上安全的條件下的單一伺服器私密資訊擷取機制,以達到對使用者及伺服器的公平私密性。我們也在私密資訊擷取機制的應用上付出努力,提出具有電子付費功能的私密資訊擷取機制及單一伺服器的電子投票系統。最後我們也加強了使用安全共同處理器的私密資訊擷取機制之安全性。
In the internet environment, the protection of users' privacy from a server had not been considered feasible until the private information retrieval (PIR) problem was stated and solved. A PIR scheme allows a user to retrieve data items from an online database while hiding the identity of the items from a database server. The research of PIR was initiated by Chor et al. in 1995. The communication complexity of retrieving one out of n bits is a method to measure the cost of PIR schemes. It has been proved that the communication complexity of one-server scheme is O(n) in information theoretic security condition. The “n” is the size of database. However, it is unacceptable in real application. But through using a k-server scheme, the communication complexity of a PIR scheme had been improved to O(n1/k) by Chor et al. Some subsequent research of PIR was focused on reducing the communication complexity on k-server PIR schemes. In this dissertation, we point out the serious shortcoming of k-server PIR schemes because of big overhead of management of these severs. It's astonishing that Kushilevitz et al. proposed a one-server PIR scheme based on the quadratic residue assumption in computational security condition, which is lower than information-theoretic security. Kushilevitz's PIR scheme conquers the problem of heavy overheads in managing severs of k-server schemes. But, we find out the drawback of Kushilevitz's PIR scheme. Kushilevitz's PIR scheme reveals server's privacy to the user. In the real applications, the user pays a fee in every query. So, it's not fair to the server side. In this dissertation, we present a one-server PIR scheme with fair privacy on the user side and the server side to conquer the drawback. In Chapter 3 and Chapter 4 of this dissertation, we focus on the application of PIR schemes. In Chapter 3, we consider of protecting customer's privacy in querying valuable information on the internet. We present the solution which is a PIR scheme with e-payment function. In Chapter 4, we use the concept of a one-server PIR scheme in e-voting. A novel practical e-voting system with low cost and good efficiency is proposed. The PIR schemes proposed in Chapter 3 and Chapter 4 use SC (secure coprocessor) in the scheme to promote the efficiency. The concept is inspired by Smith and Asonov. In Chapter 5 of this dissertation, we point out the security leak of their PIR schemes with SC, proposing our PIR scheme with SC to strengthen the security. In summary, this dissertation introduces PIR schemes and presents a computational one-server PIR scheme to achieve the fair privacy between the server side and the user side. We also make effort on the applications of PIR schemes to build e-payment function and to set up a one-server e-voting system. Finally, in this dissertation we strengthen the security of PIR schemes with SC.
URI: http://hdl.handle.net/11455/19508
其他識別: U0005-0706200820251900
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-0706200820251900
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.