Stacked Garbling

Abstract. Garbled Circuits (GC) is a general technique for two-party secure computation (2PC).  Classic GC, modernized with Free-XOR, half-gates, etc, is currently the most efficient 2PC technique for most settings (a setting is defined by a network/compute configuration and computed function).  The main GC cost bottleneck is that of the transmission of the encrypted (garbled) circuit. The most significant drawback of GC is that it relies on the Boolean circuit representation of the computed function. In this talk, I will discuss a Garbled Circuit (GC) gadget Stacked Garbling (SGC).  SGC equips Boolean circuits with conditional branching and allows to efficiently evaluate one of several of the branch clauses.   Specifically, the communication for evaluating the conditional is proportional to the single longest branch (vs all branches in classic GC). I will briefly discuss the usefulness of the SGC gadget in MPC, particularly as we move from Boolean circuits to the more powerful RAM machine model of representing the computed functions.

[Slides] [Video]