You are looking at a specific version 20170216:220804 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
garbled circuitshashingsecure computationcut-and-choose
Contact author(s)
xfan @ cs cornell edu
chaya ganesh @ gmail com
kolesnikov @ research bell-labs com
History
2019-05-20: revised
2017-02-16: received
See all versions
Short URL
https://ia.cr/2017/135
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.