Cryptology ePrint Archive: Report 2021/1590

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

David Heath and Vladimir Kolesnikov and Stanislav Peceny

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.

Category / Keywords: cryptographic protocols / Garbled Circuit, Conditional Branching, Stacked Garbling

Original Publication (in the same form): IACR-ASIACRYPT-2021

Date: received 3 Dec 2021

Contact author: heath davidanthony at gatech edu, kolesnikov at gatech edu, stan peceny at gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20211206:035102 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]