- Computer verification of SMPC protocols by any means necessary
- OWL: Compositional Verification of Security Protocols via an Information-Flow Type System; 2023
- Fuzzy Message Detection; 2021
- PL Theory for SMPC Implementations
- Metadata-privacy preserving Instant Messaging
- Experiment Selection for Causal Discovery; 2013
- Casual security suggestions for friends
- Field Study of Smartphone (Un) Locking Behavior and Risk Perception
- Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis
- Iconography for key-fingerprint comparison

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.)

- 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).

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.

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.