Reducing Garbled Circuit Size While Preserving Circuit Gate Privacy

This paper investigates efficient and confidential circuit garbling techniques. The primary contribution of this research is the introduction of GPGRR2 (Gate Privacy preserving Garbled Row Reduction), a technique aimed at constructing garbled circuits using at most two ciphertexts per garbled gate while ensuring gate privacy preservation. When compared to the state-of-the-art gate-privacy-preserving garbling scheme GRR3, GPGRR2 shows a remarkable reduction in the size of garbled circuits by at least 33%. Another significant achievement is the development of a linear garbling scheme for odd gates, enabling the garbling of a single gate to one ciphertext. Furthermore, leveraging the GPGRR2 scheme facilitates a substantial decrease in the number of ciphertexts in non-universal-circuit based PFE protocols by a factor of 25%.