(... crypto bite to be written)
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).
- [Y17] Sophia Yakoubov: A Gentle Introduction to Yao's Garbled Circuits.
- [L11] Yehuda Lindell: The Yao Protocol and its Proof of Security (slides of the talk above)
- [P15] Benny PInkas: Yao's Two-Party Protocol and the BMR Multi-Party Protocol (slides of the talk above)
- [LP08] Yehuda Lindell, Benny Pinkas: Secure Multiparty Computation for Privacy-Preserving Data Mining (iacr.org, full pdf)
- [HL10] Carmit Hazay, Yehuda Lindell: Efficient Secure Two-Party Protocols, Techniques and Constructions. (springer.com, read with VPN via link.springer.com)
- [BHR12] Mihir Bellare, Viet Tung Hoang, Phillip Rogaway: Foundations of Garbled Circuits (iacr.org, full pdf)
- [GMW87] Oded Goldreich, Silvio Micali, Avi Wigderson: How to Play Any Mental Game, or: A Completeness Theorem for Protocols with Honest Majority (extended abstract). In Proceedings of the 19th Symposium on the Theory of Computing (STOC), pp. 218-229, May 1987. (IEEE (paywalled), full pdf).
- [MNPS04] Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella: Fairplay, A Secure Two-Party Computation System. In: Proceedings of the 13th USENIX Security Symposium, San Diego, CA, USA. August 9-13, 2004. (usenix full pdf, also as pinkas full pdf)
- [HEKM11] Yan Huang, David Evans, Jonathan Katz, Lior Malka: Faster Secure Two-Party Computation Using Garbled Circuits. In: SEC'11 Proceedings of the 20th USENIX conference on Security. Pages 35pp (full pdf).
- [SHSSK15] Ebrahim M. Songhori, Siam U. Hussain, Ahmad-Reza Sadeghi, Thomas Schneider and Farinaz Koushanfar, "TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits." Security and Privacy, 2015 IEEE Symposium on May, 2015. (full pdf, github repo, video, video)