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

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

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