COMS E6261: Advanced Cryptography

Spring 2020: Information Theoretic Cryptography

General Information | Lectures and Reading | Class Requirements | Projects

General Information

Instructor:

Teaching Assistants:

Administrative Notes:
Class meets Tuesdays 4:10-6:00pm, at 303 Hamilton Hall.
This course can be used as a theory elective for the PhD program in computer science, as a track elective for MS students in the "Foundations of Computer Science" track or the "Computer Security" track, or as a track elective for undergraduates in the "Foundations" track. COMS E-6261 Advanced Cryptography focuses around a different topic, possibly with a different format, every time it is taught. The class can be repeated for credit.

Prerequisites

COMS-4261 Introduction to Cryptography or COMS-W4236 Introduction to Computational Complexity or instructor approval. The most important prerequisite is mathematical maturity, and comfort with (preferably also strong affection for) rigorous definitions and proofs.

Course Description

This course is an advanced graduate level seminar, where most lectures will be given by students taking the class (see more below). The course will focus on selected topics and techniques in information-theoretic cryptography, namely settings with perfect or statistical security against a computationally unbounded adversary (without relying on computational assumptions). This is a very wide umbrella including topics such as the following (and many more): Most of these topics could easily span a full semester each, and include various interesting subtopics, upper and lower bounds, and connections to various other areas of cryptography and theoretical computer science. We will not attempt to give an exhaustive treatment, and we will likely not be able to even touch on all the above topics. Instead, we will study in depth a few results in different areas, and give an overview and pointers to some other directions and applications. The results we cover will range from classic results from the 80s to cutting edge research papers. We will also try to highlight open problems.

Lectures and Readings

Below are very brief summaries of the lectures that have already happened, and plans/readings that will be presented in the upcoming lectures.

A more extensive summary of the lectures and upcoming class topics, with many links for supplementary reading and project ideas related to the the class topics, is available here:

Information Theoretic Cryptography: Lectures, Readings, Proposed Project Topics (evolving document, last updated 2/9/20).

Lecture 1 (1/21): Introduction to class. Threshold secret sharing definition. Shamir's secret sharing construction (and proof). Informal overview of the use of Shamir's secret sharing for secure computation (BGW protocol). No required reading.

Lecture 2 (1/28)(plus some of Lecture 3): Secure computation (in semi-honest, honest majority, information theoretic setting): definition, and construction (BGW). Optimality of threshold (impossibility for corrupted majority). Motivation and context for next topics. No required reading.

Lectures 3,4 (Feb 4,11) (taught by Lali Devadas and Tim Randolph , with support from Ruth Wang):

Lecture 5 (Feb 18): Lower Bounds for Private Simultaneous Messages (PSM), Conditional Disclosure of Secrets (CDS). To be presented in class:
  1. On the Complexity of Decomposable Randomized Encodings. Ball, Holmgren, Ishai, Liu, Malkin, ITCS 2020. We will focus on the information theoretic lower bound.
  2. Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption. Romain Gay, Iordanis Kerenidis, Hoeteck Wee, CRYPTO 2015. We will focus on the lower bound, and super simple upper bounds.
Lecture 6 (Feb 25): Conditional Disclosure of Secrets (CDS): upper bounds, lower bounds, and overview of other connections/applications. Papers to be presented:
  1. Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption. Romain Gay, Iordanis Kerenidis, Hoeteck Wee, CRYPTO 2015.
  2. Conditional Disclosure of Secrets via Non-Linear Reconstruction. Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee, CRYPTO 2017. We will present the first CDS construction (section 3.3 / theorem 3.4).
Lecture 7 (March 3): Private Information Retrieval (PIR). To be presented in class:
  1. A survey of information-theoretic PIR, current results, and connections to other areas (CDS, secret sharing, locally-decodable codes). See the recent Bar-Ilan University winter school slides by Yuval Ishai and Klim Efremenko (although we will have less time, and will not cover all of it).
  2. Private Information Retrieval with Sublinear Online Time. Henry Corrigan-Gibbs and Dmitry Kogan, EUROCRYPT 2020.
The first one is not a single paper, but rather a survey, focusing on communication complexity (the typical focus in PIR). There's no required reading for it, though you may want to skim the slides. No in-depth reading for this one either, although if you want to read a (technical, information-theoretic) PIR paper of your choice as a thorough reading you can inquire and I will probably approve (e.g., the Katz-Trevisan one proving equivalence of LDC and PIR). For the second paper, required reading is sections 1.1-1.3 of the Corrigan-Gibbs and Kogan paper (and the whole paper for thorough reading).

Upcoming: Distributed Computing: Byzantine Agreement, etc.

Requirements

The class requirements are as follows:

Academic Honesty

I expect that the primary goal of everyone in the class is to learn (I can imagine no other reason that you would be in this class). Hopefully this means that there will be no focus on grades (which I can tolerate but do not like), and no issues of dishonesty (which I absolutely will not tolerate).

As in every CS class, students are expected to adhere to the academic honesty policy of the CS department.