BitGC: Garbled Circuits with 1 Bit per Gate

on YouTube ↗33m

" summary

BitGC claims a rate-one garbling that sends a SWHE-encrypted seed plus one-bit per gate stitching data under ring‑RLWE with key‑dependent‑message security. Computation homomorphically expands the seed with a low‑depth PRG, then uses two extra multiplication levels to assemble garbled tables, so it requires no bootstrapping. An implementation optimizes the PRG and gate assembly and reports about 10 microseconds per gate (comparable to TFHE per‑gate bootstrapping speeds).

AI-written summary · about

" chapters (10)

1. 0:00BitGC introduction
2. 1:58Stronger assumptions for garbling
3. 5:19Classical garbled circuits
4. 7:28Homomorphic random oracle
5. 12:01Polynomial ring labels
6. 18:47Distributed garbled evaluation
7. 23:01Dec tilde gadget
8. 27:24PRG and gate optimization
9. 30:43Performance vs classical
10. 31:28Q&A

" related talks

• 01h 07mGarbled Circuits IBenny Applebaum · Cryptography Boot Camp 2015
• 51mNew Ways to Garble Arithmetic CircuitsRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 28mNew Advances in Secure RAM ComputationSanjam Garg · Securing Computation (Simons Institute, June 2015)
• 44mGarbled Circuits IIBenny Applebaum · Cryptography Boot Camp 2015
• 46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...Ji Luo · Obfuscation
• 01h 04mFully Homomorphic Encryption IIShai Halevi · Cryptography Boot Camp 2015
• 53mFoundations 1Iftach Haitner · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mTowards general-purpose program obfuscation via local mixingRan Canetti, Claudio Chamon, Eduardo R. Mucciolo, Andrei E. Ruckenstein · Obfuscation