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