Paper 2012/265

Foundations of Garbled Circuits

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway

Abstract

Garbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). Starting from a PRF, we provide an efficient garbling scheme achieving privacy and we analyze its concrete security. We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. We extend our scheme to achieve these ends. We provide highly efficient blockcipher-based instantiations of both schemes. Our treatment of garbling schemes presages more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Proceeding version appears in CCS 2012
Keywords
Garbled circuitsgarbling schemesprovable securitysecure function evaluationYao’s protocol
Contact author(s)
tvhoang @ ucdavis edu
History
2013-06-30: last of 4 revisions
2012-05-17: received
See all versions
Short URL
https://ia.cr/2012/265
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/265,
      author = {Mihir Bellare and Viet Tung Hoang and Phillip Rogaway},
      title = {Foundations of Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2012/265},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/265}},
      url = {https://eprint.iacr.org/2012/265}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.