Garbled Circuits Optimization #2: Garbled Row Reduction (GRR3)
One needs to know which gate’s ciphertext must be decrypted during computation in Garbled Circuits , but does not allow him to deduce the truth value of any input or output. The oldest and most secure method is Point and Permute (P&P), which was proposed by Beaver et al. [1].
Besides the point-and-permute optimization that allows more efficient evaluation of gates, there are other important optimizations that are now standard in garbled circuit construction. These include free XOR (and fexibleXOR), row reduction, and cut-and-choose. This article will focus on row reduction. Naor et al.[2] proposed Garbled Row Reduction 3 Ciphertexts (GRR3) in 1999.
This optimization reduces the size of garbled tables from 4 rows to 3 rows. Here, instead of generating a label for the output wire of a gate randomly, Alice（garbler）generates it using a function of the input labels. She generates the output labels such that the first entry of the garbled table becomes all 0 and no longer needs to be sent, Its details are as follows:
The number of entries at each garbled gate is reduced by replacing the first entry with the all zero (0 ) string
1: Chooses the first output masked value in label order, which produces a ciphertext with all 0 bits
i.e. decrypts all 0s at the end, C1←EA0, B1−1(0n)
2: The resulting masked value is still pseudo-random. Since there is no need to send the first ciphertext, it is sufficient to send 3 ciphertexts per gate.
3: Although the Garbled circuit produced by GRR3 is smaller than that produced by P&P, it has a small impact on the amount of computation, because the less encryption is replaced by the decryption of the first ciphertext.
4: The optimization comparison between each methods:
References:
1: Beaver, Donald; Micali, Silvio; Rogaway, Phillip (1990). The round complexity of secure protocols. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing. pp. 503–513.
2: Naor, Moni; Pinkas, Benny; Sumner, Reuban (1999). Privacy preserving auctions and mechanism design. Proceedings of the 1st ACM Conference on Electronic Commerce. pp. 129–139.
