International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Garbling, Stacked and Staggered: Faster k-out-of-n Garbled Function Evaluation

David Heath , Georgia Institute of Technology
Vladimir Kolesnikov , Georgia Institute of Technology
Stanislav Peceny , Georgia Institute of Technology
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: Stacked Garbling (SGC) is a Garbled Circuit (GC) improvement that efficiently and securely evaluates programs with conditional branching. SGC reduces bandwidth consumption such that communication is proportional to the size of the single longest program execution path, rather than to the size of the entire program. Crucially, the parties expend increased computational effort compared to classic GC. Motivated by procuring a subset in a menu of computational services or tasks, we consider GC evaluation of k-out-of-n branches, whose indices are known (or eventually revealed) to the GC evaluator E. Our stack-and-stagger technique amortizes GC computation in this setting. We retain the communication advantage of SGC, while significantly improving computation and wall-clock time. Namely, each GC party garbles (or evaluates) the total of n branches, a significant improvement over the O(nk) garblings/evaluations needed by standard SGC. We present our construction as a garbling scheme. Our technique brings significant overall performance improvement in various settings, including those typically considered in the literature: e.g. on a 1Gbps LAN we evaluate 16-out-of-128 functions ~7.68x faster than standard stacked garbling.
  title={Garbling, Stacked and Staggered: Faster k-out-of-n Garbled Function Evaluation},
  author={David Heath and Vladimir Kolesnikov and Stanislav Peceny},