Cryptology ePrint Archive: Report 2017/135

Hashing Garbled Circuits for Free

Xiong Fan and Chaya Ganesh and 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.

Category / Keywords: garbled circuits, hashing, secure computation, cut-and-choose

Original Publication (in the same form): IACR-EUROCRYPT-2017

Date: received 14 Feb 2017

Contact author: xfan at cs cornell edu, chaya ganesh@gmail com, kolesnikov@research bell-labs com

Available format(s): PDF | BibTeX Citation

Version: 20170216:220804 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]