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

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.

Categories:

Garbling