Advanced Search
Article Contents
Article Contents

Extended combinatorial constructions for peer-to-peer user-private information retrieval

Abstract Related Papers Cited by
  • We consider user-private information retrieval (UPIR), an interesting alternative to private information retrieval (PIR) introduced by Domingo-Ferrer et al. In UPIR, the database knows which records have been retrieved, but does not know the identity of the query issuer. The goal of UPIR is to disguise user profiles from the database. Domingo-Ferrer et al. focus on using a peer-to-peer community to construct a UPIR scheme, which we term P2P UPIR. In this paper, we establish a strengthened model for P2P UPIR and clarify the privacy goals of such schemes using standard terminology from the field of privacy research. In particular, we argue that any solution providing privacy against the database should attempt to minimize any corresponding loss of privacy against other users. We give an analysis of existing schemes, including a new attack by the database. Finally, we introduce and analyze two new protocols. Whereas previous work focuses on a special type of combinatorial design known as a configuration, our protocols make use of more general designs. This allows for flexibility in protocol set-up, allowing for a choice between having a dynamic scheme (in which users are permitted to enter and leave the system), or providing increased privacy against other users.
    Mathematics Subject Classification: Primary: 05B05, 94A60.


    \begin{equation} \\ \end{equation}
  • [1]

    J. Domingo-Ferrer, Coprivacy: towards a theory of sustainable privacy, in "Proceedings of the 2010 International Conference on Privacy in Statistical Databases,'' (2010), 258-268.doi: 10.1007/978-3-642-15838-4_23.


    J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer user-private information retrieval, in "Proceedings of the 2008 International Conference on Privacy in Statistical Databases,'' (2008), 315-323.doi: 10.1007/978-3-540-87471-3_26.


    J. Domingo-Ferrer, M. Bras-Amorós, Q. Wu and J. Manjón, User-private information retrieval based on a peer-to-peer community, Data Knowl. Engin., 68 (2009), 1237-1252.doi: 10.1016/j.datak.2009.06.004.


    M. Garey and D. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,'' W. H. Freeman and Co., 1979.


    J. Lee and D. Stinson, A combinatorial approach to key predistribution for distributed sensor networks, in "IEEE Wireless Communications and Networking Conference,'' 2 (2005), 1200-1205.doi: 10.1109/WCNC.2005.1424679.


    A. Pfitzmann and M. Hansen, A terminology for talking about privacy by data minimization: anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management, version 0.34, 2010; available online at http://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf


    D. Stinson, "Combinatorial Designs: Constructions and Analysis,'' Springer-Verlag, 2003.


    K. Stokes and M. Bras-Amorós, Optimal configurations for peer-to-peer user-private information retrieval, Comp. Math. Appl., 59 (2010), 1568-1577.doi: 10.1016/j.camwa.2010.01.003.


    K. Stokes and M. Bras-Amorós, On query self-submission in peer-to-peer user-private information retrieval, in "Proceedings of the 4th International Workshop on Privacy and Anonymity in the Information Society,'' ACM, (2011).


    K. Stokes and M. Bras-Amorós, Combinatorial structures for an anonymous data search protocol, in "Workshop on Computational Security,'' Barcelona, (2011).

  • 加载中

Article Metrics

HTML views() PDF downloads(109) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint