Foundations of Privacy Winter 2007/8

Seminar in Foundations of Privacy - Winter 2007/8

Instructor: Moni Naor

When: Tuesday 14:00--16:00 - Until March 17th Monday 14:00-16:00
Where: Ziskind 1 -Until March 17th Monday Ziskind 261
First meeting: Oct 23rd 2007

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.

Background Material

· 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

Cynthia Dwork An Ad Omnia Approach to Defining and Achieving Private Data Analysis

Advice on giving Academic Talks

Below is a compilation of source on giving talks. Some of it humorous and some contradicts each other

Giving an Academic Talk by Jonathan Shewchuk
Oral Presentation Advice by Mark D. Hill
Pointers on giving a talk by David Messerschmitt
How to give a good talk by Hany Farid
Giving Talks by Tom Cormen

Informal Talks held During the Strike

Tuesday, Nov 13: Voting Schemes (slides in pptx) by Tal Moran

Tuesday Nov 20: Everlasting Security by Danny Harnik. Papers:

Salil Vadhan, Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
Stefan Dziembowski and Ueli Maurer, On Generating the Initial Key in the Bounded-Storage Model, Eurocrypt 2004.
Danny Harnik and Moni Naor, On Everlasting Security in the Hybrid Bounded Storage Model, ICALP 2006.

Tuesday Nov 27: Manual Channel Authentication by Gil Segev. Slides (ppt).
Tuesday Dec 4th: On the (in)security of the random number generators of Linux and Windows (slides in ppt) by Benny Pinkas. Papers:

Leo Dorrendorf and Zvi Gutterman and Benny Pinkas, Cryptanalysis of the Random Number Generator of the Windows Operating System. ACM CCS 2007
Zvi Gutterman, Benny Pinkas and Tzachy Reinman, Analysis of the Linux Random Number Generator, IEEE Symposium on Security and Privacy (Oakland ) 2006

Tuesday Dec 11th: RFIDs and Privacy (slides in PDF) by Alon Rosen

Tuesday Dec 18th: Cryptography: on the Hope for Privacy in a Digital World by Omer Reingold.

Tuesday Dec 25th: Obfuscating Programs by Guy Rothblum. Papers:

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, Crypto 2001.
B. Lynn, M. Prabhakaran and A. Sahai, Positive Results and Techniques for Obfuscation, Eurocrypt 2004
Shafi Goldwasser and Guy Rothblum, On Best-Possible Obfuscation, TCC 2007.

Tuesday January 1st: History Independent Data Structures by Moni Naor. Papers:

Moni Naor and Vanessa Teague, Anti-persistence: History Independent Data Structures, STOC 2001. Abstract, Postscript, gzipped Postscript. Slides: ppt.
J. D. Hartline, E. S. Hong, A. E. Mohr, W. Pentney and E. C. Rocke, Characterizing History-Independent Data Structures , Algorithmica 2005
N. Buchbinder and E. Petrank, Lower and upper bounds on obtaining history independence, Information and Computation 2006
Guy Blelloch and Daniel Golovin, Strongly History-Independent Hashing with Applications, FOCS 2007

Tal Moran, Moni Naor and Gil Segev, Deterministic History-Independent Strategies for Storing Information on Write-Once Memories, ICALP 2007. Abstract, Postscript, gzipped Postscript, PDF. Slides: short talk (ppt), long talk (ppt).

Tuesday January 8th, Private data analysis: basics by Kobbi Nissim

Tuesday January 15, The Impossibility of Disclosure Prevention or The Case for Differential Privacy by Moni Naor

Lectures:

Lecture 1, October 23rd: Secure Function Evaluation.
- See background in Yehuda Lindell's Secure Multiparty Computation for Privacy Preserving Data Mining
Lecture 2: Tuesday January 22nd: Randomized Response by Chandan Dubey Slides
Lecture 3: Tuesday January 29th: Zero-Knowledge and Deniable Authentication by Moni Naor. Papers:
- Moni Naor Deniable Ring Authentication, Crypto 2002.
- Ron Rivest, Adi Shamir and Yael Tauman, How to Leak a Secret: Theory and Applications of Ring Signatures, Essays in Theoretical Computer Science: in Memory of Shimon Even.
Lecture 6: Monday February 18th: Shlomo Jozeph, K- Anonymity and linkability. Papers:
- Latanya Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570.
A. Narayanan, V. Shmatikov. How To Break Anonymity of the Netflix Prize Dataset.
A.Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity. In Proc. 22nd Int Conf. Data Eng. (ICDE), page 24, 2006.
Ninghui Li, Tiancheng Li, Suresh Venkatasubramanian. t-closeness: Privacy Beyond k-Anonymity and l-Diversity In 23rd IEEE International Conference on Data Engineering (ICDE), 2007

