Paper 2017/135
Hashing Garbled Circuits for Free
Xiong Fan, 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.
Note: Updated the paper to reflect recent result by Guo et al., which affects Free Hash.
Metadata
- Available format(s)
-
PDF
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2017
- Keywords
- garbled circuitshashingsecure computationcut-and-choose
- Contact author(s)
-
xfan @ cs cornell edu
chaya ganesh @ gmail com
vlad kolesnikov @ gmail com - History
- 2019-05-20: revised
- 2017-02-16: received
- See all versions
- Short URL
- https://ia.cr/2017/135
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/135,
author = {Xiong Fan and Chaya Ganesh and Vladimir Kolesnikov},
title = {Hashing Garbled Circuits for Free},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/135},
year = {2017},
url = {https://eprint.iacr.org/2017/135}
}