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.