New Directions in Garbled Circuits

Abstract

The Garbled Circuit (GC) technique is foundational in secure multiparty computation (MPC). GC allows parties to jointly and securely compute functions of their private inputs while revealing nothing but the output. GC is unique in that it achieves secure computation while using only a constant number of rounds of communication. This property makes GC a distinctly flexible and powerful technology.

When Andrew Yao originally explained GC, he described a way to encrypt a Boolean circuit by representing each gate as four encryptions; these encryptions together encode the logic of the gate by hiding keys used as input to future gates. One party – the circuit generator – methodically encrypts each gate, then sends the encryptions to the second party – the circuit evaluator. The evaluator is given input keys and then propagates keys gate-by-gate through the circuit and eventually obtains output keys. Despite the fact that the evaluator correctly computes the circuit, she remains oblivious to the cleartext value on each circuit wire.

Although powerful, Yao’s technique is expensive: each gate uses four ciphertexts, and complicated functions can have billions of gates or more. Thus, researchers sought – and still seek – cheaper gates. Significant effort has been put into this line, to modest ends. Today, XOR gates are communication-free, but each AND gate still requires 1.5 ciphertexts.

From a certain perspective, the focus on fan-in two gates is ad hoc; there is no rule that states fan-in two gates are the only – or even the best – fit for GC. Indeed, one can imagine that there might exist other computations that are naturally encoded such that cost is greatly diminished.

This dissertation focuses on this relatively unexplored dimension of GC. We present three classes of improved GC computations that go beyond fan-in two Boolean gates: * One-hot garbling. This technique provides new GC gates that efficiently compute over short vectors of bits, as opposed to only two bits. One-hot garbling improves the GC cost of many important primitives, such as integer multiplication and matrix multiplication.

* Stacked garbling. Traditionally, it was assumed that GC necessarily incurs communication cost proportional to the entire function description. My work on ‘stacked garbling’ shows that this assumption is wrong. Stacked garbling improves the communication consumption of functions with conditional behavior: we only need sufficient communication to represent the single longest execution path of the function, not the function in its entirety.

* Garbled RAM. Many computations are best described as RAM programs, not as circuits, and the reduction from RAM programs to circuits is expensive. Thus, it is natural to consider adding a sublinear cost RAM to GC. Techniques that achieve this are called Garbled RAMs (GRAMs). Prior to our work, GRAMs were known but were prohibitively expensive. This dissertation presents new GC primitives that allow for a dramatically improved GRAM construction.

This dissertation presents these three advances in technical detail. The advances are carefully designed such that they can be used separately or in composition to greatly accelerate GC-based secure computation.

Together, these advances improve GC to the point that the cumulative change is qualitative. There are many computations that were previously infeasibly expensive and that are now well within scope. It is now realistic to consider, for example, a GC-embedded processor that conditionally executes complex instructions and that repeatedly accesses a large main memory. Thus, the techniques in this dissertation lay the groundwork for shifting away from the circuit model of computation and towards the more powerful RAM model of computation. This shift enables GC to handle new classes of complex secure computations, and hence enables a variety of interesting privacy-preserving and authenticated applications.