Paper 2016/184

Efficiently Enforcing Input Validity in Secure Two-party Computation

Jonathan Katz, Alex J. Malozemoff, and Xiao Wang


Secure two-party computation based on cut-and-choose has made great strides in recent years, with a significant reduction in the total number of garbled circuits required. Nevertheless, the overhead of cut-and-choose can still be significant for large circuits (i.e., a factor of $\rho$ in both communication and computation for statistical security $2^{-\rho}$). We show that for a particular class of computation it is possible to do better. Namely, consider the case where a function on the parties' inputs is computed only if each party's input satisfies some publicly checkable predicate (e.g., is signed by a third party, or lies in some desired domain). Using existing cut-and-choose-based protocols, both the predicate checks and the function would need to be garbled $\rho$ times. Here we show a protocol in which only the underlying function is garbled $\rho$ times, and the predicate checks are each garbled only \emph{once}. For certain natural examples (e.g., signature verification followed by evaluation of a million-gate circuit), this can lead to huge savings in communication (up to 80$\times$) and computation (up to 56$\times$). We provide detailed estimates using realistic examples to validate our claims.

Note: Added acknowledgments.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secure computationgarbled circuit
Contact author(s)
amaloz @ cs umd edu
2016-02-28: revised
2016-02-23: received
See all versions
Short URL
Creative Commons Attribution


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