# CS 7810 - Foundations of Cryptography, Fall 2017

### 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 modern 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 such as public-key encryption, digital signatures, multi-party computation, 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, algorithms, and theory of computation. 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: ** Monday, Wednesday: 2:50 pm - 4:30 pm

** Location: ** Ryder Hall 157

** Instructor: ** Daniel Wichs. Email:
(instructor's five-letter last name)@ccs.neu.edu.

Office hours: By appointment. Office 622 ISEC.

### Grading

Problem Sets 40%, Scribe Notes 10%, Class Project 20%, Final Exam 30%
### 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:

Graduate Crypto Book by Dan Boneh and Victor Shoup.

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

Problem sets will be posted here. Use latex to write up your solutions. A template file is provided for you for each problem set. You should try to solve each problem on your own. If you can't solve the problem on your own, you are allowed to discuss with others from the class. However, you must write down the solution on your own. You should also write down who you discussed each problem with. You are not allowed to use any other external resources.
### Lectures

** Class/Date ** | **Topic Covered** | **Notes** |

Class 1, 9/6: | introduction, perfect secrecy, one-time pad, optimality. | notes , slides |

Class 2, 9/11: | authentication, secret sharing | scribe notes. |

Class 3, 9/13: | multiparty computation, statistical distance | |

Class 4, 9/18: | statistical security, computational security, indistinguishability | |

### Tentative Syllabus

** Information-Theoretic Cryptography **

- One-time pad, optimality
- Pairwise-independent hashing and one-time MAC
- Secret-sharing
- Multiparty computation with honest majority

** Foundations of Symmetric-Key Cryptography **

- Computational security, Indistinguishability, Hybrid Argument
- Pseudorandom generators, functions and permutations (block ciphers)
- Symmetric-key encryption and message authentication
- Collision-resistant hashing, Random oracle model
- One-way functions/permutations (OWF/OWP) and hard-core bits
- Goldreich-Levin theorem

** Number-Theory Assumptions and Cryptosystems I**
- 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, Rabin cryptosystem

** Assumptions and Cryptosystems II **
- Lattices, Learning with Errors (LWE), Short Integer Solution (SIS)
- Identity Based Encryption
- Fully Homomorphic Encryption
- Chosen Ciphertext Security

** Sigma Protocols, Signatures, and Zero-Knowledge Proofs **
- Signatures from OWFs
- RSA signatures
- Identification protocols, Schnorr and Okamoto schemes
- Schnorr signatures
- Zero-knowledge proofs

** Advanced Topics (depending on time and interest)**
- Yao garbled circuits, Secure function evaluation
- Attribute-based encryption, functional Encryption
- Private information retrieval
- Obfuscation
- ...