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

Mike Rosulek and Lawrence Roy

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

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Keywords
garbled circuits
Contact author(s)
rosulekm @ oregonstate edu
ldr709 @ gmail com
History
Short URL
https://ia.cr/2021/749

CC BY

BibTeX

@misc{cryptoeprint:2021/749,
author = {Mike Rosulek and Lawrence Roy},
title = {Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits},
howpublished = {Cryptology ePrint Archive, Paper 2021/749},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/749}},
url = {https://eprint.iacr.org/2021/749}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.