(Authenticated) BitGC for (Active) Rate-One 2PC

This talk introduces BitGC, a computationally efficient rate-one garbling scheme based on ring-RLWE with key-dependent message security. The garbling consists of a SWHE-encrypted seed and one-bit per gate stitching information. The computation requires homomorphically expanding the seed using a low-depth PRG and then two additional levels of multiplication to assemble the garbled tables. As a result, it does not require bootstrapping operations needed for FHE.

Second, I will describe a rate-one constant-round active two-party computation protocol by authenticating BitGC. We show efficient ways to distributively garble BitGC and to authenticate its correctness. In practice, the total cost in addition to BitGC is sublinear for layered circuits and one bit per gate for generic circuits.

Finally, I will discuss some ongoing efforts and remarks on their concrete efficiency.

BitGC will appear in Eurocrypt 2025, available at https://eprint.iacr.org/2024/1988. Authenticated BitGC is available at https://eprint.iacr.org/2025/232. Both results are joint work with Hanlin Liu, Kang Yang, and Yu Yu.