CS 7880: Graduate Cryptography (Topics in Theory, Fall 2015)

Course Description

Cryptography is the science of protecting information against adversarial eavesdropping and tampering. Although people have been fascinated with cryptography since ancient times, it has only recently blossomed into a scientific discipline with rigorous mathematical foundations and methodologies. In this graduate course, intended for students at the PhD level, we will provide an accelerated introduction to cryptography and quickly progress to advanced topics that are at the forefront of current research. We will start by understanding what kind of security properties can be achieved by relying solely on probability and information theory, without restricting the adversary's computational power. We will then study the complexity-theoretic basis of modern cryptography and the connection between computational hardness and pseudoradnomness. As the main component of the course, we will explore how to take a few well-studied problems in number theory and algebra and use them to build powerful cryptosystems with advanced functionality and security properties (public-key encryption, chosen-ciphertext security, digital signatures, identity-based encryption, fully-homomorphic encryption, etc.).

Prerequisites: The main pre-requisite is a high degree of mathematical maturity. We will also rely on some rudimentary knowledge of probability. No prior knowledge of cryptography or number theory is required (but some familiarity will be helpful).

Although the course is intended for PhD students, interested undergraduate and Masters students are encouraged to contact the instructor.

Logistics

Lecture Time: Tuesday, Thursday 10 - 11:40 am
Location: 242 Forsyth
Instructor: Daniel Wichs. Email: (instructor's five-letter last name)@ccs.neu.edu.
Office hours: By appointment. West Village H, Office 340.

Grading

Problem Sets, Scribe Notes, Final Project

Resources

Students will be asked to scribe lecture notes in latex, which will serve as the main resource for the course. The following textbook is useful as a reference: Introduction to Modern Cryptography by Katz and Lindell.
Other useful resources include:
Lecture Notes by Rafael Pass and Abhi Shelat.
Lecture notes by Yevgeniy Dodis
Lecture notes by Chris Peikert
Lecture notes by Boaz Barak.
Slides by Stefan Dziembowski.
Slides,Notes by Gil Segev.

Scribing

You should scribe notes in LaTex. Use the following example notes as a template. You also need this preamble to compile. The scribed notes are due one week after the lecture.


Problem Sets

Use latex to write up your solutions. A template file is provided for you for each problem set.

Lectures

Class/Date Topic Covered Notes
Class 1, 9/10: Introduction, perfect secrecy, one-time pad, optimality and beginning of authentication. scribe notes, slides.
Class 2, 9/17: Continuation of authentication, secret sharing, statistical distance, statistical security for encryption. scribe notes.
Class 3, 9/22: Lower bound on statistically secure encryption, extractors. scribe notes.
Class 4, 9/24: Finish proof of leftover hash. Computational security, one-way functions (OWFs) and one-way puzzles. scribe notes.
Class 5, 9/29: Impagliazzo's worlds, examples of OWFs, computational indistinguishability, pseudorandom generators (PRGs).scribe notes.
Class 6, 10/1: PRG with 1-bit stretch implies arbitrary stretch. Building PRGs from OWFs? scribe notes.
Class 7, 10/6: Goldreich-Levin theorem scribe notes
Class 8, 10/8: Goldreich-Levin theorem continued scribe notes
Class 9, 10/13: Pseudorandom Functions, GGM Construction, Symmetric-Key Encryption scribe notes
Class 10, 10/15: CPA Encryption, MACs, Hash Functions scribe notes
Class 11, 10/20: Hash Functions, Merkle-Damgaard, Merkle Tree, Random Oracle scribe notes
Class 12, 10/22: Number Theory, Crypto in Cyclic Groups scribe notes
Class 13, 10/27: Discrete Log, CDH and DDH Assumptions and Diffie-Hellman Key-Agreement (same as above)
Class 14, 10/29: ElGamal Encryption, Hash Functions from DL, PRGs from DDH scribe notes (unedited)
Class 15, 11/5: Naor-Reingold PRF, Threshold ElGamal, Trapdoor Permutations, RSA scribe notes (unedited)
Class 16, 11/10: Squaring modulo N, Rabin TDP, Signatures from TDP in RO model scribe notes (unedited)
Class 17, 11/12: Signatures from Collision-Resistant Hashing (and OWFs) scribe notes (unedited)
Class 18, 11/17: Identification schemes, Schnorr ID Scheme scribe notes (unedited)
Class 19, 11/19: Schnorr Signatures, Zero Knowledge Proofs, Graph Isomorphism
Class 20, 12/1: Zero Knowledge Proof for all of NP (3-COLOR)
Class 21, 12/3: Lattice-based cryptography, Fully Homomorphic Encryption (FHE)


Tentative Syllabus

Information-Theoretic Cryptography
Foundations of Symmetric-Key Cryptography
Number-Theory Assumptions and Cryptosystems I Assumptions and Cryptosystems II Sigma Protocols and Zero-Knowledge Proofs Signatures Chosen-Ciphertext Security Advanced Topics (will cover some subset of these)