The Whole is Greater than the Sum of its Parts: Linear Garbling and Applications
summary
Proposes a linear garbling framework that treats garbling as secret sharing (apply matrices to random vectors) and proves that two algebraic properties—linear reconstruction and linear privacy—imply simulation security. Shows how slicing circuits into larger units circumvents gate-by-gate lower bounds (example: a quadratic example uses four rows vs twelve rows from a trivial half-gates circuit), gives better parallelism of random-oracle calls, and extends to arithmetic garbling for small finite fields and Beaver-style MPC, with concrete matrix constructions and row counts per polynomial.
AI-written summary · about
chapters (5)
- 0:00Start
- 1:47What is garbling? BHR12
- 4:53Linear garbling ZRE15
- 18:09Generalized half-gates
- 21:54Summary, Sneek Peak, and Extras
related talks
27mSparsity and Privacy in Distributed Matrix Multiplication
44mThe Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
01h 57mFun with Lattices
01h 05mAn Algebraic Framework for Universal and Updatable zkSNARKs
44mHow Robust are Linear Sketches to Adaptive Inputs?
01h 06mOn the Assumptions Used for Obfuscation
01h 31mIntroduction to Secure Multi-Party Computation
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation