Paper 2020/973

Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path

David Heath and Vladimir Kolesnikov


Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that for direct 2PC evaluation of a Boolean circuit, it is necessary to transmit the entire GC, including garbled truth tables corresponding to subcomputations whose output is ultimately discarded by conditional logic. This folklore belief is false. We propose a novel GC technique, stacked garbling, that eliminates the communication cost of inactive conditional branches. We extend the ideas of conditional GC evaluation explored in (Kolesnikov, Asiacrypt 18) and (Heath and Kolesnikov, Eurocrypt 20). Unlike these works, ours is for general 2PC where no player knows which conditional branch is taken. Our garbling scheme, Stack, requires communication proportional to the longest execution path rather than to the entire circuit. Stack is compatible with state-of-the-art techniques, such as free XOR and half-gates. Stack is a garbling scheme. As such, it can be plugged into a variety of existing protocols, and the resulting round complexity is the same as that of standard GC. The approach does incur computation cost quadratic in the conditional branching factor vs linear in standard schemes, but the tradeoff is beneficial for most programs: GC computation even on weak hardware is faster than GC transmission on fast channels. We implemented Stack in C++. Stack reduces communication cost by approximately the branching factor: for 16 branches, communication is reduced by 10.5x. In terms of wall-clock time for circuits with branching factor 16 over a 50 Mbps WAN on a laptop, Stack outperforms state-of- the-art half-gates-based 2PC by more than 4x.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Multiparty ComputationGarbled CircuitsInactive Branch Elimination
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
2022-05-10: revised
2020-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov},
      title = {Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path},
      howpublished = {Cryptology ePrint Archive, Paper 2020/973},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.