2012, 6(4): 479-497. doi: 10.3934/amc.2012.6.479

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

1. 

University of Waterloo, David C. Cheriton School of Computer Science, 200 University Avenue West, Waterloo, ON, N2L 3G1, Canada, Canada

Received  December 2011 Published  December 2012

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.
Citation: Colleen M. Swanson, Douglas R. Stinson. Extended combinatorial constructions for peer-to-peer user-private information retrieval. Advances in Mathematics of Communications, 2012, 6 (4) : 479-497. doi: 10.3934/amc.2012.6.479
References:
[1]

J. Domingo-Ferrer, Coprivacy: towards a theory of sustainable privacy,, in, (2010), 258. doi: 10.1007/978-3-642-15838-4_23.

[2]

J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer user-private information retrieval,, in, (2008), 315. doi: 10.1007/978-3-540-87471-3_26.

[3]

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. doi: 10.1016/j.datak.2009.06.004.

[4]

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

[5]

J. Lee and D. Stinson, A combinatorial approach to key predistribution for distributed sensor networks,, in, 2 (2005), 1200. doi: 10.1109/WCNC.2005.1424679.

[6]

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).

[7]

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

[8]

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

[9]

K. Stokes and M. Bras-Amorós, On query self-submission in peer-to-peer user-private information retrieval,, in, (2011).

[10]

K. Stokes and M. Bras-Amorós, Combinatorial structures for an anonymous data search protocol,, in, (2011).

show all references

References:
[1]

J. Domingo-Ferrer, Coprivacy: towards a theory of sustainable privacy,, in, (2010), 258. doi: 10.1007/978-3-642-15838-4_23.

[2]

J. Domingo-Ferrer and M. Bras-Amorós, Peer-to-peer user-private information retrieval,, in, (2008), 315. doi: 10.1007/978-3-540-87471-3_26.

[3]

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. doi: 10.1016/j.datak.2009.06.004.

[4]

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

[5]

J. Lee and D. Stinson, A combinatorial approach to key predistribution for distributed sensor networks,, in, 2 (2005), 1200. doi: 10.1109/WCNC.2005.1424679.

[6]

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).

[7]

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

[8]

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

[9]

K. Stokes and M. Bras-Amorós, On query self-submission in peer-to-peer user-private information retrieval,, in, (2011).

[10]

K. Stokes and M. Bras-Amorós, Combinatorial structures for an anonymous data search protocol,, in, (2011).

[1]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191

[2]

Michael Kiermaier, Reinhard Laue. Derived and residual subspace designs. Advances in Mathematics of Communications, 2015, 9 (1) : 105-115. doi: 10.3934/amc.2015.9.105

[3]

Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007

[4]

Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015

[5]

M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13

[6]

JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003

[7]

Ivica Martinjak, Mario-Osvin Pavčević. Symmetric designs possessing tactical decompositions. Advances in Mathematics of Communications, 2011, 5 (2) : 199-208. doi: 10.3934/amc.2011.5.199

[8]

Peter Boyvalenkov, Maya Stoyanova. New nonexistence results for spherical designs. Advances in Mathematics of Communications, 2013, 7 (3) : 279-292. doi: 10.3934/amc.2013.7.279

[9]

Xiangmin Zhang. User perceived learning from interactive searching on big medical literature data. Big Data & Information Analytics, 2017, 2 (5) : 1-16. doi: 10.3934/bdia.2017019

[10]

Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder. Combinatorial batch codes and transversal matroids. Advances in Mathematics of Communications, 2010, 4 (3) : 419-431. doi: 10.3934/amc.2010.4.419

[11]

Yunmei Lu, Mingyuan Yan, Meng Han, Qingliang Yang, Yanqing Zhang. Privacy preserving feature selection and Multiclass Classification for horizontally distributed data. Mathematical Foundations of Computing, 2018, 1 (4) : 331-348. doi: 10.3934/mfc.2018016

[12]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

[13]

Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003

[14]

Bastian Laubner, Dierk Schleicher, Vlad Vicol. A combinatorial classification of postsingularly finite complex exponential maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 663-682. doi: 10.3934/dcds.2008.22.663

[15]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[16]

Cuiling Fan, Koji Momihara. Unified combinatorial constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2014, 8 (1) : 53-66. doi: 10.3934/amc.2014.8.53

[17]

Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165

[18]

Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040

[19]

Feng Yang, Kok Lay Teo, Ryan Loxton, Volker Rehbock, Bin Li, Changjun Yu, Leslie Jennings. VISUAL MISER: An efficient user-friendly visual program for solving optimal control problems. Journal of Industrial & Management Optimization, 2016, 12 (2) : 781-810. doi: 10.3934/jimo.2016.12.781

[20]

Dean Crnković, Bernardo Gabriel Rodrigues, Sanja Rukavina, Loredana Simčić. Self-orthogonal codes from orbit matrices of 2-designs. Advances in Mathematics of Communications, 2013, 7 (2) : 161-174. doi: 10.3934/amc.2013.7.161

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]