Garbling Schemes

Authors: 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 twoparty 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.

Cite as: M. Bellare, V. Hoang, and P. Rogaway. Garbling Schemes. ePrint Report 2012/265, May 2012.

@misc{cryptoeprint:2012:265,
author = {Mihir Bellare and Viet Tung Hoang and Phillip Rogaway},
title = {Garbling Schemes},
howpublished = {Cryptology ePrint Archive, Report 2012/265},
year = {2012},
note = {\url{http://eprint.iacr.org/}},
}

Availability: Full version in pdf.