CS 598 DH: Secure Computation
Spring 2024

Instructor
Professor David Heath
daheath@illinois.edu
4322 Siebel Center

TA
Bolton Bailey
boltonb2@illinois.edu

Description

We will discuss secure multiparty computation (MPC), a suprisingly powerful branch of cryptography that allows mutually untrusting parties to work together to securely run programs on private data. We will discuss both the theory and the practice of this emerging technology. Our discussion will cover computing on private data, zero-knowledge proofs, oblivious RAM, and more.

Class Times

We will meet Tuesdays and Thursdays from 11:00am – 12:15pm in 1214 Siebel Center. Lectures will be recorded and made available here.

Office Hours

Office Hours are tentatively scheduled for 12:30–1:30pm on Tuesdays and 1:30-2:30pm on Thursdays (update based on in-class discussion) in 4322 Siebel Center.

Resources

Prerequisites

The main prerequisite is mathematical maturity. You will be expected to read, understand, and write formal definitions/proofs. The course is designed for a wide audience, and cryptographic background is not expected. Basic understanding of probability theory and of computational models, e.g. Turing machines, will be helpful.

Formally, the following courses (or equivalent experience) is required:

Grade Distribution

Final Project

The instructions/rubric for your final project are here. You can download a template for your review here.

Homework

Homework materials follow:

Collaboration.

Homeworks are to be completed and submitted individually. However, you may collaborate with up to one other student on homework assignments. On each homework submission, declare your collaborator (if any). In your collaboration you are expected to discuss the homework, not to copy answers. Plagiarism will not be tolerated (see Academic Integrity).

Course Schedule

Date Topic Slides Video Reading Extra
1/16 Course Overview and Introduction Slides Video Pragmatic MPC Chapter 1
1/18 MPC Applications and Semi-honest Security Slides No audio – sorry! Pragmatic MPC Chapter 2 A, B, C
1/23 Semi-honest Security Slides Video Pragmatic MPC Chapter 2 A
1/25 Oblivious Transfer Slides Video Pragmatic MPC Chapter 3 A, B
1/30 The GMW Protocol Slides Video Pragmatic MPC Chapter 3.2 A
2/1 Randomized Functionalities and GMW Continued Slides Video Pragmatic MPC Chapter 3.2, Goldreich, 7.2 and 7.2 A
2/6 Garbled Circuits Slides Video Pragmatic MPC Chapter 3.1 A
2/8 Introduction to Malicious Security Slides Video Pragmatic MPC Chapter 6 A
2/13 Malicious Security Continued Slides Video Section 7 Chapter 6
2/15 Introduction to Zero Knowledge Proofs Slides Video Section 4 Chapter 6.5, Seminal Work, ZK for all NP, GMW Compiler,
2/20 Final Project Discussion Slides Video
2/22 Zero Knowledge from MPC Slides Video Chapter 6.5 ZK from GC, Fast ZK, MPC-ITH, KKW MPC-ITH, Ligero MPC-ITH
2/27 Oblivious RAM Slides No audio – sorry! Chapter 5.2 A, B, C,
2/29 Oblivious RAM, Continued Slides No audio – sorry! Chapter 5.2 Path ORAM, ORAM Lower Bound, Optimal ORAM
3/05 Malicious Garbled Circuits Slides Chapter 6 Cut and Choose, Authenticated Garbling, Authenticated Multiplication Triples
3/07 Malicious Garbled Circuits Slides Chapter 6 Cut and Choose, Authenticated Garbling, Authenticated Multiplication Triples
3/19 Homework 2 Review Slides Video
3/21 OT Extension Slides Video Chapter 3.7 OT is public-key, OT extension feasibility, IKNP OT Extension
3/26 Private Information Retrieval and Function Secret Sharing Slides Video Lecture on PCGs, PIR, DPFs, FSS, Silent OT
3/28 Private Set Intersection Slides Video Circuit PSI, 1-out-of-N OT, PSI from OT
4/2 Course Review Slides
4/22 Single Server PIR Slides
4/24 ZK-SNARKs Slides

Course Topics

Topics covered in the course include – but are not limited to – the following:

Depending on time remaining, we will review previously discussed topics, and move on to other topics such as (but not limited to):

Academic Integrity

Academic dishonesty is a serious offense. The University of Illinois Urbana-Champaign Student Code (https://studentcode.illinois.edu) is considered a part of this syllabus. If you are ever in doubt of what constitutes plagiarism or cheating, do not hesitate to ask me.

Disability Accommodations

To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor and the Disability Resources and Educational Services (DRES) as soon as possible. To contact DRES you may visit 1207 S. Oak St., Champaign, call 333-4603 (V/TTY), or e-mail a message to disability@illinois.edu.