This is the webpage for the Northeastern University course *Cryptography and Communications Security (CS 6750)* in Spring, 2014.

Class | Topics Covered | Relevant Reading |
---|---|---|

1/7 | introduction, encryption problem, perfect secrecy, one-time pad, limitations (Shannon's Theorem), authentication problem, one-time MAC | KL Chapters 1,2 |

1/14 | continuation of one-time MACs, secret sharing, threshold secret sharing, computational security, define semantic-security for encryption, semantic security with small keys implies P != NP. | KL Chapter 3.1, 3.2 |

1/21 | Class canceled due to snow | |

1/28 | Construct semantically secure encryption from PRG. Theory of indistinguishability, hybrid argument. PRG with 1-bit stretch implies many bit stretch. CPA secure encryption. Using Pseudorandom Functions (PRFs) to get CPA encryption. | KL rest of chapter 3, section 6.8 |

2/4 | The hybrid argument for games. Construct PRF from PRG. Pseudorandom Permutation (PRP) and construction from PRF via Feistel Network. Message Authentication Codes and constructions from PRF. | KL rest of chapter 3, chapter 4, and sections 6.5,6.6 |

2/11 | Message Authentication Codes for long messages. Collision Resistant Hashing. Random Oracle Model. Introduction to public-key encryption and signatures, certificate authorities, public key infrastructure. | KL rest of chapter 4, and sections 9.1- 9.3 |

2/18 | Number Theory, Part I: greatest common divisor (GCD) and Euclid's algorithm. Modular addition, multiplication, division, exponentiation. Intro to groups and Lagrange's Theorem. | KL 7.1 |

2/25 | Midterm | |

3/4 | Spring Break | |

3/11 | Number Theory, Part II: Discrete logarithm problem and Diffie-Hellman key agreement, RSA Trapdoor Permutation, Primality Testing | KL, rest of chapter 7 |

3/18 | Solving discrete log in square-root time. Definition of semantic security for public-key encryption. How to encrypt with DDH, RSA. PRGs and PRFs from DDH. CCA security. | KL, 8.2.1, Chapter 10. |

3/25 | Quadratic Residues, Rabin trapdoor permutation from hardness of factoring, Digital signatures | KL, 11.1.1,11.1.2, 11.2, 12.1-12.7. |

4/1 | Zero Knowledge Proofs | |

4/8 | Secure Function Evaluation (SFE) using garbled circuits and oblivious transfer. |

The course will aim to carefully balance theory and practice. On the one hand, we will cover most of the cryptographic notions encountered in practice and explain how they are used to solve real security challenges. On the other hand, we will focus on elegant constructions and mathematical justifications of security, and will not go over many important but ad-hoc constructions and standards that are used in practice (beyond a brief mention). The course will also focus solely on cryptography and will not cover other important aspects of computer security.

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

Optional project: You can do a class project for fun or to improve your grade.

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.

- Historical perspectives
- Cryptography in the modern world
- The wide scope of cryptography
- Theory vs. practice

- Review of probability, conditional probability
- Privacy: the one-time pad
- Lower-bound on key length
- Authentication: one-time auth
- Secret-sharing

- Asymptotic Security
- One-way function/permutation (OWF/OWP), Trapdoor-permutations (TDP)
- Pseudorandom-Generator (PRG), Public-Key Encryption (PKE)
- A discussion of definitions: indistinguishability vs. semantic security
- Hybrid Argument

- Stream-Ciphers
- Pseudorandom-Functions (PRFs), Pseduorandom-Permutations (PRPs)
- Constructing PRF from PRG
- Symmetric-key encryption from PRF/PRP: modes of operation

- Definitions
- Message Authentication from PRFs
- Variable-length messages
- Authenticated-encryption + Chosen-Ciphertext Secure Encryption
- Collision-Resistant Hashing, Domain Extension

- Arithmetic modulo a prime
- Discrete-logarithms, CDH/DDH Assumptions, Diffie-Hellman Key-Exchange, ElGamal-Encryption
- Arithmetic modulo a composite, Chinese-Remainder Theorem, Quadratic-Residues
- RSA, Rabin, Goldwasser-Micali Cryptosystems

- RSA Encryption in practice
- Learning-with-Errors
- Homomorphism: a blessing and a liability
- Chosen-Ciphertext Security

- Role of Signatures in Public-Key Infrastructure
- RSA Signatures and the Hash-and-Sign Paradigm
- One-time signatures from OWFs
- The tree construction

- Bit-commitment
- Coin-flipping
- Oblivious Transfer
- Yao garbled circuits
- Fully Homomorphic Encryption (mention)
- Zero-Knowledge Proofs