Aug 23 | Course outline, security definition | [Ps 1.1-1.3], [KL 1.1,1.2,1.4,2.1] |
Aug 28 | Perfect security, one-time pads | [Ps 1.3], [KL 2.1-2.3] |
Aug 30 | One-way functions, factoring | [Ps 2.1-2.3], [KL 8.1.1-8.1.2, 9.2, 9.2.3] |
Sep 4 | Factoring, reduction | [Ps 2.3-2.4], [KL 9.2.3] |
Sep 6 | From weak to strong OWF | [Ps 2.4], Wichs@NEU, Goldwasser@Berkeley, LTW05 |
Sep 11 | Primality testing | [KL 9.2.2] |
Sep 13 | Finish Miller-Rabin, universal OWF | [Ps 2.13], Wichs@NEU |
Sep 18 | Computational indistinguishability | [Ps 3.1] |
Sep 20 | Pseudo-random generators | [Ps 3.3.5] [KL 3.3, 8.4.2] |
Sep 25 | Pseudo-random functions | [Ps 3.7, 3.8] [KL 8.5] |
Sep 27 | CPA-secure encryption | [Ps 3.9] [KL 3.2, 3.4] |
Oct 4 | Construct PRG, hard-core lemma | [Ps 3.4] [KL 8.1.3,8.2,8.3] |
Oct 9 | Hard-core lemma | [Ps 3.4] [KL 8.3.3] Bellare@UCSD |
Oct 11 | Recitation, pairwise independent hash, entropy | [V, Pseudorandomness] Barak@Princeton |
Oct 16 | Weak pseudo-entropy generator | Barak@Princeton |
Oct 18 | Pseudo-entropy generator | [Barak@Princeton] |
Oct 23 | From PEG to PRG | [Barak@Princeton] |
Oct 25 | Message Authentication | [Ps 5.1, 5.2] [KL 4.1-4.3] |
Oct 30 | Digital Signatures | [Ps 5.3] [KL 13.1, 13.2, 13.6, 14.4], Lamport’79, Goldwasser@Berkeley |
Nov 1 | Collision-resistant hash, discrete log | [Ps 5.5] [KL 9.3] |
Nov 6 | Zero-knowledge proofs, commitments | [Ps 4.1-4.6] |
Nov 8 | ZKP for graph 3-coloring | [Ps 4.7-4.9] |
Nov 13 | Learning with errors, homomorphic encryption | [KL 14.3] |
Nov 15 | Public-key encryption, multiplicative HE | Rothblum, TCC 2011, BV, FOCS 2011 BGV, ITCS 2012 |
Nov 20 | Bootstrapping FHE, PIR | Gentry, STOC 2009, LMW, STOC 2023 |
Nov 27 | Shamir secret sharing | [Ps 6.1], Arora@Princeton |
Nov 29 | Yao’s garbling, oblivious transfer | [Ps 6.2], Barak@Princeton |
Dec 4 | Project presentations | |