Modern Cryptography

Fall 2019

CUNY Graduate Center
Computer Science Department

Instructor: 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 ]

Course Description

This introductory, graduate-level course covers the theoretical foundations of modern cryptography. Emphasis will be placed on precise definitions, rigorous proof techniques, and analysis of the relations among the various cryptographic primitives (such as one-way functions, pseudo-random generators, pseudo-random permutations, and trapdoor permutations). List of topics includes: computational security, cryptographic hash functions, private-key encryption, message authentication codes, public-key encryption, digital signatures, commitment schemes. No previous knowledge of cryptography is required. However, general ease with algorithms and elementary probability theory, and maturity with mathematical proofs will be assumed.


Required: Recommended:

List of Topics


Grading will be based on the assignments, a term paper and class attendance/participation, according to the following tentative grading policy:


Assignments must be submitted by 11:55pm on the due date. The preferred submission method is as PDF attachment to my e-mail address.

Collaboration Policy
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.

LaTeX Tutorial
I strongly encourage you to prepare your PDF solution sets using LaTeX.

Weekly Schedule (tentative)

Lecture Topic Readings
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,
7.2.3-7.2.4, 7.3.1-7.3.3
4 Computational-Secure Private-Key Encryption. Pseudorandomness. Pseudorandom generators. KL Ch. 3.2–3.4.2
5 One-Way Functions. One-Way Permutations. OWF Candidate: Integer Multiplication. OWP Candidate: Modular Exponentiation.
Quadratic Residue. Legendre Symbol. LSB. MSB. Hardcore Bits. Goldreich-Levin Theorem.
KL 6.1, 6.2,
6.3.1, 7.4.1
6 Next-Bit Unpredictability. Blum/Micali Construction. Pseudo Random Generators.
Computational Indistinguishability. Hybrid Argument.
KL 6.4
7 Blum-Micali construction. Efficient instantiation: Blum-Blum-Shub construction.
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
8 Security for Multiple Encryptions. Security Against Chosen-Plaintext Attacks (CPA).
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
3.6.2-3.6.4, 3.7
KL 4.1–4.6.4
9 Diffie-Hellman Key Exchange. Asymmetric Setting. Computationally-Secure
Public-Key Encryption. Security Against Chosen-Plaintext Attacks (CPA).
KL 9, 10.1–10.2
10 Security for Multiple Encryptions. Hybrid Encryption. ElGamal.
Security Against Chosen-Ciphertext Attacks (CCA).
KL 10.2.2, 10.3, 10.5, 10.6
11 Trapdoor Permutations and Hardcore Predicates. Blum-Goldwasser
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).
KL 12.1–12.5
13 Schnorr signature scheme. Signature schemes for multiple messages:
"chain-based" signatures and "tree-based" signatures
KL 12.6
14 TBD
Final Report Presentations

Copyright © Nelly Fazio