Cryptology ePrint Archive: Report 2012/265

Foundations of Garbled Circuits

Mihir Bellare and 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.

Category / Keywords: Garbled circuits, garbling schemes, provable security, secure function evaluation, Yao’s protocol

Publication Info: Proceeding version appears in CCS 2012

Date: received 9 May 2012, last revised 30 Jun 2013

Contact author: tvhoang at ucdavis edu

Available format(s): PDF | BibTeX Citation

Version: 20130630:182204 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]