CrySP Speaker Series on Privacy • Zero-Knowledge Proofs Beyond Circuits and Constraints — How to Efficiently Build a “ZK CPU”

Please note: This CrySP Speaker Series on Privacy talk will take place in DC 1302 and online.

Yibin Yang, PhD candidate
School of Computer Science, Georgia Institute of Technology

With recent advances in efficient Zero-Knowledge Proofs (ZKP) schemes, ZKP has become one of the most active areas in cryptography that enables fruitful real-world applications. However, generic ZK schemes usually express the statements as circuits or constraint systems. The complicated front-end compiling problem brings efficiency overhead and a technical barrier for a broad deployment of ZKP.

In this talk, I will focus on our recent progress in emulating “Central Processing Unit (CPU)” inside ZKP. The talk will be divided into two parts. In the first half of the talk, I will present our recent work (ACM CCS ’23, joint with David Heath, Carmit Hazay, Vladimir Kolesnikov and Muthuramakrishnan Venkitasubramaniam) on proving batched ZK disjunctive statements. Namely, the prover wishes to repeatedly prove to the verifier that she knows the inputs that can satisfy 1-out-of-B circuits. This models the execution of CPU steps. In the second half of the talk, I will present our other recent work (USENIX Security ’24, joint with David Heath) on enabling ACCESS gates in the circuit. Namely, the prover and the verifier want to access a large read-write memory. This models the RAM machinery. Together, these two works enable an efficient full-fledged “ZK CPU”.

Bio: Yibin Yang (He/Him/His) is a PhD candidate from Georgia Institute of Technology, USA, advised by Professor Vladimir Kolesnikov. Yibin’s research is centered around cryptography, with a particular focus on Zero-Knowledge Proofs (ZKP) and Multi-Party Computation (MPC). Recently, he has been focusing on enabling generic ZK/MPC systems to support the RAM model of computation — namely, parties can perform ZKP/MPC while directly using high-level programming languages such as C/C++/assembly to express the computation task. He also heavily gets involved in the fair MPC, arithmetic garblings, and Blockchain layer-2 programmability.

To attend this talk in person, please go to DC 1302. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/91444262018.