Improved garbled circuit: free XOR gates and applications

Improved garbled circuit: free XOR gates and applications

Vladimir Kolesnikov, Thomas Schneider
ICALP 2008 [pdf] [bibtex]

The garbler arranges for all wire labels to be of the form ⚠ {$(A, A \oplus R)$}, for a random secret ⚠ {$R$}. Then if two wires entering an XOR gate have wire labels ⚠ {$(A, A\oplus R)$} and ⚠ {$(B, B\oplus R)$}, the garbler arranges the labels of the outgoing wire to be ⚠ {$(A\oplus B, A \oplus B \oplus R)$}. Then the evaluator can compute the correct output wire label of this gate by simply XOR-ing the wire labels. Nothing needs to be included in the garbled circuit for XOR gates, while the garbler and evaluator need only perform XOR operations rather than cryptographic operations for these gates.

The gate-level cipher suggested is ⚠ {$ H(K_1 \| K_2 \| T) \oplus M $}, which is proven secure when ⚠ {$H$} is modeled as a random oracle. In the standard model, ⚠ {$H$} is required to be circular correlation-robust (CKKZ12).

When using the free-XOR technique, the non-XOR gates in the circuit can be reduced to 3 ciphertexts using garbled row-reduction (PSSW09), but not down to 2 ciphertexts. Free-XOR is also compatible with the point-and-permute optimization. In that case, assuming the least significant bit of a wire label specifies its select bit, we must have the least significant bit of ⚠ {$R$} be 1 (so that pairs of wire labels have opposite select bits).

Other links:

ICALP presentation slides (PDF)

See also:

CKKZ12 A12?

Categories:

Garbling