Paper 2016/762

Faster Secure Two-Party Computation in the Single-Execution Setting

Xiao Wang, Alex J. Malozemoff, and Jonathan Katz


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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
secure computationgarbled circuitcut-and-choose
Contact author(s)
wangxiao @ cs umd edu
2017-02-14: last of 4 revisions
2016-08-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiao Wang and Alex J.  Malozemoff and Jonathan Katz},
      title = {Faster Secure Two-Party Computation in the Single-Execution Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2016/762},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.