posted 25 Jan, 2021

Half Gates; Samee Zahur, Mike Rosulek, and David Evans

author	Samee Zahur, Mike Rosulek, and David Evans
title	Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates
howpublished	EuroCrypt 2015
year	2015
month	April
where	University of Virginia & Oregon State University

The goal of this paper is to reduce the amount of material that must be transmitted from the Generator to the Evaluator in Yao’s Garbled Circuits. It builds on a fair bit of pre existing work. As is often the case, the assumption is that only XOR and AND gates are used. (In other contexts NOT would also be included; they don’t mention Not here; probably it’s not important.)

Prior work:

• Point-and-permute: The wire labels (keys or whatever) include pointers to the rows they decrypt. Since the order/pointers are random, this doesn’t leak anything. This doesn’t save the Generator anything, but it saves the Evaluator some work (they don’t have to try decrypting rows they can’t decrypt). Also, one no-longer has to use encryption per se; you can use XOR(hash,_).
• Simple (“3”) row reduction: One of the possible output wire labels from each gate is just a hash of the input labels. That means when it’s XOR’d (per point-n-permute) you a priori get all-zeros, which you don’t need to transmit. (It’s not 100% clear why this can only get you a 1/4 reduction.)
• “2” row reduction: A “polynomial interpolation” somehow reduces another row; how is not explained here.
• Free XOR: By choosing the wire-labels as having a random, secret, common XOR factor that relates each truthy value to it’s corresponding falsey one, one gets homomorphic XOR without consuming any material. This is compatible with 3-RR for the AND gates, but it doesn’t work with 2-RR (because that has conflicting constraints on wire labels).
• FleXOR: A refinement of Free XOR that does work with 2-RR, at the cost of not always actually giving free XOR gates (depending on the context).

Half gates:

A half gate is just an AND gate for which one party (either, so long as we know who in advance) knows the plain-text of one of the inputs. If the knowing party is the Generator, then constructing the GC half-gate is just intelligently constructing a unary gate: either const or id. If the knowing party is the Evaluator, then the construction is more complicated. In both cases, simple row reduction works fine, so the unary gate requires only a single unit of material.

Whole gates:

The key identity involves introducing a new value r, with random secret value chosen by the Generator.

c = a AND b = a AND (FALSE XOR b) = a AND ((r XOR r) XOR b) = (a AND r) XOR (a AND (r XOR b))

Obviously the first half (a AND r) is a Generator half-gate. Since the Evaluator never learns r, it’s safe to share (r XOR b) with them; the Evaluator embeds the respective such values with the wire labels. Thus (a AND (r XOR b)) is an Evaluator half-gate. (In practice, the point-n-permute pointer does double-duty as (r XOR b).)

Since the combining XOR is free, that makes up a whole AND gate that consumes only two units of material and is consistent with free XOR.
This is a relatively big idea.