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

TLDR

Classical garbled circuit constructions use four ciphertexts per gate, and prior optimizations for AND and XOR gates were incompatible, leading most implementations to use a three‑ciphertext scheme compatible with free‑XOR gates. This work shows how to garble AND gates with two ciphertexts and XOR gates with zero ciphertexts, yielding smaller circuits than any previous scheme. The construction splits each AND gate into two half‑gates, each garbled with a single ciphertext, enabling two ciphertexts per AND gate while remaining compatible with free‑XOR gates, at the cost of an extra cryptographic operation per gate for the evaluator. Experimental results demonstrate up to 25 % faster execution, 33 % less bandwidth, and 20 % lower energy consumption, and the scheme is optimal for a broad class of practical garbling techniques.

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.