Table of Lecture Notes

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