Garbled Circuits I

on YouTube ↗01h 07m

" summary

Starts from precise definitions of garbled circuits as randomized encodings and works through simple encodings to a general template that yields Yao-style garbling via a decomposable affine randomized encoding plus a key-shrinking gadget. Gives constructions that achieve online rate one using homomorphic-style tools (DDH/LWE variants), a practical set-encryption gadget to compress keys, and an impossibility for fully arithmetic decoders; lists open problems about NC2/field variants and implementation tradeoffs.

AI-written summary · about

" chapters (30)

1. 0:00Intro
2. 0:30Plan
3. 1:20Garbled Circuit
4. 3:30Randomized Encoding of Functions
5. 6:26(Silly) Example
6. 6:50(Less Silly) Example II
7. 9:29Usefulness
8. 10:18Example: Non-Interactive Delegation
9. 11:41Useful Properties
10. 14:54Encoding a Function Family
11. 19:55Notions of simplicity: Affinity
12. 21:23Notions of simplicity: Decomposability
13. 22:19Decomposable Affine RE'S (DARE)
14. 26:00Goal l: perfect DARE for formulas
15. 26:35DARE for Simple Functions
16. 30:36Encoding the Circuit Layer-by-Layer
17. 31:50Garbling the Circuit Layer-by-Layer
18. 37:52Garbling General Circuits
19. 38:21Key-Shrinking Gadget
20. 39:13Implementing Key-Shrinking (Boolean case)
21. 41:44Corollary: DARE for Boolean Circuits
22. 42:33Q: DARE for Arithmetic Circuits?
23. 44:05Implementing Key-Shrinking (Arithmetic case)
24. 45:47DARE for Circuits over Integers
25. 52:33Efficiency Improvements
26. 53:01Improving Online Rate
27. 56:08Gadget: Set Encryption Bob
28. 57:01Gadget = Compressing Keys
29. 58:49Implementing the Gadget
30. 59:25From Homomorphism to Set Encryption

" related talks

• 01h 03mBeyond Boolean Circuits in Garbled CircuitsDavid Heath · Secure Computation 2025
• 51mNew Ways to Garble Arithmetic CircuitsRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 35mA Unified Framework for Succinct Garbling from Homomorphic Secret SharingRachel Lin · Secure Computation 2025
• 46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...Ji Luo · Obfuscation
• 33mBitGC: Garbled Circuits with 1 Bit per GateXiao Wang · Secure Computation 2025
• 37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and SimplerRachit Garg · Obfuscation
• 28mNew Advances in Secure RAM ComputationSanjam Garg · Securing Computation (Simons Institute, June 2015)
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020