Free XOR

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

  • The garbler chooses a global uniformly random string with .

  • For any gate with input wires and output wire , the garbler chooses uniformly random labels and .

  • Let and denote the 0 label and 1 label for input wire , respectively. Similarly for wire .

  • Let and denote the 0 label and 1 label for input wire , respectively.

  • The garbler does not need to send garbled gate for each gate. The evaluator locally s the input labels of gate to gets the output label. This is correct because given a 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 .

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

  • Garbling gate is the same as before except that all the labels are of the form for uniformly random .