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). We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. Starting from a PRF, we give efficient schemes to achieve all security notions above, and analyze their concrete security. Our treatment of garbling schemes provides ground for more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.
On the practical side, we provide extremely efficient garbling schemes based on fixed-key AES. We justify the security of these methods in the random-permutation model, where parties have access to a public random permutation, and build the JustGarble system to implement them. 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.
Standard constructions of garbling schemes, including ours, provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some application—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, which signifies the absence of a good abstraction boundary. We then investigate adaptive security of garbling schemes, giving 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. This gives another compelling evidence that conceptualizing garbling schemes as a first-class cryptographic primitive can simplify, unify, or improve treatments for higher-level protocols.