In this work we present new malicious-secure 2PC protocols that are round-optimal and also take advantage of batching to reduce cost. Our contributions include: \begin{itemize} \item A 2-message protocol for batch secure computation ($N$ instances of the same function). The number of garbled circuits is reduced by a $O(\log N)$ factor over the single-execution case. However, other aspects of the protocol that depend on the input/output size of the function do not benefit from the same $O(\log N)$-factor savings. \item A 2-message protocol for batch secure computation, in the random oracle model. All aspects of this protocol benefit from the $O(\log N)$-factor improvement, except for small terms that do not depend on the function being evaluated. \item A protocol in the offline/online setting. After an offline preprocessing phase that depends only on the function $f$ and $N$, the parties can securely evaluate $f$, $N$ times (not necessarily all at once). Our protocol's online phase is only 2 messages, and the total online communication is only $\ell + O(\kappa)$ bits, where $\ell$ is the input length of $f$ and $\kappa$ is a computational security parameter. This is only $O(\kappa)$ bits more than the information-theoretic lower bound for malicious 2PC.
Category / Keywords: secure two-party computation, garbled circuits, batched cut-and-choose, non-interactive secure computation (NISC) Original Publication (in the same form): IACR-EUROCRYPT-2017 Date: received 13 Feb 2017 Contact author: payman mohassel at gmail com,rosulekm@eecs oregonstate edu Available format(s): PDF | BibTeX Citation Version: 20170216:220001 (All versions of this report) Short URL: ia.cr/2017/125 Discussion forum: Show discussion | Start new discussion