Abstract
Private information retrieval (PIR) allows a client to retrieve any block x i from a database x = x 1 ⋯ x n (stored on a server) such that i remains hidden from the server. PIR schemes with unconditional privacy and sublinear (in n) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers. There are also extra properties such as efficient update of the database. In this paper, we consider a verifiable multi-server PIR (VPIR) model where the servers may be malicious and provide fraudulent answers. We construct an unconditionally t-private and computationally secure k-server VPIR scheme with communication complexity comparable to the best t-private k-server PIR scheme in the honest-but-curious server model. Our scheme supports efficient update of the database, identification of the cheating servers, tolerance of slightly corrupted answers, and multiple database outsourcing.
Chapter PDF
Similar content being viewed by others
Keywords
- Cloud Server
- Communication Complexity
- Main Construction
- Overwhelming Probability
- Probabilistic Polynomial Time
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Beimel, A.: Private Information Retrieval: A Primer (2008) (manuscript)
Beimel, A., Ishai, Y., Kushilevitz, E.: General Constructions for Information-Theoretic Private Information Retrieval. J. Comput. Syst. Sci. 71(2), 213–247 (2005)
Beimel, A., Ishai, Y., Malkin, T.: Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing. J. Cryptol. 17(2), 125–151 (2004)
Beimel, A., Stahl, Y.: Robust Information-Theoretic Private Information Retrieval. J. Cryptol. 20(3), 295–321 (2007)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: FOCS, pp. 41–50 (1995)
Devet, C.: Evaluating Private Information Retrieval on the Cloud. Technical Report (2013), http://cacr.uwaterloo.ca/techreports/2013/cacr2013-05.pdf
Devet, C., Goldberg, I., Heninger, N.: Optimally Robust Private Information Retrieval. In: USENIX Security Symposium (2012)
Gennaro, R., Gentry, C., Parno, B.: Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010)
Goldberg, I.: Improving the Robustness of Private Information Retrieval. In: IEEE Symposium on Security and Privacy, pp. 131–148 (2007)
Goldreich, O., Micali, S., Widgerson, A.: How to Play any Mental Game-A Completeness Theorem for Protocols with Honest Majority. In: STOC, pp. 218–229. ACM (1987)
Groth, J., Kiayias, A., Lipmaa, H.: Multi-query Computationally-Private Information Retrieval with Constant Communication Rate. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 107–123. Springer, Heidelberg (2010)
Huang, Y., Goldberg, I.: Outsourced Private Information Retrieval. In: Workshop on Privacy in the Electronic Society, pp. 119–130. ACM (2013)
Kushilevitz, E., Ostrovsky, R.: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval. In: FOCS, pp. 364–373 (1997)
Mayberry, T., Blass, E., Chan, A.: PIRMAP: Efficient Private Information Retrieval for MapReduce. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 371–385. Springer, Heidelberg (2013)
Papamanthou, C., Shi, E., Tamassia, R.: Signatures of Correct Computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 222–242. Springer, Heidelberg (2013), http://eprint.iacr.org/2011/587.pdf
Sion, R., Carbunar, B.: On the Computational Practicality of Private Information Retrieval. In: NDSS 2007 (2007)
Woodruff, D.P., Yekhanin, S.: A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM J. Comp. 37(4), 1046–1056 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhang, L.F., Safavi-Naini, R. (2014). Verifiable Multi-server Private Information Retrieval. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds) Applied Cryptography and Network Security. ACNS 2014. Lecture Notes in Computer Science, vol 8479. Springer, Cham. https://doi.org/10.1007/978-3-319-07536-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-07536-5_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07535-8
Online ISBN: 978-3-319-07536-5
eBook Packages: Computer ScienceComputer Science (R0)