Free XOR

The Free-XOR optimization significantly improves the efficiency of garbled circuit. The garbler and evaluator could handle $\mathsf{XOR}$ gates for free! The method is given in KS08.

• The garbler chooses a global uniformly random string $\Delta$ with $\mathsf{LSB}(\Delta )=1$.

• For any $\mathsf{XOR}$ gate with input wires $a,b$ and output wire $c$, the garbler chooses uniformly random labels $X_a$ and $X_b$.

• Let $X_a$ and $X_a\oplus \Delta$ denote the 0 label and 1 label for input wire $a$, respectively. Similarly for wire $b$.

• Let $X_a\oplus X_b$ and $X_a\oplus X_b\oplus \Delta$ denote the 0 label and 1 label for input wire $c$, respectively.

• The garbler does not need to send garbled gate for each $\mathsf{XOR}$ gate. The evaluator locally $\mathsf{XOR}$s the input labels of $\mathsf{XOR}$ gate to gets the output label. This is correct because given a $\mathsf{XOR}$ gate, the label table could be as follows.

Here are some remarks of the Free-XOR optimization.

• Free XOR is compatible with the point-and-permute optimization because $\mathsf{LSB}(\Delta )=1$.

• The garbler should keep $\Delta$ private all the time for security reasons.

• Garbling $\mathsf{AND}$ gate is the same as before except that all the labels are of the form $(X,X\oplus \Delta )$ for uniformly random $X$.