Cryptology ePrint Archive: Report 2014/756

Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates

Samee Zahur and Mike Rosulek and David Evans

Abstract: The well-known classical constructions of garbled circuits use four ciphertexts per gate, although various methods have been proposed to reduce this cost. The best previously known methods for optimizing AND gates (two ciphertexts; Pinkas et al., ASIACRYPT 2009) and XOR gates (zero ciphertexts; Kolesnikov & Schneider, ICALP 2008) were incompatible, so most implementations used the best known method compatible with free-XOR gates (three ciphertexts; Kolesnikov & Schneider, ICALP 2008). In this work we show how to simultaneously garble AND gates using two ciphertexts and XOR gates using zero ciphertexts, resulting in smaller garbled circuits than any prior scheme. The main idea behind our construction is to break an AND gate into two half-gates --- AND gates for which one party knows one input. Each half-gate can be garbled with a single ciphertext, so our construction uses two ciphertexts for each AND gate while being compatible with free-XOR gates. The price for the reduction in size is that the evaluator must perform two cryptographic operations per AND gate, rather than one as in previous schemes. We experimentally demonstrate that our garbling scheme leads to an overall decrease in time (up to 25%), bandwidth (up to 33%), and energy use (up to 20%) over several benchmark applications. We also initiate a study of lower bounds for garbled gate size, and show that our construction is optimal for a large class of garbling schemes encompassing all known practical garbling techniques.

Category / Keywords: cryptographic protocols /

Date: received 28 Sep 2014, last revised 17 Mar 2015

Contact author: samee at virginia edu

Available format(s): PDF | BibTeX Citation

Version: 20150317:143453 (All versions of this report)

Short URL: ia.cr/2014/756

Discussion forum: Show discussion | Start new discussion