Yao's garbled circuits

Yao's garbled circuits
Name	Yao's garbled circuits
Inventor	Andrew Yao
Year	1986
Field	Cryptography
Type	Secure computation protocol

Yao's garbled circuits is a cryptographic protocol for secure two-party computation that enables two parties to jointly evaluate a Boolean function on private inputs without revealing those inputs. Developed to address problems in secure function evaluation, the method transforms a computation into an encrypted Boolean circuit whose wires carry encrypted labels, allowing one party to evaluate the circuit while learning only the prescribed output. The protocol underpins modern research in multiparty computation, privacy-preserving machine learning, and secure outsourcing, influencing both theoretical cryptography and practical systems.

Overview

Yao's garbled circuits was introduced by Andrew Yao and builds on ideas from Boolean circuit representation, encryption primitives, and complexity-theoretic models such as the Turing machine and NP problem. The protocol involves a garbler and an evaluator; the garbler creates a garbled circuit using symmetric-key techniques like one-time pad style masking and oblivious transfer for input delivery. Foundational work connected this construction to notions in zero-knowledge proof research, interactive proof systems, and reductions used in computational complexity theory. Subsequent formalizations relate garbling to primitives studied at venues such as CRYPTO, EUROCRYPT, IEEE Symposium on Security and Privacy, and ACM CCS.

Construction and Protocol

The garbling procedure converts each gate of a Boolean circuit (built from gates such as AND gate, OR gate, XOR gate) into a table of ciphertexts; wire labels correspond to masked semantics and are produced using cryptographic building blocks like pseudorandom functions, block ciphers (e.g., AES), and hash functions. The garbler assigns two random labels per wire corresponding to semantic values 0 and 1 and encrypts gate outputs under combinations of input labels, producing a garbled table. The evaluator receives garbled tables and obtains labels for its inputs through protocols such as oblivious transfer (e.g., 1-out-of-2 OT) implemented using assumptions like RSA or Diffie–Hellman and variants based on elliptic curve cryptography such as ECDH. Evaluation proceeds by decrypting appropriate table entries to propagate labels to outputs, and a final decoding maps labels to explicit outputs with assistance from mapping data such as a decode table. Optimizations exploit results from free-XOR technique, point-and-permute, and techniques using random oracle heuristics common in proofs presented at FOCS and STOC.

Security Definitions and Proofs

Security of the protocol is typically stated in a simulation-based paradigm originating from works by Odlyzko-era cryptographers and formalized in frameworks like the Universal Composability model and the stand-alone model. Proofs show that for semi-honest adversaries the evaluator learns nothing beyond the output by constructing a simulator that generates indistinguishable garbled circuits using computational assumptions such as the hardness of discrete logarithm problem or security of PRF families. For malicious adversaries, techniques like cut-and-choose, zero-knowledge proofs, and commitment schemes (e.g., Pedersen commitment) are incorporated; security reductions often reference hardness assumptions associated with LWE, RSA, and collision-resistance of SHA-2 or SHA-3. Formal notions include privacy, correctness, and fairness discussed in literature from IACR workshops and textbooks by authors affiliated with MIT, Stanford University, UC Berkeley, and ETH Zurich.

Optimizations and Variants

A large body of work focuses on reducing communication and computation overhead: free-XOR technique eliminates costs for XOR gates, while half-gates optimization and garbled row reduction halve garbled table sizes for AND gates. Variants include GMW protocol hybrids, half-gates and batching strategies, and approaches leveraging homomorphic encryption and function secret sharing to support private function evaluation and outsourced computation. Implementations exploit hardware such as Intel SGX for trusted execution, and protocols integrate with TLS stacks and standards like IETF specifications. Optimizations also draw upon algorithmic primitives studied at SODA and ICALP.

Applications

Yao-style garbling is applied in privacy-preserving analytics including secure auctions involving institutions like NASDAQ and Euronext, privacy-aware biometric matching in projects at NIST and National Institutes of Health, and secure machine learning in collaborations between Google and academic labs at Carnegie Mellon University and University of Toronto. Use cases extend to secure voting systems evaluated against standards from Election Assistance Commission, private set intersection deployments in industry partners such as Microsoft and Facebook, and genomic computation researched at Broad Institute and Wellcome Sanger Institute. Research prototypes demonstrate secure inference for models originally developed at OpenAI, DeepMind, and academic groups at University of California, San Diego.

Implementation and Performance

Practical systems implement garbled circuits using optimized cryptographic libraries like OpenSSL, libsodium, and frameworks such as Obliv-C, EMP-toolkit, and HElib integrations. Performance engineering involves choices of symmetric-key primitives (e.g., AES-NI acceleration), OT extension protocols like IKNP OT extension, and parallelization across multicore servers in data centers operated by Amazon Web Services, Google Cloud Platform, and Microsoft Azure. Benchmarks reported at Usenix Security and NDSS measure throughput and latency for workloads including secure neural network inference, private set intersection, and secure database joins, reflecting trade-offs between bandwidth, computation, and security level parameters aligned with standards from NIST.

History and Attribution

The concept was introduced by Andrew Yao in the 1980s, rooted in earlier studies of secure computation and complexity dating to the 1970s and developments surrounding Yao's Millionaires' problem and subsequent formalizations by researchers at institutions such as Princeton University, Harvard University, and Tsinghua University. Major contributions refining the technique came from scholars associated with conferences like CRYPTO, EUROCRYPT, FOCS, and STOC and organizations including IACR and ACM. Later industrial and academic collaborations emanated from labs at IBM Research, Bell Labs, and Microsoft Research contributing optimizations, security proofs, and systems engineering that propelled garbled circuits into widespread study and deployment.

Category:Cryptographic protocols