Garbled Circuits with 1 Bit per Gate

Hanlin Liu; Xiao Wang; Kang Yang; Yu Yu

Paper 2024/1988

Garbled Circuits with 1 Bit per Gate

Hanlin Liu

, Northwestern University

Xiao Wang

, Northwestern University

Kang Yang

, State Key Laboratory of Cryptology

Yu Yu

, Shanghai Jiao Tong University

Abstract

We present 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.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: Secure multiparty computation
Contact author(s): hanlin liu @ northwestern edu
wangxiao @ northwestern edu
yangk @ sklc org
yuyu @ yuyu hk
History: 2024-12-12: approved; 2024-12-09: received; See all versions
Short URL: https://ia.cr/2024/1988
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1988,
      author = {Hanlin Liu and Xiao Wang and Kang Yang and Yu Yu},
      title = {Garbled Circuits with 1 Bit per Gate},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1988},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1988}
}