The Garbling Papers

In this sequence of three papers we rework the foundations of garbled circuits. This includes developing multiple security definitions for garbling, providing new garbling schemes, proving security for various garbling schemes, investigating applications, and looking at some past errors in the literature. We view the papers as a set—a single storyline that, due to its breadth, was published as a sequence of work.

1. Foundations of Garbled Circuits

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.

Proceedings version appears in ACM Conference on Computer and Communications Security 2012.
Full version available in pdf.

2. Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing

Authors: Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway,

Abstract: Standard constructions of garbled circuits provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some applications—notably one-time programs (Goldwasser, Kalai, and Rothblum 2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)— need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with regard to adaptive security and suggest the need of a better abstraction boundary. To this end we investigate the adaptive security of garbling schemes, an abstraction of Yao’s garbled-circuit technique that we recently introduced (Bellare, Hoang, Rogaway 2012). Building on that framework, we give definitions encompassing privacy, authenticity, and obliviousness, with either coarse-grained or fine-grained adaptivity. We show how adaptively secure garbling schemes support simple solutions for one-time programs and secure outsourcing, with privacy being the goal in the first case and obliviousness and authenticity the goal in the second. We give transforms that promote static-secure garbling schemes to adaptive-secure ones. Our work advances the thesis that conceptualizing garbling schemes as a first-class cryptographic primitive can simplify, unify, or improve treatments for higher-level protocols

Proceedings version appears in Asiacrypt 2012.
Full version available in pdf.

3. Efficient Garbling from a Fixed-Key Blockcipher

Authors: Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway,

Abstract: We advocate schemes based on fixed-key AES as the best route to highly eprintcient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the JustGarble system, which implements our schemes. JustGarble evaluates moderate-sized garbled-circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results

Proceedings version appears in IEEE Security and Privacy 2012.
Full version available in pdf.