Special Seminar: David Heath, "New Directions in Garbled Circuits"

Abstract: Today, individuals and organizations often wish to run computations on sensitive private data, but if this data is too valuable or is legally protected, the parties cannot run the desired computations. Secure Multiparty Computation (MPC) is a subfield of cryptography that allows users to compute on encrypted data. Since the data remains encrypted, MPC circumvents the privacy problem: the parties can operate on highly sensitive data while retaining privacy, so MPC enables many useful applications.
Yao's Garbled Circuit (GC) is a foundational and widely used approach in MPC. MPC approaches consume three resources: computation, network bandwidth, and rounds of interaction. GC’s tradeoff between these costs is excellent, as it uses only constant rounds of interaction and relies primarily on fast cryptographic primitives. Techniques that further improve GC are highly valued.
 
For almost 40 years and until my work, practical GC techniques required that the desired computation be encoded as a circuit with fan-in two gates. This encoding is problematic: end-user programs often utilize expressive programming features such as vector operations, rich control flow, and array accesses. Encoding these features in a circuit is often prohibitively expensive, so circuits cannot efficiently express end-user programs.
 
In this talk, I will present fundamentally new GC techniques. These new techniques escape the GC status quo of simple circuits and give results previously believed to be either impossible or impractical.  My work enables a qualitative shift in practical MPC: GCs will no longer be limited to circuits, but will instead support expressive RAM-machine programs. This shift enables secure computation of programs written in common programming languages and underlies my current work on a complete MPC toolchain for the C language. Such toolchains will greatly improve MPC’s applicability, ease of use, and adoption.  

Bio: David Heath is a Ph.D. candidate studying cryptography at Georgia Tech and is advised by Professor Vladimir Kolesnikov. David’s focus is applied secure multiparty computation (applied MPC), a subfield of cryptography that allows parties to compute directly on encrypted data. His research has uncovered surprising improvements to Garbled Circuits, a fundamental MPC technology, and to Zero-Knowledge proofs, an important MPC special case. David’s goal is to construct end-to-end toolchains that will enable engineers to use MPC to solve real-world problems.