Boolean Garbling with 1-Bit per Gate from HSS Techniques
Hanjun Li
Abstract:
A garbling scheme transforms a program (e.g., circuit) C into a garbled program \hat{C}, along with a pair of short keys (k_{i,0},k_{i,1}) for each input bit x_i, such that the program, garbled program and input keys (C,\hat{C}, {k_{i,x_i}}) can be used to recover the output z = C(x) while revealing nothing else about the input x.
A main objective in the research of garbling schemes is reducing the size of the garbled program \hat{C}. On the one hand, theoretical schemes using the heavy tools of attribute-based encryption (ABE) and fully homomorphic encryption (FHE) can achieve constant size, independent of |C|. On the other hand, practically oriented schemes using only symmetric key crypto all have sizes Omega(lambda * |C|). We explore the space in-between by presenting a scheme with garbling size |C|, using relatively lightweight tools such as homomorphic secret sharing (HSS).
In this talk, I'll first review a recent work [MORS24] that brought HSS techniques to the context of garbling, obtaining rate-1 arithmetic garbling for bounded integers. I will then present a succinct partial garbling scheme using HSS techniques, where partial garbling is a relaxation of standard garbling introduced by [IW14] that guarantees privacy for only part of the inputs. Finally, building onto the succinct partial garbling technique, I'll present our new Boolean garbling scheme costing 1-bit per gate. We rely on a new circular Power-DDH assumption in Paillier groups, or an analogous circular Power-RLWE assumption. A recent independent work by [LWYY25] obtains a scheme with the same size, 1-bit per gate, while relying on the heavier tool of FHE (and assuming KDM-security).
The talk is based on joint work with Yuval Ishai and Huijia Lin.
Bio:
Hanjun Li is a fifth year PhD student at University of Washington, advised by Huijia Lin and Stefano Tessaro. His research interests lie in the area of secure multi-party computation (MPC).