Welcome to the resource topic for 2017/135
Title:
Hashing Garbled Circuits for Free
Authors: Xiong Fan, Chaya Ganesh, Vladimir Kolesnikov
Abstract:We introduce {\em Free Hash}, a new approach to generating Garbled Circuit (GC) hash at no extra cost during GC generation. This is in contrast with state-of-the-art approaches, which hash GCs at computational cost of up to 6\times of GC generation. GC hashing is at the core of the cut-and-choose technique of GC-based secure function evaluation (SFE). Our main idea is to intertwine hash generation/verification with GC generation and evaluation. While we {\em allow} an adversary to generate a GC \widehat{\GC} whose hash collides with an honestly generated \GC, such a \widehat{\GC} w.h.p. will fail evaluation and cheating will be discovered. Our GC hash is simply a (slightly modified) XOR of all the gate table rows of GC. It is compatible with Free XOR and half-gates garbling, and can be made to work with many cut-and-choose SFE protocols. With today’s network speeds being not far behind hardware-assisted fixed-key garbling throughput, eliminating the GC hashing cost will significantly improve SFE performance. Our estimates show substantial cost reduction in typical settings, and up to factor 6 in specialized applications relying on GC hashes. We implemented GC hashing algorithm and report on its performance.
ePrint: https://eprint.iacr.org/2017/135
Talk: https://www.youtube.com/watch?v=G5ePO6F7tX0
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 .