## 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:

- encryption of
`⚠ {$A'$}`

under`⚠ {$A$}`

- encryption of
`⚠ {$A' \oplus \Delta_C$}`

under`⚠ {$A \oplus \Delta_A$}`

- encryption of
`⚠ {$B'$}`

under`⚠ {$B$}`

- 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:

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories