Credits: 3-0-0-0(9)
Prerequisite: CS201, CS202, and CS203 or equivalent. CS 641 or equivalent would be useful, but not necessary.
Who can take the course: Ph.D., Masters, 3rd and 4th year UG Students
Departments that may be interested: CSE, Mathematics and Statistics
The last couple of decades have seen a significant proliferation of the Internet in our daily lives. From essential services like banking and health to entertainment like movies and music, have moved online. The Covid-19 pandemic only accelerated these trends. While these trends have made our lives easier and brought great conveniences, it has also resulted in a substantial infringement on the privacy of individuals. Privacy Enhancing Technologies (PETs) are technologies that help protect the privacy of individuals or groups. There are several ways in which PETs can constructed. In this course, we will look at some of the cryptographic approaches to achieving privacy. In particular, some of the topics that will be covered are: (i) Can one stream a movie on, say, Netflix while Netflix has no idea what one watched? (Private Information Retrieval); (ii) Can two millionaires find out who is richer without revealing to each other their wealth (Secure Multi-Party Computation)? (iii) Can you convince your friend that you know a solution to the Graph 3-coloring problem without them learning the 3-coloring or any new information? (Zero Knowledge Proofs); (iv) Can you outsource storage to a remote server and access data from it while all your access patterns are hidden? (Oblivious Random Access Memory).
On completion of this course, a student should be able to: (i) articulate how Private Information Retrieval (PIR) works, what are the different types of PIR, when one would prefer to use a certain type of PIR over the other; (ii) articulate what Secure Multiparty Computation (MPC) is, some MPC constructions, prove their security and correctness; (iii) build zero-knowledge proof systems and prove the correctness and security; (iv) articulate the construction of different types of Oblivious RAM (ORAM) protocols; (v) build cryptographically secure systems using the above Privacy Enchaining Technologies.
| Module | Topic | No. of 1-hour Lecturess |
|---|---|---|
| Introduction | Why do we need Privacy? Cryptography Refresher | 2 |
| Private Information Retrieval (PIR) | Information Theoretic PIR Computation PIR PIR using Trusted Execution Environments Distributed Point Functions PIR by keywords | 8 |
| Secure Multi-Party Computation (MPC) | Garbled Circuits GMW BGW-Protocol ABY-Protocol Server Aided MPC Oblivious Transfer | 8 |
| Zero-Knowledge Proofs (ZKPs) | Sigma Protocols Zk-SNARKs MPC-in-the-head | 6 |
| Oblivious Random Access Memory (ORAM) | Client-Server ORAMs Hierarchical ORAM Tree ORAM Path ORAM Distributed ORAMs | 8 |
| Applications | Tor, Off-the-Record Messaging, Private Recommendation Systems | 8 |
| Total Lecture hours | 40 hours |
There is no one textbook for such a course. Research papers will be the main sources of study material.
Some useful textbooks are:
There will be other resources put on the web by the instructor.