1 |
2015.08.27 |
- introduction to the course
- negligible and noticeable functions
- (uniform and non-uniform) probabilistic polynomial time algorithms
- one-way functions (strong and weak)
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 2.2 , One-way functions: definitions
- Introduction to Modern Cryptography
Papers:
Videos:
Scribe notes: by Brian Gluzman
|
2 |
2015.09.01 |
- hardness amplification: from weak to strong one-way functions
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 2.3, Weak one-way functions imply strong ones
Videos:
Scribe notes: by David Dinh
|
3 |
2015.09.03 |
- universal one-way functions
- hardcore predicates
- Goldreich–Levin predicate
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 2.4.1, Universal one-way function
- § 2.5, Hard-core predicates
- Introduction to Modern Cryptography
- § 7.3, Hard-core predicates from one-way functions
Videos:
Scribe notes: by Akshayaram Srinivasan
|
4 |
2015.09.08 |
- statistical vs computational indistinghuishability of distributions
- hybrid argument
- pseudorandomness generators (PRGs)
- one-way permutations imply PRGs with 1-bit expansion
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 3.1, Motivating discussion
- § 3.2, Computational indistinguishability
- § 3.3.1, Standard definition of pseudorandom generators
- § 3.4, Constructions based on one-way permutations
- Introduction to Modern Cryptography
- § 7.8, Computational indistinguishability
- § 7.4, Constructing pseudorandom generators
Videos:
Scribe notes: by Tobias Boelter
|
5 |
2015.09.10 |
- PRGs evaluated on independent seeds
- PRGs with 1-bit expansion imply PRGs with polynomial expansion
- pseudorandom functions
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 3.3.2, Increasing the expansion factor
- § 3.6, Pseudorandom functions
- Introduction to Modern Cryptography
- § 7.5, Constructing pseudorandom functions
Videos:
Scribe notes: by Pratyush Mishra
|
6 |
2015.09.15 |
- PRGs imply pseudorandom functions
- pseudorandom permutations
- Feistel permutations
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 3.6, Pseudorandom functions
- § 3.7, Pseudorandom permutations
- Introduction to Modern Cryptography
- § 7.5, Constructing pseudorandom functions
- § 7.6, Constructing (strong) pseudorandom permutations
Videos:
Papers:
Scribe notes: by Brian Gluzman
|
7 |
2015.09.17 |
- Luby–Rackoff construction of pseudorandom permutations
- commitment schemes
- one-way permutations imply 1-bit commitment schemes
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 3.7, Pseudorandom permutations
- § 4.4.1, Commitment schemes
Papers:
Scribe notes: by Rohan Mathuria
|
8 |
2015.09.22 |
- 1-bit commitment schemes imply multi-bit commitment schemes
- intro to encryption schemes
- single-message perfect message indistinguishability
- one-time pad and its limitations
- single-message computational message indistinguishability
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 5.1, The basic setting
- § 5.2, Definitions of security
- Introduction to Modern Cryptography
- § 2, Perfectly secret encryption
- § 3.1, Computational security
- § 3.2, Defining computationally secure encryption
Papers:
Videos:
Scribe notes: by Pratyush Mishra
|
9 |
2015.09.24 |
- equivalence of message indistinguishability and semantic security
- shrinking one-time pad's key with PRGs
- multi-message computational message indistinguishability
- security against chosen plaintext attacks
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 5.3.3, Private-key encryption schemes
- § 5.4.3, Chosen plaintext attack
- Introduction to Modern Cryptography
- § 3.3, Constructing secure encryption schemes
- § 3.4, Stronger security notions
Papers:
Videos:
Scribe notes: by Eleanor Cawthon
|
10 |
2015.09.29 |
- PRFs imply security against chosen plaintext attacks
- modes of encryption
- security against CPA vs CCA1 vs CCA2
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 5.4.4, Chosen ciphertext attack
- Introduction to Modern Cryptography
- § 3.5, Constructing CPA-secure encryption schemes
- § 3.6, Modes of operation
- § 3.7, Chosen-ciphertext attacks
Papers:
Videos:
Scribe notes: by Joseph Hui
|
11 |
2015.10.01 |
- message authentication codes
- constructions based on PRFs
- CPA security and MACs imply CCA2 security
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 6.1, The setting and definitional issues
- § 6.3, Constructions of message authentication schemes
- § 6.1.5.1, Augmenting the attack with a verification oracle
- Introduction to Modern Cryptography
- § 4.1, Message integrity
- § 4.2, Message authentication codes - definitions
- § 4.3, Constructing secure message authentication codes
- § 4.4, CBC-MAC
Papers:
Videos:
Scribe notes: by David Fifield
|
12 |
2015.10.06 |
- CPA security and MACs imply CCA2 security
- combining CPA security and MACs in other (insecure) ways
- collision-resistant functions
- Merkle–Damgård transform
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 6.2.3, Constructing collision-free hashing functions
- Introduction to Modern Cryptography
- § 4.5, Authenticated encryption
- § 5.1.1, Collision resistance
- § 5.2, Domain extension: the Merkle–Damgård transform
- § 5.4, Generic attacks on hash functions
Papers:
Videos:
Scribe notes: by Tongzhou Wang
|
13 |
2015.10.08 |
- intro to public-key cryptography
- public-key encryption schemes
- trapdoor one-way permutations
- TOWPs imply public-key encryption schemes
- RSA as a TOWP
- hybrid encryption
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 5.1.1, Private-key versus public-key schemes
- § 5.1.2, The syntax of encryption schemes
- § 5.3.4, Public-key encryption schemes
- § 5.5.1, On using encryption schemes
- Introduction to Modern Cryptography
- § 11.1, Public-key encryption - an overview
- § 11.2, Definitions
- § 11.5, RSA encryption
- § 13.1, Public-key encryption from trapdoor permutations
Papers:
Scribe notes: by Xingyou Song
|
14 |
2015.10.13 |
- finish hybrid encryption
- DDH assumption (and where it might hold)
- ElGamal encryption scheme
- CCA2 security in the asymmetric setting
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 5.5.3, On some popular schemes
- Introduction to Modern Cryptography
- § 8.3, Cryptographic assumptions in cyclic groups
- § 11.3, Hybrid encryption and the KEM/DEM paradigm
- § 11.4, CDH/DDH-based encryption
Papers:
Scribe notes: by Peter Manohar
|
15 |
2015.10.15 |
- CCA2 security in the random oracle model
- definition of signature schemes
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 6.1, The setting and definitional issues
- Introduction to Modern Cryptography
- § 11.5.5, A CCA-Secure KEM in the random-oracle model
- § 12.1, Digital signatures - an overview
- § 12.2, Definitions
Papers:
Scribe notes: by Lynn Chua
|
16 |
2015.10.20 |
- one-time signatures
- hash-then-sign paradigm
- key refreshing
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 6.2, Length-restricted signature scheme
- § 6.4.1, One-time signature schemes
- Introduction to Modern Cryptography
- § 12.2, The hash-and-sign paradigm
- § 12.6.1, Lamport's signature scheme
- § 12.6.2, Chain-based signatures
Papers:
Scribe notes: by Benjamin Caulfield
|
17 |
2015.10.22 |
- from one-time signatures to full security
- signatures in the random oracle model
- signcryption
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 2
- § 6.4.2, From one-time signature schemes to general ones
- Introduction to Modern Cryptography
- § 12.4.2, RSA-FDH
- § 12.6.3, Tree-based signatures
- § 12.9, Signcryption
Papers:
Scribe notes: by Willem Y. Van Eck
|
18 |
2015.10.27 |
- interactive proofs
- graph isomorphism is in IP
- honest-verifier zero knowledge
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 4.1, Zero-knowledge proofs: motivation
- § 4.2, Interactive proof systems
- § 4.3, Zero-knowledge proofs: definitions
Papers:
Videos:
Scribe notes: by Pasin Manurangsi
|
19 |
2015.10.29 |
- interactive proofs
- honest-verifier zero knowledge
- (malicious-verifier) zero knowledge
- perfect zero knowledge for graph isomorphism
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 4.1, Zero-knowledge proofs: motivation
- § 4.2, Interactive proof systems
- § 4.3, Zero-knowledge proofs: definitions
Papers:
Videos:
Scribe notes: by Chenyang Yuan
|
20 |
2015.11.03 |
- computational zero knowledge for graph 3-coloring
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 4.4, Zero-knowledge proofs for NP
Papers:
Scribe notes: by Praagya Singh
|
21 |
2015.11.05 |
- computational zero knowledge for graph 3-coloring
- zero knowledge is not closed under parallel composition
- witness indistinguishability
- parallel composition for witness indistinguishability
|
Lecture notes:
Textbooks:
- Foundations of Cryptography, Volume 1
- § 4.4, Zero-knowledge proofs for NP
- § 4.5.4, Zero-Knowledge and parallel Composition
- § 4.6, Witness indistinguishability and hiding
Papers:
|
22 |
2015.11.10 |
- VBB obfuscation for TMs and circuits
- impossibility of VBB obfuscation
|
Lecture notes:
Papers:
|
23 |
2015.11.12 |
- indistinguishability obfuscation (iO)
- witness encryption
- iO implies witness encryption
- iO and OWFs imply public-key encryption
- best-possible obfuscation (BPO)
- VBBO implies BPO
- BPO vs IO
|
Lecture notes:
Papers:
Videos:
Scribe notes: by Joseph Hui
|
24 |
2015.11.17 |
- iO amplification: from NC1 to all circuits
- iO and coRP != NP implies OWFs
|
Lecture notes:
Papers:
- Candidate indistinguishability obfuscation and functional encryption for all circuits (by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters)
- There is no indistinguishability obfuscation in Pessiland (by Tal Moran and Alon Rosen)
- One-way functions and (im)perfect obfuscation (by Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev)
Videos:
Scribe notes: by Linyue Zhu
|
25 |
2015.11.19 |
- iO and coRP != NP implies OWFs
- VBB implies OWFs
- differing-inputs obfuscation
- extractable witness encryption
|
Papers:
- On the (im)possibility of obfuscating programs (by Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang)
- One-way functions and (im)perfect obfuscation (by Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev)
- Differing-inputs obfuscation and applications (by Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry)
- On Extractability (a.k.a. Differing-Inputs) Obfuscation (by Elette Boyle, Kai-Min Chung, and Rafael Pass)
Videos:
Scribe notes: by Akshay Ramachandran
|
26 |
2015.11.24 |
Class project presentations:
- Tobias Boelter, Akshay Srinivasan
- Alex Irpan
- Tongzhou Wang
- Brian Gluzman
- Pratyush Mishra
- Gil Lederman
|
|
X |
2015.11.26 |
No class.
|
No class.
|
27 |
2015.12.01 |
Class project presentations:
- Joseph Hui, Chenyang Yuan
- Rohan Mathuria
- Akshay Ramachandran
- Qi Zhong, Linyue Zhu
|
|
28 |
2015.12.03 |
Class project presentations:
- Lynn Chua, Pasin Manurangsi
- David Dinh
- Peter Manohar, Xingyou Song
- Willem Van Eck
- Ben Caulfield
- Praagya Singh
|
Parting materials:
|