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

David Heath, Vladimir Kolesnikov, Stanislav Peceny

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(n· k) 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.68 × faster than standard stacked garbling.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 2
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer
Pages245-274
Number of pages30
ISBN (Print)9783030920746
DOIs
StatePublished - 2021
Externally publishedYes
Event27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online
Duration: Dec 6 2021Dec 10 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13091 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
CityVirtual, Online
Period12/6/2112/10/21

Keywords

  • Conditional branching
  • Garbled circuit
  • Stacked garbling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Garbling, Stacked and Staggered: Faster k-out-of-n Garbled Function Evaluation'. Together they form a unique fingerprint.

Cite this