Instructor: Moni Naor
When: Sunday
Where: Ziskind
1
First meeting:
DESCRIPTION: The availability of fast and cheap computers coupled
with massive storage devices has enabled the collection and mining of data on a
scale previously unimaginable. This opens the door to potential abuse regarding
individuals' information. There has been considerable research exploring the
tension between utility and privacy in this context.
The goal of this course is to explore
techniques and issues related to data privacy. In particular to study:
PREREQUISITES: Students are expected to be familiar with algorithms,
data structures, probability theory, and linear algebra, at an undergraduate
level. No prior cryptography course will be assumed.
REQUIREMENTS: Students are required to present one set of the papers
and the background leading to it, write a summary as well as attend all
meeting, read all assigned papers, and participate in class discussion. In
addition there will be a few homework sets. You may discuss the problems with
other students, but the write-up should be individual.
|
Lecture 1 (March 15 2010)
Slides |
Administrivia,
Cryptography and Privacy, Attacks on Privacy, Impossibility of achieving
Privacy in with general auxiliary information. |
see Lindell's writeup for a
brief intro on SFE Narayanan Shmatikov on breaking the Netflix challenge |
|
Lecture 2 (March 22 2010)
Slides |
Finish Impossibility of achieving Privacy in with general
auxiliary information, differential privacy |
Dwork-Naor paper on impossibility Shaltiel's survey on extractors Dwork, McSherry, Nissim and Smith Differential Privacy |
|
Lecture 3 (April 12 2010)
Slides |
Randomized Response, examples of noisy response:
histograms, k-means. Global and Local Sensitivity. |
Nissim, Raskhodnikova and Smith, Smooth
Sensitivity and Sampling in Private Data Analysis Blum, Dwork, McSherry and Nissim, Practical Privacy: The SuLQ Framework |
|
Lecture 4 (April 26 2010)
Slides |
The exponential mechanism, counting queries and the Blum Ligett Roth algorithm |
McSherry and Talwar, Mechanism
Design via Differential Privacy Blum, Ligett and Roth, A Learning Theory Approach to Non-Interactive Database Privacy. |
|
Lecture 5 (May 3 2010)
Slides |
Answering predicate queries efficiently Cryptographic lower bounds |
Dwork, Naor, Reingold, Rothblum, and Vadhan, On the Complexity of
Differentially Private Data Release |
|
Lecture 6 (May 10 2010)
Slides |
Cryptographic lower bounds and Tracing Traitors Interactive mechanisms |
Dwork, Naor, Reingold, Rothblum, and Vadhan, On the Complexity of
Differentially Private Data Release Roth and Roughgarden, Interactive Privacy via the Median Mechanism |
|
Lecture 7 (May 17 2010)
Slides |
Interactive mechanisms Changing Data: Continual Output |
Roth and Roughgarden,
Interactive Privacy
via the Median Mechanism |
|
Lecture 8 (May 24 2010)
Slides |
Changing Data: Continual Output and Pan Privacy |
Dwork, Naor, Pitassi
and Rothblum, Differential Privacy Under Continual Observation Dwork, Naor, Pitassi, Rothblum, and Yekhanin, Pan-Private Streaming Algorithms |
|
Lecture 9 (May 31 2010)
Slides |
History-Independent Hashing Schemes (and applications) |
Naor and Teague Anti-persistence: History-Independent
Data Structures |
|
Lecture 10 (June 7 2010)
Slides |
Changing Data: Continual Output and Pan Privacy |
Dwork, Naor, Pitassi
and Rothblum, Differential Privacy Under Continual Observation Dwork, Naor, Pitassi, Rothblum, and Yekhanin, Pan-Private Streaming Algorithms |
|
Lecture 11 (June 14 2010)
Slides
|
Reconstructing databases from counting queries |
Dinur and Nissim, Revealing information while
preserving privacy Dwork and Yekhanin, New Efficient
Attacks on Statistical Disclosure Control Mechanisms |
|
Student presentations: o Guy
Katz: RFID o Ilan Ko: Deanonyming
network
|
Narayanan and Shmatikov.
De-anonymizing Social Networks |
|
|
Lecture 12 (June 21 2010)
Slides
|
Reconstructing databases from counting queries. Private Learning Private Approximation |
Dinur and Nissim, Revealing information while
preserving privacy Dwork and Yekhanin, New Efficient
Attacks on Statistical Disclosure Control Mechanisms Kasiviswanath, Lee, Nissim,
Raskhodnikova and Smith, What
Can We Learn Privately?
Gupta,
Ligett, McSherry, Roth
and Talwar, Differentially Private Approximation
Algorithms |
|
Lecture 13 (June 28 2010)
Slides
|
Linear Programming Decoding (e,d)-Differential Privacy Computational Differential Privacy
|
Dwork, McSherry and Talwar, The price of
privacy and the limits of LP decoding Hardt and Talwar, On the
Geometry of Differential Privacy
|
|
Student presentations: o Tomer Ashur: Collection and aggregation of
IP addresses over the Internet o Itay Gonshorovitz:
Privacy and
Targeted Online Advertising
|
|
Toubiana, Narayanan, Boneh, Nissenbaum and Barocas, Adnostic: Privacy Preserving Targeted Advertising |
Background Material
Systems:
Fiction
Blogs related to privacy