Garbled Circuit Lookup Tables

Abstract. Garbled Circuit (GC) is a fundamental technique for achieving secure two-party computation (2PC). Classic GC allows two parties to securely execute any program over their joint private inputs, so long that program is expressed as a Boolean circuit. The requirement that programs be expressed as a Boolean circuit is a weakness of the approach, as many programs are more efficient when expressed in other forms. In this talk, I will discuss two GC gadgets: One-Hot Garbling and Garbled RAM. Roughly speaking, these gadgets upgrade GC with the ability to efficiently handle lookup tables and arrays. These capabilities are traditionally expensive to encode as circuits, and their efficient handling can accelerate many secure computations. I will explain how these basic tools are useful in the broad context of MPC, and how they might be useful in specific contexts, such as the secure evaluation of block ciphers.

[Slides] [Video]