1. We propose the notion of an interactive garbling scheme, where the garbled circuit is generated through an interactive protocol between the garbler and the evaluator. The garbled circuit is correct and privacy preserving even if one of the two parties was acting maliciously during garbling. The security notion is game based.
2. We show that an interactive garbling scheme combined with a Universally Composable (UC) secure oblivious transfer protocol can be used in a black-box manner to implement two-party computation (2PC) UC securely against any probabilistic polynomial time static and malicious adversary. The protocol abstracts many recent protocols for implementing 2PC from garbled circuits and will allow future designers of interactive garbling schemes to prove security with the simple game based definitions, as opposed to directly proving UC security for each new scheme.
3. We propose an instantiation of interactive garbling by designing a new protocol in the LEGO family of protocols for efficient garbling against a malicious adversary. The new protocol is based on several new technical contributions and optimizations, for example making it possible to get distinct output to both parties with minimal overhead. The scheme makes black-box usage of a XOR-homomorphic commitment scheme, an authentic, private and oblivious garbling scheme and a 2-correlation-robust and collision-resistant hash function. When comparing our resulting 2PC protocol to previous works in the same setting we see a noticeable reduction in the communication that directly depends on the size of the circuit (e.g. 33% for circuits larger than 501,271 AND gates).Category / Keywords: Secure Computation, XOR-Homomorphic Commitments, Garbled Circuits, Interactive Garbling Scheme, Oblivious Transfer, Universal Composability, Standard Assumptions, Large Circuits. Date: received 3 Apr 2015, last revised 3 May 2016 Contact author: roberto at cs au dk Available format(s): PDF | BibTeX Citation Note: Fixed many typos and recomputed all tables with k'=80. Also addressed an oversight in the protocol with regards to how to determine the real input of a malicious A. Version: 20160503:185024 (All versions of this report) Short URL: ia.cr/2015/309 Discussion forum: Show discussion | Start new discussion