Welcome to CS 171!

Alice and Bob

Week 1

Aug 27

Lecture Introduction. Private-key cryptography. The syntax of private-key encryption. Kerckhoffs’s principle. Historical ciphers: the shift cipher.: KL 1.1-1.3

Week 2

Sep 1

Lecture Historical ciphers and their cryptanalysis: substitution and Vigenère ciphers. Principles of Modern Cryptography: definitions, assumptions, and proofs. Defining perfectly secure encryption; three equivalent definitions of perfect secrecy.: KL 1.4 and 2.1

Sep 2

Discussion Discussion 1 (Solution)

Sep 3

Homework Homework 1 (LaTeX Template, Solution)

Sep 3

Lecture Game-Based Definition for Encryption. The one-time pad. Limitations of perfect secrecy. A computational notion of security.: KL 2.2-2.3, 3.1, and 3.2.1

Week 3

Sep 8

Lecture Pseudorandomness. The pseudo-OTP. Proofs by reduction, and a proof of security for the pseudo-OTP.: KL 3.3

Sep 8

Discussion Discussion 2 (Solution)

Sep 9

Homework Homework 2 (LaTeX Template, Solution)

Sep 10

Lecture Security for multiple encryptions. Drawbacks of deterministic encryption. Chosen-plaintext attacks and CPA-security. Pseudorandom Functions. CPA Secure Encryption from Pseudorandom Functions: KL 3.4 and 3.5

Week 4

Sep 15

Lecture Multiple-message security vs. CPA-security. Hybrid Arguments. Chosen-Ciphertext Attacks and CCA-security.: KL 3.6 and 3.7

Discussion Discussion 3 (Solution)

Sep 17

Lecture Practical constructions of stream ciphers (LFSRs, Trivium, RC4). Pseudorandom permutations and block ciphers. Modes of operation.: KL 6.1 and 6.2.1

Week 5

Sep 22

Lecture Practical constructions of block ciphers. Substitution-permutation networks (SPNs). Feistel Networks. The data encryption standard (DES). Double and triple DES; meet-in-the-middle attacks.: KL 6.2.1, 6.2.2, 6.2.3, and 6.2.4.

Sep 24

Midterm Midterm I

Sep 26

Homework Homework 3 (LaTeX Template)

Week 6

Sep 29

Lecture Message integrity and message authentication codes (MACs). Defining security for MACs. Constructing MACs.: KL 4.1, 4.2, 4.3 and 4.4.1

Discussion Discussion 4 (Solution)

Oct 1

Lecture Authenticated encryption and CCA-security.: KL 4.5.1, and 4.5.2 (no proof), 4.5.3, 4.5.4

Oct 3

Homework Homework 4 (LaTeX Template)

Week 7

Oct 6

Lecture Hash functions and collision resistance. Birthday attacks on hash functions. Domain extension: the Merkle-Damgård transform. Hash-and-MAC. Additional applications of hash functions.: KL 5.1.1, 5.2, 5.3.1, 5.4.1, and 5.6.1-5.6.3

Discussion Discussion 5 (Solution)

Oct 8

Lecture One-way functions. Hardness concentration bits (hard-core predicates). A PRG from a one-way permutation.: KL 7.1, 7.2, 7.3.1, 7.4, 7.5, and 7.7

Oct 9

Homework Homework 5 (LaTeX Template)

Week 8

Oct 13

Lecture Increasing the stretch of PRGs. PRFs from PRGs (GGM). Limitations of private-key cryptography; key-distribution centers. Groups. The discrete-logarithm assumption. Collision-resistant hash functions from discrete log.: KL 8.1.1-8.1.2 (self-study), 8.1.3, 8.3.1-8.3.3, 8.4.2, and 10

Discussion Discussion 6 (Solution)

Oct 15

Lecture Diffie-Hellman problems. Key exchange and the Diffie-Hellman key-exchange protocol. Public-key encryption: syntax and definitions of security. El Gamal encryption. Hybrid encryption.: KL 11.1 11.2, 11.4.1, and 11.4.4 (only the discussion that El Gamal encryption is malleable).

Week 9

Oct 20

Lecture Hybrid encryption and the KEM/DEM paradigm. El Gamal is not CCA-secure: malleability and homomorphism. Encryption combiners. Composite-order groups. RSA encryption.: 11.3 (skip proof of Theorem 11.12), 11.4.2, and 11.5.1

Discussion Discussion 7 (Solution)

Oct 22

Lecture Digital signatures. Certificates and public-key infrastructures. Textbook RSA signatures and their insecurity. The hash-and-sign paradigm. Identification schemes: the Schnorr identification scheme.: KL 12.1-12.3, 12.4.1, 12.5.1, and 12.7

Week 10

Oct 27

Lecture The random-oracle model. RSA-FDH signatures. The Fiat-Shamir transform and Schnorr signatures.: KL 5.5, 12.4.2, and 12.5.2; Joy of Cryptography, Ch. 12 and Ch. 16

Oct 29

Midterm Midterm II

Week 11

Nov 3

Lecture Pairings, Identity Based Encryption, CCA Secure Public-Key Encryption: Boneh & Shoup, Chapter 15

Nov 5

Lecture Commitment Schemes: Special Topics

Week 12

Nov 10

Lecture Zero-Knowledge Proofs: Supplemental Materials

Nov 12

Lecture Zero-Knowledge Proofs: Supplemental Materials

Week 13

Nov 17

Lecture Succinct Proofs: Special Topics

Nov 19

Lecture Secret Sharing: Special Topics

Week 14

Nov 24

Lecture Multiparty computation: Special Topics

Nov 26

Holiday No Class — Academic and Administrative Holiday (Thanksgiving)

Week 15

Dec 1

Lecture Special Topics: Special Topics

Dec 3

Lecture Special Topics: Special Topics

Week 17

Dec 18: Final Exam Final Exam