An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

Yehuda Lindell, Benny Pinkas
EUROCRYPT 2007 [pdf] [bibtex]

Presents a protocol based on cut-and-choose applied to Yao's protocol, achieving security against maliciosu adversaries. This was the first cut-and-choose based protocol with a simulation-based rigorous proof of security. Furthermore, the construction is based on generic assumptions, in the standard model.

The structure of the protocol is a standard cut-and-choose, in which the sender generates ⚠ {$s$} garbled circuits of the target circuit. The main technical ideas are how the problems of input consistency and selective failure are handled:

  • To prevent selective failure attacks, each input bit ⚠ {$b^*$} of the receiver is encoded as ⚠ {$s$} random bits ⚠ {$b_1, \ldots, b_s$} so that ⚠ {$b_1 \oplus \cdots \oplus b_s = b^*$}. The circuit is augmented with a tree of XOR gates to reconstruct ⚠ {$b^*$} from these inputs. In a selective abort attack, the sender provides invalid wire labels to the oblivious transfers, so that the receiver aborts if his OT select bits are certain values. By using this transformation, the receivers select bits to the OTs are ⚠ {$b_i$}, which are nearly independent of his actual input. Hence, his probability of abort can be simulated without knowing his true input ⚠ {$b^*$}.
  • To prove input consistency, the sender generates many (⚠ {$O(s^2)$}) commitments of the input wire labels. For each input wire in the circuit, she commits to a large matrix of wire labels. Columns in the matrix correspond to each of the ⚠ {$s$} circuits; each row contains pairs of the two input wires, with consistent ordering by their truth value throughout the whole row. That way, the sender can open a consistent set of wire labels by opening either the first component in a whole row or the second component in a whole row. The sender can open an entire circuit for checking by opening up both wire labels of one of these pairs. By doing a careful cut-and-choose for both the row- and column-properties of this matrix, the receiver can become convinced that the unopened rows do indeed satisfy the consistency property, without revealing the association between wire labels and their truth values.

The security proof establishes that ⚠ {$s$} circuits provide security approximately ⚠ {$2^{-s/17}$}.

Categories:

CutAndChoose