Lecture 6: Monday February 25th: Or Brostovski, De-identifying Facial Images using k-anonymity and Protecting privacy from CCTV. Papers:

Elaine M. Newton, Latanya Sweeney, Bradley Malin, Preserving Privacy by De-identifying Facial Images, IEEE Trans. Knowl. Data Eng. 17(2): 232-243 (2005)
A. Senior, S. Pankanti, A. Hampapur, L. Brown, Y. Tian, A. Ekin, J. H. Connell, C.-F. Shu, M. Lu Enabling Video Privacy through Computer Vision

Lecture 7: Monday March 3rd: Inbal Talgam, Adding Consistency to Differential Privacy and Attacks on Anonymized Social Networks

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.

Lecture 8: Monday March 10th: Lidor Avigad, Mechanism Design via Differential Privacy and Smooth Sensitivity and Sampling in Private Data Analysis.

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.

Lecture 9: Monday March 31st: Yoav Tzur,

Irit Dinur and Kobbi Nissim, Revealing information while preserving privacy, 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 202-210, 2003.
Cynthia Dwork and Sergey Yekhanin, New Efficient Attacks on Statistical Disclosure Control Mechanisms.

Homework:

· Homework set 1 - deadline Feb 10th.

Tentative List of Papers:

==========================================================================================================

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.
Tal Moran and Moni Naor, Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, Eurocrypt '06 - Slides

=========================================================================================================

More Randomized Response

Nina Mishra and Mark Sandler, Privacy via Pseudorandom Sketches, 25th ACM Symposium on Principles of Database Systems (PODS). 2006
Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting Privacy Breaches in Privacy Preserving Data Mining. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems (PODS 2003). San Diego, CA, June 2003.

=========================================================================================================

K- Anonymity and linkability

Latanya Sweeney, k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570.
A. Narayanan, V. Shmatikov, How To Break Anonymity of the Netflix Prize Dataset.
A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity. In Proc. 22nd Int Conf. Data Eng. (ICDE), page 24, 2006.
Ninghui Li, Tiancheng Li, Suresh Venkatasubramanian. t-closeness: Privacy Beyond k-Anonymity and l-Diversity In 23rd IEEE International Conference on Data Engineering (ICDE), 2007.

=========================================================================================================

Auditing

J. Kleinberg, C. Papadimitriou, P. Raghavan. Auditing Boolean Attributes, Proc. 19th ACM Symposium on Principles of Database Systems, 2000.
Krishnaram Kenthapadi, Nina Mishra, Kobbi Nissim, Simulatable Auditing, 24th PODS, 2005.

==========================================================================================================

Irit Dinur and Kobbi Nissim, Revealing information while preserving privacy. 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 202-210, 2003.
Cynthia Dwork, Frank McSherry and Kunal Talwar, The price of privacy and the limits of LP decoding. STOC 2007, 85-94

==========================================================================================================

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.
A. Blum, C. Dwork, F. McSherry, and K. Nissim, Practical Privacy: The SuLQ Framework, Principles of Database Systems, 2005.

==========================================================================================================

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
Stephen A. Weis Security of HB+

==========================================================================================================

Privacy Protection in Images

A. Senior, S. Pankanti, A. Hampapur, L. Brown, Y. Tian, A. Ekin, J. H. Connell, C.-F. Shu, M. Lu, Enabling Video Privacy through Computer Vision, IEEE Security & Privacy 3(3): 50-57 (2005)
Elaine M. Newton, Latanya Sweeney, Bradley Malin, Preserving Privacy by De-identifying Facial Images, IEEE Trans. Knowl. Data Eng. 17(2), pp. 232-243 (2005)

Related Courses:

Vitaly Shamtikov, Theory and Practice of Secure Systems, UT Austin

Aleksandra Slavkovic and Adam Smith, Privacy in Statistical Databases, Penn State.

Cynthia Dwork, Nina Mishra and Kobbi Nissim, A Study of Perturbation Techniques for Data Privacy, Stanford University

Computation and Society: Privacy and Technology, Harvard

Workshop and talks

Center for Computational Thinking, October 2007, CMU

Privacy Day, Weizmann Institute, July 2006

Bibliographies

Anonymity bibliography at Free Haven (a project for for distributed, anonymous, persistent data storage)

Surveys from statistics point of view:

S. Feinberg and A. Slavkovic, Making the Release of Confidential Data from Multi-Way Tables Count Chance

N. R. Adam and , J. C. Wortman, Security control methods for statistical databases: A comparative study, ACM Computing. Surveys Vol. 21, No. 4, December 1989