General Information

Instructor:

• Tal Malkin
  • Email: tal at cs
  • Office hours: Fridays 9:30-10:30am or by appointment, 514 CSB.

Teaching Assistants:

• Marshall Ball
  • Email: marshall at cs
  • Office hours: Thursdays 9:00-10:00am or by appointment, 516 CSB.
• Negev Shekel Nosatzki
  • Email: negev at cs
  • Office hours: Tuesdays 1:30-2:30pm or by appointment, 5th floor lounge CSB.

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

Course Description

• Secret sharing
• Byzantine agreement, consensus, etc
• Secure computation (information theoretic MPC for general functions, IT garbled circuits, minimal-interaction secure computation models, etc).
• Randomized Encodings and their applications
• IT PIR (private information retrieval)
• Proof systems (IP, PCP, MIP, ZK,...)
• Connections of cryptography to coding theory (secret sharing, locally decodable codes, non-malleable codes, ...)
• Randomness extraction and cryptographic applications

Lectures and Readings

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):

• Required reading: Randomization Techniques for Secure Computation, Yuval Ishai, 2013, sections 1 and 2. This is a survey of Randomized Encodings -- we will cover some of it (as well as later work) in this and future lectures
• To be presented in class: Randomized encoding (RE): definitions and overview. Constructions for decomposable RE (or PSM) and low degree RE: Yao's garbled circuits (information-theoretic presentation), and RE from branching programs. Application to getting constant round secure computation. These are covered in various sources but we will use the following:
  1. The same Ishai survey above.
  2. Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials, Yuval Ishai, Eyal Kushilevitz, ICALP 2002
  Notes: garbled circuits correspond to source 1 sections 4.1.2, 4.2.3, and source 2 section 3, while RE from branching programs correspond to source 1 sections 4.1.3, 4.2.4, and source 2 section 4.

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.

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).

• Required reading: Introduction of both above papers (the second paper's intro can be viewed as an update of the first paper, reflecting better understanding in light of new results).
• Thorough reading: If you choose to read one of these papers throughly, for the first paper this includes the whole body of the paper plus appendices B,C, and for the second paper this includes reading the paper through the end of section 3.3.

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.

Upcoming: Distributed Computing: Byzantine Agreement, etc.

Requirements

• Presentation: Most lectures will be delivered by students. For each lecture there will be about two students in charge of the lecture (presenting the assigned papers), and about two other students supporting the presenters. The presenters and supporters should work together to thoroughly understand the assigned papers, so that the presenters can effectively teach them. Motivation and context, as well as definitions, proofs, and techniques, are all important. The teaching staff will provide help and guidance as well. Every student is expected to take the role of a presenter once, and the role of a supporter once throughout the semester.
• Reading: Most classes will have assigned readings that are required of every student. For example, this may consist of reading the introduction and technical overview of the papers to be presented. In addition, every student has to thoroughly read (including proofs) 2 of the assigned papers throughout the semester, not including the papers that the student is designated as a presenter or supporter for. Note you must notify the TAs that you are thoroughly reading the papers for a given class, before that class takes place, in order to get credit.
• Presence: Students are expected to be present in lectures (physically, but not only). Come prepared, pay attention, try to get the most out of the lecture.
• Homework: There may be a small number (between 0 and 3, likely closer to 0) of homeworks.
• Project: Every student should complete a research project on any cryptographic topic of their choice (subject to instructor approval). Students may work on their research project individually or in a group. If you would like to collaborate with others outside the class, e.g., other professors or fellow students, you may do so, provided that all your collaborators know and approve, and that you're not getting double credit for the same project (and of course, I will hold you accountable for your project).
  More information about the requirements, deadlines, and suggested topics for the projects is available on the projects page. Each project will be presented to the class, either during the final exam slot for the class, or during a scheduled day on reading week.

Academic Honesty

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