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