Beyond Boolean Circuits in Garbled Circuits

on YouTube ↗01h 03m

" summary

Claims that garbled circuits compile arithmetic gates and RAM to a small set of primitives and that, using only symmetric cryptography (a random oracle), multiplication and memory access cost scale roughly linearly in word size instead of quadratically. The construction compiles programs to a switch system of one-hot vector lookups plus XORs, pays communication only at join gates, and achieves short encodings for small-word arithmetic and RAM-style access while preserving obliviousness via simple randomness.

AI-written summary · about

" chapters (10)

1. 0:00Introduction to garbled circuits
2. 3:59Beyond boolean circuits
3. 7:04The switch system model
4. 13:12Foundations and preliminaries
5. 18:55Switch system gates
6. 28:38Encoding and evaluation
7. 37:20Oblivious switch systems
8. 40:33One-hot garbling and scaling
9. 47:11Arithmetic circuit multiplication
10. 56:22Conclusion and future work

" related talks

• 51mNew Ways to Garble Arithmetic CircuitsRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mGarbled Circuits IBenny Applebaum · Cryptography Boot Camp 2015
• 28mNew Advances in Secure RAM ComputationSanjam Garg · Securing Computation (Simons Institute, June 2015)
• 44mGarbled Circuits IIBenny Applebaum · Cryptography Boot Camp 2015
• 01h 06mOblivious RAM IIElaine Shi, Daniel Wichs · Cryptography Boot Camp 2015
• 01h 06mTowards general-purpose program obfuscation via local mixingRan Canetti, Claudio Chamon, Eduardo R. Mucciolo, Andrei E. Ruckenstein · Obfuscation
• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 35mOblivious RAM for MPCStanislaw Jarecki · Securing Computation (Simons Institute, June 2015)