Privacy in a Mobile-Social World

CompSci 590.03, Fall 2012

Instructor: Ashwin Machanavajjhala
When: 1:25 PM - 2:40 PM Wednesdays and Fridays
D106, LSRC
Office Hours: By appointment (send email to


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.

This project-oriented course focuses on the foundations of statistical privacy -- the problem of disclosing aggregate statistics about data collected from individuals while ensuring that individual level sensitive properties are not disclosed. The course will cover fundamentals of defining privacy and developing efficient algorithms for enforcing privacy, as well as the challenges in developing privacy preserving algorithms in real-world applications -- publishing social science data (like in the US Census), continuous user activity monitoring (like in search logs, location traces, energy monitoring), social networks, recommendation engines and targeted advertising.

Prerequisites: The course is open to interested graduate and undergraduate students with sufficient mathematical maturity. Basic knowledge in algorithms, proof techniques, and probability will be assumed. 




Wed, Aug 29

Fri, Aug 31
Introduction and Attacks on privacy (slides)
"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
Wed, Sep 5
De-anonymization (slides)
"Robust deanonymization of Sparse Datasets (Netflix Prize Data)",
   A. Narayanan, V. Shmatikov, IEEE S&P 2008
Optional: "Wherefore Art Thou R3579X?",
   L. Backstrom, C. Dwork, J. Kleinberg, WWW 2007


Fri, Sep 7
k-Anonymity + algorithms (slides)
"Incognito: Efficient full domain k-anonymity",
   K. Lefevre, D. DeWitt, R. Ramakrishnan, SIGMOD  2005
Optional: "k-anonymity: a model for protecting privacy",
   L. Sweeney, IJUFKS 2002
Wed, Sep 12
Anonymity in Social Networks (slides)
"Resisting Structural Re-identification in Anonymized Social Networks"
M. Hay, G. Miklau, D. Jensen, D. Towsley, C. Li VLDBJ 2010


Fri, Sep 17
Adversaries and Background Knowledge (slides)
"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
Wed, Sep 19
Simulatability (or "the adversary knows the privacy mechanism") (slides)
"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


Fri, Sep 21
Differential privacy, Laplace Mechanism and Composability (slides)
"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
Wed, Sep 26
Exponential and median mechanisms (slides)

"Mechanism design via differential privacy"
F. McSherry, K. Talwar FOCS 2008
Optional: "Interactive Privacy via Median Mechanism", A. Roth, T. Roughgarden, STOC 2010
Fri, Sep 28
Smooth Sensitivity and Sample Aggregate Framework (slides)
(Deadline for choosing project topics)
"Smooth Sensitivity and Sampling in Private Data Analysis", K. Nissim, S. Raskhodnikova, A. Smith STOC 2007
Optional: "Privacy-preserving statistical estimation with optimal convergence rates", A. Smith STOC 2011
Wed, Oct 3
Optimization utility for differential privacy - constrained inference (slides)
"Boosting the Accuracy of Differentially Private Histograms
Through Consistency
", M. Hay, V. Rastogi, G. Miklau, D. Suciu, PVLDB 2010
Fri, Oct 5
Optimization utility for differential privacy - Query strategies (Wavelet and Matrix Mechanisms) (slides) "Differential Privacy via Wavelet Transforms",
X. Xiao, G. Wang, J. Gehrke ICDE 2009
Optional: "Optimizing Linear Counting Queries Under Differential Privacy"
C. Li, M. Hay, V. Rastogi, G. Miklau, A. McGregor PODS 2010
Wed, Oct 10
Sparse Vector Technique (slides)
"The Sparse Vector Technique" Lecture Notes, Aaron Roth
Fri, Oct 12
Multiplicative Weights Algorithms (slides)(proofs)
(Deadline for submitting project proposal)
"A simple and practical algorithm for differentially private data release", F. McSherry, K. Ligett, M. Hardt, NIPS 2012
Optional: "A Multiplicative Weights Mechanism for Privacy Preserving Data Analysis" M. Hardt, G. Rothblum, FOCS 2010
Wed, Oct 17
Implementing Differential Privacy Privately (slides)

"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


Fri, Oct 19
No Free Lunch Theorem (slides)
"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
Wed, Oct 24
Customizing privacy definitions for realistic applications (slides)
"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


Fri, Oct 26
Differential Privacy in the US Census (slides)
"Privacy: Theory meets practice on the map", A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, L. Vilhuber, ICDE 2008

Wed Oct 31
Fri, Nov 2
Guest Lecture: Jerry Reiter, Confidentiality in the US Census, and synthetic data generation
"Estimating Risks of Identification Disclosure in Partially Synthetic Data", Reiter & Mitra, JPC '09
Wed, Nov 7
Publishing Search Logs  (slides)
"User 4xxxxx9: Anonymizing Query Logs", E. Adar, WWW 2007
"Publishing Search Logs", M. Gotz, A. Machanavajjhala, G. Wang, X. Xiao, J, Gehrke, TKDE 2012
Fri, Nov 9
Cloaking/Mixes for Location Privacy (slides) "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
Wed, Nov 14
Recommendation Engines (slides)
"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
Fri, Nov 16
Targeted Advertising
(Deadline for midterm report)
"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

Wed, Nov 21
NO CLASS - thanksgiving break

Fri, Nov 23
NO CLASS - thanksgiving break
Wed, Nov 28
Privacy in Machine Learning
Functional Mechanism: Regression Analysis under Differential Privacy
J.  Zhang, Z. Zhang, X. Xiao, Y. Yang, M. Winslett, PVLDB 2012
Optional: "Differentially Private Empirical Risk Minimization", K. Chaudhuri, C. Monteleoni, A. Sarwate JMLR 2011
Fri, Nov 31
Privacy and Economics
"A Theory of Pricing Private Data" C. Li, D.  Li, G. Miklau, D. Suciu Corr 2012
Optional: "Privacy Consensus in Anonymization Systems via Game Theory", R. Karimi Adl, M. Askari, K. Barker, R. Safavi-Naini DBSec 2012
Wed, Dec 5
Project Presentations
(Deadline for final report)

Fri, Dec 7
Project Presentations