Let’s Standardize Garbled Circuits!

Abstract: Garbled Circuits (GC) is the classic, most popular and often the fastest approach to general secure two-party computation (2PC). In the semi-honest model, we can evaluate about two million AND gates per second on commodity devices and networks. This translates, for example, to approximately 330 shared-key AES evaluations per second. With specialized hardware or allowing precomputation, this number can be further greatly increased.Since its introduction by Andrew Yao in 1986, there have been only a small number of improvements to the basic protocol. In this talk, time permitting, I will briefly review the basic protocol and some of the improvements, such as Free-XOR and our recent work Stacked Garbling. I will also talk about stronger security models, particularly cheap-to-achieve covert and publicly verifiable covert (PVC) models.The stability, wide acceptance, simplicity, efficiency and generality of the GC protocol is unique among MPC protocols, and make it a strong candidate for standardization. A standardized GC variant would be a powerful and versatile tool, which would catalyze both wide practical adoption of rich cryptography and further MPC research.