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.