CUNY Graduate Center
Computer Science Department
Dr. Nelly Fazio
Lectures: Wednesdays, 11:45am–1:45pm (Room 4422)
Office hours: By appointment
Email: nfazio AT gc DOT cuny DOT edu [Put Modern Cryptography in Subject line]
[ Course Description | List of Topics | Textbook | Grading | Assignments | Weekly Schedule ]
You are encouraged to solve all problem questions on your own, but brainstorming difficult questions with other classmates is of course permitted. You must, however, write the solution individually and list your collaborators for each problem set. Discussing the assignments with anyone outside the class is not permitted, nor is consulting solutions to assignments that were used in previous offerings of this course or similar ones at other institutions.
I strongly encourage you to prepare your PDF solution sets using LaTeX.
|1||Introduction. Classical vs. Modern Cryptography.
Brush-up on Probability Theory. Information-Theoretic Security.
|KL Ch. 1–2
KL Appendix A
|2||More on Perfect Secrecy. From Information Theory to the Computational Approach.||KL Ch. 3.1|
|3||Brush-up on Number Theory.|| KL Appendix B |
KL Ch. 7.1, 7.2.1,
|4||Computational-Secure Private-Key Encryption. Pseudorandomness. Pseudorandom generators.||KL Ch. 3.2–3.4.2|
One-Way Functions. One-Way Permutations.
OWF Candidate: Integer Multiplication. OWP Candidate: Modular
Quadratic Residue. Legendre Symbol. LSB. MSB. Hardcore Bits. Goldreich-Levin Theorem.
|KL 6.1, 6.2,
|6||Next-Bit Unpredictability. Blum/Micali Construction. Pseudo Random
Computational Indistinguishability. Hybrid Argument.
|7||Blum-Micali construction. Efficient instantiation: Blum-Blum-Shub
Pseudo-random functions (PRF). Goldreich-Goldwasser-Micali construction.
Application of PRF. Pseudo-random permutations (PRP). Feistel Network. Luby-Rackoff construction.
|KL 3.6.1, 6.5
KL 3.6.2, 3.6.3, 6.6
Security for Multiple Encryptions. Security Against Chosen-Plaintext
Security Against Chosen-Ciphertext Attacks (CCA). Block-ciphers and mode of operations.
Integrity. Message Authentication Codes (MACs).
ε-universal, universal one-way, and collision resistant hash functions.
Merkle-Damgaard construction. Hash-then-MAC paradigm.
|KL 3.4.3, 3.5
|9||Diffie-Hellman Key Exchange. Asymmetric
Public-Key Encryption. Security Against Chosen-Plaintext Attacks (CPA).
|KL 9, 10.1–10.2|
Security for Multiple Encryptions. Hybrid
Security Against Chosen-Ciphertext Attacks (CCA).
|KL 10.2.2, 10.3, 10.5, 10.6|
|11|| Trapdoor Permutations and Hardcore
Construction. Example of trapdoor permutations: RSA. OAEP. OAEP+
|KL 10.4 10.7|
|12||Digital Signatures. The Hash_then_Sign paradigm.
One Time Signature Schemes. Lamport's Scheme.
Rabin and RSA Schemes. Padding Schemes (PSSR).
|13||Schnorr signature scheme. Signature schemes for multiple messages:
"chain-based" signatures and "tree-based" signatures
|Final Report Presentations|
Copyright © Nelly Fazio