Foundations of Privacy - First Semester 2015/6

Instructor: Moni Naor

When:     Monday 16:15--18:00
Where:    Ziskind 1
First meeting:   October 26th 2015

         Lectures           Homework         


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.


Material from previous editions of the course:

Homework:

·        First assignment due April 15th

Lectures:

·        Lecture 1 (March 11th 2012): Administrivia, Cryptography and Privacy, Attacks on Privacy. Beginning of OT

o   see Lindell's writeup for a brief intro on SFE

·        Lecture 2 (March 18, 2012): Slides OT and Secure Function Evaluation. How to ask embarrassing questions?

o   Stanley L. Warner, Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias, Journal of the American Statistical Association, Vol. 60(309) ,  1965, pp. 63-69.

·        Lecture 3 (March 25, 2012): Slides of SFE and beginning of impossibility proof

o   Dwork and Naor, On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy

·        Lecture 4 (April 1st, 2012): Slides of Impossibility proof and begin differential privacy

·        Lecture 5 (April 15th, 2012): Slides of Differential privacy: (im)possibility bounds and Laplacian noise

o   Dinur and Nissim, Revealing information while preserving privacy

o   Dwork, McSherry, Nissim and Smith,  Differential Privacy

·        Lecture 6 (April 22nd, 2012): Slides of Composition, Global and Local Sensitivity, the Exponential Mechanism

o   Dwork, Rothblum and Vadhan, Boosting and Differential Privacy

o   Nissim, Raskhodnikova and Smith, Smooth Sensitivity and Sampling in Private Data Analysis

o   McSherry and Talwar, Mechanism Design via Differential Privacy

·        Lecture 7 (April 29th, 2012): Slides of Exponential Mechanism, Net Mechanism (BLR) and Private Multiplicative Weights

o   Blum, Ligett and Roth, A Learning Theory Approach to Non-Interactive Database Privacy

o   Hardt and Rothblum, A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis

·        Lecture 8 (May 6th, 2012): Slides of Exponential Mechanism, Net Mechanism (BLR) and Private Multiplicative Weights

·        Lecture 9 (May 20th, 2012): finish proof of PMW. Privacy in combinatorial optimization

o   Gupta, Ligett, McSherry, Roth and Talwar, Differentially Private Combinatorial Optimization   

 

Papers for projects

o    Reed,  Aviv,  Wagner, Haeberlen, Pierce and  Smith, Differential Privacy for Collaborative Security

·         פרטיות בישראל

o        המאגר הביומטרי: אלי ביהם אל תיתנו את האצבע למאגר

o        כרטיס הרב קו  ותל אופן: קול ההגיון, IT MARKER, ידיעה על מאגר המידע של תל אופן

o        מצלמות במרחב הציבורי: דיון בוועדת המדע והטכנולוגיה של הכנסת, ההיתר לGoogle לצלם את Street View

o        המועצה הציבורית להגנה על פרטיות

 

Lectures (2010):

 

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
Naor, Segev and Wieder,  History-Independent Cuckoo Hashing
Moran, Naor and Segev, Deterministic History-Independent Strategies for Storing Information on Write-Once Memories

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 TalwarThe 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, BonehNissenbaum and BarocasAdnostic: 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

 

Related Courses and Workshops: