GARBLED CIRCUITS & SECURE TWO-PARTY COMPUTATION Payman Mohassel Yahoo Labs History of Garbled Circuits 1982: First oral presentation [Andrew Yao] 1987: First written account [GMW] (public-key) 1990: First use of term ``Garbled circuits” [BMR] (symmetric-key) 1994: First abstraction as a primitive [FKN] (minimal model for sec. comp.) 1999: First PRF-based construction [NPS] (PP-auctions) 2004: First implementation [MNPS] (Fairplay) 2004: First proof of 2PC based on garbled circuits [LP] (double-encryption) A Garbling Scheme seed , = (, ) Eval( ) (, ) Basic Properties Privacy: Knowing , , and does no leak any info (, ) Output Authenticity: Cannot compute another valid output ‘ Many Applications Secure multi-party computation Zero-knowledge proofs Verifiable computation Homomorphic encryption One-time programs Circular-secure encryption Functional encryption ... Emerged as a powerful building block! Secure Multiparty Computation (MPC) P2, x2 P1, x1 P3, x3 P5, x5 P4, x4 Correctness: honest parties learn the correct output Privacy: Nothing but the final output is leaked Parties learn only f(x1,…,xn) Fairness, Output Delivery, … Applications of MPC Data mining Electronic Voting Auctions Exchanges/financial analysis Location privacy Genomic computation Electronic commerce Healthcare When there is IP, NDA, user consent involved When you need to distribute trust Secure Two-Party Computation (2PC) , = (, ) ← (, ) ← (, ) Evaluator Garbler Oblivious Transfer (, ) Yao’s Garbled Circuit Protocol First secure computation protocol Efficient and simple Implementations › Fairplay, 2004 TASTY, 2010 FastGarble, 2011 SCAPI, 2013 JustGarble, 2013 › … › › › › • Circuits with millions of gates in less than a second Research Directions Garbling Constructions Functionality & Security Properties Secure 2PC Basic Garbling/Evaluation Evaluate Garble 01 , 11 AND 02 , 12 3 3 0 , 1 AND 0,0 = 01,02 (03 ) 0,1 = 01,12 (03 ) 1,0 = 11,02 1,1 = 11,12 (03 ) (13 ) 3 1 , 2 , = & Constructions (Efficiency) 1990: Point-and-Permute [BMR] 1999: 3-row reduction [NPS] 2008: Free-XOR [KS] 2009: 2-row reduction [PSSW] 2013: Fixed-key block-cipher [BHKR] 2014: FleXor [KMR] 2014: Privacy-free garbling [KNO] 2015: HalfGates [ZRE] (2-row non-XORs, and 0-row XORs) How low can we get? Lower bounds? Fresh ideas for garbling needed? Constructions (Security) Weak Assumptions PRF double-encryption LPN Free-XOR Correlation-robustness row reduction techniques Correlation-robustness FleXor Strong Assumptions Circular-security Free-XOR Circular-security Half-Gates Ideal-permutation Fixed-key block-cipher RO Adaptive security Can we achieve these using weak assumptions? Standard Security Properties Input privacy › Needed in most applications (not in ZK application) Function privacy › Private function evaluation Output authentication › Malicious 2PC, dual-execution, verifiable comp., server-aided comp., ZK Adaptive privacy › Verifiable comp, offline/online batch execution, … New Security Properties? Only a subset of properties (e.g. privacy-free garbling) Leaky privacy (e.g. leak a few bits, protect/leak certain functions) Tunable security! (tunable privacy, authenticity, …) Leveled privacy (inputs with different sensitivity levels) Functionality? Standard ones › Garble, encode inputs, evaluate, authenticate outputs Circuit property enforcing (with Rosulek and Kolesnikov) › Checking circuit properties › Topology, depth, input size, gate types › Useful in limiting malicious behavior Input property enforcing › Unique input identifier (for input consistency) › Enforcing input formats › Enforce relation between inputs in multiple executions (beyond equality) Output property enforcing › Enforcing output format Malicious 2PC Are all inputs the same? Evaluate Open 1 2 ⋮ 1 3 Is the output correct? 1 2 2 1 − 2−Ω ≥ 40 3 4 5 Majority 4 4 6 6 5 6 = (, ) Secure 2PC Malicious security › › › › Cut-and-choose (state of the art: Lindell 2013) Abstracting out cut-and-choose (joint work with Seny Kamara) A new paradigm? Lower bounds for cut-and-choose? RAM programs › › › › Optimizing ORAM for 2PC ([WCS]: Circuit-ORAMs) Implementation framework (SCVM) Extending cut-and-choose to RAM programs ([AHMR]) Lots of interesting questions 2PC with relaxed security › › Covert security, leaky 2PC, one-sided security Restricting leakage functions Questi ons?