Garbled row reduction

A method for reducing the size of a garbled truth table in constructions of garbled circuits. The basic concept was first introduced by Philip Rogaway. Consider the "first" ciphertext ⚠ {$\mathsf{Enc}_{A,B}(C)$} of a garbled gate, where ⚠ {$A,B$} are wire labels of input wires and ⚠ {$C$} is a wire label of the output wire. In a "textbook" garbled circuit, ⚠ {$C$} is chosen randomly. Garbled row reduction suggests to choose ⚠ {$C$} indirectly as the value that causes ⚠ {$\mathsf{Enc}_{A,B}(C) = 0^k$} (this can be made possible when using the point and permute optimization, where the ⚠ {$\mathsf{Enc}$} can be a simple cipher rather than a full-fledge encryption scheme). As such, the first ciphertext does not need to be sent (it will always be the all-zeroes string), reducing the size of the garbled gate by 25%. A more sophisticated technique that reduces the size by 50% was described in PSSW09.