CSCI 5520: Data Privacy

The Chinese University of Hong Kong, Spring 2015

• Lectures Tue 2:30-5:15 in BMS1
• Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
• Office hours Fri 2-4 (or by appointment)

Recent Announcements

• Mar 31 The project report should be handed in by Sun Apr 19.
• Mar 31 I sketched a corrected proof for Lemma 5 in the Lecture 12 notes.
• Mar 24 For the project presentation, you should aim to speak for 25 minutes if working in a group or 15 minutes if working individually. There is no requirement on the length of the report; you can aim for 5-6 pages for groups and 3-4 for individuals, but deviations are fine.
• Mar 24 Homework 3 is due on Wed Apr 8. Please bring it to my office or send me a pdf or a scan over email.

Course Description

In this course we will study the privacy loss that occurs when public information is released from databases that contain sensitive information about individuals. We will start with mathematical definitions of database privacy, study the privacy guarantees of various mechanisms for publishing data and show their statistical and computational limitations. Time permitting, we will explore connections to other areas like mechanism design, cryptography, and statistical learning.

Lectures

This is a tentative (and somewhat ambitious) schedule. Changes are possible depending on progress and interest.

	date	topic	reading
1	Jan 6	Definitions of privacy. The Laplace mechanism.	pdf
2	Jan 13	The exponential mechanism.	pdf
3	Jan 20	Interactive data release I.	pdf
4	Jan 27	Interactive data release II. Composition of queries.	pdf
5	Feb 3	Mechanisms for sensitive queries.	pdf
6	Feb 10	Statistical limitations of private data release.	pdf
7	Feb 17	Computational limitations for synthetic data.	pdf
	Feb 24	Lunar New Year holiday
8	Mar 3	Hardness of efficient mechanisms for counting queries.	pdf
9	Mar 10	Privacy and truthfulness.	pdf
10	Mar 17	Privacy in learning.	pdf
11	Mar 24	Private implementations.	pdf
12	Mar 31	Other definitions.	pdf
	Apr 7	Easter holiday
	Apr 14	Project presentations

Homeworks

• Homework 3 due Wed Apr 8 | solutions
• Midterm exam due Tue Mar 17
• Homework 2 due Tue Mar 3 | solutions
• Homework 1 due Tue Feb 3

Course Information

• Prerequisites A good grasp of probability and statistics and some knowledge of algorithms is helpful for this course. If you are not sure you know these topics please talk to me.
• Grading and homeworks Your grade will be determined from 2-3 homeworks (30%), a take-home midterm exam (30%), and a final project (40%). Homeworks will be issued throughout the semester.
• You are encouraged to collaborate on the homeworks as long as you write up your own solutions and provide the names of your collaborators. I discourage you from looking up solutions to homework problems online, unless you have exhausted all other resources; if you do so, please provide proper credit and make sure you understand the solution before you write it.
• Final project For your final project you will be expected to do some independent reading, a presentation in class, and a short report. A list of suggested projects and more details will be provided around the middle of the semester.

References

Notes will be provided for every lecture. The main reference for the course is

• Cynthia Dwork and Aaron Roth. The algorithmic foundations of data privacy. Foundations and Trends in Theoretical Computer Science, vol. 9, no. 3-4, 2014.

The survey is free for download for personal use. Hard copies can also be ordered from Now Publishers.

Here are some notes on probability that refresh some basic concepts and explain the notation we use.