## Two-Output Secure Computation with Malicious Adversaries

abhi shelat, Chih-Hao Shen
EUROCRYPT 2011 [pdf] [bibtex]

The paper presents a complete, malicious-secure 2PC protocol containing several new techniques and efficiency improvements:

### Input Consistency

This paper presents a new method for input consistency in which the sender chooses wire labels for input wires as Pedersen commitments to the wire's logical value ({$g^b h^r$}, where {$b$} is the logical value, {$r$} is random, and {$g,h$} are distinct generators of a cyclic group). This allows for a highly efficient sigma protocol to prove equality of inputs across circuits.

More generally, any malleable claw-free function can be used in place of Pedersen commitments.

### Output Authenticity

In the new technique for output authenticity, the sender chooses wire labels of output wires to be signatures of {$(b,i,j)$} tuples, where {$b$} is the truth value on the wire, {$i$} is the index of the output wire, and {$j$} is the index of the circuit. It is unsafe for the receiver to reveal these signatures to the sender, for they leak the identity of a majority-output circuit. Hence, the approach proposed here is to prove knowledge of such a signature. The key observation is that a witness-indistinguishable proof is significantly more efficient than a zero-knowledge proof, yet suffices for this purpose.

### Selective Failure

To protect against selective failure attacks, this paper suggests the following approach. For OTs corresponding to circuits that are opened/checked, the sender can reveal the randomness she used in the OT protocol (since her input -- the wire labels -- are revealed anyway for checked circuits). A mild binding property is required by the OT protocol.

### Optimal Cut-and-Choose Split

In the cut-and-choose paradigm, the sender generates many garbled circuits, and then the receiver chooses some fraction of them to open and check for correctness. This work shows that checking 60% rather than 50% leads to optimal parameters.

Note: Optimality is for cut-and-choose applications where the evaulator takes the majority opinion of the unchecked circuits. In other words, the adversary succeeds by inducing a majority of incorrect evaluation circuits. Later work L13 gives techniques where the adversary can only succeed by having all evaluation circuits be incorrect.