Cryptographic Techniques for Privacy Preservation
Postgraduate course, IIT Kanpur, Computer Science and Engineering, 2024
About the Course
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).
Course Organization
Where and When?
KD101. Monday and Wednesday, 5.15 PM to 6.30 PM.
Course Staff
- Instructor: Adithya Vadapalli
Teaching Assistants
- Anindya anindyag@cse.iitk.ac.in
- Dhananjay dhananjayg@cse.iitk.ac.in
- Hrithik hrithik@cse.iitk.ac.in
- Naman prgmaz@cse.iitk.ac.in
Office Hours
Location: KD-317, Time: Monday 11 AM to 12 PM
Quizzes
Students are welcome to meet the instructor and discuss any thing from the course during the office hours.
Assignments
- Assignment 1 can be downloaded here.
Course Schedule
| # | Module | Date | Topic | Compulsory Reading | Optional Reading | |
|---|---|---|---|---|---|---|
| 1 | 0: Intro | 8.1.24 | Why Privacy | I have nothing to hide | TBD | |
| 2 | 0: Intro | 10.1.24 | Crypto Refresher | TBD | TBD | TBD |
| 3 | 1: PIR | 15.1.24 | Quiz 1 + Information Theoretic Private Information Retrieval | Section 1 to Section 3.2 , Section 5 in Chor et al’s Paper | Section 3.3, 3.4, and 4 Chor et al’s Paper | |
| 4 | 1: PIR | 17.1.24 | Information Theoretic Private Information Retrieval | Goldberg’s Paper, Shamir’s Secret Sharing | Optimally Robust PIR, How to share a secret | |
| 5 | 1: PIR | 22.1.24 | Distributed Point Functions | Section 2.1.1 from Duoram paper, Figure 1 from DPF paper, Section II-A from Sabre Paper, Section 6.1 from the Pirsona Paper, Section 4.1 to 4.3 in the Riposte paper | Section 3 from Grotto Paper , The original DPF paper, DPF based PIR scheme | |
| 6 | 1: PIR | 24.1.24 | Review Lecture | TBD | TBD | |
| 7 | 1: PIR | 29.1.24 | Computational PIR | Survey on CPIR | TBD | |
| 8 | 1: PIR | 31.1.24 | Quiz 2 + Pirsona | Pirsona Paper | TBD | |
| 9 | 1: PIR | 5.2.24 | Pirsona | Pirsona Paper | TBD | |
| 10 | 2: MPC | 7.2.24 | Introduction to MPC | Chapter 2 MPC Book, MPC | How To Simulate It | |
| 11 | 2: MPC | 12.2.24 | Oblivious Transfer | TBD | TBD | |
| 12 | 2: MPC | 14.2.24 | Garbled Circuits (GC) | TBD | Introduction to Garbled Circuits | |
| 19.2.24 | Midsems | |||||
| 21.2.24 | Midsems | |||||
| 13 | 2: MPC | 26.2.24 | Optimizatios of GC, GMW protocol | TBD | TBD | |
| 14 | 2: MPC | 28.2.24 | Quiz 3 + Beaver Triples | TBD | TBD | |
| 15 | 2: MPC | 4.3.24 | MPC Applications | TBD | TBD | |
| 16 | 2: MPC | 6.3.24 | Review Lecture on MPC | TBD | TBD | |
| 17 | 3: ORAM | 9.3.24 (Extra Class) | Squareroot ORAM | Sections 1 to 4 here | Original ORAM Paper | |
| 18 | 3: ORAM | 11.3.24 | Hierarchical ORAM | Chapter 1 from here, Original Tree ORAM paper | TBD | |
| 19 | 3: ORAM | 13.3.24 | ORAM for MPC, Floram | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 20 | 3: ORAM | 18.3.24 | ORAM for MPC, Floram | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 21 | 3: ORAM | 21.3.24 | ORAM for MPC, Floram | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 22 | 3: ORAM | 13.4.24 (Extra Class) | ORAM Recap | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 23 | 4: ZKP | 13.4.24 (Extra Class) | ORAM Recap | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 24 | 4: ZKP | 14.4.24 (Extra Class) | ORAM Recap | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 25 | 4: ZKP | 15.4.24 | ORAM Recap | Revisiting Square Root ORAM paper, Original Floram Paper | TBD | |
| 26 | End Sem Prep | 17.4.24 | ORAM Recap | Revisiting Square Root ORAM paper, Original Floram Paper | TBD |
References
- [1] Private Information Retrieval Chor, Goldreich, Kushilevitz here
- [2] Gentle Introduction to Yao’s Garbled Circuits here
- [3] Blog on TEE here
- [4] Resources for MPC: here, and here
- [5] Winter School on MPC
Additional Resources
The are of Privacy and Security really benefits from some outstanding lectures available online. Some of them are below.
- Kevin Yeo’s talk at CrySP on Private Information Retrieval
- Ryan Henry’s tutorial on PIR at ACM CCS 2017
Course Resources
There is no one textbook for this course. There are few useful books though.
- Modern Cryptography by Katz and Lindell
- Pragmatic MPC by Evans, Koselnikov, and Rosulek
Grading
| Assignment 1 | 20% |
| Assignment 2 | 20% |
| Assignment 3 | 40% |
| Quizzes | 5% |
| Final Exam | 15% |
Academic Integrity
See CSE Department’s Policy here
Mental Health Support
See Counselling Service of CSE Deparment here