General Information

Location and Hours:

Dan David 202, Thursday 10:00 - 13:00

Instructor:

Nir Bitansky

Reception Hours:

Please coordinate by moc.liamg|yksnatibn#liame

Overview

Cryptography is magical, it solves paradoxical problems such as communicating privately without ever meeting, proving you know a secret without revealing it, or computing over encrypted data. This magic is, in fact, based on a rigorous theory with beautiful definitions and proofs of security based on computational complexity. The course will provide a graduate-level introduction to the theory of cryptography. We will cover foundational concepts, abstractions, and techniques, with the aim of giving students the basic tools needed to start research in the area. We will also sneak a peek into some advanced topics as time permits.

Prerequisites

Basic probability theory, basic complexity (P, NP, BPP, NP-completeness). Prior informal-level knowledge of cryptography (such as the undergraduate course
0369.3049) is helpful but not required. Perhaps the most important prerequisite is mathematical maturity: The ability to read, understand, and write mathematical proofs. This is a graduate course. Undergraduate students are encouraged to take 0369.3049. In some special cases, however, undergraduates who receive personal permission of the instructor can take the course.

Requirements

1. Class notes (10%): each week a group of students will prepare notes covering that week's class. Each student will participate in preparing at least one set of notes.
2. Homework assignments (60%): 6 problem sets.
3. A final exam (30%).

Tentative Syllabus

• Introduction
  • Perfect secrecy and its limitations.

• Computational Hardness
  • Computationally-bounded adversaries
  • One-way functions
  • Hardness amplification

• Indistinguishability and Pseudorandomness
  • Computational indistinguishability
  • Cryptographic pseudorandom generators and pseudorandom functions
  • Multi-message encryption and authentication
  • Hardcore bits and the Goldreich-Levin theorem

• Securing Communication
  • Key exchange and public-key Encryption
  • Digital signatures

• Zero Knowledge
  • The Simulation Paradigm
  • ZK proofs for NP

• Securing Computation
  • Secure Multi-Party Computation: oblivious-transfer, Yao's garbled circuit
  • Advanced topics (as time permits): fully-homomorphic encryption, functional encryption, obfuscation, and verifying delegated copmutation

Text Books

1. J. Katz and Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.
2. O. Goldreich, Foundations of Cryptography Volumes 1,2, Cambridge University Press 2001,2004. Drafts available online.
3. D. Boneh and V. Shoup, A Graduate Course in Applied Cryptography. Draft available online.

Crypto Courses with Online Material

1. Benny Applebaum and Iftach Haitner
2. Boaz Barak
3. Ran Canetti
4. Benny Chor (The Undergraduate Course)
5. Yevgeniy Dodis
6. Rafael Pass and Abhi Shelat
7. Gil Segev
8. Salil Vadhan
9. Daniel Wichs

Lecture Notes

Each week 2-3 scribes will prepare the lecture notes (10% of the final grade). Please sign up here.
The notes should be written in Latex —- you will get an initial scribe that will consist of the outline and some of my notes. You will need to fill in missing details according to what we cover in class and if needed beyond (for instance, complete the details of a proof that was only sketched). You should hand-in the first draft on (the first) Monday after the talk.