Abstract
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the database is replicated among k servers, and the user’s privacy is protected from any collusion of up to t servers. The main cost-measure of such protocols is the communication complexity of retrieving a single bit of data.
This work addresses the information-theoretic setting for PIR, in which the user’s privacy should be unconditionally protected from collusions of servers. We present a unified general construction, whose abstract components can be instantiated to yield both old and new families of PIR protocols. A main ingredient in the new protocols is a generalization of a solution by Babai, Kimmel, and Lokam to a communication complexity problem in the so-called simultaneous messages model.
Our construction strictly improves upon previous constructions and resolves some previous anomalies. In particular, we obtain: (1) t-private k-server PIR protocols with O(n 1/⌊ (2k-1)/tc⌋) communication bits, where n is the database size. For t > 1, this is a substantial asymptotic improvement over the previous state of the art; (2) a constant-factor improvement in the communication complexity of 1-private PIR, providing the first improvement to the 2-server case since PIR protocols were introduced; (3) efficient PIR protocols with logarithmic query length. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Ambainis. Upper bound on the communication complexity of private information retrieval. In Proc. of the 24th ICALP, vol. 1256 of LNCS, pp. 401–407. 1997.
A. Ambainis and S. Lokam. Improved upper bounds on the simultaneous messages complexity of the generalized addressing function. In LATIN 2000, vol. 1776 of LNCS, pp. 207–216. 2000.
L. Babai, P. G. Kimmel, and S. V. Lokam. Simultaneous messages vs. communication. In 12th STOC, vol. 900 of LNCS, pp. 361–372. 1995.
D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In STACS’ 90, vol. 415 of LNCS, pp. 37–48. 1990.
D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. J. of Cryptology, 10(1):17–36. 1997.
A. Beimel and Y. Ishai. Information-Theoretic Private Information Retrieval: A Unified Construction. TR01-15, Electronic Colloquium on Computational Complexity. 2001.
A. Beimel, Y. Ishai, and T. Malkin. Reducing the servers’ computation in private information retrieval: PIR with preprocessing. In CRYPTO 2000, vol. 1880 of LNCS, pp. 56–74. 2000.
J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In CRYPTO’ 88, vol. 403 of LNCS, pp. 27–35. 1990.
C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In EUROCRYPT’ 99, vol. 1592 of LNCS, 402–414. 1999.
B. Chor and N. Gilboa. Computationally private information retrieval. In Proc. of the 29th STOC, pp. 304–313. 1997.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. J. of the ACM, 45:965–981. 1998.
G. Di-Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for private information retrieval. J. of Cryptology, 14(1):37–74. 2001.
Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. JCSS, 60(3):592–629. 2000.
O. Goldreich and L. Trevisan. On the length of linear error-correcting codes having a 2-query local decoding procedure. Manuscript, 2000.
Y. Ishai and E. Kushilevitz. Improved upper bounds on information theoretic private information retrieval. In Proc. of the 31th STOC, pp. 79–88. 1999.
M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structure. In Proc. of Globecom 87, pp. 99–102. 1987.
H. Karloff and L. Schulman. Manuscript, 2000.
J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proc. of the 32th STOC, pp. 80–86. 2000.
E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Proc. of the 38th FOCS, pp. 364–373. 1997.
E. Mann. Private access to distributed information. Master’s thesis, Technion-Israel Institute of Technology, Haifa, 1998.
A. Shamir. How to share a secret. CACM, 22:612–613. 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beimel, A., Ishai, Y. (2001). Information-Theoretic Private Information Retrieval: A Unified Construction. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48224-5_74
Download citation
DOI: https://doi.org/10.1007/3-540-48224-5_74
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42287-7
Online ISBN: 978-3-540-48224-6
eBook Packages: Springer Book Archive