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.


Stacked Garbling

September 28, 2023


Vladimir Kolesnikov - Georgia Tech


Abstract. Garbled Circuits (GC) is a general technique for two-party secure computation (2PC).  Classic GC, modernized with Free-XOR, half-gates, etc, is currently the most efficient 2PC technique for most settings (a setting is defined by a network/compute configuration and computed function).  The main GC cost bottleneck is that of the transmission of the encrypted (garbled) circuit. The most significant drawback of GC is that it relies on the Boolean circuit representation of the computed function. In this talk, I will discuss a Garbled Circuit (GC) gadget Stacked Garbling (SGC).  SGC equips Boolean circuits with conditional branching and allows to efficiently evaluate one of several of the branch clauses.   Specifically, the communication for evaluating the conditional is proportional to the single longest branch (vs all branches in classic GC). I will briefly discuss the usefulness of the SGC gadget in MPC, particularly as we move from Boolean circuits to the more powerful RAM machine model of representing the computed functions.

[Slides] [Video]

Presented at

MPTS 2023: NIST Workshop (virtual) on Multi-Party Threshold Schemes 2023

Event Details



Related Topics

Security and Privacy: cryptography

Created September 21, 2023, Updated October 25, 2023