COMS E6261:  Advanced Cryptography

Spring 2010: Data Privacy

Main Page Project Page Lecture Topics and Readings

Additional Papers by Topic

--This page is still under construction (feel free to suggest additional papers of interest)--

• General surveys and slides
  Ipam workshop
  New York area Crypto day (3/11/10)
• Definition of differential privacy:
  Differential Privacy. C. Dwork. ICALP 06. [Lecture 2]
  On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy. C. Dwork, M. Naor
  Our Data, Ourselves: Privacy via Distributed Noise Generation. C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, M. Naor. EUROCRYPT 06.
• Output perturbation (noise addition)
  Revealing Information while preserving privacy. I. Dinur, K. Nissim. PODS 03. [Lecture 3] (also appears in the "Lower bounds" category below)
  Calibrating Noise Sensitivity in Private Data Analysis. C. Dwork, F. McSherry, K. Nissim, A. Smith. TCC 06. [Lecture 4]
  Practical Privacy: The SuLQ Framework. A. Blum, C. Dwork, F. McSherry, K. Nissim. PODS 05. [Lecture 4]
• Negative results/Lower bounds
  Revealing Information while preserving privacy. I. Dinur, K. Nissim. PODS 03. [Lecture 3] (also appears in the "Output perturbation" category above)
  The price of privacy and the limits of LP decoding. C. Dwork, F. McSherry, K. Talwar. STOC 07.
  New Efficient Attacks on Statistical Disclosure Control Mechanisms. C. Dwork, S. Yekhanin. CRYPTO 08.
  On the Geometry of Differential Privacy. STOC 10 (to appear).
  The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows. S. Kasiviswanathan, M. Rudelson, A. Smith, J. Ullman. STOC 10 (to appear).
• Exponential mechanism and beyond
  Mechanism Design via Differential Privacy. F. McSherry, K. Talwar. FOCS 07.
  A Learning Theory Approach to Non-Interactive Database Privacy. A. Blum, K. Ligett, A. Roth. STOC 08. (also appears in the "Learning" category below)
  What Can We Learn Privately? S. Kasiviswanathan, H. Lee, K. Nissim, S. Raskhodnikova, A. Smith FOCS 08 (also appears in the "Learning" category below)
  The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries. A. Roth, T. Roughgarden. STOC 10 (to appear)
• Learning and differential privacy
  What Can We Learn Privately? S. Kasiviswanathan, H. Lee, K. Nissim, S. Raskhodnikova, A. Smith FOCS 08 (also appears in the "Exponential Mechanism" category above)
  Bounds on the Sample Complexity for Private Learning and Private Data Release. A. Beimel, S. P. Kasiviswanathan, K. Nissim. TCC 10
  A Learning Theory Approach to Non-Interactive Database Privacy. A. Blum, K. Ligett, A. Roth. STOC 08. (also appears in the "Exponential Mechanism" category above)
• Computational complexity in differential privacy
  On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results. C. Dwork, M. Naor, O. Reingold, G. Rothblum, S. Vadhan. STOC 09
  Computational Differential Privacy. I. Mironov, O. Pandey, O. Reingold, S. Vadhan. CRYPTO 09
  PCPs and the Hardness of Generating Synthetic Data. J. Ullman, S. Vadhan. ECCC 10
• Differential privacy in a distributed setting
  Distributed private data analysis: Simultaneously solving how and what. A. Beimel, K. Nissim, and E. Omri. CRYPTO 08
  See also collaborative filtering papers in the non-differential privacy list below.
• Other approaches to privacy, that are not differential privacy
  Enhancing privacy and preserving accuracy of a distributed collaborative filtering. S. Berkovsky, Y. Eytani, T. Kuflik, F. Ricci. 07
  Private distributed collaborative filtering using estimated concordance measures. N. Lathia, S. Hailes, L. Capra. 07
  Preserving privacy in collaborative filtering through distributed aggregation of offline profiles. R. Shokri, P. Pedarsani, G. Theodorakopoulos, J.-P. Hubaux. 09