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

Office hours: By appointment. West Village H, Office 340.

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.

- Problem set 1, due 10/20. pdf , latex.
- Problem set 2, due 11/10. pdf , latex.
- Problem set 3, due 12/10. pdf , latex.

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

- One-time pad, optimality
- Pairwise-independent hashing and one-time MAC
- Secret-sharing
- Statistical distance and randomness extractors

- Asymptotic security
- One-way functions/permutations (OWF/OWP) and hard-core bits
- Goldreich-Levin theorem
- Pseudorandom generators and functions
- The hybrid argument and the GGM construction
- Collision-resistant hashing, Random oracle model

- Arithmetic modulo a prime
- Discrete-logarithms, CDH/DDH Assumptions
- Diffie-Hellman Key-Exchange, ElGamal-Encryption
- Collision-resistant hashing from DL
- Naor-Reingold PRF
- Arithmetic modulo a composite, RSA encryption

- Lattices, Learning with Errors (LWE), Short Integer Solution (SIS)
- Collision-resistant hashing from SIS
- Regev's public-key encryption from LWE
- Fully Homomorphic Encryption

- Identification protocols, Schnorr and Okamoto schemes
- Zero-knowledge proofs

- Signatures from OWFs
- RSA signatures
- Schnorr signatures
- LWE-based signatures

- CCA Security in the Random Oracle Model
- Cramer-Shoup Encryption
- Lossy Trapdoor Functions

- Threshold Cryptography
- Identity-Based Encryption and Functional Encryption
- Multiparty computation
- Yao garbled circuits
- Private Information Retrieval
- Oblivious RAM