Paper 2014/667

Cut-and-Choose Based Two-Party Computation in the Online/Offline and Batch Settings

Yehuda Lindell and Ben Riva

Abstract

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao's garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, $s$ garbled circuits are used in order to obtain a maximum cheating probability of $2^{-s}$. In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to ${\cal O}\(\frac{s}{\log N}\)$ garbled circuits when $N$ secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-and-choose method on garbled circuits can be used in an online/offline setting in order to obtain a very fast online phase with very few exponentiations, and we apply our amortization method to this setting as well. Our online/offline protocols are competitive with the TinyOT and SPDZ protocols due to the minimal interaction in the online phase (previous protocols require only information-theoretic operations in the online phase and are therefore very efficient; however, they also require many rounds of communication which increases latency). Although ${\cal O}(\frac{s}{\log N})$ may seem to be a mild efficiency improvement asymptotically, it is a \emph{dramatic improvement} for concrete parameters since $s$ is a statistical security parameter and so is typically small. Specifically, instead of $40$ circuits to obtain an error of $2^{-40}$, when running $2^{10}$ executions we need only $7.06$ circuits on average per secure computation, and when running $2^{20}$ executions this is reduced to an average of just $4.08$. In addition, in the online/offline setting, the online phase per secure computation consists of evaluating only $6$ garbled circuits for $2^{10}$ executions and $4$ garbled circuits for $2^{20}$ executions (plus some small additional overhead). In practice, when using fast implementations (like the JustGarble framework of Bellare et al.), the resulting protocol is remarkably fast. We present a number of variants of our protocols with different assumptions and efficiency levels. Our basic protocols rely on the DDH assumption alone, while our most efficient variants are proven secure in the random-oracle model. Interestingly, the variant in the random-oracle model of our protocol for the online/offline setting has online communication that is independent of the size of the circuit in use. None of the previous protocols in the online/offline setting achieves this property, which is very significant since communication is usually a dominant cost in practice.