Welcome to the resource topic for 2021/749
Title:
Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits
Authors: Mike Rosulek, 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.
ePrint: https://eprint.iacr.org/2021/749
Talk: https://www.youtube.com/watch?v=9FZb7LLyN6A
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .