A Brief History of Practical Garbled Circuit Optimizations
summary
Thirty years of concrete optimizations cut garbled-circuit cost from four ciphertexts per gate to practical lows: row reduction drops four→three, free XOR makes XOR gates free (delta offsets), two‑ciphertext schemes (polynomial trick) shave ANDs to two, and the recent half‑gates combine free XOR with a two‑ciphertext AND that is provably optimal among linear/PRF/hash-based gate‑by‑gate methods. Implementations move AES garbling from seconds to microseconds using fixed‑key AES/AES‑NI; special‑case uses (authenticity only) reduce some ANDs to one.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 3:50Garbled Circuits
- 5:14Security Properties
- 6:15Optimization Parameters
- 8:05Graph
- 11:08Position Leaks
- 13:48First Optimization
- 15:35Instantiations
- 21:35Baseline
- 22:00Row Reduction
- 24:45Free XOR
- 28:31Incentives
- 29:19Assumptions
- 39:44Half Gates
- 44:43And Gates
- 50:30Optimization Floor
related talks
40mImplementation
44mThe Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
01h 01mSecurity: from Transistors to Compilers
34mRecent Advances in Asynchronous Multi-Party Computation
37mFrontiers in Cryptography
54mAttribute-based Encryption for Circuits
19mOn the Efficiency of RISC-V Cryptographic Instruction Set Extensions
41mFrom Caesar Cipher To Quantum Cryptography