Cryptology ePrint Archive: Report 2016/762
Faster Secure Two-Party Computation in the Single-Execution Setting
Xiao Wang and Alex J. Malozemoff and Jonathan Katz
Abstract: We propose a new protocol for two-party computation, secure against malicious adversaries, that is significantly faster than prior work in the single-execution setting (i.e., non-amortized and with no pre-processing). In particular, for computational security parameter $\kappa$ and statistical security parameter $\rho$, our protocol uses only $\rho$ garbled circuits and $O(\kappa)$ public-key operations, whereas previous work with the same number of garbled circuits required either $O(\rho n + \kappa)$ public-key operations (where n is the input/output length) or a second execution of a secure-computation sub-protocol. Our protocol can be based on the decisional Diffie-Hellman assumption in the standard model.
We implement our protocol to evaluate its performance. With $\rho = 40$, our implementation securely computes an AES evaluation in 65 ms over a local-area network using a single thread without any pre-computation, 22x faster than the best prior work in the non-amortized setting. The relative performance of our protocol is even better for functions with larger input/output lengths.
Category / Keywords: cryptographic protocols / secure computation, garbled circuit, cut-and-choose
Original Publication (with minor differences): IACR-EUROCRYPT-2017
Date: received 7 Aug 2016, last revised 13 Feb 2017
Contact author: wangxiao at cs umd edu
Available format(s): PDF | BibTeX Citation
Version: 20170214:010910 (All versions of this report)
Short URL: ia.cr/2016/762
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]