Paper 2018/789

Free IF: How to Omit Inactive Branches and Implement S-Universal Garbled Circuit (Almost) for Free

Vladimir Kolesnikov

Abstract

Two-party Secure Function Evaluation (SFE) allows two parties to evaluate a function known to both parties on their private inputs. In some settings, the input of one of the parties is the definition of the computed function, and requires protection as well. The standard solution for SFE of private functions (PF-SFE) is to rely on Universal Circuits (UC), which can be programmed to implement any circuit of size s. Recent UC optimizations report the cost of UC for s-gate Boolean circuits is \approx 5s log s. Instead, we consider garbling that allows evaluating one of a given set S of circuits. We show how to evaluate one of the circuits in S at the communication cost comparable to that of evaluating the largest circuit in S. In other words, we show how to omit generating and sending inactive GC branches. Our main insight is that a garbled circuit is just a collection of garbled tables, and as such can be reused to emulate the throw-away computation of an inactive execution branch without revealing to the Evaluator whether it evaluates active or inactive branch. This cannot be proven within the standard BHR garbled circuits framework because the function description is inseparable from the garbling by denition. We carefully extend BHR in a general way, introducing topology-decoupling circuit garbling. We preserve all existing constructions and proofs of the BHR framework, while allowing this and other future constructions which may treat garbled tables separately from function description. Our construction is presented in the semi-honest model.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2018
Keywords
Garbled CircuitUniversal CircuitGC frameworkinactive GC clauses
Contact author(s)
kolesnikov @ gatech edu
History
2018-09-01: received
Short URL
https://ia.cr/2018/789
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/789,
      author = {Vladimir Kolesnikov},
      title = {Free IF: How to Omit Inactive Branches and Implement S-Universal Garbled Circuit (Almost) for Free},
      howpublished = {Cryptology ePrint Archive, Paper 2018/789},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/789}},
      url = {https://eprint.iacr.org/2018/789}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.