BitGC: Garbled Circuits with 1 Bit per Gate

Hanlin Liu; Xiao Wang; Kang Yang; Yu Yu

doi:10.1007/978-3-031-91098-2_16

BitGC: Garbled Circuits with 1 Bit per Gate

Hanlin Liu
, Xiao Wang^*
, Kang Yang^*
, Yu Yu^*

^*Corresponding author for this work

Northwestern University
State Key Laboratory of Cryptology
Shanghai Jiao Tong University
Shanghai Qi Zhi Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

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.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Serge Fehr, Pierre-Alain Fouque
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	437-466
Number of pages	30
ISBN (Print)	9783031910975
DOIs	https://doi.org/10.1007/978-3-031-91098-2_16
State	Published - 2025
Externally published	Yes
Event	44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 - Madrid, Spain Duration: 4 May 2025 → 8 May 2025

Publication series

Name	Lecture Notes in Computer Science
Volume	15607 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
Country/Territory	Spain
City	Madrid
Period	4/05/25 → 8/05/25

Access to Document

10.1007/978-3-031-91098-2_16

Cite this

Liu, H., Wang, X., Yang, K., & Yu, Y. (2025). BitGC: Garbled Circuits with 1 Bit per Gate. In S. Fehr, & P.-A. Fouque (Eds.), Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 437-466). (Lecture Notes in Computer Science; Vol. 15607 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-91098-2_16

Liu, Hanlin ; Wang, Xiao ; Yang, Kang et al. / BitGC : Garbled Circuits with 1 Bit per Gate. Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Serge Fehr ; Pierre-Alain Fouque. Springer Science and Business Media Deutschland GmbH, 2025. pp. 437-466 (Lecture Notes in Computer Science).

@inproceedings{6407da8d8d4044759676019cfab71553,

title = "BitGC: Garbled Circuits with 1 Bit per Gate",

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.",

author = "Hanlin Liu and Xiao Wang and Kang Yang and Yu Yu",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2025.; 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 ; Conference date: 04-05-2025 Through 08-05-2025",

year = "2025",

doi = "10.1007/978-3-031-91098-2\_16",

language = "英语",

isbn = "9783031910975",

series = "Lecture Notes in Computer Science",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "437--466",

editor = "Serge Fehr and Pierre-Alain Fouque",

booktitle = "Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "德国",

}

Liu, H, Wang, X, Yang, K & Yu, Y 2025, BitGC: Garbled Circuits with 1 Bit per Gate. in S Fehr & P-A Fouque (eds), Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science, vol. 15607 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 437-466, 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025, Madrid, Spain, 4/05/25. https://doi.org/10.1007/978-3-031-91098-2_16

BitGC: Garbled Circuits with 1 Bit per Gate. / Liu, Hanlin; Wang, Xiao; Yang, Kang et al.
Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Serge Fehr; Pierre-Alain Fouque. Springer Science and Business Media Deutschland GmbH, 2025. p. 437-466 (Lecture Notes in Computer Science; Vol. 15607 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - BitGC

T2 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025

AU - Liu, Hanlin

AU - Wang, Xiao

AU - Yang, Kang

AU - Yu, Yu

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/105004788985

U2 - 10.1007/978-3-031-91098-2_16

DO - 10.1007/978-3-031-91098-2_16

M3 - 会议稿件

AN - SCOPUS:105004788985

SN - 9783031910975

T3 - Lecture Notes in Computer Science

SP - 437

EP - 466

BT - Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Fehr, Serge

A2 - Fouque, Pierre-Alain

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 4 May 2025 through 8 May 2025

ER -

Liu H, Wang X, Yang K, Yu Y. BitGC: Garbled Circuits with 1 Bit per Gate. In Fehr S, Fouque PA, editors, Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 437-466. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-91098-2_16