Garbled Circuits: Optimizations and Implementations

Keywords:

Abstract:

Garbled Circuits were first introduced by Yao in 1984 as a generic approach to perform secure two-party computation between two semi-honest participants. While the result already has a great theoretical significance, it was believed to have very limited applicability due to performance aspects. In the last ten-fifteen years, though, many researchers revived this approach by optimizing one aspect after the other, which results in total in several orders of magnitude of speed-up. In this article, we start by describing the original garbled circuits construction through a simple example. We then review the optimizations of garbled circuits, from point-and-permute to half-gates, going through garbled row reduction, oblivious transfer extensions, and free XOR. Finally, we present several projects that implemented garbled circuits with some of these optimizations, starting from fairplay to the more recent approaches of OblivC and ObliVM.