On Garbled Circuits and Constant Round Secure Function Evaluation
Stephen R. Tate, Ke Xu · 2012
In this paper, we examine a form of garbled (or encrypted) circuit introduced by Beaver, Micali, and Rogaway as part of their design of a constant-round secure function evaluation (SFE) protocol [5]. We show that a subtle flaw in their construction allows even a simple passive adversary (also known as an "honest-but-curious adversary") to discover private data when evaluating such a garbled circuit. In particular, information leaks from the garbled circuit at places where multiple gates share a common input wire, and is extracted by exploiting dependencies between the gate labels of the multiple gates that share that input wire. In addition to showing how this flaw manifests itself and how it can be exploited, we pinpoint the errors in the corresponding security proof [19]. Finally, we introduce a new type of gate called a "splitter" which corrects the security flaw by removing all instances of shared input wires, and using this we can correct the problems in the proof as well, giving a secure garbled circuit. This corrected