Smooth sensitivity and sampling in private data analysis

ABSTRACT

We introduce a new, generic framework for private data analysis.The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.Our framework allows one to release functions f of the data withinstance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x. The new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy.

Our framework raises many interesting algorithmic questions. Namely,to apply the framework one must compute or approximate the smoothsensitivity of f on x. We show how to do this efficiently for several different functions, including the median and the cost ofthe minimum spanning tree. We also give a generic procedure based on sampling that allows one to release f(x) accurately on manydatabases x. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known orwhen f is given as a black box. We illustrate the procedure by applying it to k-SED (k-means) clustering and learning mixtures of Gaussians.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 4: S. Chawla, C. Dwork, F. McSherry, A. Smith, and H. Wee. Toward privacy in public databases. In Theory of Cryptography Conference (TCC), pages 363--385, 2005.
• 5: S. Chawla, C. Dwork, F. McSherry, and K. Talwar. On the utility of privacy-preserving histograms. In 21st Conference on Uncertainty in Artificial Intelligence (UAI), 2005.
• 6: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 7: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 8: C. Dwork. Differential privacy. In ICALP, pages 1--12, 2006.
• 9: C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486--503, 2006.
• 10: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265--284, 2006.
• 11: C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO, pages 528--544, 2004.
• 12: 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]
• 13: J. Gehrke. Models and methods for privacy-preserving data publishing and analysis (tutorial slides). In Twelfth Annual SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2006), 2006.
• 14: Ramgopal R. Mettu , C. Greg Plaxton, Optimal Time Bounds for Approximate Clustering, Machine Learning, v.56 n.1-3, p.35-60 [doi>10.1023/B:MACH.0000033114.18632.e0]
• 15: Rafail Ostrovsky , Yuval Rabani , Leonard J. Schulman , Chaitanya Swamy, The Effectiveness of Lloyd-Type Methods for the k-Means Problem, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.165-176, October 21-24, 2006 [doi>10.1109/FOCS.2006.75]
• 16: A. Slavkovic. Statistical Disclosure Limitation Beyond the Margins: Characterization of Joint Distributions for Contingency Tables. Ph.D. Thesis, Department of Statistics, Carnegie Mellon University, 2004.
• 17: Latanya Sweeney, Privacy-enhanced linking, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.72-75, December 2005 [doi>10.1145/1117454.1117464]
• 18: Santosh Vempala , Grant Wang, A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, v.68 n.4, p.841-860, June 2004 [doi>10.1016/j.jcss.2003.11.008]
• 19: Van H. Vu, On the concentration of multivariate polynomials with small expectation, Random Structures & Algorithms, v.16 n.4, p.344-363, July 2000 [doi>10.1002/1098-2418(200007)16:4<344::AID-RSA4>3.0.CO;2-5]
• 20: L.N. Wasserstein. Markov processes over denumerable products of spaces describing large systems of automata. Probl. Inform. Transmission, 5:47--52, 1969.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Security, Theory

Keywords:
clustering, output perturbation, privacy preserving data mining, private data analysis, sensitivity