Hashing Garbled Circuits for Free

We show how to generate Garbled Circuit (GC) hash at no extra overhead during GC generation. This is in contrast with state-of-the-art approaches, which hash GCs at computational cost of about $6times$ 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 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 massaged) XOR of all the gate table rows of GC. We show that this is sufficient for GC-based SFE. 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 cost reduction by $36%$ in a typical setting, and up to factor $6$ in specialized applications relying on GC hashes.