Two-Output Secure Computation with Malicious Adversaries

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.

Categories:

CutAndChoose