Paper 2025/1810
BitGC Made (More) Efficient
, Northwestern University, Northwestern University, State Key Laboratory of Cryptology, TikTok, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute, Northwestern University, Arizona State UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2026
- Keywords
- Garbled CircuitSecure Multi-Party Computation
- Contact author(s)
-
wenhao zhang @ northwestern edu
hanlin liu @ northwestern edu
yangk @ sklc org
fionser @ gmail com
yuyu @ yuyu hk
wangxiao1254 @ gmail com
Chenkai Weng @ asu edu - History
- 2026-05-19: last of 2 revisions
- 2025-10-02: received
- See all versions
- Short URL
- https://ia.cr/2025/1810
- License
-
CC BY
BibTeX
@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}
}
