Welcome to the resource topic for 2017/125
Title:
Non-Interactive Secure 2PC in the Offline/Online and Batch Settings
Authors: Payman Mohassel, 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.
ePrint: https://eprint.iacr.org/2017/125
Talk: https://www.youtube.com/watch?v=k-bVsWv9qvE
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .