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
- garbled circuit $\hat{C}$, which contains 7 wires (in different colors above), each with two labels
- .$GI(a)$
- $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?