New Ways to Garble Arithmetic Circuits
summary
Presents a construction that achieves constant-rate for bounded integers using the Decisional Composite Residuosity (Paillier) assumption and an alternative LWE instantiation, plus a modular Zp garbling based on DCR or LWE and a mixed arithmetic+Boolean model that keeps the arithmetic part constant-rate. Key technical tool is a linear-homomorphic key-extension gadget (Paillier/LWE variants) that shrinks labels; concrete gains claim ~600–800× smaller garbled multiplication size versus Boolean baseline and a tradeoff of roughly one Paillier modular multiply per key extension vs ~450 AES; bit-decomposition remains quadratic in DCR key length.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:44Garbled Circuit [Yao82,BHR12]
- 9:02AIK11: Garble Arithmetic Circuits
- 11:55AIK14: Garble Arithmetic Circuits
- 15:39Efficiency: Rate of Garbling
- 21:20Constant-Rate
- 22:41Potential for Concrete Efficiency
- 23:49Arithmetic Garbling for Zp-comp
- 28:43Gadget for Multiplication over R
- 29:44Compose to handle ANY circuit
- 30:36Key Extension to Help
- 31:55Our Idea: Key Extension
- 33:17Use Linearly Homomorphic Encryption (LHE)
- 35:22Simulation Security
- 39:14Paillier One-Time LHE
- 42:23Key Extension for Bounded Int from Paillier
- 44:07Key Extension for Zp-computation
- 45:07Open Problems
related talks
01h 03mBeyond Boolean Circuits in Garbled Circuits
01h 07mGarbled Circuits I
35mA Unified Framework for Succinct Garbling from Homomorphic Secret Sharing
46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...
01h 00mSecure Computation 3
01h 29mLattices, Multilinear Maps and Program Obfuscation
28mNew Advances in Secure RAM Computation
01h 03mLockable Obfuscation