01388nas a2200181   4500000000100000000000100001008004100002653001700043653002100060653002000081653001800101653003500119100002200154245005600176300001000232490000700242520095700249       2017                            d10acryptography10aGarbled Circuits10aImplementations10aOptimizations10aSecure Multi-Party Computation1 aAbdullatif Shikfa00aGarbled Circuits: Optimizations and Implementations  a11-270 v373 a<p>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.</p>