International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

BitGC: Garbled Circuits with 1 Bit per Gate

Authors:
Hanlin Liu , Northwestern University
Xiao Wang , Northwestern University
Kang Yang , State Key Laboratory of Cryptology
Yu Yu , Shanghai Jiao Tong University, Shanghai Qi Zhi Institute
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2025
Abstract: We present BitGC, a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of 1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and 2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.
BibTeX
@inproceedings{eurocrypt-2025-35218,
  title={BitGC: Garbled Circuits with 1 Bit per Gate},
  publisher={Springer-Verlag},
  author={Hanlin Liu and Xiao Wang and Kang Yang and Yu Yu},
  year=2025
}