Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. TCC 2009
Keywords
Two-Party ComputationYao Circuits
Contact author(s)
jbn @ cs au dk
orlandi @ cs au dk
History
2011-04-04: revised
2008-10-08: received
See all versions
Short URL
https://ia.cr/2008/427
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/427,
      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{https://eprint.iacr.org/2008/427}},
      url = {https://eprint.iacr.org/2008/427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.