Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


Let’s Standardize Garbled Circuits!

November 5, 2020


Vladimir Kolesnikov - Georgia Tech


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.

Presented at

NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2020.

This talk relied on joint works with David Heath and Thomas Schneider.

Event Details



Related Topics

Security and Privacy: cryptography

Created May 04, 2021, Updated June 07, 2021