Cryptology ePrint Archive: Report 2008/427
LEGO for Two Party Secure Computation
Jesper Buus Nielsen and Claudio Orlandi
Abstract: The first and still most popular solution for secure two-party
computation relies on Yao's garbled circuits. Unfortunately, Yao's
construction provide security only against passive adversaries.
Several constructions (zero-knowledge compiler, cut-and-choose) are
known in order to provide security against active adversaries, but
most of them are not efficient enough to be considered practical. In
this paper we propose a new approach called LEGO (Large Efficient
Garbled-circuit Optimization) for two-party computation, which allows
to construct more efficient protocols secure against active
adversaries. The basic idea is the following: Alice constructs and
provides Bob a set of garbled NAND gates. A fraction of them is
checked by Alice giving Bob the randomness used to construct
them. When the check goes through, with overwhelming probability there
are very few bad gates among the non-checked gates. These gates Bob
permutes and connects to a Yao circuit, according to a fault-tolerant
circuit design which computes the desired function even in the
presence of a few random faulty gates. Finally he evaluates this Yao
circuit in the usual way.
For large circuits, our protocol offers better performance than any
other existing protocol.
The protocol is universally composable (UC) in the OT-hybrid model.
Category / Keywords: cryptographic protocols / Two-Party Computation, Yao Circuits
Publication Info: TCC 2009
Date: received 3 Oct 2008, last revised 4 Apr 2011
Contact author: jbn at cs au dk, orlandi@cs au dk
Available format(s): PDF | BibTeX Citation
Version: 20110404:111035 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]