Abstract
Private information retrieval (PIR) is normally modeled as a game between two players: a user and a database. The user wants to retrieve some item from the database without the latter learning which item. Most current PIR protocols are ill-suited to provide PIR from a search engine or large database: i) their computational complexity is linear in the size of the database; ii) they assume active cooperation by the database server in the PIR protocol. If the database cannot be assumed to cooperate, a peer-to-peer user community is a natural alternative to achieve some query anonymity: a user submits a query on behalf of another user in the community. A peer-to-peer PIR system is described in this paper which relies on an underlying combinatorial structure to reduce the required key material and increase availability.
This is a preview of subscription content, log in via an institution to check access.
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
Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers computation in private information retrieval: Pir with preprocessing. Journal of Cryptology 17, 125–151 (2004)
Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Technical Report TR CS0917, Department of Computer Science, Technion (1997)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 41–50 (1995)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. Journal of the ACM 45, 965–981 (1998)
Colbourn, C.J., Dinitz, J.H. (eds.): Handbook of Combinatorial Designs, 2nd edn. Chapman and Hall/CRC, London (2007)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and Systems Science 28(1), 270–299 (1984)
Gropp, H.: On the history of configurations. In: International Symposium on Structures in Mathematical Theories, Bilbo, pp. 263–268. Euskal Herriko Unibertsitatea (1990)
Gropp, H.: Configurations between geometry and combinatorics. Discrete Appl. Math. 138(1-2), 79–88 (2000); Optimal discrete structures and algorithms (ODSA 2000)
Gropp, H.: Existence and enumeration of configurations. Bayreuth. Math. Schr. 74, 123–129 (2005)
Gropp, H.: Configurations. In: Colbourn, C.J., Dinitz, J.H. (eds.) Handbook of Combinatorial Designs. Chapman & Hall/CRC, Boca Raton (2007)
Solanas, A., Domingo-Ferrer, J., Bujalance, S.: k-private information retrieval from privacy-uncooperative queryable databases (submitted, 2008)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, pp. 364–373 (1997)
Lee, J., Stinson, D.R.: A combinatorial approach to key predistribution for distributed sensor networks. In: Wireless Communications and Networking Conference-WCNC 2005, vol. 2, pp. 1200–1205 (2005)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A. (eds.): Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
Ostrovsky, R., Skeith-III, W.E.: A survey of single-database pir: techniques and applications. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 393–411. Springer, Heidelberg (2007)
Stinson, D.R.: Combinatorial Designs: Constructions and Analysis. Springer, New York (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Domingo-Ferrer, J., Bras-Amorós, M. (2008). Peer-to-Peer Private Information Retrieval. In: Domingo-Ferrer, J., Saygın, Y. (eds) Privacy in Statistical Databases. PSD 2008. Lecture Notes in Computer Science, vol 5262. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87471-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-87471-3_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87470-6
Online ISBN: 978-3-540-87471-3
eBook Packages: Computer ScienceComputer Science (R0)