* We design an efficient fully-secure 2PC protocol for two-output functions that only requires $O(t|C|)$ symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, where $|C|$ is the circuit size and $t$ is a statistical security parameter. This is essentially the {\em optimal} complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject.
Our protocol utilizes novel techniques for enforcing \emph{garbler's input consistency} and handling \emph{two-output functions} that are more efficient than all prior solutions.
* Motivated by the goal of eliminating the \emph{all-or-nothing} nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the \emph{right deterrence factor}. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability ($1-\epsilon$), and with probability $\epsilon$ (i.e. the event of undetected cheating), privacy is only ``partially compromised" with at most a {\em single bit} of information leaked, in \emph{case of an abort}.
We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose.
A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves \emph{garbled circuits}, and to verify validity of these gadgets using \emph{multi-stage} cut-and-choose openings.
Category / Keywords: Secure Two-Party Computation, Cut-and-choose 2PC Publication Info: An extended abstract will appear at Crypto 2013. This is the full version Date: received 1 Feb 2013, last revised 20 Jun 2013 Contact author: benriva at post tau ac il Available format(s): PDF | BibTeX Citation Version: 20130620:093854 (All versions of this report) Short URL: ia.cr/2013/051 Discussion forum: Show discussion | Start new discussion