Modern Cryptography Fall 2021

CUNY Graduate Center Computer Science Department

Instructor: Dr. Nelly Fazio
Lectures: Tuesdays, 11:45am–1:45pm (ONLINE)
Office hours: Thursdays, 11:00am–12:00pm (and by appointment), Online
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

Textbook

• Introduction to Modern Cryptography (2nd edition)
  by Jonathan Katz and Yehuda Lindell.

• 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).

Grading

• 40%: Assignments.
• 50%: Term paper.
• 10%: Class participation.

Assignments

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)

Copyright © Nelly Fazio