## 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.

*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:

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories