Table of Lecture Notes

“Date” links to scribe notes, and “Topic” links to the note on this website.

Date	Topic	References
Aug 27	Course outline, security definition	[Ps 1.1-1.3], [KL 1.1,1.2,1.4,2.1]
Aug 29	Perfect security, one-time pads, Efficient computation	[Ps 1.3], [KL 2.1-2.3]
Sep 3	Non-uniform, computational indistinguishability	[Ps 2.1,3.1-3.2], [KL 3.1-3.3]
Sep 5	Hybrid lemma, PRGs	[Ps 3.1-3.3], [KL 3.3]
Sep 10	PRG expansion	[Ps 3.3], [KL 3.3]
Sep 12	Pseudorandom functions	[Ps 3.7, 3.8] [KL 3.5]
Sep 17	CPA-secure encryption	[Ps 3.9] [KL 3.2, 3.4]
Sep 19	GGM PRF	[Ps 3.7, 3.8] [KL 8.5], Abhishek@JHU, Goldwasser@Berkeley, Wichs@Northeastern
Sep 24	One-way functions	[Ps 2.2] [KL 8.1]
Sep 26	Factoring, From weak to strong OWF	[Ps 2.3-2.4], [KL 9.2.3], Wichs@NEU, Goldwasser@Berkeley, LTW05
Oct 1	Universal OWF	[Ps 2.13], Wichs@NEU
Oct 3	Hard-core lemma	[Ps 3.4] [KL 8.3.3] Bellare@UCSD
Oct 8	Hard-core lemma, proof	[Ps 3.4] [KL 8.3.3] Bellare@UCSD
Oct 10	PRG from any OWF	Vadhan12, Sec 6
Oct 17	Leftover Hash Lemma	Vadhan12, Sec 6, Barak@Princeton
Oct 22	Weak Pseudor-Entropy Generator	Barak@Princeton
Oct 24	Regular OWFs to PEG	Barak@Princeton
Oct 29	MAC and digital signatures	[Ps 5.1-5.3] [KL 4.1-4.3, 13.1]
Oct 31	Cryptographic hash functions	[Ps 5.5] [KL 6.1-6.3]
Nov 07	Hash and MAC	[Ps 5.5] [KL 6.3]
Nov 12	Digital Signature	[Ps 5.3] [KL 13.1, 13.2, 13.6, 14.4], Lamport’79, Goldwasser@Berkeley
Nov 14	Zero-knowledge proof, definition	[Ps 4.1-4.6]
Nov 19	ZKP for graph 3-coloring	[Ps 4.7]
Nov 21	ZKP and NP reduction	[Ps 4.7-4.9]
Nov 26-Part1	ZKP and NP reduction	[Ps 4.7-4.9]
Nov 26-Part2	ZKP and NP reduction	[Ps 4.7-4.9]
Dec 03-Part2	Learning with errors, homomorphic encryption	[KL 14.3]
Dec 03-Part2	Learning with errors, homomorphic encryption	[KL 14.3]