International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits

Authors:
Mike Rosulek , Oregon State University
Lawrence Roy , Oregon State University
Download:
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: We describe a garbling scheme for boolean circuits, in which XOR gates are free and AND gates require communication of $1.5\kappa + 5$ bits. This improves over the state-of-the-art ``half-gates'' scheme of Zahur, Rosulek, and Evans (Eurocrypt 2015), in which XOR gates are free and AND gates cost $2\kappa$ bits. The half-gates paper proved a lower bound of $2\kappa$ bits per AND gate, in a model that captured all known garbling techniques at the time. We bypass this lower bound with a novel technique that we call \textbf{slicing and dicing}, which involves slicing wire labels in half and operating separately on those halves. Ours is the first to bypass the lower bound while being fully compatible with free-XOR, making it a drop-in replacement for half-gates. Our construction is proven secure from a similar assumption to prior free-XOR garbling (circular correlation-robust hash), and uses only slightly more computation than half-gates.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31234,
  title={Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits},
  publisher={Springer-Verlag},
  author={Mike Rosulek and Lawrence Roy},
  year=2021
}