Paper 2008/427

LEGO for Two Party Secure Computation

Jesper Buus Nielsen and Claudio Orlandi


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. TCC 2009
Two-Party ComputationYao Circuits
Contact author(s)
jbn @ cs au dk
orlandi @ cs au dk
2011-04-04: revised
2008-10-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jesper Buus Nielsen and Claudio Orlandi},
      title = {{LEGO} for Two Party Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2008/427},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.