Difference between FleXOR and Free-XOR

Question

I would like to know the differences between FleXOR and Free-XOR. I searched in the web but I couldn’t understand the information I found. I understand that there are both cryptographic methods as well as optimizations for Yao's Garbled Circuits, but I don't practically understand their differences and which is to be preferred. What exactly is (or are) the difference(s) between FleXOR and Free-XOR?

Answer 1

I am an author on the FleXOR paper and can comment a bit. Let $A_0$ and $A_1$ are the false/true wire labels on some wire, and let $A_0 \oplus A_1$ denote the offset of that wire. The idea behind free-XOR is that when the 3 wires that touch an XOR gate have the same offset, then the XOR gate can be garbled for free. So you arrange for all wires in the circuit to have the same offset.

The idea behind fleXOR is to have not one global offset but several throughout the circuit. Again, whenever 3 wires touching an XOR gate have the same offset, you get that XOR gate for free. When only 2 wires touching the XOR gate have the same offset, you get that XOR gate for a cost of 1 ciphertext. So now we have made [some] XOR gates cost a little bit more. But it turns out by adding this flexibility you can make the AND gates cost less. In some cases it turns out to do better than free-XOR. (Another reason to favor fleXOR is because it can be instantiated in a way that requires a milder hardness assumption.)

I will point out that if the size of a garbled circuit is all you care about, then fleXOR has been made obsolete by the half-gates construction:

Samee Zahur, Mike Rosulek, David Evans: Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates. EUROCRYPT (2) 2015: 220-250

As for implementations, free-XOR is implemented probably in every GC library out there (JustGarble, etc). I'm not sure about implementations of fleXOR, its moment of fame was short-lived before it was superseded by half-gates. For the paper we implemented the circuit-analysis steps so that we could determine the concrete garbled circuit size, but we didn't implement the actual garbling/evaluation algorithms. Yehuda Lindell hangs around here; he has a recent paper with some followup work on the fleXOR techniques, which may have involved an implementation (I don't remember off the top of my head).

For more details about the differences between various garbled circuit constructions, you can check out a survey talk I gave about the topic: video, slides.