Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Calibrating Noise to Sensitivity in Private Data Analysis

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 3876))

Included in the following conference series:

Abstract

We continue a line of research initiated in [10,11]on privacy-preserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query functionf mapping databases to reals, the so-calledtrue answer is the result of applyingf to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user.

Previous work focused on the case of noisy sums, in whichf = ∑ig(xi), wherexi denotes theith row of the database andg maps database rows to [0,1]. We extend the study to general functionsf, proving that privacy can be preserved by calibrating the standard deviation of the noise according to thesensitivity of the functionf. Roughly speaking, this is the amount that any single argument tof can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case.

The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.

The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI:10.1007/978-3-540-32732-5_32

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Adam, N.R., Wortmann, J.C.: Security-control methods for statistical databases: a comparative study. ACM Computing Surveys 25(4) (December 1989)

    Google Scholar 

  2. Agrawal, D., Aggarwal, C.C.: On the design and quantification of privacy preserving data mining algorithms. In: Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York (2001)

    Google Scholar 

  3. Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: Chen, W., Naughton, J.F., Bernstein, P.A. (eds.) SIGMOD Conference, pp. 439–450. ACM, New York (2000)

    Google Scholar 

  4. Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3cnf properties are hard to test. In: STOC, pp. 345–354. ACM, New York (2000)

    Google Scholar 

  5. Web page for the Bertinoro CS-Statistics workshop on privacy and confidentiality (July 2005), Available from,http://www.stat.cmu.edu/~hwainer

  6. Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: The sulq framework. In: PODS (2005)

    Google Scholar 

  7. Chawla, S., Dwork, C., McSherry, F., Smith, A., Wee, H.: Toward privacy in public databases. In: Theory of Cryptography Conference (TCC), pp. 363–385 (2005)

    Google Scholar 

  8. Chawla, S., Dwork, C., McSherry, F., Talwar, K.: On the utility of privacy-preserving histograms. In: 21st Conference on Uncertainty in Artificial Intelligence (UAI) (2005)

    Google Scholar 

  9. Denning, D.E.: Secure statistical databases with random sample queries. ACM Transactions on Database Systems 5(3), 291–315 (September 1980)

    Article MATH  Google Scholar 

  10. Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 202–210 (2003)

    Google Scholar 

  11. Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 528–544. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  12. Evfimievski, A.V., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: Proceedings of the Twenty- Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 211–222 (2003)

    Google Scholar 

  13. Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)

    Article MathSciNet MATH  Google Scholar 

  14. Roque, G.: Masking microdata with mixtures of normal distributions. University of California, Riverside (2000); Doctoral Dissertation

    Google Scholar 

  15. Sweeney, L.: k-anonymity: A model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems 10(5), 557–570 (2002)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Research, Silicon Valley

    Cynthia Dwork & Frank McSherry

  2. Ben-Gurion University, Israel

    Kobbi Nissim

  3. Weizmann Institute of Science, Israel

    Adam Smith

Authors
  1. Cynthia Dwork

    You can also search for this author inPubMed Google Scholar

  2. Frank McSherry

    You can also search for this author inPubMed Google Scholar

  3. Kobbi Nissim

    You can also search for this author inPubMed Google Scholar

  4. Adam Smith

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. IBM Research, Hawthorne, NY, USA

    Shai Halevi

  2. IBM T.J.Watson Research Center, Hawthorne, NY, USA

    Tal Rabin

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dwork, C., McSherry, F., Nissim, K., Smith, A. (2006). Calibrating Noise to Sensitivity in Private Data Analysis. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_14

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp