Please use this identifier to cite or link to this item:
Private Information Retrieval Schemes and their Applications
|關鍵字:||private information retrieval(PIR)|
|引用:|| 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.  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.  B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, “Private information retrieval,” Journal of ACM, vol. 45, pp. 965-981, 1998.  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.  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.  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.  B. Chor and N. Gilboa, “Computationally private information retrieval,” Proc. of the 29th annual ACM symposium on Theory of computing, pp. 304-313, 1997.  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.  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.  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.  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.  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.  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.  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.  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.  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.  S.W. Smith and D. Safford, “Practical server privacy using secure coprocessors,” IBM System Journal, vol. 40, no.3, pp. 683-695, 2001.  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.  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.  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.  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.  T. Itoh, “Efficient private information retrieval,” IEICE Transactions on Fundamentals, vol. E82-A(1), pp.11-20, 1999.  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.  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.  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.  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.  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.  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.  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.  Dmitri Asonov, “Private information retrieval - an overview and current trends,” Proc. of the ECDPvA Workshop, Informatik 2001, Vienna, Austria, September, pp. 889-894, 2001.  B. Chor, N. Gilboa and M. Naor, “Private information retrieval by keywords,” Technical report CS0917, Technion: Israel Institute of Technology, 1997.  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.  I. Kerenidis and R. d. Wolf, “Quantum symmetrically- private information retrieval,” Information Processing Letters, vol. 90, no. 3, pp. 109-114, 2004.  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.  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.  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.  P. Gutmann, “An open-source cryptographic coprocessor,” Proc. of the 9th Usenix Security Symposium, Denver, Colorado, USA, Aug. 14-17, pp. 97-112, 2000.  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.  J. A. Buchmann, Introduction to cryptography, second edition, (pp. 41-42), Springer, 2004.  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.  D. Chaum, “Blind signatures for untraceable payments”, Proc. on Advances in Cryptology- CRYPTO' 82, pp. 199-203, 1982.  D. Chaum, A. Fiat and M. Naor, “Untraceable electronic cash”, Proc. on Advances in Cryptology- CRYPTO'88, pp. 319-327, 1990.  R. C. Merkle, “A fast software one-way hash function,” Journal of Cryptology, vol. 3, no. 1, pp. 43-58, 1990.  D. E. Knuth, The Art of computer programming, Addison- Wesley, second edition, vol. 2, 1981.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  K. Sako, “Electronic voting schemes allowing open objection to the tally,” IEICE Transactions on Fundamentals, vol. E77-A(1), pp. 24-30, 1994.  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年所提出。
在此論文中的第三、四章，我們將焦點放在私密資訊擷取機制的應用上。第三章我們考慮在網際網路的環境中保護使用者隱私於查詢有價資訊時。我們提出一個具有電子付費(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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.