CS 594 Secure Computation (Spring 2021)

Course Overview

Nowadays, vast amounts of individual information are collected by numerous entities, which fuels a wide range of personalized services. However, since the collected data may contain sensitive private information, due to regulatory compliance or corporate policies, securely computing on the collected data in a privacy-preserving yet efficient way becomes significantly important.

This course is an introduction to secure computation, which achieves the above goal, providing great promise and potential to facilitate research in various domains. We will cover both the theoretical foundations and practical implementations of secure computation. By the end of this course, you will be able to understand cryptography research papers and initiate research studies in this area.

Basic Information

Lecture Time: 6:30-9:00pm Thursdays (synchronous, online).

Instructor: Peihan Miao

Office Hour: 3:00-4:00pm Thursdays or by appointment.

Online Lecture/Offie Hour Location:
Zoom link: https://uic.zoom.us/j/82207166004?pwd=S1FYZHZsQzBjeWxkWVhwdTJoOE1IZz09
Meeting ID: 822 0716 6004
Passcode: h6XA648c
One tap mobile: +13126266799,,82207166004#,,,,*86646078# US (Chicago)
All the lectures will be recorded and will be available online in a day after each lecture.

Course Announcements: We will be using Piazza (https://piazza.com/uic/spring2021/cs59442282) for all course announcements, discussions, etc. (You don't need the instructor's approval to enroll.)

Prerequisites: CS 401 or equivalent (soft). We don't require any prior background in cryptography, but mathematical maturity is required.

Course Requirements and Grading

• Regular attendance and active participation in class 30%

• Scribe lecture notes at least once (in LaTeX) 20%

• Course project presentation (report is optional) 50%

Tentative Schedule

• Jan 14, Lecture 1
  Topics: Introduction. Cryptographic background. Motivation and definition of secure multi-party computation (MPC).
  References: Surveys and overviews of secure computation by Lindell'20, Lindell-Pinkas'08.

• Jan 21, Lecture 2
  Topics: Real/Ideal-world paradigm and different security variants.
  References: Real/Ideal-world paradigm nicely explained in Lindell's tutorial. Computationally indistinguishability covered in Katz-Lindell's book, Chapter 3 and Rosulek's book, Chapter 4.

• Jan 28, Lecture 3
  Topics: Oblivious transfer (OT) and OT extension. GMW protocol for semi-honest secure MPC.
  References: OT protocol covered in Pass-shelat's Lecture Notes, Chapter 6.2.4. OT extension by IKNP'03. GMW protocol covered in Goldreich's book, Volume 2, Chapter 7.

• Feb 4, Lecture 4
  Topics: Yao’s garbled circuit. BMR protocol for MPC in constant rounds.
  References: Proof of Yao's 2PC protocol by Lindell-Pinkas. Constant-round MPC protocol by BMR'90.

• Feb 11, Lecture 5
  Topics: Optimizations for garbled circuits. Zero-knowledge (ZK) proofs.
  References: Optimizations of garbled circuits: Kolesnikov-Schneider'08, PSSW'09, ZRE'15. ZK proofs for all NP languages covered in Lindell's Notes, Chapter 7.

• Feb 18, Lecture 6
  Topics: Non-interactive zero-knowledge (NIZK) proofs. ZK from MPC in the head. GMW compiler. Cut-and-choose technique.
  References: ZK from MPC in the head by IKOS'07. GMW compiler covered in Lindell's Notes, Chapter 13. Cut-and-choose proof by Lindell-Pinkas'12, LEGO by Nielsen-Orlandi'09.

• Feb 25, Lecture 7
  Topics: Information-theoretic security. BGW protocol in the semi-honest model.
  References: Full security proof by Asharov-Lindell'17.

• Mar 4, Lecture 8
  Topics: BGW protocol in the malicious model.
  References: Full security proof by Asharov-Lindell'17.

• Mar 11, Lecture 9
  Topics: Oblivious RAM and secure RAM computation.
  References: A simple ORAM construction by Chung-Pass'13. Secure two-party RAM computation by Gordon et al.'12. Garbled RAM by Gentry et al.'14.

• Mar 18, Lecture 10
  Topics: Special-purpose MPC for Private set intersection (PSI) and privacy-preserving machine learning.
  References: Diffie-Hellman-based construction by Ion et al.'20. OT-based construction by KKRT'16. Secure ML framework by Mohassel-Zhang'17.

• Mar 25, No lecture (spring vacation)

• April 1, Lecture 11
  Topics: Fully homomorphic encryption (FHE) and its connections to MPC.
  References: Survey of FHE by Vaikuntanathan'11, Brakerski'18. The first construction of FHE by Gentry'09 and a conceptually simpler construction by Dijk et al.'10, Gentry'10.

• April 8, Lecture 12 (Guest Lecturer: Yilei Chen)
  Topics: Program obfuscation, secure enclaves, and their connections to MPC.
  References: A survey of indistinguishability obfuscation (iO) by Barak'16. A recent construction of iO by Jain-Lin-Sahai'20. Intel SGX explained by Costan-Devadas'16.

• April 15, Lecture 13
  Topics: Blockchain and its connections to MPC.
  References: Bitcoin white paper by Nakamoto'08.

• April 22, Lecture 14
  Final project presentations.

• April 29, Lecture 15
  Final project presentations.