Garbled Circuits with 1 Bit per Gate

Hanlin Liu, Xiao Wang, Kang Yang, Yu Yu

TL;DR

This paper introduces BitGC, a novel garbled circuit (GC) scheme that achieves a groundbreaking 1 bit of communication per gate. This is accomplished by leveraging a specialized somewhat homomorphic encryption (SWHE) scheme with distributed decryption, significantly reducing communication overhead compared to existing GC techniques.

What Problem Does This Paper Address?

Garbled circuits (GCs) are a fundamental cryptographic primitive for secure two-party computation (2PC), enabling parties to jointly compute a function on their private inputs without revealing those inputs. A key challenge in GC research has been optimizing the communication complexity, especially for large circuits. Traditional GC schemes require communication proportional to the circuit size (O(|C|)), while more advanced techniques offer sublinear communication but often rely on computationally heavy primitives or have poor concrete efficiency. This creates a significant gap between practical and theoretical solutions. BitGC aims to bridge this gap by offering a concretely efficient GC scheme with minimal communication per gate.

Methods

BitGC builds upon the concept of garbled circuits but introduces two key innovations:

  • Homomorphically Encrypted Seed and Pseudo-Random Generator (PRG): Instead of garbling each bit individually, BitGC uses a homomorphically encrypted seed. This seed is then expanded into many pseudo-random bits using a low-depth PRG, which is evaluated homomorphically. This significantly reduces the amount of data that needs to be transmitted.
  • 1-Bit "Stitching Information": For each gate, only a single bit of "stitching information" is transmitted. This bit, combined with the homomorphically evaluated PRG outputs, allows the evaluator to reconstruct the garbled table for that gate. This is the core mechanism that achieves the 1-bit-per-gate communication.

The underlying cryptographic primitive is a Somewhat Homomorphic Encryption (SWHE) scheme with distributed decryption. This specialized SWHE scheme allows for homomorphic computations on ciphertexts and has a unique decryption property that enables distributed decryption, which is crucial for the BitGC scheme. The paper presents instantiations of this SWHE scheme based on the Ring Learning With Errors (RLWE) and NTRU assumptions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of "Stitching Information": The insight that a single bit of information per gate can be sufficient to "stitch" together homomorphically generated random bits into a functional garbled table is a major breakthrough. This elegantly decouples the generation of randomness from the garbled table construction.
  • SWHE with Distributed Decryption as a Building Block: The paper highlights how a specific type of SWHE, with distributed decryption properties, is perfectly suited for this task. This type of encryption allows for homomorphic evaluation of the PRG and enables the efficient reconstruction of garbled tables.
  • Bridging the Practicality Gap: BitGC demonstrates that it's possible to achieve sublinear communication (specifically, 1 bit per gate) without resorting to overly complex or computationally expensive cryptographic primitives like fully homomorphic encryption or multilinear maps.

Key Results

  • 1 Bit of Communication Per Gate: The primary result is the BitGC scheme, which achieves a communication complexity of just 1 bit per gate. This is a significant improvement over previous GC schemes.
  • Efficiency: The scheme requires only O(1) homomorphic addition/multiplication operations per gate for both garbling and evaluation, without the need for bootstrapping.
  • Security: The scheme is proven secure in the simulation-based model, relying on the hardness of RLWE or NTRU assumptions and key-dependent message (KDM) security for the underlying SWHE scheme.
  • Concrete Efficiency: The paper emphasizes the concrete efficiency of BitGC, aiming to provide practical advantages over existing solutions.

Limitations and Future Work

  • KDM Security Requirement: The security of the scheme relies on the KDM security of the underlying SWHE scheme, which is a strong assumption.
  • Authenticity Extension: The paper discusses how to extend the scheme to support authenticity, which is crucial for applications like zero-knowledge proofs, but this extension requires additional modifications and a hash function.
  • Future Work: The authors suggest exploring further optimizations and applications of their scheme, particularly in the context of actively secure 2PC. The paper also mentions that their protocol can be strengthened against malicious security with a small additional cost.

Summary updated

BibTeX
@article{liu2024garbled,
  author = {Hanlin Liu and Xiao Wang and Kang Yang and Yu Yu},
  title = {{Garbled Circuits with 1 Bit per Gate}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
}
Figure