COMS E6261:  Advanced Cryptography

Spring 2010: Data Privacy

Lecture Topics and Readings Project Page Additional Papers

General Information

This is a three-credit advanced graduate level course. The course serves as a theory elective for the PhD program in computer science. It also serves as an elective for MS students in the Foundations of Computer Science Track and the Computer Security Track.  The class will focus around a different topic, possibly with a different format, every time it is taught. The class can be repeated for credit.  Auditing the class requires instructor approval. CVN students should contact the instructor before registering.

Instructor: Tal Malkin, 514 CSB, Office hours: Tuesdays 2:30-4:00pm

TA: Dana Dachman-Soled, 516 CSB, Office hours: Wednesdays 10:00-11:00am

Time & Place: Wed 2:10-4:00pm, 477 CSB

Prerequisites: COMS-4261 Introduction to Cryptography or equivalent with instructor approval.  It is assumed that all students already have good knowledge of basic notions from foundations of cryptography. Background in probability and statistics is useful.

Course Description

Concerns about privacy are becoming part of our everyday lives, as huge amounts of information are collected, stored, and analyzed. Such data can often be sensitive and include medical, financial, and other personal information. While such data can provide aggregate and large-scale statistics that are very useful, it also poses significant privacy risks to individuals, and may also prevent individuals from voluntarily providing their data. A common goal is then to collect the information in a way that provides as much utility as possible, while at the same time protecting personal information. Defining (let alone achieving and proving) this type of privacy is a difficult and challenging task, that received much attention in the last few years in different communities (e.g., databases, security, cryptography, machine learning, etc).

In this course we will focus on the a rigorous approach to understanding, defining, and achieving information privacy. We will NOT discuss at depth the (fascinating) legal, social, and psychological aspects of privacy, but rather concentrate on the technical aspects. We will review several approaches from different communities (e.g., secure computation, k-anonymity, ad-hoc anonymization and randomization techniques), but our main focus will be on the notion of differential privacy that emerged in the cryptographic community in the last few years, and discuss current work utilizing differential privacy.

We do not necessarily aim at giving an exhaustive treatment of the subject, but rather go in depth into several papers, biased by the interests of the instructor and the students taking the class. The concrete topics will be adjusted based on student interest, too. See below for an evolving schedule and topics covered.

The class format will be a combination of lectures given by the instructor, students, and occasional guest speakers, as well as discussions of recent papers, which students are expected to participate in.

Syllabus: Evolving Schedule and Reading

A brief description of topics covered in class and papers to be presented or read for the following class is here.

Class Requirements

Reading Papers and Participation:   There will be reading assignments for each class. Students are expected to read the required papers before class and participate in discussion about them during class.

Presentation:   Students will be required to present a paper (and lead a discussion about it) in class, once or twice during the semester. Project presentations will also be required at the end of the semester.

(No) Tests and Homework:   There will be at most two (but likely significantly fewer) homework assignments to be turned in throughout the semester. There will be no tests.    

Project:  Students should complete a research project on a cryptographic topic determined in consultation with the instructor (any topic related to the foundations of cryptography is likely to be approved). Students are encouraged to work on the research project in groups of two, but individual or three-student projects are allowed, if called for by the project topic.

The first stage of the project will consist of literature study of the selected area.  Based on that, you will then select a research problem or direction which you expect to make new progress in by the end of the semester.  I will be available to help you with both these stages, and expect to be updated about your progress throughout the semester.  You will be required to submit a short project proposal (before first stage) and a short midterm progress report (before the second stage), as well as a final report. For more details, see here.