Improved Garbled Circuit: Free XOR Gates and Applications
The authors present a new garbled circuit construction for two-party Secure Function Evaluation (SFE). In their one-round protocol, XOR gates are evaluated \"For free\", which results in the corresponding improvement over the best garbled circuit implementations (e.g. Fairplay). They build permutation networks and Universal Circuits (UC) almost exclusively of XOR gates; this results in a factor of up to 4 improvement (in both computation and communication) of their SFE. They also improve integer addition and equality testing by factor of up to 2. They rely on the Random Oracle (RO) assumption. Their constructions are proven secure in the semi-honest model.