Paper 2025/1810

BitGC Made (More) Efficient

Hanlin Liu, Northwestern University

Kang Yang, State Key Laboratory of Cryptology

Wen-jie Lu, TikTok

Yu Yu, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute

Xiao Wang, Northwestern University

Chenkai Weng, Arizona State University

Abstract

Garbled circuits with one-bit-per-gate communication were recently introduced by Liu et al. (BitGC, Eurocrypt 2025), Meyer et al. (Crypto 2025), and Ishai et al. (Crypto 2025). However, these works focus primarily on the theoretical communication complexity, leaving open questions about practical computational efficiency. In this paper, we present a set of optimizations that substantially improve its practical efficiency. First, we eliminate key barriers to enable SIMD support for BitGC, leading to a substantial speedup in its homomorphic operations. Second, we demonstrate that XOR gates can be garbled without any communication, improving both efficiency and simplicity. Finally, we present a computationally efficient garbling scheme that requires zero communication for XOR gates and only 5 bits per AND gate. When applied to an AES-128 circuit, our fastest garbling scheme generates a garbled circuit of just 4 KB in 2 minutes on a single CPU core.

@misc{cryptoeprint:2025/1810,
      author = {Wenhao Zhang and Hanlin Liu and Kang Yang and Wen-jie Lu and Yu Yu and Xiao Wang and Chenkai Weng},
      title = {{BitGC} Made (More) Efficient},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1810},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1810}
}