Course Information
- Instructor: Prof. Yupeng Zhang zhangyp@illinois.edu
- Lectures: TuTh 5:00 pm - 6:20 pm
- Office Hour: By appointment
- Location: 2015 ECEB
Course Description and Prerequisites
This course covers techniques in applied cryptography and their applications in machine learning and blockchain to enhance privacy, integrity and scalability. In this course, we will explore the cutting-edge cryptographic techniques such as zero-knowledge proofs and secure multiparty computations. We will discuss the basic concepts and state-of-the-art constructions of these cryptographic schemes. Additionally, we will talk about how to use these techniques to construct privacy-preserving blockchain and crypto-currencies, zkRollups and zkEVM, privacy preserving machine learning and zero-knowledge proofs for machine learning. We will focus on efficiency and scalability constraints in practice, and discuss challenges and solutions to efficiently realize these cryptographic protocols.
Prerequisites: ECE 374 or equivalent courses approved by the instructor. Basic knowledge of algorithms, data structures and programming is recommended.
Textbook and Resource Materials
MOOC on Zero-Knowledge Proofs: https://zk-learning.org/
No textbook is required for the course. Reading materials will be posted online during the semester
Schedule (tentative)
| Date | Topic | Readings | Deadline |
|---|---|---|---|
| Week 1 | Introduction and logitics, background on Cryptography | ||
| Week 1 | Introduction to verifiable computation and zero-knowledge proof | Merkle Hash Tree | |
| Week 2 | Introduction to blockchain and cryptocurrency | Bitcoin | |
| Week 2 | Pricacy-preserving crypto-currencies | ||
| Week 3 | Polynomial commitments | Polynomial commitments | Team Formation |
| Week 3 | Generic solutions: interactive proofs | ||
| Week 4 | |||
| Week 4 | Generic solutions:Plonk | Plonk | |
| Week 5 | Smart contract | ||
| Week 5 | Privacy-preserving smart contract and zkRollups | Hawk | Proposal due |
| Week 6 | Generic solutions: SNARK | ||
| Week 6 | |||
| Week 7 | Zero-knowledge proofs for machine learning CNN | zkCNN | |
| Week 7 | Zero-knowledge decision tree | Zero-knowledge decision trees | |
| Week 8 | ZKP based on error-correcting codes | ||
| Week 8 | Interactive Oracle Proofs and FRI | FRI | |
| Week 9 | Midterm Presentation | ||
| Week 9 | |||
| Week 10 | Introduction to secure multiparty computation and Oblivious Transfer | Wikipedia | |
| Week 10 | Yao's Garbled circuit | ||
| Week 11 | GMW protocol | Youtube tutorial | |
| Week 11 | Malicious security and fairness | Cut and choose | |
| Week 12 | Privacy-preserving machine learning and linear regression | ||
| Week 12 | Privacy-preserving logistic regression and neural networks |
|
|
| Week 13 | Stacked Garbling | |
|
| Week 13 | No class on 11/16 | ||
| Week 14 | Fall break | ||
| Week 15 | Presentations | ||
| Week 15 | Presentations | Final report due |
Grading
Class Participation: 10%.
Reading assignments: 30%. Students will submit reviews for one of the reading materials every 1-2 weeks. The reviews should include a brief summary of the paper, the contributions and potential improvements.
Course project: 60%. Project (60%): Students will form groups and complete research projects related to the topics of the course. The grading consists of a project proposal, a mid-term progress report, a final presentation and a final project report. Students may propose their own topics or choose from a list of suggested topics on secure multiparty computations, verifiable computations and zero knowledge proof, privacy-preserving machine learning and blockchain.
- Proposal (10%)
- Mid-term presentation (10%)
- Final presentation (20%)
- Final report (20%)
Suggested topics for projects:
Blockchains
- Information inference from public data on Bitcoin blockchain: 1. Understand the public data posted on the blockchain of Bitcoin and figure out ways to download the data. 2. Repeat data analysis from existing papers. 3. Design new attacks to infer sensitive information from the public data, such as dead coins and large volume transactions and its correlations with the price of bitcoin.
- Information inference from public data on Ethereum: Same as bitcoin. In addition, analyze the smart contracts.
- Scaling up blockchains: Understand zk-rollup and its relationship to zero knowledge proofs. Survey existing protocols and challenges. Other techinques: sharding, optimistim rollup etc.
Zero Knowledge Proof
- Zero knowledge proof for machine learning model predictions: generate a proof that the predictions of a secret model on a public testing dataset reaches certain accuracy. Design efficient ZKP protocols for neural networks, CNN, GNN, RNN etc.
- Privacy-preserving smart contracts: 1. Understand the mechanism of smart contract. 2. Find commonly used smart contracts on existing blockchains and cryptocurrencies. 3. Given general purpose ZKP, design protocols for privacy-preserving smart contracts. 4. Implement the ZKP protocol using existing libraries and optimize for those commonly used smart contracts.
- Distributed and memory-efficient zero-knowledge proofs: improve the scalability of ZKPs via a protocol with sublinear memory usage, or a distributed protocol with multiple machines.
- Zero knowledge proof for graph algorithms: generate a proof that the result of graph algorithm is correct. Design efficient ZKP protocols for shortest path etc.
Secure Multiparty Computations
- Privacy-preserving alternating direction method of multipliers (ADMM): apply MPC techniques to train models on encrypted data using ditributed training algorithms (such as ADMM). 1. Understand ADMM. 2. Collect datasets and implement training and predictions on plaintext data. 3. Use only those computations efficiently supported by MPC, compare the accuracy to the baseline. 4. Implement the MPC protocol.
- Privacy-preserving decision trees and random forest training and/or predictions: apply MPC techniques to train decision tree and random forest models on encrypted data. 1. Understand decision tree and random forest. 2. Collect datasets and implement training and predictions on plaintext data. 3. Use only those computations efficiently supported by MPC, compare the accuracy to the baseline. 4. Implement the MPC protocol using existing libraries.
- Privacy-preserving SVM training and/or predictions: apply MPC techniques to train SVM models on encrypted data. 1. Understand SVM. 2. Collect datasets and implement training and predictions on plaintext data. 3. Use only those computations efficiently supported by MPC, compare the accuracy to the baseline. 4. Implement the MPC protocol using existing libraries.