CSc 85031: Modern Cryptography

Instructor: Dr. Nelly Fazio
Lectures: Thursdays, 11:45am–1:45pm (Room 3310B)
Office hours: By appointment (Room 4439)
Email: nfazio AT gc DOT cuny DOT edu

Textbook

Foundations of Cryptography, Volumes 1 and 2
by Oded Goldreich. Cambridge University Press. 2001.
Preliminary notes of these books are available on-line.
A comprehensive treatment of the theoretical foundations of cryptography.

A Computational Introduction to Number Theory and Algebra, 2nd Edition
by Victor Shoup. Cambridge University Press. 2008.
Notes of this book are freely available on-line, under the Creative Commons license.
A great source for computational number theory.

Introduction to Cryptography, New York University, Fall 2008.
Lecture notes for a course taught by Yevgeniy Dodis at NYU in the Fall 2008.

List of Topics

Introduction

Classical vs. modern cryptography.
Information-theoretic security: Shannon's definition of perfect secrecy. Vernam's one-time pad.
Limitation of the information theoretic approach.

Computational Hardness and One-Wayness

One-way functions. One-way permutations. Trapdoor permutations. Concrete examples: integer multiplication and modular exponentiation.
Hardcore predicates. Goldreich-Levin construction.
Pseudo-random generators. Blum-Micali construction. Efficient instantiation: Blum-Blum-Shub construction.
Pseudo-random functions. Goldreich-Goldwasser-Micali construction.
Pseudo-random permutations. Luby-Rackoff construction.
ε-universal, universal one-way, and collision resistant hash functions. Merkle-Damgaard construction.
The hash-the-MAC paradigm.

Computationally Secure Symmetric Cryptography

Definition of secure symmetric encryption: IND, CPA, CCA.
Block-ciphers and mode of operations.
Message authentication codes.
Hash-then-authenticate paradigm.

Managing Shared Keys

The key distribution problem
Diffie-Hellman Key Exchange

Computationally Secure Asymmetric Cryptography

Definition of secure asymmetric encryption: IND, CPA, CCA.
Efficient constructions (ElGamal, RSA and Rabin's schemes) and padding schemes (OAEP+).
Blum-Goldwasser construction. Goldwasser-Micali construction.

Digital Signatures

Definition of secure digital signatures.
Lamport's one-time signature scheme.
The hash-then-sign paradigm.
Rabin and RSA signature schemes. Padding Schemes (PSS, PSSR).
Schnorr signature scheme.
Signature schemes for multiple messages: chain-based and tree-based constructions.

A taste of more advanced topics (identification schemes, commitment schemes, secret sharing).

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

Modern Cryptography

CSc 80010–Fall 2018

Course Description

Textbook

List of Topics

Weekly Schedule (tentative)