Garbled Circuits and the Universal Composability Framework
Stub. The second major approach to secure two/three-party computation: Yao's garbled-circuit technique for Boolean circuits (encrypting each gate's truth table so evaluation reveals only the output wire), formal garbling-scheme security definitions and an efficient construction, protocols secure against honest-but-curious and against malicious adversaries; and the universal composability (UC) framework — the formal real-vs-ideal-world paradigm used to prove all of this (and the Beaver's-protocol constructions) secure, worked through on warmup and real examples.
Corresponds to Chapter 23.3, 23.5–23.6, 23.8. Where mpc-via-arithmetic-circuits-and-beavers-protocol secret-shares values across an arithmetic circuit, Yao’s garbled circuit technique instead encrypts an entire Boolean circuit gate-by-gate: each gate’s truth table is encrypted under combinations of wire-label keys, such that knowing only the correct input labels lets you decrypt exactly one (the correct) output label and nothing else — a single message from “garbler” to “evaluator” suffices for a whole computation, originally devised for two-party computation and extended here to a maliciously-secure three-party variant, with garbling schemes also useful standalone for outsourcing computation. The universal composability (UC) framework is the formal machinery underlying every security proof in this chapter and the previous one: define an “ideal” protocol where a trusted third party does the computation directly, and prove the real protocol is indistinguishable from it to any environment — covered via a warmup honest-but-curious proof and a warmup malicious-security proof (both for a simple OT protocol), then applied to Beaver’s protocol, the secure-distributed-core construction, and the three-party garbled-circuit protocol, plus extending DKG’s ideal functionality to full threshold MPC.
Outline (TODO — flesh out each)
- Boolean circuit evaluation
- Yao’s 2-party garbled circuit technique — basic ideas
- Garbling schemes — an application to outsourcing computation
- A simple but efficient garbling scheme (Garble0)
- Garbling schemes — formal security definitions
- A 2-party honest-but-curious garbling-based protocol
- A 3-party maliciously-secure garbling-based protocol
- The universal composability (UC) framework — real and ideal protocols
- Secure implementation; consequences of secure implementation
- Defining honest-but-curious security; a warmup OT security proof
- A warmup malicious-security proof for a simple OT protocol
- Malicious security proofs: Beaver’s protocol, the distributed core, the 3-party garbled circuit protocol
- Distributed key generation: ideal functionalities, extension to threshold MPC