CS4230/CS5430, AY22/23, Sem 2

Instructor: Prashant Nalini Vasudevan

TA: Kareem Shehata

Lectures: Thu 4pm - 6pm

Tutorials: Tue 2pm - 3pm

Location: COM1-VCRM (COM1-02-13)

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:

define their security requirements rigorously,

construct them, and,

prove that these constructions are secure

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:

CS1231/CS1231S (Discrete Structures)

CS3230 (Design and Analysis of Algorithms)

ST2334 (Probability and Statistics) or ST2131 or MA2216

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

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 |

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 will be based on:

Problem sets (40%)

Scribing (10%)

Midterm exam (25%)

Final project (25%)

Problem Set 1: released 13 Jan, due 20 Jan

Problem Set 2: released 27 Jan, due 10 Feb

Problem Set 3: released 17 Feb, due 10 Mar

Problem Set 4: released 17 Mar, due 31 Mar

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.

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.

Time: 18 March, 10am to noon

Venue: COM1-VCRM (tentative)

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

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.

Textbooks on cryptography

Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell

The Foundations of Cryptography (Volumes 1 and 2), by Oded Goldreich

The Joy of Cryptography, by Mike Rosulek

Lecture Notes on Cryptography, by Goldwasser and Bellare

Other courses on the foundations of cryptography

6.875 Foundations of Cryptography, by Vinod Vaikuntanathan at MIT, Fall 2022

CS7810 Foundations of Cryptography, by Daniel Wichs at Northeastern University, Fall 2017

CS276 Cryptography, by Sanjam Garg at UC Berkeley, Fall 2014

CMSC858K Advanced Topics in Cryptography, by Jonathan Katz at University of Maryland, Spring 2004

Other references

Tutorials on the Foundations of Cryptography, edited by Yehuda Lindell

A Graduate Course in Applied Cryptography, by Dan Boneh and Victor Shoup

By the end of this module, students should develop:

An understanding of the theoretical foundations of cryptography and its connections to other areas of computer science.

An understanding of the source of security in advanced cryptographic primitives.

The ability to define and construct new cryptographic primitives tailored to various applications.

The ability to prove the security of advanced cryptographic constructions using reductions to computational hardness assumptions.

A knowledge of the capabilities of modern cryptographic primitives that are available for them to use in applications.