Relationship privacy: output perturbation for queries with joins

ABSTRACT

We study privacy-preserving query answering over data containing relationships. A social network is a prime example of such data, where the nodes represent individuals and edges represent relationships. Nearly all interesting queries over social networks involve joins, and for such queries, existing output perturbation algorithms severely distort query answers. We propose an algorithm that significantly improves utility over competing techniques, typically reducing the error bound from polynomial in the number of nodes to polylogarithmic. The algorithm is, to the best of our knowledge, the first to answer such queries with acceptable accuracy, even for worst-case inputs.

The improved utility is achieved by relaxing the privacy condition. Instead of ensuring strict differential privacy, we guarantee a weaker (but still quite practical) condition based on adversarial privacy. To explain precisely the nature of our relaxation in privacy, we provide a new result that characterizes the relationship between ε-indistinguishability~(a variant of the differential privacy definition) and adversarial privacy, which is of independent interest: an algorithm is ε-indistinguishable iff it is private for a particular class of adversaries (defined precisely herein). Our perturbation algorithm guarantees privacy against adversaries in this class whose prior distribution is numerically bounded.

REFERENCES

• 1: Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242598]
• 2: H. W. Block, T. H. Savits, and M. Shaked. Some concepts of negative dependence. In Ann. of Prob., 1982.
• 3: A. Campan and T. M. Truta. A clustering approach for data and structural anonymity in social networks. In PinKDD, 2008.
• 4: C. Dwork. Differential privacy. In ICALP, 2006.
• 5: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006.
• 6: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 7: Alexandre Evfimievski , Ronald Fagin , David P. Woodruff, Epistemic privacy, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376941]
• 8: Tomás Feder , Milena Mihail, Balanced matroids, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.26-38, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129716]
• 9: Full version: http://www.cs.washington.edu/homes/vibhor/relationship_privacy.pdf.
• 10: Srivatsava Ranjit Ganta , Shiva Prasad Kasiviswanathan , Adam Smith, Composition attacks and auxiliary information in data privacy, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401926]
• 11: Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Philipp Weis, Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453873]
• 12: Kun Liu , Evimaria Terzi, Towards identity anonymization on graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376629]
• 13: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 14: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 15: M. Newman. The structure and function of complex networks. SIREV: SIAM Review, 2003.
• 16: Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, Smooth sensitivity and sampling in private data analysis, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250803]
• 17: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 18: J. G. Shanthikumar and H.-W. Koo. On uniform conditional stochastic order conditioned on planar regions. In Ann. of Probab., 1990.
• 19: V. H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures & Algorithms, v.20 n.3, p.262-316, May 2002 [doi>10.1002/rsa.10032]
• 20: X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In SIAM, 2007.
• 21: E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In PinKDD, 2007.
• 22: Bin Zhou , Jian Pei, Preserving Privacy in Social Networks Against Neighborhood Attacks, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.506-515, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497459]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Security, Theory

Keywords:
join queries, output perturbation, privacy preserving data mining, private data analysis, sensitivity, social networks