Foundations of Modern Cryptography

CS4230/CS5430, AY22/23, Sem 2


Information

Instructor:       Prashant Nalini Vasudevan
TA:                  Kareem Shehata
Lectures:        Thu 4pm - 6pm
Tutorials:        Tue 2pm - 3pm
Location:        COM1-VCRM (COM1-02-13)

Course Description

Modern cryptographic primitives can generate strings that look random, send messages that only intended recipients can read, authenticate individuals, run computations on sensitive data without compromising privacy, and perform several other seemingly paradoxical tasks.

We will study a number of these primitives with emphasis on how to:

We will focus on the theoretical foundations that they are built upon, using tools from algebra, number theory, combinatorics, and probability. This will involve rigorous mathematical definitions and proofs.

Pre-requisites: The following modules are pre-requisites:

Having taken CS4236 (Cryptography Theory and Practice) would be helpful, but is not necessary.

Schedule

Lectures

Week Date Topics
1 Jan 12 Introduction, Security Definitions, Computational Hardness
2 Jan 19 Pseudo-Random Generators, Security Reductions
3 Jan 26 Pseudo-Random Functions, Secret-Key Encryption, Security Games
4 Feb 2 One-Way Functions
5 Feb 9 Public-Key Cryptography
6 Feb 16 Security from Algebra: Diffie-Hellman, Discrete Log
7 Mar 2 Security from Number Theory: RSA, Quadratic Residuosity
8 Mar 9 Digital Signatures, CCA-secure Encryption
9 Mar 16 Hashing, Random Oracle Model
10 Mar 23 Secure Multi-Party Computation, Garbled Circuits
11 Mar 30 Zero-Knowledge
12 Apr 4 Lattice-Based Cryptography (in tutorial slot)
13 Apr 11 Homomorphic Encryption (in tutorial slot)
13 Apr 13 Program Obfuscation, Review

Tutorials

Week Date Topics
2 Jan 17 Probability, Tail Bounds
4 Jan 31 Complexity Theory
5 Feb 7 Review
6 Feb 14 Group Theory
7 Feb 28 Number Theory
8 Mar 7 Circuits
9 Mar 14 Review
10 Mar 21 Secret Sharing
11 Mar 28 Interactive Proofs

Grading

Grading will be based on:

Problem Sets

Submissions are due at 23:59 on the respective dates. Late submissions will be accepted during the subsequent 48 hours, but their score will be scaled down linearly with time (e.g., a submission that is 12 hours late will only be given 75% of the marks it deserves, and one that is 48 hours late will be given 0%). Extensions will only be granted for medical reasons and emergencies.

Scribing

Every lecture (except the first) will be scribed by 2-3 students. The scribe notes should be written in latex, and should be complete and polished - see the notes for the first lecture for an example. The notes for each lecture are to be submitted before the subsequent lecture. The procedure for signing up will be discussed in class. The latex templates to be used may be downloaded here.

Midterm Exam

Time: 18 March, 10am to noon
Venue: COM1-VCRM (tentative)

Final Project

The final project will involve reading a few topically related papers and writing a survey of them. Details will be posted later.

References

There is no prescribed textbook for the course, but many of the topics we will cover may be found in the references below. I will update this list over the course of the semester. With your help, we will also be preparing notes for the lectures, which you can use for reference afterward.

Learning Objectives

By the end of this module, students should develop: