Cryptography and Communications Security (CS 6750)

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

Problem Sets, Lecture Slides

Log-in to Piazza to view course materials.

Schedule

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.

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.

Course Description

This is a graduate-level course that serves as an introduction to cryptography. We will define various cryptographic notions such as one-way functions, pseudorandom generators, symmetric & public key encryption, message-authentication codes, signatures, etc. The course will focus on understanding what these notions mean, what practical problems they aim to solve, the relationships between them, and how to construct them using number theory. We will emphasize the need to rely on precise mathematical definitions and rigorous proofs to analyze security. Towards the end of the course, we will also cover some fun advanced topics such as coin-flipping over the phone, and zero-knowledge proofs. We will need elementary number-theory to build many of the cryptosystems, and will cover all of required math as-needed, without attempting to be comprehensive. No prior knowledge of cryptography or number theory is assumed.

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.

Logistics

Lecture Time: 6:00 pm - 9:00 pm on Tuesdays
Location: Forsyth Building, room 241.
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: 40%, Midterm 20%, Final: 30%, Participation: 10%
Optional project: You can do a class project for fun or to improve your grade.

Pre-requisites

The main pre-requisite is mathematical maturity and comfort with understanding/writing proofs. It may help if you have taken Theory of Computation, Algorithms and Probability, but none of these are crucial.

Resources

We will use the textbook Introduction to Modern Cryptography by Katz and Lindell, although we will often deviate from it.
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.

Tentative Syllabus

Introduction

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

Information-Theoretic Cryptography

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

Basic Primitives & Definitions

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

Symmetric-Key Encryption

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

Message-Authentication & Collision-Resistant Hashing

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

Number-Theory Review & Computational Hardness Assumptions

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

More Public-Key Encryption

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

Signature Schemes

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

Advanced Topics

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