Row Reduction

With the Free-XOR optimization, the bottleneck of garbled circuit is to handle $\mathsf{AND}$ gates. Row reduction aims to reduce the number of ciphertexts of each garbled $\mathsf{AND}$ gate. More specifically, it reduces $4$ ciphertexts into $3$. The optimization is given in the NPS99 paper.

To be compatible with the Free-XOR optimization, the garbled $\mathsf{AND}$ gates are of the following form (still use the example in the point-and-permute optimization).

Since $\mathsf{H}$ is modeled as a random oracle, one could set the first row of the above garbled gate as $0$, and then we could remove that row from the garbled gate. This means that we could choose $X_c=\mathsf{H}(X_a,X_b\oplus \Delta )$. Therefore, the garbled circuit is changed as follows.

The evaluator handles garbled $\mathsf{AND}$ gates as before, except he/she directly computes the hash function if the color bits are $(0,0)$