Instructor: Moni Naor
Grader: Gil Segev
When: Tuesday
Where: Ziskind 1 -Until March 17th Monday Ziskind 261
First meeting:
Informal Lectures Lectures Homework Tentative List of Papers
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:
* Definitions of data privacy, and ways in which they can be refined
* Techniques for achieving privacy
* Limitations (i.e. lower bounds) on privacy in various settings.
* Privacy issues in specific settings
The course will consist of seminar-style presentations by the students.
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.
· Seinfled on privacy vs. security and different attitudes to privacy: The Reversed Peephole or the script
· The story Scroogled, by Cory Doctorow
· New York times article on identifying users from AOL search records
Advice on giving Academic Talks
Below is a compilation of source on giving talks. Some of it humorous and some contradicts each other
Lecture 1, October 23rd: Secure Function
Evaluation.
· Homework set 1 -
deadline Feb 10th.
==========================================================================================================
Randomized Response
Stanley L. Warner, Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias, Journal of the American Statistical Association, Vol. 60, No. 309. (Mar., 1965), pp. 63-69.
=========================================================================================================
More Randomized Response
=========================================================================================================
K- Anonymity and linkability
=========================================================================================================
Auditing
==========================================================================================================
==========================================================================================================
Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith: Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography Conference (TCC) 2006, p. 265-284.
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry and Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release. PODS 2007: 273-282
Lars Backstrom, Cynthia Dwork and Jon M. Kleinberg: Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography. WWW 2007: 181-190
Kunal Talwar and Frank McSherry, Mechanism Design via Differential Privacy. FOCS, 2007.
Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. Smooth
Sensitivity and Sampling in Private Data Analysis , STOC 2007,
==========================================================================================================
Fuzzy Extractors
Yevgeniy Dodis and Adam Smith, Correcting Errors Without Leaking Partial Information, STOC 2005.
RFIDs
Yossi Oren and Adi Shamir, Power Analysis of RFID Tags
Privacy Protection in Images
Center for Computational Thinking, October 2007, CMU
Privacy Day, Weizmann Institute, July 2006
Anonymity bibliography at Free Haven (a project for for distributed, anonymous, persistent data storage)
Surveys from statistics point of view: