Yao's Garbled Circuit

(... crypto bite to be written)

Source

Parts of this crypto bite are inspired by [Y17, LP08]. Another gentle introduction to Yao's protocol can also be found in [HL10, Chapter 3], which I highly recommend. A rigorous formalism which distills the cryptographic primitive called a garbling scheme from the technique of garbled circuits can be found in [BHR12]. One of the first papers which presented Yao's Garbled Circuit in writing was [GMW87]. Fairplay, an implementation of Yao's Garbled Circuit is described in [MNPS04]. Many software frameworks using garbled circuits are listen in awesome-mpc.

One way to implement Garbled Circuits in general is to generate a netlist via a Verilog description of the function. This netlist, which represents the circuit, is then augmented accordingly, and then evaluated[SHSSK15].

A good introduction to Yao's Garbled Circuits is the talk "Yao’s Two-Party Protocol and the BMR Multi-Party Protocol" by Prof. Benny Pinkas at the 5th BIU Winter School on Cryptography: Advances in Practical Multiparty Computation, February 15-19, 2015, Bar-Ilan University, Israel. The first part of the talk up to 58:10 covers Yao's Garbled Circuit. Slides available [P15].

An earlier presentation of Yao's Protocol is Prof. Yehuda Lindell's talk "The Yao Construction and its Proof of Security" at the 1st BIU Winter School on Cryptography: Secure Computation and Efficiency, January 30-February 1, 2011, Bar-Ilan University. The slides of this talk als avaible too [L11].

Here's another introduction to Yao's garbled circuits by Omer Paneth in an advanced lecture of the MIT course 6.875 (Cryptography): L20. Garbled Circuits (inofficial video).

Literature