TY - GEN
T1 - BitGC Made (More) Efficient
AU - Zhang, Wenhao
AU - Liu, Hanlin
AU - Yang, Kang
AU - Lu, Wen Jie
AU - Yu, Yu
AU - Wang, Xiao
AU - Weng, Chenkai
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2026.
PY - 2026
Y1 - 2026
N2 - 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 to 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 3 min on a single CPU core.
AB - 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 to 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 3 min on a single CPU core.
UR - https://www.scopus.com/pages/publications/105039606073
U2 - 10.1007/978-3-032-25324-8_8
DO - 10.1007/978-3-032-25324-8_8
M3 - 会议稿件
AN - SCOPUS:105039606073
SN - 9783032253231
T3 - Lecture Notes in Computer Science
SP - 214
EP - 245
BT - Advances in Cryptology – EUROCRYPT 2026 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Daemen, Joan
A2 - Thomé, Emmanuel
PB - Springer Science and Business Media Deutschland GmbH
T2 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2026
Y2 - 10 May 2026 through 14 May 2026
ER -