Why XOR and NOT is free in garbled circuit

Question

I am having trouble understanding the term "free" in V.Kolesnikov et al's paper.

1. Why NOT is free

In page 4, section 3.1, they said that NOT gate is free

by simply eliminating them and inverting the correspondence of the wires’ values and garbling

I came up with the following example, which confused me

Let's say that $a,b$ are two single digit inputs from Alice and Bob, respectively. Suppose Alice is the garbler, she garbles the above circuit and sends to Bob, along with her garbled input $GI(a)$. She then sends Bob's garbled input $GI(b)$ to Bob through obvlivious transfer. In this example, without trying to implement NOT "for free", Alice only has to send

1. garbled circuit $\hat{C}$, which contains 7 wires (in different colors above), each with two labels
2. .$GI(a)$
3. $GI(b)$, and Bob can figure out the result.

Following the first step "simply eliminating them", I remove all the NOT gates and get the following circuit

Now, AND1 and OR1 shares the same input from $b$. No matter how I invert the wire's value, the circuit will not represent the same function as before.

It seems now I have to separate the inputs for AND1 and OR1, and then give them different labels, although they came from a single source in the original circuit. Then the circuit would still have 6 wires, which isn't quite "free". If it was free, shouldn't we be able only to use 5 wires to construct the ciruit?

2. Why XOR is free In the same page, they showed their XOR gate $G$.

I see that by doing this the garbler won't have to generate random labels for $w_i^1$ and $w_c^0$. But why is it called free?

In addition, what's the computational saving between generating random labels for all wires and generating only $w_a^0,w_b^0,R$ then computing other labels from the three?

Answer 1

Regarding the NOT gates in your example. Suppose the wire called $b$ has wire labels $B$ for false and $B \oplus R$ for true. Then you would garble gate "AND1" using these labels as normal, and you would garble gate "OR1" imagining that $B \oplus R$ means false and $B$ means true.

There are two equivalent ways to think about this. One is to consider the output of the NOT gate to be a separate wire (separate from the input to the NOT gate). If the NOT gate input wire has labels $A, A\oplus R$ then the output wire has labels $A \oplus R, A$.

The other way to think about it is to absorb all NOT gates into their neighboring AND/OR gates. In your example we could garble a NAND for gate AND1 and we could garble a gate $(x,y) \mapsto (\lnot x \lor y)$ for OR1. The way to actually do this is the same as above, just let the garbler switch the "meaning" of the two wire labels, locally for this gate.

Regarding free XOR: the main cost that it saves is not in generating random wire labels for output wires. (In fact, advanced GC constructions do not sample wire labels at random except at the inputs.) The savings are: (1) neither garbler nor evaluator have to evaluate a cryptographic primitive to process this gate. Instead they just make one xor computation. (2) Nothing must be included in the garbled circuit, saving bandwidth. So XOR gates are free for communication cost, and are "free" in computational cost of crypto operations (as you point out, not "free" of all computational cost since some minor xor computation is required).