Cryptology ePrint Archive: Report 2015/309

TinyLEGO: An Interactive Garbling Scheme for Maliciously Secure Two-Party Computation

Tore Kasper Frederiksen and Thomas P. Jakobsen and Jesper Buus Nielsen and Roberto Trifiletti

Abstract: This paper reports on a number of conceptual and technical contributions to the currently very lively field of two-party computation (2PC) based on garbled circuits. Our main contributions are as follows:

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]