Paper 2017/125

Non-Interactive Secure 2PC in the Offline/Online and Batch Settings

Payman Mohassel and Mike Rosulek

Abstract

In cut-and-choose protocols for two-party secure computation (2PC) the main overhead is the number of garbled circuits that must be sent. Recent work (Lindell, Riva; Huang et al., Crypto 2014) has shown that in a batched setting, when the parties plan to evaluate the same function $N$ times, the number of garbled circuits per execution can be reduced by a $O(\log N)$ factor compared to the single-execution setting. This improvement is significant in practice: an order of magnitude for $N$ as low as one thousand. % Besides the number of garbled circuits, communication round trips are another significant performance bottleneck. Afshar et al. (Eurocrypt 2014) proposed an efficient cut-and-choose 2PC that is round-optimal (one message from each party), but in the single-execution setting. 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
secure two-party computationgarbled circuitsbatched cut-and-choosenon-interactive secure computation (NISC)
Contact author(s)
payman mohassel @ gmail com
rosulekm @ eecs oregonstate edu
History
2017-02-16: received
Short URL
https://ia.cr/2017/125
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/125,
      author = {Payman Mohassel and Mike Rosulek},
      title = {Non-Interactive Secure 2PC in the Offline/Online and Batch Settings},
      howpublished = {Cryptology ePrint Archive, Paper 2017/125},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/125}},
      url = {https://eprint.iacr.org/2017/125}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.