Instructor: Moni Naor
When: Monday
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: The course will be based on reading the manuscript "The Algorithmic Foundations
of Differential Privacy" by Dwork and Roth. Students should read the appropriate chapter before each class.
o
see Lindell's writeup for a brief
intro on SFE
o Nissim, Raskhodnikova and Smith, Smooth
Sensitivity and Sampling in Private Data Analysis
o
McSherry and Talwar, Mechanism
Design via Differential Privacy
o Reed, Aviv, Wagner, Haeberlen, Pierce and Smith, Differential Privacy for Collaborative Security
· פרטיות בישראל
o
המאגר
הביומטרי: אלי ביהם
אל תיתנו
את האצבע
למאגר
o
כרטיס
הרב קו ותל
אופן:
קול
ההגיון,
IT MARKER, ידיעה
על מאגר המידע
של תל אופן
o
מצלמות
במרחב
הציבורי: דיון
בוועדת המדע
והטכנולוגיה
של הכנסת, ההיתר
לGoogle לצלם את Street View
o
המועצה
הציבורית
להגנה על
פרטיות
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
·
Arvind Narayanan: 33 Bits of Entropy
·
Freedom to
Tinker (A collective Blog from Princeton)
·
Tech at FTC,
Ed Felten, Chief Technologist at the FTC (Federal Trade Committee) and professor at
Princeton
·
Dana Boyd: Apophenia
In Hebrew:
· האח הקטןאבנר פינצ'וק:
· Intellect or Insanityיהונתן קלינגר:
Advice
on giving Academic Talks
Below is a compilation of source on giving talks. Some of it humorous and some contradicts each other
· Oral Presentation Advice by Mark D. Hill
· Giving an Academic Talk by Jonathan Shewchuk
· Pointers on giving a talk by David Messerschmitt
· How to give a good talk by Hany Farid