1. We propose the notion of an \emph{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.
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 27 Aug 2015 Contact author: roberto at cs au dk Available format(s): PDF | BibTeX Citation Note: Large rewrite of original paper. Changes include, but are not limited to: - Now uses a xor-homomorphic commitment scheme and "gate" garbling scheme black-box. - Allows for both parties to learn distinct output. This had a huge impact on the security definitions of an interactive garbling scheme. - Lots of typo fixes and updated performance calculations. Version: 20150827:131458 (All versions of this report) Short URL: ia.cr/2015/309 Discussion forum: Show discussion | Start new discussion