International Association
for Cryptologic Research

Name: Viet Tung Hoang
Topic: Foundations of garbled circuits
Category: foundations

Description:

\r\nGarbled 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.\r\n

\r\nOn 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.\r\n

\r\nStandard 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 Rothblum2008) 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,[...]