Irving Street Functionality

This is supposed to be a blog.

recent posts
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:

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.