Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We show by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators. Our algorithms use a new paradigm for differentially private mechanisms, which we call Propose-Test-Release (PTR), and for which we give a formal definition and general composition theorems.

REFERENCES

• 1: 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]
• 2: Avrim Blum , Katrina Ligett , Aaron Roth, A learning theory approach to non-interactive database privacy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374464]
• 3: J. M. Borwein and A. S. Lewis. Convex analysis and nonlinear optimization, theory and examples. Springer, 2006.
• 4: C. Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP)(2), pages 1--12, 2006.
• 5: C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: privacy via distributed noise generation. In Advances in Cryptology: Proceedings of EUROCRYPT, pages 486--503, 2006.
• 6: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference, pages 265--284, 2006.
• 7: C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of CRYPTO 2004, volume 3152, pages 528--544, 2004.
• 8: D. Freedman and P. Diaconis. On the histogram as a density estimator: l₂ theory. Z. Wahrscheinlichkeitstheorie verw. Gebiete, 57:453--476, 1981.
• 9: F. Hampel, E. Ronchetti, P. Rousseeuw, , and W. Stahel. Robust Statistics: The Approach Based on Influence Functions. John Wiley, New York, 1986.
• 10: J. Heitzig. The "jackknife" method: Confidentiality protection for complext statistical analyses. In Joint UNECE/Eurostat work session on statistical data confidentiality, 2005.
• 11: P. Huber. Robust statistics. John Wiley &#;amp; Sons, 1981.
• 12: J. Kiefer and J. Wolfowitz. On the deviations of the empiric distribution function of vector chance variables. Transactions of the American Mathematical Society, 87:173--186, January 1958.
• 13: Frank McSherry , Kunal Talwar, Mechanism Design via Differential Privacy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.94-103, October 21-23, 2007 [doi>10.1109/FOCS.2007.41]
• 14: 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]
• 15: D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984.
• 16: A. Smith. Efficient, differentially private point estimators, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Security, Theory

Keywords:
differential privacy, local sensitivity, propose-test-release paradigm, robust statistics