Welcome to the resource topic for 2016/184
Title:
Efficiently Enforcing Input Validity in Secure Two-party Computation
Authors: Jonathan Katz, Alex J. Malozemoff, 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.
ePrint: https://eprint.iacr.org/2016/184
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .