Offerings:
Fall 2013, CompSci 590.03, W/F 1:25 - 2:40 PM, LSRC D106 (course page)
Fall 2012, CompSci 590.03, W/F 1:25 - 2:40 PM, LSRC D106 (course page)
Overview: Terabytes of data about individuals are collected and analyzed daily through the use of mobile and social applications. Disseminating the data or results of analysis over this data to third parties (e.g., researchers or advertisers) has tremendous scientific and commercial value. However, such data dissemination can lead to potential identification of individuals, and disclosure of their sensitive information.
Administrivia:
There are no exams.
Each lecture will be based on one or two recent publications. Students are expected to read the assigned papers before class and will be graded based on class participation.
Students must complete a class project either individually or in groups of size 2-3. Projects can focus on developing new theory/algorithms, or on implementing/adapting known algorithms to a real application setting. Details on projects are forthcoming.
Topics Covered:
Topic |
Readings |
INTRODUCTION & DE-ANONYMIZATION |
|
"Privacy", J. DeCew, The Stanford Encyclopedia of Philosophy
(Fall 2012 Edition), Edward N. Zalta (ed.) "A Face is exposed for AOL Searcher No. 4417749", New York Times, Aug 2006 "How Companies Learn your Secrets", New York Times, Feb 2012 "Robust deanonymization of Sparse Datasets (Netflix Prize Data)", A. Narayanan, V. Shmatikov, IEEE S&P 2008 "Wherefore Art Thou R3579X?", L. Backstrom, C. Dwork, J. Kleinberg, WWW 2007 |
|
ANONYMITY |
|
"Incognito: Efficient full domain k-anonymity", K. Lefevre, D. DeWitt, R. Ramakrishnan, SIGMOD 2005 "k-anonymity: a model for protecting privacy", L. Sweeney, IJUFKS 2002 "Resisting Structural Re-identification in Anonymized Social Networks" M. Hay, G. Miklau, D. Jensen, D. Towsley, C. Li VLDBJ 2010 |
|
BEYOND ANONYMITY |
|
"L-diversity: privacy beyond k-anonymity" A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam, ICDE 2006 "T-closeness: privacy beyond k-anonymity and l-diversity" N. Li, T. Li, S. Venkatasubramanian "Simulatable Auditing", K. Kenthapadi, N. Mishra, K. Nissim PODS 2005 "Minimality Attack in Privacy Preserving Data Publishing", R. C. Wong, A. Fu, K. Wang, J. Pei, VLDB 2007 |
|
DIFFERENTIAL PRIVACY |
|
Differential privacy, Composability and basic mechanisms |
"Calibrating Noise to Sensitivity in Private Date Analysis" C. Dwork, F. McSherry, K. Nissim, A.Smith TCC 2006 "Composition Attacks and Auxiliary Information in Data Privacy" S. Ganta, S. Kasiviswanathan, A. Smith KDD 2008 "Mechanism design via differential privacy" F. McSherry, K. Talwar FOCS 2008 "Interactive Privacy via Median Mechanism", A. Roth, T. Roughgarden, STOC 2010 "Smooth Sensitivity and Sampling in Private Data Analysis", K. Nissim, S. Raskhodnikova, A. Smith STOC 2007 "Privacy-preserving statistical estimation with optimal convergence rates", A. Smith STOC 2011 |
Optimization utility for differential privacy |
"Boosting the Accuracy of Differentially Private Histograms Through Consistency", M. Hay, V. Rastogi, G. Miklau, D. Suciu, PVLDB 2010 "Differential Privacy via Wavelet Transforms", X. Xiao, G. Wang, J. Gehrke ICDE 2009 "Optimizing Linear Counting Queries Under Differential Privacy" C. Li, M. Hay, V. Rastogi, G. Miklau, A. McGregor PODS 2010 "The Sparse Vector Technique" Lecture Notes, Aaron Roth "A simple and practical algorithm for differentially private data release", F. McSherry, K. Ligett, M. Hardt, NIPS 2012 "A Multiplicative Weights Mechanism for Privacy Preserving Data Analysis" M. Hardt, G. Rothblum, FOCS 2010 |
Implementing Differential Privacy Privately |
"Airavat: Security and Privacy for MapReduce", I. Roy, S. Setty, A. Kilzer, V. Shmatikov, E. Witchel "Differential Privacy Under Fire". Haeberlen, Pierce, and Narayan, 2011 "Gupt: Privacy Preserving Data Analysis Made Easy", P. Mohan, A. Thakurtha, E. Shi, D. Song, D. Culler, SIGMOD 2012 |
BEYOND DIFFERENTIAL PRIVACY |
|
"No Free Lunch in Data Privacy", D. Kifer, A. Machanavajjhala SIGMOD 2011 Optional: "The Case for Differential Privacy" C. Dwork, M, Naor, Journal of Privacy and Confidentiality 2010 "A rigorous and customizable framework for privacy", D. Kifer, A. Machanavajjhala PODS 2012 Optional: "Crowd-Blending Privacy", J. Gehrke, M. Hay, E. Liu, R. Pass, CRYPTO 2012 Optional: "Data Publishing against Realistic Adversaries", A. Machanavajjhala, J. Gehrke, M. Gotz, PVLDB 2009 |
|
APPLICATIONS |
|
US Census | "Privacy: Theory meets practice on the map", A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, L. Vilhuber, ICDE 2008 "Estimating Risks of Identification Disclosure in Partially Synthetic Data", Reiter & Mitra, JPC '09 |
Publishing Search Logs |
"User 4xxxxx9: Anonymizing Query Logs", E. Adar, WWW 2007 "Publishing Search Logs", M. Gotz, A. Machanavajjhala, G. Wang, X. Xiao, J, Gehrke, TKDE 2012 |
Location Privacy | "Location Privacy in Pervasive Computing", A. Beresford, F. Stajano, 2003 "Preserving privacy in gps traces via uncertainty-aware path cloaking", B. Hoh, M. Gruteser, H. Xiong , A. Alrabby, ACM CCS 2007 |
Recommendation Systems & Targeted Advertising |
"Differentially Private Recommender Systems", F. McSherry, I. Mironov KDD 2009 "Personalized Social Recommendations - Accurate or Private?", A. Machanavajjhala, A. Korolova, A. Das Sarma PVLDB 2011 "Adnostic: Privacy Preserving Targeted Advertising", V. Toubiana, A. Narayanan, D. Boneh, H. Nissenbaum, S. Barocas NDSS 2010 "Privacy Violations Using Microtargeted Ads", A. Korolova JPC 2011 |
Machine Learning and Auctions |
Functional Mechanism: Regression Analysis under Differential Privacy "Differentially Private Empirical Risk Minimization", K. Chaudhuri, C. Monteleoni, A. Sarwate JMLR 2011 "A Theory of Pricing Private Data" C. Li, D. Li, G. Miklau, D. Suciu Corr 2012 |