Introduction to Cryptography

Key Information

Overview

Cryptography is magical, it solves paradoxical problems such as communicating privately without ever meeting, proving you know a secret without revealing it, or computing over encrypted data. This magic is, in fact, based on a rigorous theory with beautiful definitions and proofs of security founded on computational complexity.

The course will provide a graduate-level introduction to the theory of cryptography. We will cover foundational concepts, abstractions, and techniques, with the aim of giving students the basic tools needed to start research in the area. We will also sneak a peek into some advanced topics as time permits.

Tentative list of topics

• Introduction
  • Perfect secrecy and its limitations.
• Computational Hardness
  • Computationally-bounded adversaries
  • One-way functions
  • Hardness amplification
• Indistinguishability and Pseudorandomness
  • Computational indistinguishability
  • Cryptographic pseudorandom generators and pseudorandom functions
  • Multi-message encryption and authentication
  • Hardcore bits and the Goldreich-Levin theorem
• Securing Communication
  • Key exchange and public-key encryption
  • Digital signatures
• Zero Knowledge
  • The Simulation Paradigm
  • ZK proofs for NP
  • Non-Interactive ZK
• Securing Computation
  • Secure Multi-Party Computation: oblivious transfer, Yao's garbled circuit
  • Advanced topics (as time permits): CCA encryption, fully-homomorphic encryption, functional encryption, obfuscation, and verifying delegated computation

Grading

Participation includes both participation in class and on the course forum.

Prerequisites

Basic probability theory, basic algorithms or complexity (basic familiarity with P, NP). Perhaps the most important prerequisite is mathematical maturity: the ability to read, understand, and write mathematical proofs.

Schedule

The schedule will be updated throughout the semester.

Resources

We will not follow a single textbook. The following are useful references for the course.

• Lecture notes by Daniel Wichs
• An Intensive Introduction to Cryptography, Boaz Barak
• Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell
• Foundations of Cryptography, Oded Goldreich
• The Joy of Cryptography, Mike Rosulek
• A Course in Cryptography, Rafael Pass and Abhi Shelat
• A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup
• Lecture notes by Yevgeniy Dodis
• Lecture notes by Chris Peikert

Course Policies

Homework

There will be about 6 homework assignments during the semester. Homework should be submitted in PDF form in Gradescope. Submissions should be typeset in LaTeX. These days, you don't need to know LaTeX; you can use free AI tools (e.g. OpenAI's Prism).

You will be graded not only for correctness, but also clarity. If you do not understand how to solve a question, you may write “I don't know how to do this,” and you will receive 15% credit for that question.

Collaboration

We strongly encourage you to discuss assignments with your peers, but you must (a) list the names of your discussion partners on your submission, and (b) write up your solution on your own.

Academic Integrity

Your work should be your own. Students should be aware of the CS Department's Policy on Academic Integrity. Violations of academic integrity will not be tolerated.

AI

AI is likely to be able to solve all of your homework. We will not prevent you from using AI to solve your homework. However, if you do use AI, please list the exact model as a collaborator, and add as an appendix your prompts. We strongly suggest that you do your best to solve the questions yourselves. The final exam will mostly include variants of HW questions. If you solved those yourselves, you would have a significant advantage.

Religious Observance

As a nonsectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the University Calendar Policy on Religious Holidays.

Disability Disclosure

Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing. Students should please register with the Moses Center for Students with Disabilities.