Cryptology ePrint Archive: Report 2016/184

Efficiently Enforcing Input Validity in Secure Two-party Computation

Jonathan Katz and Alex J. Malozemoff and Xiao Wang

Abstract: 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.

Category / Keywords: cryptographic protocols / secure computation, garbled circuit

Date: received 22 Feb 2016, last revised 28 Feb 2016

Contact author: amaloz at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Added acknowledgments.

Version: 20160228:210935 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]