Cryptology ePrint Archive: Report 2016/495

Cross&Clean: Amortized Garbled Circuits with Constant Overhead

Jesper Buus Nielsen and Claudio Orlandi

Abstract: Garbled circuits (GC) are one of the main tools for secure two-party computation. One of the most promising techniques for efficiently achieving active-security in the context of GCs is the so called \emph{cut-and-choose} approach, which in the last few years has received many refinements in terms of the number of garbled circuits which need to be constructed, exchanged and evaluated.

In this paper we ask a simple question, namely \emph{how many garbled circuits are needed to achieve active security?} and we propose a novel protocol which achieves active security while using only a constant number of garbled circuits per evaluation in the amortized setting.

Category / Keywords: cryptographic protocols / garbling schemes, two-party computation

Date: received 21 May 2016, last revised 20 Jan 2017

Contact author: jbn at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20170120:115853 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]