International Association
for Cryptologic Research

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.