FleXOR: Flexible garbling for XOR gates that beats free-XOR

Vladimir Kolesnikov, Payman Mohassel, Mike Rosulek
CRYPTO 2014 [pdf]

When garbling a circuit, suppose an XOR gate has input wire labels {$(A, A\oplus \Delta_A)$} and {$(B, B\oplus \Delta_B)$} and we would like the output wire to have labels {$(C, C\oplus \Delta_C)$} for some value {$C$}. The case of {$\Delta_A = \Delta_B = \Delta_C$} corresponds to free XOR, since we can simply set {$C = A \oplus B$}.

Flexible XOR (fleXOR) is an approach for garbling XOR gates that works with any {$\Delta_A, \Delta_B, \Delta_C$} values (these {$\Delta$} values are called offsets). Roughly speaking, the garbler chooses random labels {$A', B'$} and includes the following ciphertexts:

  1. encryption of {$A'$} under {$A$}
  2. encryption of {$A' \oplus \Delta_C$} under {$A \oplus \Delta_A$}
  3. encryption of {$B'$} under {$B$}
  4. encryption of {$B' \oplus \Delta_C$} under {$B \oplus \Delta_B$}

Hence, the evaluator can open up exactly one of ciphertexts 1/2, and one of ciphertexts 3/4. This effectively translates {$(A, A\oplus \Delta_A)$} labels to {$(A', A'\oplus \Delta_C)$}, and translates {$(B, B\oplus \Delta_B)$} labels to {$(B', B'\oplus \Delta_C)$}. Since the "translated" labels have the same desired offset {$\Delta_C$}, we can now do the free-XOR trick of setting {$C = A' \oplus B'$}.

Using garbled row-reduction, ciphertexts 1 & 3 can be removed (by choosing {$A'$} and {$C'$} implicitly and pseudorandomly). Further, if {$\Delta_A = \Delta_C$} then ciphertext 2 is not needed; if {$\Delta_B = \Delta_C$}, then ciphertext 4 is not needed. Overall, the fleXOR method results in a garbled gate consisting of {$|\{\Delta_A, \Delta_B, \Delta_C\}| - 1$} ciphertexts.

By choosing {$\Delta$} offsets for each wire in different ways, different properties can be achieved:

  • By setting {$\Delta$} to be the same for all wires, the construction collapses to standard Free-XOR
  • It is possible to set the {$\Delta$} values to avoid the circularity problem of Free-XOR, pointed out by CKKZ12. With appropriate choice of offsets, fleXOR can be instantiated under a weaker (related-key, non-circular) hardness assumption.
  • Free-XOR is compatible with 4-to-3 garbled row-reduction applied to non-XOR gates, but it is incompatible with the 4-to-2 variant described in PSSW09. Hence, with free-XOR the XOR gates cost nothing (in terms of garbled circuit size) while the AND gates cost 3 ciphertexts. With appropriate choice of offsets, fleXOR is compatible with 4-to-2 row reduction of its non-XOR gates. Hence, XOR gates cost 0, 1, or 2 ciphertexts, and non-XOR gates cost 2. For many circuits, this can lead to smaller overall size of garbled circuits than previous methods.