Grainger College of Engineering, All Events

Abstract:    Boolean circuits are perhaps our simplest complete model of computation. A circuit is a combinatorial object composed of simple, fan-in two gates whose interconnections (wires) are fixed in advance. This structural simplicity makes circuits convenient in many settings; in this talk, I will discuss how it enables powerful cryptographic constructions.

By contrast, the RAM model of computation is arguably the most pragmatic: we often reason about algorithms as programs that can efficiently perform random access to a large memory.

Establishing strong connections between circuits and RAM would therefore be highly desirable. In particular, a reduction from RAM to circuits would automatically lift circuit-based tools to the more pragmatic RAM model. Unfortunately, known reductions incur severe polynomial overhead in circuit size.

Motivated by applications to a cryptographic technique known as Garbled RAM, my work has uncovered surprising connections between circuits and RAM. The key insight is to slightly relax the standard circuit model. While Boolean circuits are traditionally required to be acyclic—so that wires never “feed back”—I will show that it is both natural and useful to consider circuits that contain cycles. Crucially, these cyclic circuits remain purely combinational and have no notion of state.

Under this relaxation, the gap between circuits and RAM shrinks dramatically. We can construct circuit-based RAM where the overhead in terms of the number of gates is only polylogarithmic.

This perspective has led to orders-of-magnitude improvements to Garbled RAM, and it may have other applications beyond cryptography. 

My talk will focus on circuits; no background in cryptography is required.

Bio:  David Heath is an assistant professor studying cryptography. His work focuses on reducing the cost of cryptographically-secured computations, including those enabled by secure multiparty computation (MPC) and zero knowledge proofs (ZKP).