###
Two Halves Make a Whole

Reducing Data Transfer in Garbled Circuits using Half Gates

Samee Zahur, Mike Rosulek, and David Evans

Eurocrypt
2015

*34*^{th} Conference on the Theory and Applications of Cryptographic Techniques

Sofia, Bulgaria

26-30 April 2015
**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 and Schneider, ICALP 2008) were
incompatible, so most implementations used the best known method
compatible with free-XOR gates (three ciphertexts; Kolesnikov and
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 show that our construction is optimal
for a large class of garbling schemes encompassing all known practical
garbling techniques.

### Code

The source code for our half gates implementation and the benchmarks
used in this paper is available under an open source license at

*http://github.com/samee/obliv-c*.

### Paper

[

PDF], 28 pages