LogStack: Stacked Garbling with O(b log b) Computation
David Heath
Abstract:
Secure two party computation (2PC) can be efficiently achieved using garbled circuits (GC). Recently, our Stacked Garbling (SGC) technique showed that GC can be greatly improved for circuits that include conditional behavior (Heath and Kolesnikov, Crypto 2020). SGC shows that we need communication proportional only to the program’s longest execution path, not to the entire circuit. Unfortunately, SGC greatly increases computation: one party, the GC generator, must use computation quadratic in the number of program branches. In this talk I will present LogStack (Heath and Kolesnikov, Eurocrypt 2021), an improvement to SGC that demonstrates quadratic scaling is unnecessary. LogStack allows the parties to enjoy SGC communication improvement with only logarithmic computation overhead. Additionally, LogStack consumes far less memory than our previous work. At the highest level, SGC’s increased computation stems from the oblivious elimination of “garbage labels” that emerge when evaluating inactive conditional branches. LogStack introduces new circuit gadgets in order to reorganize the handling of garbage labels. This reorganization allows the parties to re-use the same work to collect garbage in different scenarios, and hence greatly improves performance LogStack is a substantial practical improvement to SGC and opens the door to efficient handling of high branching factors.