David Heath

daheath@illinois.edu

Siebel Center for Computer Science, Room 4322

About Me

I am a cryptographer and an assistant professor at the University of Illinois Urbana-Champaign. My research focuses on Secure Multiparty Computation (MPC) and Zero Knowledge proofs. I am broadly interested in algorithmic techniques for reducing the cost of MPC and ZK.

To learn more about my research, you can peruse my work below or have a look at my CV.

Advisees

PhD Advisees

• Cruz Barnum. Fall 2022 – Present.
• Ananya Appan (co-advised by Ling Ren). Fall 2023 – Present.
• Anwesh Bhattacharya. Fall 2023 – Present.
• Ziling Yang. Fall 2023 – Present.

MS Advisees

Zexiang Chen. 2023. Masters Thesis: “3PC Honest-Majority PRAM Computation with Perfect Security and Low Overhead”.

Undergraduate Advisees

Pranav Rajpal. Spring 2024 – Present.

Conference Publications

2024

• David Heath. Efficient Arithmetic in Garbled Circuits. EUROCRYPT 2024.
• David Heath, Vladimir Kolesnikov, and Lucien Ng. Garbled circuit lookup tables with logarithmic number of ciphertexts. EUROCRYPT 2024.
• David Heath and Yibin Yang. Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM. USENIX 2024.

2023

• Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, and Muthu Venkitasubramaniam. Batchman and Robin: Batched and non-batched branching for interactive ZK. CCS 2023 Distinguished Paper Award.
• David Heath, Stanislav Peceny, and Yibin Yang. Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs). CCS 2023.
• David Heath, Vladimir Kolesnikov, and Rafail Ostrovsky. Tri-State Circuits: A Circuit Model that Captures RAM. CRYPTO 2023. Conference Talk.

2022

• David Heath, Vladimir Kolesnikov, and Rafail Ostrovsky. Practical Garbled RAM. EUROCRYPT 2022 Best Paper Award. Conference Talk.
• Abida Haque, David Heath, Vladimir Kolesnikov, Steve Lu, Rafail Ostrovsky, and Akash Shah. GCWise: Garbled Circuits With Sublinear Evaluator. EUROCRYPT 2022. Conference Talk.
• Yibin Yang, David Heath,Vladimir Kolesnikov,and David Devecsery. EZEE: Epoch Parallel Zero Knowledge for ANSI C. EuroS&P 2022.

2021

• David Heath and Vladimir Kolesnikov. One Hot Garbling. CCS 2021. Conference Talk.
• David Heath and Vladimir Kolesnikov. PrORAM: Fast O(log n) Private Coin ZK ORAM. ASIACRYPT 2021. Conference Talk.
• David Heath, Vladimir Kolesnikov, and Stanislav Peceny. Garbling, Stacked and Staggered. ASIACRYPT 2021. Conference Talk.
• David Heath and Vladimir Kolesnikov. LogStack: Stacked Garbling with O(b log b) Computation. EUROCRYPT 2021. Conference Talk.
• David Heath, Yibin Yang, David Devecsery, and Vladimir Kolesnikov. Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached ORAM for ANSI C programs. S&P 2021. Conference Talk.
• David Heath, Vladimir Kolesnikov, and Stanislav Peceny. Masked Triples - Amortizing Multiplication Triples Across Conditionals. PKC 2021. Conference Talk.
• David Heath, Vladimir Kolesnikov, and Jiahui Lu. Efficient Generic Arithmetic for KKW: Practical Linear MPC-in-the-Head NIZK on Commodity Hardware without Trusted Setup. CSCML 2021.

2020

• David Heath, Vladimir Kolesnikov, and Stanislav Peceny. MOTIF: (almost) Free Branching in GMW via Vector-Scalar Multiplication. ASIACRYPT 2020. Conference Talk.
• David Heath and Vladimir Kolesnikov. A 2.1 KHz Zero-Knowledge Processor with BubbleRAM. CCS 2020. Conference Talk.
• David Heath and Vladimir Kolesnikov. Stacked Garbling - Garbled Circuit Proportional to Longest Execution Path. CRYPTO 2020. Conference Talk.
• David Heath and Vladimir Kolesnikov. Stacked Garbling for Disjunctive Zero-Knowledge Proofs. EUROCRYPT 2020. Conference Talk.

2019

• Qi Zhou, David Heath, and William Harris. Relational verification via invariant-guided synchronization. EPTCS 2019.

2018

• Qi Zhou, David Heath, and William Harris. Solving constrained horn clauses using dependence-disjoint expansions EPTCS 2018.

Unpublished Manuscripts

• David Heath, Vladimir Kolesnikov, Varun Narayanan, Rafail Ostrovsky, and Akash Shah. Multiparty Garbled RAM with Linear Scaling. 2024.
• Ananya Appan, David Heath, and Ling Ren. Oblivious Single Access Machines: A New Model for Oblivious Computation. 2024.
• Cruz Barnum, David Heath, Vladimir Kolesnikov, and Rafail Ostrovsky. Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles. 2024.
• Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, and Muthuramakrishnan Venkitasubramaniam. Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction. 2024.
• David Heath. Parallel RAM from Cyclic Circuits. 2023.

Talks

• Garbled RAM from Tri-State circuits. Invited Speaker at MongoDB Inc. Cryptography Research Group Seminars, February 2024.
• Garbled RAM from Tri-State circuits. Invited Speaker at AlgoCRYPT Seminars, January 2024.
• Garbled RAM from Tri-State Circuits. Invited Speaker at Midwest Crypto Day, April 2023.
• Stacked Garbling and MPC with Improved Conditional Branching. Invited Speaker at NY Crypto Day, October 2022.
• New Directions in Garbled Circuits. Invited Speaker at TPMPC, June 2022.
• EpiGRAM: Practical Garbled RAM. Invited Speaker at Charles River Crypto Day, March 2022.
• Practical Garbled RAM. CMU Reading Group, December 2021.
• Practical Garbled RAM. Berkeley Reading Group, December 2021.
• Practical Garbled RAM. UMD Reading Group, December 2021.
• Practical Garbled RAM. Stanford Security Seminar, November 2021.
• Logstack: Stacked Garbling with O(b log b) Computation. TCC 2021 Special in-person Workshop, November 2021.
• Logstack: Stacked Garbling with O(b log b) Computation. Stanford Security Seminar, May 2021.
• Zero-knowledge for Everything and Everyone. Georgia Tech Cybersecurity Lecture Series, February 2021.
• Stacked garbling: Garbled circuit proportional to longest execution path. Stanford Security Seminar, September 2020
• Efficiently Computing with Private Data. Georgia Tech Cybersecurity Lecture Series, September 2019.