A Unified Framework for Succinct Garbling from Homomorphic Secret Sharing
summary
Framework claims a path between fast symmetric garbling and fully succinct lattice-based schemes by using algebraic homomorphic MACs plus linear homomorphic encryption and homomorphic secret sharing. Concrete results: group-based constructions (DDH/RLWE variants) give rate 1 garbling — about 1 bit per gate plus lower-order terms — and fully succinct private garbling for many “simple” programs; layered circuits can slightly beat rate 1. Key tool: publish g^s and g^{s^2} to turn multiplicative label products into an authenticated share, converting multiplicative shares to additive ones; arbitrary-depth requires circular-power DDH. Practicality: neither as cheap as pure AES nor as slow as lattices, but plausibly useful.
AI-written summary · about
chapters (15)
- 0:00Succinct garbling via HSS
- 1:27Boolean to arithmetic circuits
- 3:14Garbling size optimization
- 5:24Garbled circuit extremes
- 7:37Design space exploration
- 9:50Efficiency vs security trade-offs
- 12:45Rate-1 garbled circuits
- 14:10Garbling and HSS connection
- 17:47HSS drawbacks with HMAC
- 20:17Algebraic homomorphic MACs
- 25:08aHMAC as authenticity shares
- 27:41Partial garbling with aHMAC
- 29:50Fully succinct garbling
- 31:13All circuits with HSS
- 33:48Summary and open questions
