Paper 2021/1590

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

David Heath, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2021
DOI
10.1007/978-3-030-92075-3_9
Keywords
Garbled CircuitConditional BranchingStacked Garbling
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
stan peceny @ gatech edu
History
2021-12-06: received
Short URL
https://ia.cr/2021/1590
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1590,
      author = {David Heath and Vladimir Kolesnikov and Stanislav Peceny},
      title = {Garbling, Stacked and Staggered: Faster k-out-of-n Garbled Function Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1590},
      year = {2021},
      doi = {10.1007/978-3-030-92075-3_9},
      note = {\url{https://eprint.iacr.org/2021/1590}},
      url = {https://eprint.iacr.org/2021/1590}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.