Warning: This is the Spring 2019 course website.
The latest CS355 website is online here.

Course Schedule

Date	Topic and Readings
Foundations of Cryptography
April 1 (Henry)	Topics (Lecture Notes) Logistics and administration Merkle Puzzles The Random-Oracle Model If time: Commitments from random oracles Readings Boneh-Shoup (Section 2.4, 3.4.2-3.4.3)
April 3 (Dima)	Topics (Lecture Notes) Basic cryptogrpahic primitives and the relation between them: OWFs, PRGs, PRFs The Blum-Micali PRG and hybrid arguments
Cryptographic Protocols
April 8 (Florian)	Topics (Lecture Notes) The Blum-Micali PRG and hybrid arguments (cont.) Interactive proof systems
April 10 (Henry)	Topics (Lecture Notes) Definition of zero-knowledge proofs A zero-knowledge protocol for Hamiltonicity Readings Boaz Barak's notes on Zero Knowledge (Read until section on quadratic residues) Sanjam Garg's lecture notes Just for fun: Knuth on Hamiltonian paths and cycles
April 12	Problem Set 1 Due at 5pm via Gradescope.
April 15 (Dima)	Topics (Lecture Notes) Proofs of knowledge Non-interactive zero-knowledge Fiat-Shamir heuristic Readings Susan Hohenberger's lecture notes on Fiat-Shamir Boneh-Shoup (Section 19.1, 20.3)
April 17 (Dima)	Topics (Lecture Notes) Sigma protocols Secret sharing Readings Sigma protocols: Boneh-Shoup, Sections 19.4–19.6 On Σ-protocols, by Ivan Damgård Shamir secret sharing: How to Share a Secret, by Adi Shamir (CACM 1979) Boneh-Shoup, Section 11.6.1
Privacy-Preserving Protocols
April 22 (Florian)	Topics (Lecture Notes) Multiparty computation Readings A Pragmatic Introduction to Secure Multi-Party Computation, by Evans et al. (Chapters 2 and 3) Nigel Smart's slides on MPC and Secret Sharing
April 24 (Henry)	Topics (Lecture Notes) Private Information Retrieval
April 26	Problem Set 2 Due at 5pm via Gradescope
April 29 (Florian)	Topics (Lecture Notes) Differential privacy Readings Two great surveys: The Algorithmic Foundations of Differential Privacy, by Cynthia Dwork and Aaron Roth Differential Privacy: A Survey of Results, by Cynthia Dwork
Cryptanalysis
May 1 (Henry)	Topics (Lecture Notes) Real-world cryptanalysis: Infineon attack Readings The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli, by Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, and Vashek Matyas (CCS 2017) Mining Your Ps and Qs - Widespread Weak Keys in Network Devices, by Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman (USENIX Security 2012)
May 6 (Dima)	Topics (Lecture Notes) Discrete-log algorithms: Baby-Step Giant-Step, Pollard Rho Shoup's Lower Bound for Generic Algorithms Readings Chapters 13 and 14 in Galbraith's book Notes for Lecture 10 of Sutherland's class at MIT
Elliptic-Curve Cryptography
May 8 (Dima)	Topics (Lecture Notes) Introduction to elliptic curves Readings Boneh-Shoup (Chapter 15) Elliptic Curve Cryptosystems, by Neal Koblitz
May 10	Problem Set 3 Due at 5pm via Gradescope
May 13 (Florian)	Topics (Lecture Notes) Pairings-based cryptography: 3-party key-exchange, short signatures, identity-based encryption Readings Short Signatures from the Weil Pairing, by Dan Boneh, Ben Lynn, and Hovav Shacham (Asiacrypt 2001) Identity-Based Encryption from the Weil Pairing, By Dan Boneh and Matthew Franklin (Crypto 2001). This paper is quite approachable and enjoyable to read
Post-Quantum Cryptography
May 15 (Henry)	Topics (Lecture Notes) The short integer solutions (SIS) problem SIS Hash Function Readings A Decade of Lattice Cryptography (Sections 2.2 and 4.1), by Chris Peikert
May 20 (Florian)	Topics (Lecture Notes) Lattice signatures The learning with errors (LWE) problem Regev encryption Readings A Decade of Lattice Cryptography (Sections 4.2 and 5.2.1), by Chris Peikert
May 22 (Henry)	Topics (Lecture Notes, see also David Wu's notes from last year) Fully homomorphic encryption (FHE) Readings A Decade of Lattice Cryptography (Section 6.1), by Chris Peikert
May 24	Problem Set 4 Due at 5pm via Gradescope
May 27	No class: Memorial Day holiday
May 29 (Dima)	Topics (Lecture Notes) Succinct Non-interactive Arguments (SNARGs) Readings Succinct Non-Interactive Arguments via Linear Interactive Proofs, by Bitansky, Chiesa, Ishai, Ostrovsky, and Paneth (TCC 2013) Alessandro Chiesa's class on proof systems at Berkeley Several blog posts give an accessible explanation of zkSNARKs
June 3 (Florian)	Topics (Lecture Notes) Program obfuscation Readings Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Garg et al. (FOCS 2013, SIAM Journal on Computing 2016)
June 5 (Henry)	Topics (Lecture Notes) Time-memory tradeoffs and preprocessing attacks Readings A Cryptanalytic Time - Memory Trade-Off by Hellman (Transactions on Info. Theory 1980) Rigorous time/space tradeoffs for inverting functions by Fiat and Naor (STOC 1991)
June 7	Problem Set 5 Due at 5pm via Gradescope

Warning: This is the Spring 2019 course website. The latest CS355 website is online here.

Warning: This is the Spring 2019 course website.
The latest CS355 website is online here.